基于同时取送货的多温共配冷链车辆路径优化

胡 卫，梁承姬，樊陆彬

(上海海事大学物流研究中心， 上海201306)



基于同时取送货的多温共配冷链车辆路径优化

胡 卫，梁承姬，樊陆彬

(上海海事大学物流研究中心， 上海201306)

为降低成本，提高效率，提出了多温共配冷链车辆路径优化问题。在同时取送货的基础上，充分考虑了多温共配运输过程中的特性以及配送节点的时间窗约束，构建了基于VRPDSP的机械式冷冻区隔车多温共配模型。利用遗传算法(GA)，设计了适合于求解问题模型的染色体编码方式以及遗传算子。最后对算例进行求解，结果表明多温层冷链配送模式能够有效解决多温货物配送问题，且对比传统的冷链配送模式，总成本降低了45.72%。

取送结合；多温共配；车辆路径问题；遗传算法；时间窗

0 引 言

车辆路径问题(vehicle routing problem,VRP)最早由Dantzig和Ramser提出，目前已经成为运输配送中的核心问题，其中冷链品的车辆路径规划是在该理论基础上发展起来的。随着冷链物流业的高速发展，冷链品的配送优化也成为国内外学者所关注的焦点，不仅构建出了冷链品配送的数学模型，而且运用启发式优化算法对配送路径进行优化[1-8]。Gendreau等[9]提出六种启发式算法求解带回程取货的旅行商问题。郭伏等[10]对传统的VRPB问题进行改进，不限制车辆的取送货顺序，避免了货物的重新排列，设计了先通过分支定界及遗传算法确定可行路线，再运用整数规划方法求解的算法，对改进后的VRPB问题进行了研究。陈幼林[11]针对回程取货的车辆路径问题，分别研究了有无时间窗的VRPB问题，用遗传算法和蚁群算法求解。李淑琴等[12]建立带软时间窗约束的多车型车辆路径优化模型，设计了模拟退火算法，进行仿真，通过对参数进行敏感性分析，研究不同环保性能车辆的影响。李露蓉等[13]在路径规划模型中考虑到了交通信息的不确定性，并将基于优化蚁群算法的动态路径规划模型与传统动态路径模型进行比较。

上述文献通过不同的角度对冷链配送问题以及VRPB问题进行了研究，成果颇丰。但是针对带同时取送货的多温共配车辆路径问题尚不多见。本文以机械式冷冻区隔车辆的总成本最小化为目标函数，建立冷链车辆路径优化模型，考虑到客户节点对取货和送货需求的不同，结合同时取送货的车辆路径基本模型，用遗传算法进行求解，对车辆进行调度优化。

在传统的冷链配送模式中，按照温度通常将货物分为常温货、冷藏货和冷冻货，则与之对应的配送车辆分别为常温车、冷藏车和冷冻车，不同温度的货物采用相应的配送车辆进行配送。这种配送模式，造成了车辆的专用性，从而大大降低了车辆的使用效率，同时也增加了成本。机械式冷冻区隔车辆无疑满足了消费者多样化、个性化的配送需求，同时增加了车辆的使用效率，进而节省了配送费用。

遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法[14]，最早由Holland[15]提出。遗传算法是通过对初始种群进行选择、交叉和变异的演化过程，最后达到最优或近似最优解。因而，作为一种相对高效的人工智能算法，遗传算法在解决大规模VRP问题上具有自身独特的优势。

1 模型建立

本文研究了以机械式冷冻区隔车总成本作为目标函数，构建基于同时取送货的多温共配冷链车辆路径优化模型。机械式冷冻车厢区隔车将车厢通过用绝缘材料分成常温区、冷藏区和冷冻区三个温区，通过制冷机提供货物所需的温度。相比较传统冷链配送模式而言，机械式冷冻区隔车实现了多温货物的共同配送，从而降低了成本。

1.1 问题描述

本文所研究的冷链车辆配送模型是单一配送中心配送多个客户，配送中心配送常温货、冷藏货和冷冻货三种不同温度的货物，配送这三种货物的车辆是机械式冷冻区隔车辆，这三种产品除了温度不同其他参数都相同。在配送过程中的车辆需要符合如下约束条件,每辆车及各温层区必须符合相应的容量限制，每个客户节点只能受到一次服务，且每个客户节点都有时间窗限制等。根据这些约束条件，计算最小车辆总成本，并得出最优化的车辆行驶路径。

1.2 模型假设

