基于遗传算法的农产品物流车辆路径问题决策研究

钱 华 （上海潇翔国际物流有限公司，上海 200090）

基于遗传算法的农产品物流车辆路径问题决策研究

钱 华 （上海潇翔国际物流有限公司，上海 200090）

我国农产品物流成本较高的主要原因之一是缺乏科学的管理技术，尤其是基于定量分析的决策技术。对物流车辆路径问题的优化可以有效降低农产品的物流成本。针对农产品的时效性，对带有时间窗的农产品物流车辆路径问题，引入客户满意度函数，建立实例决策模型，运用遗传算法工具箱进行优化求解。通过对优化前后的数据进行比较，验证决策模型的可行性和合理性。

农产品物流；时间窗；车辆路径问题；遗传算法

1 VRP问题一般描述

车辆路径问题 （Vehicle Routing Problem,VRP）是运筹学与物流管理决策的一个重要问题。目前，一般意义上的物流，指物流中心按照不同客户多频度、小批量的订货要求进行组织物流、其中主要内容是根据确定的货物量进行车辆的分配和物流路线的生成，即广受研究的车辆路径问题，如图1-1所示。

由于从事农产品物流物流的汽车货运工作尤其是从事城市果蔬物流的汽车货运工作条件复杂，不仅货运点多、货物种类繁多、道路网复杂、服务地区网点分布不均匀，最重要的是果蔬农产品物流有一个严格的时间限制。因此，如何应用计算机快速求解路线优化方案是国内外专家学者普遍探索的重要课题。

VRP问题需满足以下条件：

（1）每条物流路径上各客户的需求量之和不超过货车的最大载重量。

（2）每条物流路径的长度不超过货车一次物流的最大行程。

（3）每个满足每个客户要求 （如时间要求），且只能由一辆货车送货。

（4）每辆货车均从物流中心出发，完成任务后又全部返回物流中心。

2 VRP问题的一般数学模型

设物流中心为1个，货车编号为k，客户编号为1,2,…l，考虑车辆载重量约束、数量数目约束、时间约束等，可定义如下的基本数学模型：

定义变量：

目标函数及约束条件：

3 VRP问题的分类及求解方法

VRP问题根据有无时间要求分为有时间窗VRP问题（TWVRP）和无时间窗 VRP问题。对有时间窗VRP的求解算法如图3-1所示。

本文主要研究现代启发式算法中的遗传算法，其适合客户达到一定数目时，并加入了时间因素和客户满意度等多目标问题决策。

4 时间窗问题

农产品如水果和蔬菜的保鲜时间各不相同，若每家门店对送货时间有要求，则物流企业必须在规定的时间段内将农产品送货上门，这就是带有时间窗的VRP问题。

时间窗问题可以用不等式eTi≤ti≤lTi表示，eTi表示物流任务最早时间，lTi为物流任务最晚时间，ti为某物流任务需要的物流时间。时间窗限制可分为可调剂时间窗和不可调剂时间窗。可调剂时间窗表示如果货车没有按时送货，则必须支付罚款；不可调剂时间窗表示每个物流任务必须在规定的一个时间段内送到门店，无论早晚都完全被接受。很明显，不可调剂的时间窗所产生了惩罚成本要大于可调剂的时间窗，且只有后者才有可行解。

由此产生客户满意度函数 （CS Val），果蔬农产品要在其有限的保鲜期限内及时销售，就必须做到及时物流，尽量缩短上架前流通时间。物流企业要实现农产品利润最大化，就必须考虑农产品的时间成本。这些成本包括由于延迟交货而产生的罚款和最佳销售时段的机会成本损失。我们可以用下图4-1表示实际客户满意随物流时间的长短而变化。

工业品物流往往以降低总物流送成本或缩短物流时间为目标，而没有考虑将客户满意度和VRP问题的模型相互结合，使它成为可以1个约束变量。农产品物流更注重客户的满意度，客户满意度可以通过如下时间函数表示：

如上例，当货车XY（第1类4吨车第1辆）在完成门店J的物流任务后驶向门店A时，如到达A的时间太早，那么货车XY必须在A门店处等待，如图4-2所示。

货车XY在A门店的等待时间表示为：

式中：tij表示物流车辆从顾客i到顾客j的行使时间；uti为物流车辆在顾客i处的卸货时间；wi（ti）表示当顾客i的开始时间为ti时，物流车辆在顾客i处的等待时间。

