基于2-Opt免疫遗传算法的冷链配送路径优化问题研究

王　咪，杨孔雨

（北京信息科技大学　信息管理学院，北京　100192）



基于2-Opt免疫遗传算法的冷链配送路径优化问题研究

王咪，杨孔雨

（北京信息科技大学信息管理学院，北京100192）

分析了生鲜产品冷链配送的现状，并指出了研究生鲜产品冷链配送路径优化问题的重要意义。考虑配送过程中道路颠簸对于生鲜产品配送成本的影响，同时结合车辆固定成本、运输成本、能源成本、惩罚成本、货损成本等建立冷链物流车辆配送路径优化模型，并将2-Opt算法与免疫遗传算法相结合对该模型进行求解，最后通过实例分析，证明该模型有效实用，为相关行业的发展和企业运营提供参考。

冷链；2-Opt；免疫遗传算法；配送路径优化

1　引言

随着生鲜电商如雨后春笋般崛起，生鲜电商的“O2B+O2O”时代已经到来，冷链物流成本越来越受到食品企业、快递企业和电商企业的关注［1］。生鲜产品集易腐性、季节性、地域性、储存保鲜条件要求高等特点于一身，造成其配送成本极其高昂，大约占到产品整体成本的70%［2］。这已经成为了冷链物流的短板之一，严重制约着生鲜电商的发展。影响冷链配送成本的因素主要有配送路线设计、配送时间、客户对时间的要求等，正是这些不确定的因素，形成了成本迥异的配送方案，可见，车辆配送路径的选择对冷链成本的影响是重大的，对它的研究具有应用的广泛性和经济上的重大价值，受到国内外学者的广泛关注。李宏研究城市冷链物流配送车辆运行时间和一天之中温度变化的依时特性，对传统冷链配送路径模型进行改进，并运用时间导向最近邻点法进行演算、求解并进行主要参数的敏感度分析［3］。何琴飞考虑道路畅通状况，基于道路阻抗函数的相关理论，建立冷链配送路径优化的数学模型，分析比较得出道路畅通状况对于冷链配送有重大影响的结论［4］；李亚男、刘联辉等基于城市发展理念，以碳排放为约束条件，构建冷链物流配送网络优化模型，并根据配送运输网络模型求解的复杂性，使用遗传算法得出优化模型的最优解［5］。

2　模型分析与建立

2.1问题描述

由于冷链物流车辆配送路径中涉及到的因素比较多，配送中心需对配送车辆、路径选择、配送时间等作出合理安排，才能达到既使配送成本最小，又能使客户满意度最大化的目的。本文所描述的配送中心有K辆冷藏车，每辆冷藏车的固定成本Ck、耗油量、使用年限、载重、极限行驶里程Dis等相同。配送的货物为单一类型，配送中心的缺货率为零，时刻能够满足客户的需求。假设该配送中心有n个客户，且每一位客户的需求量、地理位置、到货时间窗要求等基本信息已知，配送中心安排冷藏车和装卸人员为客户配送，每辆冷藏车对应一条配送路径，每辆车可服务多个客户，每个客户只能由一辆车服务，装卸人员的装卸货速率一致。冷藏车从配送中心出发，最后返回配送中心。

2.2模型建立

2.2.1目标函数

（1）固定成本。通常要完成一次配送任务需要预计使用多少辆冷藏车，这样做一是可以尽可能的节约成本，二是减少问题的约束，使组织路线更容易，更有弹性。一般来说，可以使用以下公式来确定车辆数：

Qi是客户i本次配送的需求量；α是对装（卸）车复杂度及约束的多少的估计参数（0＜α＜1），一般来讲，装（卸）车越复杂，约束越多，α应越小，表示一辆车所能容纳的货物量越少；Cap是冷藏车额定载重量。

那么，配送过程中使用K辆冷藏车的配送成本为：

Ck表示第k辆程中使用K辆冷藏车的固定成本。

（2）运输成本。冷藏车在配送过程中的运输成本是与行驶里程成正比的。但是生鲜产品在配送过程中的腐损程度与受到的颠簸有很大的关系，从而影响到配送中心的配送成本。配送过程中生鲜产品受到的颠簸少，产品损坏程度就小，配送中心的配送成本也会相应减少。我国道路收费的标准是按照路面好坏程度来收费的。高速公路路面平整、颠簸少、速度快，因此收费最高，其次是国道、省道等［6］。因此，要保证生鲜产品的新鲜度和客户的满意度，配送中心在选择配送路径时需要充分考虑道路质量的问题，确定这批生鲜产品在哪种道路上配送才能保证供应商与消费者的双赢。本文提出一个带道路等级评估系数的模型，表1所示是不同路面质量的道路等级分类以及它的道路等级评估系数μij。

表1　道路分类与评价系数表