假设每辆车只能从唯一的一个配送中心出发且只有一条配送线路；每辆车在配送过程中的装载量不能大于车的容量；车的数量不限；最大容量已知；配送中心到各客户节点的位置和距离已知；每个客户的取送货量都已知；每个客户节点的时间窗己知；仅对货物的重量有要求而不考虑尺寸大小及整理时间；机械式冷冻区隔车辆中的冷藏区和冷冻区能够满足低温货物对于温度的需求，且所有车辆的容量相同。

1.3 参数定义

表1 不同外界温度对应不同的α1

表2 常用的u值

1.4 数学模型

带同时取送货的多温共配车辆配送成本包括：运输成本，配送过程中的能源成本，开关车门所消耗的能源成本，低温货物的货损成本与固定成本。

车辆在配送过程中的运输成本和车辆行驶距离成正比，通常包含有车辆定时养护费用、随时维修的费用、耗油量等成本。则运输成本为：

(1)

在机械式冷冻区隔车的运输过程中，消耗的能源成本包含了冷藏区和冷冻区。制冷成本主要产生在运输过程中制冷剂的消耗，以及开关门过程中热量的散失。在运输过程中，主要影响能源消耗的因素有不同温层区的内外温差、冷藏区和冷冻区内外表面积、制冷剂的价格和单位时间消耗量、传热系数等，运输所消耗的能源公式为：

(2)

开关车门所消耗的能源公式为：

(3)

在实际配送过程中，低温货物发生货损的条件分为两个部分，一为在运输途中的累计时间造成的货损成本，时间越久货损越多；二为发生装卸活动时，车门的开关使外部空气进入低温层区后温度上升，导致车内冷藏货物因此而造成的货损。货损成本为：

(4)

冷链车辆的固定成本是指每一辆冷藏车辆在执行每一次配送任务时所产生的包含有驾驶员工资、车辆与制冷设备固定损耗等固定支出。假设配送中心总共拥有冷藏配送车K辆，第k辆配送车辆的固定成本为fk，则总固定成本为：

(5)

综上，目标函数为：

(6)

约束条件为：

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

ei≤bi≤li, ∀i∈N,

(17)

式(6)表示目标函数，运输成本，配送过程中的能源成本，冷藏货物的货损成本与固定成本之和；式(7)表示决策变量的整数限制为0或者1；式(8)表示每个客户节点只能被服务一次，且只能被一辆车来服务；式(9)表示每辆车的运输路线是以配送中心为起点出发，最终回到配送中心，且车辆的数量始终相等；式(10)～式(12)表示机械式冷冻区隔车各温层区的容量不能小于每条线路中相应温层货物的送货需求量；式(13)～式(15)表示机械式冷冻区隔车各温层区的容量不能小于每条线路中相应温层货物的取货需求量；式(16)保证配送中配送流量守恒，最优化结果中行驶路线只有一条；式(17)表示时间窗限制。

2 算法的设计

针对本文建立数学模型，对染色体编码与解码、交叉变异算子、适应度函数等要素进行设计。对约束条件的处理分为两个步骤，在染色体的编码及解码环节，主要考虑车辆的容量约束进行染色体的解码；在适应度评价环节，在目标函数的基础上加入惩罚函数，对不满足时间窗约束的解施以较大的惩罚，以此来过滤掉不满足时间窗约束的解并获取优质解。

2.1 编码与解码方式

编码时，生成1～20的自然数随机排列，作为配送车辆遍历节点的顺序。解码时，需要根据单车的容量约束来进行。车辆从配送中心出发，若第1至第i-1个节点的各温层货物需求量之和，都在单车的容量限度内，而第1至第i个节点各温层货物需求量之和超过了单车的容量限度，则该车辆的遍历中止点为第i-1个节点，配送完毕后返回配送中心。下一车次的遍历从第i个节点开始，依次类推，直到遍历完所有的节点。解码的过程一方面给出了满足容量约束的可行路径;另一方面确定了对应的车辆数量。

图1 染色体编码及解码方式示意图

2.2 交叉算子

交叉算子在遗传算法中起着核心的作用，为选择操作不断提供新的个体。它使得算法能够搜索新的基因空间，从而使得新的群体中的个体具有多样性。如图2所示，首先，在父代1中随机选择3个基因位上的基因值，将其复制到子代相同基因位上；然后去掉父代2中与父代1所选基因值相同的基因；最后将父代2中剩余基因位上的基因按顺序依次填入子代1中，如果遇到某一基因位上已经存在基因值，则跳过该基因位继续填入下一个位置。

图2 交叉算子示意图

2.3 变异算子