5 EXCEL遗传算法工具箱

利用EXCEL加载Evolutionary Solver，其基本原理是根据遗传学、进化论和适者生存原理建立的。EXCEL标准Solver是从单独一个解 （初始点）开始，朝着优化解的方向移动。对所有点来说，标准solver只追踪一个唯一的解 （目前为止找到的最好的解）。相反，evolutionary solver从随机产生大量候选解开始，这些候选解被称为 “群体”。在求解过程中，evolutionary solver追踪候选解的整体群体。

在生成了群体之后，evolutionary solver接着对群体创造了新的一代。存在的候选解群体结对创造先下一代的子孙。借鉴遗传学的原理，这些子孙后代结合了每对父母的一些因子。例如，一个后代可能兼有父母一方的一些可变单元格和另一方的一些值，而其他可变单元格可能只是在父母双方之间均分。

在任何一代的解的群体中，有些解是好的 （或合适的），有些是不好的 （或不合适的）。我们通过计算群体中得候选解的目标函数来确定解的适应度。对那些不满足一个或多个约束条件的解的惩罚就是将它们排除在外。接着，借鉴进化论和适者生存的原理，群体中 “合适”的成员被允许频繁地繁殖 （创造许多后代），而 “不适合”的成员不允许繁殖。如此下去，群体最终将变得越来越合适。

遗传算法的另一个关键特征是突变。如同生物学中的基因突变一样，evolutionary solver有时对群体中的成员进行随机的改变。例如，一个可变单元格的数值可能会被一个新的随机值取代。这种突变可以创造与其余群体无关的后代。这是非常重要的，因为它可以帮助算法在局部最优值附近受到困扰时摆脱困扰。

Evolutionary solver不断创造新一代的解，直到连续几代都没有改进。然后算法就结束了，并报告目前为止找到的最佳解。

6 案例验证

6.1 案例背景

上海世纪联华生鲜物流中心为全市13家主要门店物流农产品。物流中心和13家门店实际地理位置如图6-1所示。物流中心要在一天内用一辆满载的货车将果蔬物流到各家门店，然后车辆返回物流中心，车辆出发点和返回点都是物流中心。我们将要物流的门店按字母顺序列出，每家门店都标上一个数字 （1～13之间的一个整数）和一个中文简称，如表6-1中的B6：C18单元格和E3：Q4单元格所示。数据单元格是各点之间的物流距离 （D5：Q18），给出了每一家门店之间的物流距离。需要制定的决策是车辆返回到物流中心前均物流过每家门店。因此，相应的可变单元格route（D22：P22）显示出物流各阶段物流的不同门店 （通过其数字标号引用）。换句话说，在物流中心之后第一家门店的数字标号将在单元格D22中显示出来，第二家门店将在单元格E22中显示出来，一次类推。表6-1所示的电子表格模型显示了按字母顺序物流各个门店的路径。这条物流路线的总长度为190公里。

6.2 案例求解

第23行显示了根据第22行中各门店的数字编码给出的中文简称，使用了EXCEL的INDEX函数。第24行利用INDEX函数查询出了物流路线中每个门店与前一个门店之间的距离。目标单元格Total Miles Traveled（Q26）将路线中总物流距离加总一起。

图6-1 上海世纪联华生鲜物流网络地理图

表6-1 世纪华联物流电子表格模型

由于各家门店只需要物流一次，这一模型中的一个约束条件是所有的可变单元格都必须是1～13中的一个整数，不能重复。这一约束条件很难利用标准的solver来实现。幸运的是，premium solver包含了一个新的约束类型，成为alldifferent，它能满足我们的要求。当n个可变单元格选择1～n的整数时，将这些可变单元格限制为alldifferent将迫使它们的取值为1～n之间整数且不重复。为了利用premium solver实现alldifferent这一约束条件，在solver中选择add按钮，弹出add constraint对话框。在对话框的左边选择可变单元格route（物流路线），在对话框中间的下拉菜单中选择dif，如图6-2所示。

由此得到的模型不是线性的，因为index函数用来计算距离和alldifferent约束。但是，evolutionary solver可以用来找到一个好的路径。利用evolutionary solver求解后，得到的解显示在表6-2中的D22：P22单元格和D23：P23单元格中。这条路径比表6-1所示的路径改善了很多，总物流距离为91公里，比原先190公里节约了99公里。物流优化路线为物流中心→门店8→门店4→门店6→门店5→门店13→门店3→门店9→门店2→门店11→门店7→门店12→门店1→门店10。其中在运用遗传算法求解时个参数的设置如图6-3所示。