配送过程中的运输成本可表示为：

s表示单位距离运输成本；disij表示客户i和客户j之间的距离；Xij表示配送车辆是否经过（i，j）路段，若经过，则Xij=1；否则，Xij=0。

（3）能源成本。冷藏车通过制冷装置维持车内的温度，以保证生鲜食品保持适宜的温度，减少腐损。生鲜成品配送过程中的能源成本主要来源于以下两个方面［7］：

①由于冷藏车内外温度之差而通过车厢隔热壁传入车厢内的热负荷为：

那么，在冷藏车在配送过程中通过隔热壁消耗的制冷成本为：

②冷藏车在服务顾客时，由于车厢门开启，也会造成一定的热负荷，产生制冷成本：

那么，冷藏车在服务客户时消耗的制冷成本为：

V表示冷藏车的体积；τ表示车厢传热系数（W m2·°C）；S表示车厢外表面积；φ表示车厢门开启程度系数；ΔT表示车厢内外温度之差；tij表示配送冷藏车从客户i行驶到客户j的用时；ρ表示氮液热量转化系数；Pref表示制冷剂成本。

（4）违反时间窗的惩罚成本。若配送车辆在与客户预定的时间窗ei之前，晚于客户可接受的时间窗Ei到达，则配送公司可以立即交货，但是需要承担约定的惩罚费用；若配送车辆在与客户约定的时间窗之内到达，则没有惩罚费用；若配送车辆在与客户预定的时间窗li之后，早于客户可接受的时间窗Li到达，则配送公司也要承担一定的惩罚费用，若配送车辆没有在客户可接受的时间窗之内到达，此时客户会拒绝接受货物［9］。

综上所述，冷藏车k在服务客户i时的惩罚成本为：

则冷藏车在配送一批货物时总的惩罚成本为：

（5）货损成本。考虑到生鲜产品在冷链运输过程中的温度一般为定值，故假设其变质速率为一常数R，并定义生鲜产品在配送过程中其品质随时间变化呈指数形式。函数如下：

∂是生鲜产品的质量对时间的敏感度，若产品对时间的敏感度强，该值相对小些，反之则大些；sk为冷藏车K从配送中心出发的时间。

整个配送过程中的货损成本为：

2.2.2约束条件

目标函数

上述约束条件中，式（1）表示配送过程中冷藏车的载重量不得超过它的额定载重量；式（2）表示闭环配送；式（3）和式（4）表示一个客户只能由一辆冷藏车配送，且只能被配送一次；式（5）表示冷藏车到达客户的时间不得超过客户可接受的时间窗范围。

3　基于2-opt的免疫遗传算法

目前学者们在解决冷链物流车辆配送路径优化问题时多采用模拟退火算法、禁忌搜索算法、遗传算法、改进遗传算法等。这些算法各有优势，也存在其弊端。模拟退火算法具有一定的容错机制，但是无法确保优化结果最优；禁忌搜索算法能够通过调整禁忌规模来提高搜索速度，但是容易陷入局部最优；遗传算法是一种全局收敛方法，但是不可避免的会产生退化现象。

本文采用免疫遗传算法解决冷链物流车辆配送优化问题，该算法使遗传算法具有免疫功能，有效抑制退化现象，提高全局搜索速度。同时使用2-opt算法作为变异算子，提高免疫遗传算法的局部搜索能力。2-opt邻域搜索算法是求解TSP问题的常用启发式算法，对于优化Hamilton回路有很大的优势，在冷链物流车辆路径优化问题中，单辆车配送的客户数量并不多，因此不适合使用3-opt、or-opt这样复杂的算法。并且使用2-opt算法能弥补免疫遗传算法易陷入局部最优的缺点。

免疫遗传算法的流程如下：

（1）抗体编码。将待求解的实际问题转化为免疫系统能够处理的抗原形式，抗体则对应问题的解。现在使用最多的编码方式有自然数编码、二进制编码和字符编码。本文采用自然数编码中的配送中心和客户共同编码。

并定义免疫系统由N个抗体组成，即群体规模为N，M表示抗体的基因数。

（2）产生初始抗体。

（3）计算抗体与抗体间的亲和力。在进化过程中免疫系统是一个不确定系统，其多样性由Shannon的平均信息熵来表示。定义pij是第i个等位基因在j基因座上出现的频率。

则处于j位置的基因信息熵为：

整个群体的基因信息熵为：

那么根据熵的定义，得到抗体v和w的亲和力：

（4）排除相似抗体。如果ayv，w＞ω，则淘汰一条抗体。

ω为浓度阈值；v为相同等位基因段的数量。

（5）计算抗原与抗体的亲和度。计算抗原与抗体的亲和度axv，排除亲合力小于上一代亲和度最小值的抗体：