变异算子是按照一定的变异概率用新的基因值替代旧的基因值，改变了染色体的基因链，通过这种对染色体的局部进行修改的方式，从而保证种群多样性。变异算子的作用是帮助辅助进化，防止出现早熟现象。如图3所示，在父代中随机选择两个基因位上的基因，然后互换这两个基因位上的基因，得到子代。

图3 变异算子示意图

2.4 适应度函数

遗传算法中，衡量一个个体质量优劣的标准是适应度，它的设计要结合求解问题的本身要求来定。一般是以所求问题的目标函数来确定，解的适应度函数值是遗传操作过程中进行选择操作的主要依据。本文在目标函数的基础上加上惩罚函数，作为适应度函数，并假定染色体适应度值越小，被选择到下一代的概率越大。适应度函数表达式如式(18)。

(18)

其中，M为惩罚系数，本文取M=10 000，对于不满足时间窗约束[ei,bi]的染色体来说，它的适应度函数会很大，因此在选择操作中，将被舍弃。

3 算例实验

算例数据如表3所示，编号0代表配送中心。编号1～20代表20个配送节点。整车的最大载货量为60件，其中常温货货区、冷藏货货区、冷冻货货区的最大容量都为20。单位车辆启动成本为fk=150元/次；制冷剂的价格a1=2元/kg；单位运输成本C=2.5元/km；单位货物价值c=150元/件；单位时间内制冷剂的消耗量α1=0.14；传热系数u=0.2；机械式冷冻车的低温层区车厢内外面积平均值1.6 m2，且车门面积sv=1 m2；单位货物在配送过程中的单位时间损耗比例β1=0.001 5，单位货物在装卸过程中的单位时间损耗比例β2=0.025；外界常温温度为20 ℃，冷藏温层区车厢内温度为-18 ℃，冷冻温层区车厢内温度为-10 ℃。

基于以上算例，利用遗传算法进行求解。其中，种群规模设置为100，最大迭代次数为200，交叉概率取0.8，变异概率取0.1。经过多次运行该算法，得到的最优解都为3 522.57元，算法的收敛情况如图4所示。

图4 算法收敛图

节点编号坐标常温货物冷藏货物冷冻货物X轴Y轴送货量/件取货量/件送货量/件取货量/件送货量/件取货量/件装卸时间/s时间窗/seili03535020014149103110612182351721304010495935545305011101021124552051202010192951530301041912113062530313120101391497205050401212103115810433121209374695560502011979881030603010509324111206541221010768612503530401081251331330254120401169801415102140301056661530520315213223516102041412012778917530205031119911018204052122113152819156011105086270204565322022115667

运算得出成本最低的配送方案如表4，该方案需要4辆车。

表4 模型的配送路径

最优配送方案的路线如图5所示。

最优配送方案的甘特图如图6所示，矩形方框上面的编号代表配送节点的编号，0代表配送中心。从图6中可以得出每个节点的车辆到达时间、停留时间和离开时间，以及每辆车完成配送任务返回配送中心的时间。该方案能够使配送车辆在客户节点的时间窗约束内进行配送，且每辆车的配送完成时间符合配送中心的时间窗约束。

图5 最优车辆路径安排方案示意图

图6 最优配送方案甘特图

传统的冷链配送模式下，配送三种温层货物类型则需要三种车型来实现。基于文中算例，对20个客户节点的货物需求进行配送，在满足时间窗约束及车辆容量约束的前提下，需要常温车2辆，冷藏车2辆，冷冻车2辆，总成本为6 489.88元。而多温层冷链共配模式下使用的机械式冷冻区隔车，一种车型能同时配送三种温层货物，完成上述20个客户节点的配送任务，需要的车辆数目为4，总成本为3 522.57元，相较传统冷链配送模式，总成本降低了45.72%。具体的成本对比，如表5所示：

表5 多温层冷链共配模式与传统冷链配送模式的对比

同时，为了验证该遗传算法的有效性，在Matlab环境下加载YALMIP优化工具箱，调用Cplex对算例模型重新求解，求得最终的成本目标函数值为3 475.75，运算时间为212.11 s。如表6所示，本文遗传算法(GA)获得的近似最优解与Cplex求得的较为精确的解相比，相差不大，而且求解速度上有明显的优势，这说明了上文中遗传算法的设计是有效的。

表6 两种算法的比较

4 结 论