图6-2 显示alldifferent约束的add constraint对话框

表6-2 世纪联华物流路线优化决策电子表格模型

Max time（最长运行时间）：100秒；

Interations （迭代次数）： 1000；

Precision （精度）： 1e-006；

图6-3 遗传算法参数设置

Convergence （收敛值）： 0.0001；

Population Size（种群数）：100;

Mutation Rate （突变率）： 0.075；

在 “变量的要求范围”选项选中。这就将所有的可变单元格限制在上限和下限之间。这将大大缩小evolutionary solver需要搜索的范围，并增加找到最优解的机会。

在 “evolutionary solver”选项对话框中点击 “限制” （limit）选项卡。这个对话框对何时终止搜索提供了额外的控制。在“最大子问题”、 “最大可行安全操作限制”中输入较大的数值，可以使搜索持续很长时间。 “偏差”为0.05， “最大无改善时间”为30，意味着evolutionary solver将继续搜素直到在最后30秒内解的改善不超过5%。减少 “偏差”，或增加 “最大无改善时间”通常会使搜索时间变得更长。

7 总 结

本文主要研究了现代遗传算法在解决带时间窗的农产品物流车辆路径问题决策中的应用，并结合了EXCEL遗传算法工具箱，实现决策过程自动化。在求解复杂的非线性规划问题时，evolutionary solver显示了两个重要的优点：第一，目标函数的复杂性不会影响evolutionary solver。只要函数可以根据给定的候选解进行计算 （为了确定适合的水平），那么函数是否有折点或者不连续或者许多局部最优值都没有关系。第二，通过计算不一定与当前最优解在同一领域内的所有候选解群体，evolutionary solver不会受困于一个局部最优值。另外，即使整个群体最终向只是局部最优的解前进，突变仍然可以避免搜索被困在一点上。事实上，由于随机突变的存在，如果一直运行下去，那么Evolutionaty Solver就可以保证找到任何一个最优化问题的最优解。但是，这当然是不切实际的。

另一方面，我们必须指出，Evolutionaty Solver不是万能的。首先，为了找到最优解，计算花费的时间要长。选择了某些限制性选项后，搜寻更优解的过程可能会持续几个小时甚至几天。其次，Evolutionaty Solver对于有许多约束条件的模型的效果不是很好。例如，对于线性规划问题的许多模型，标准Solver能够即刻进行求解，但evolutionary solver运行通常会产生一个不同的最终解。最后，找到的最佳解不是最优的 （虽然它可能非常接近最优值）。Evolutionary solver作为最优化工具的意义与标准solver是一个聪明的搜索引擎，尝试不同的随机解。它很可能在一个非常接近最优值的解处结束，对于非线性规划问题的大部分类型它几乎不可能获得精确的最优解。因此，在evolutionary solver之后再运行标准solver（GRG非线性）是有帮助的，从evolutionary solver找到的最优解开始，通过在该解的领域内进行搜索，能改善这个解。

[1]李大卫，王莉，王梦光.遗传算法在有时间窗车辆路径问题上的应用[J].系统工程理论与实践，1999(8)：32-33.

[2]汪祖柱，程家兴，方宏兵,等.车辆路径问题的混合优化算法[J].运筹与管理，2004(6)：42-43.

[3]刘诚，陈治亚，封全喜.带软时间窗物流配送车辆路径问题的并行遗传算法[J].系统工程，2005(10)：13-14.

Research for the VRP in Agricultural Products Based on Genetic Algorithm

QIAN Hua(Shanghai Xiaoxiang International Logistics Company,Shanghai 200090,China)

One of the main reasons that cause the high cost of China agricultural products logistics is lacking of scientific technology of management,especially the decision making tech based on data analysis.One of the approaches can reduce the cost of agricultural products logistics is the optimizing vehicle route problem.The time windows VRP in agricultural products can be solved by bringing the function of customers satisfaction to the decision making model based on the company case and getting the result with the toolkits of genetic algorithm.To certifying the feasibility and reasonability of the DM model with the comparison the results.

agricultural products logistics;time windows;VRP;genetic algorithm

F506

A

1002-3100(2012)09-0106-05

2012-07-31

钱 华（1976-），男，上海人，上海潇翔国际物流有限公司，工程师，硕士，研究方向：国际物流和供应链。