（6）选择优良抗体加入记忆库。在传统适应度选择比例的基础上增加基于浓度的调节概率因子。抗体v的浓度计算公式为：

个体的选择概率pc由适应度概率pf和浓度抑制概率pd两部分组成：

（7）交叉、变异、随机产生新抗体。交叉操作采用顺序交叉。在双亲1中随机选择一个匹配区域，产生原始后代，将双亲2中与匹配区域不同的部分按照原来的顺序插入到原始后代，组成子代1。按照同样的方法组成子代2。

变异操作采用2-opt算法。2-opt算法在改进车辆路径优化问题中的单条路线上有独特的优势。其基本思想是取路线上的两条线段（i，i+1）和（j，j+1），断开这两条线段，将点i与j+1相连，j与i+1相连，同时将线路反转，形成新的线路。如果变化后的线路里程比原路径短，则此线路为优化解。否则保留原路线。

（8）如果迭代次数超过预先的设定，则输出最优解。否则返回第3步。

4　算例分析

本文以J公司鲜奶配送的相关资料为基础进行合理假设，该公司冷藏车从配送中心出发，向同城的10个需求点配送鲜奶。冷藏车额定载重量是3t，配送一次的固定成本为200元，配送过程中车厢内的温度是0℃，车厢外的温度是20℃，单位里程的运输成本是4元，道路颠簸系数为1.12。冷藏车在预定时间窗之前到达的惩罚系数为0.1%，在预定时间窗之后到达的惩罚系数为0.2%。各需求点的需求量及时间窗限制见表2，各节点距离情况见表3。

表2　各需求点的需求量及时间窗

表3　配送中心与各需求点间的距离（km）

利用本文提出的基于2opt的免疫遗传算法求得最终结果：使用3辆冷藏车配送此次货物。第1辆冷藏车的配送路线是2-3-5-10，第2辆冷藏车的配送路线是1-8-4，第3辆冷藏车的配送路线是6-7-9。

5　结束语

本文分析了冷链物流配送的现状，重点分析冷链配送过程中的固定成本、运输成本、能源成本、时间窗惩罚成本和货损成本，建立冷链物流车辆配送路径优化问题的数学模型，并提出将2-opt算法与免疫遗传算法相结合来求解该模型。但是在实际配送过程中，可能会遇到因天气状况、交通事故等因素造成的时间的不确定性，这是本文没有考虑到的，还需要继续研究。

［1］韩春阳，伍景琼，贺瑞.国内外冷链物流发展历程综述［J］.中国物流与采购，2015，（15）：54-55.

［2］李宏.城市冷链物流配送车辆路径问题的研究［D］.长沙：长沙理工大学，2006.

［3］何琴飞.考虑道路畅通状况的冷链物流配送优化问题［D］.大连：大连海事大学，2015.

［4］李亚男，刘联辉，李小曼，等.低碳约束下城市冷链物流配送系统优化研究［J］.中国市场，2016，（10）：36-39.

［5］Peiqing Li，Jie He，Dunyong Zheng，etc.Vehicle Routing Problem with Soft Time Windows Based on Improved Genetic Alogrithm for Fruits and Vegetables Distribution［J］.Discrete Dynamics in Nature and Society，2015，（48）：30-38.

［6］章镛初.冷藏汽车热负荷计算［J］.专用汽车，1988，（2）：12-15.

［7］张金凤.带模糊时间窗的冷链物流车辆路径优化［D］.武汉：武汉理工大学，2013.

［8］苑立杰.免疫遗传算法在车辆路径问题中的应用研究［D］.大连：大连海事大学，2013.

Study on Cold Chain Distribution Route Optimization Based on 2-Opt Immunity Genetic Algorithm

Wang Mi，Yang Kongyu
（School of Information Management， Beijing Information Science Technology University， Beijing 100192， China）

In this paper， we analyzed the current status of the fresh product cold chain distribution industry， pointed out the significanceof route optimization therein， then considering the impact of bumping on the distribution cost of the fresh products and in connection with thefixed vehicle cost， transportation cost， energy cost， penalty cost， and cargo loss cost， etc.， established the cold chain logistics vehicledistribution route optimization model， combined the 2-Opt algorithm and the immunity genetic algorithm to solve it， and at the end， throughan empirical case， demonstrated the validity and practicality of the model.

cold chain； 2-Opt； immunity genetic algorithm； distribution route optimization

F224；F252.14

A

1005-152X（2016）07-0072-04

10.3969/j.issn.1005-152X.2016.07.016

2016-06-07

北京市自然科学基金项目（4132024）；北京市社会科学基金重点项目（15ZHA004）

王咪（1991-），女，山东济宁人，北京信息科技大学研究生，研究方向：物流系统规划与设计；杨孔雨（1967-），男，山东巨野人，北京信息科技大学教授，研究生导师，研究方向：智能决策和优化计算的理论应用研究。