将冷链车厢分隔成常温区、冷藏区和冷冻区的多温层冷链配送模式大大提高了多温货物冷链配送能力。本文以同时取送货的车辆路径问题为基础，充分考虑了冷链货物运输过程中的特性，构造了包含运输成本、配送过程中的制冷成本、货损成本，以及车辆固定成本的目标函数。并且根据客户节点对货物温度、和送取货需求量的不同，配备含有不同温区的机械式冷冻区隔车辆，利用遗传算法对算例进行求解，得到了最优的配送方案，该方案的车辆数量为4，最终的配送成本为3 522.57元，对比传统冷链配送模式，无论是车辆数量上还是配送成本上都有很大的优势。这也表明了多温层冷链配送模式能够有效解决同时取送货的多温货物配送问题，而且是一种低成本的冷链配送模式。最后，利用Cplex对算例重新编写代码并求解，进一步验证了本文算法的有效性。

[1] HU X,WANG Z,HUANG M, et al.A computer-enabled solution procedure for food wholesalers’ distribution in cities with a circular transportation infrastructure[J]. Computers & Operations Research,2009,36(7):2001-2209.

[2] CHENG C, WANG K.Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm[J]. Export Systems with Applications,2009,36(5):7758-7763.

[3] AMORIM P,BELO-FILHO M A F,TOLEDO F M B, et al.Lot sizing versus batching in the production and distribution planning of perishable goods[J]. International Journal of Production Economics,2013,146(1):208-218.

[4] SHUKLA M,JHARKHARIA S.Artificial Immune systembased algorithm for vehicle routing problem with time window constraint for the delivery of agri-fresh produce[J]. Journal of Decision Systems,2013,22(3),224-247.

[5] 王海丽,王勇,曾永长.带时间窗的易腐食品冷藏车配送问题[J]. 工业工程,2008,11(3)：127-130.

[6] 缪小红,周新年,林森,等.第三方冷链物流配送路线优化研究[J]. 运筹与管理,2011,20(4):32-38.

[7] 王淑云,赵敏.蓄冷式冷链物流多温共配的动力机制[J]. 公路交通科技,2012,29(2):144-148.

[8] 石兆,符桌.时变网络条件下带时间窗的视频冷链配送定位—运输路径优化问题[J]. 计算机应用研究,2013,30(1):183-188.

[9] GENDREAU M, HERTZ A, LAPORTE G.Traveling salesman problem with backhauls[J]. Computers and Operations Research,1996,23(2):501-508.

[10]郭伏,龙颖.带时间窗回程取货的车辆路径问题的算法[J]. 东北大学学报(自然科学版),2006,27(5):575-578.

[11]陈幼林.考虑回程的车辆配送模型研究[D]. 上海:同济大学,2006.

[12]李淑琴,杨斌,赵磊,等.需求带时间窗的环保多车型组合配送路径优化[J]. 广西大学学报(自然科学版),2012,32(2):388-394.

[13]李露蓉，王蕾,高应波,等.基于优化蚁群算法的动态路径规划问题研究[J]. 广西大学学报(自然科学版),2013,38(2):359-366.

[14](日)玄光男,程润伟,汪定伟,等译.遗传算法与工程设计[M]. 北京:科学出版社, 2000.

[15]HOLLAND J H.Adaptations in Natural and Artificial Systems[M]. University of Michigan Press, Ann Arbor, 1976.

(责任编辑 梁碧芬)

Optimization of multi-temperature joint-delivery based on simultaneous pickup and delivery

HU Wei, LIANG Cheng-ji, FAN Lu-bin

(Logistics Research Center, Shanghai Maritime University, Shanghai 201306,China)

To reduce costs and improve efficiency, the multi-temperature joint-delivery vehicle routing problem is studied. On the basis of simultaneous pickup and delivery, taking full account of the characteristics of multi-temperature joint-delivery and the time window constraint of delivery node, a multi-temperature joint-delivery model based on VRPDSP for mechanical separated freezer compartments vehicle is established. Then a genetic algorithm whose chromosome coding and genetic operators are designed to suit for solving the above model. Finally, the solution results of a given example shows that the multi-temperature layer cold chain distribution pattern can effectively solve the problem, and the total cost is reduced 45.72% compared to the traditional cold chain distribution model.

simultaneous pickup and delivery; multi-temperature joint-delivery; vehicle routing problem; genetic algorithm; time window

2016-04-01；

2016-05-29

国家自然科学基金资助项目(71471110；71301101；61540045)；上海市重点学科资助项目(J50604)；陕西省社会科学基金资助项目(2015D060)

梁承姬(1970—)，女(朝鲜族)，吉林龙井市人，上海海事大学教授；E-mail：liangcj@shmtu.edu.com。

胡卫，梁承姬，樊陆彬.基于同时取送货的多温共配冷链车辆路径优化[J].广西大学学报(自然科学版)，2016，41(5)：1576-1584.

10.13624/j.cnki.issn.1001-7445.2016.1576

U491

A

1001-7445(2016)05-1576-09