基于多目标和单配送中心的冷链物流配送路径优化研究——以川渝地区某公司冷链物流配送为例

付秋睿，蒲 忠，魏 卓 FU Qiurui,PU Zhong,WEI Zhuo

（1.西南石油大学 经济与管理学院，四川 成都 610500；2.中国石油吉林油田分公司物资供应处，吉林 松原 138000）

0 引言

随着国民经济的持续增长，人民生活水平的不断提高，居民对食品品质的要求逐渐增加，冷链市场需求不断扩大。在这样的背景下，冷藏设备和运输设备不断完善，冷链物流行业进入了高速发展时期。但是当前我国制冷技术仍有缺陷，单位时间制冷成本很高。不合理的线路使得配送时间长，车辆空载率高，从而导致冷链物流环节配送效率低成本高，因此，优化配送线路是提高效率降低成本的关键。

1 川渝地区冷链物流配送路径优化模型

1.1 研究内容

针对川渝地区某公司易腐食品冷链物流配送成本过高，效率很低的问题进行研究。因为冷链物流具有时效性，运输时间长短显著影响着冷链的质量。而降低成本是公司运营考虑的重要条件，所有以时间为主要目标，成本为次要目标，建立优化模型。因该公司实际情况限制，此次研究是多车辆，单配送中心的车辆运输问题。

1.2 模型建立

1.2.1 基本假设

本次研究是车辆路径问题，根据实际需要，提出如下假设：

（1）所有配送点均由一个配送中心配送。

（2）所有配送车辆型号一致，制冷设备一样，折旧年限相同。

（3）配送中心和配送点地理坐标已知。

（4）每辆车所负责配送的线路上总货物需求不超过其最大载重。

（5）每个配送点只能由一辆车完成配送。

（6）车辆配送产品为单一品种，且运输途中外部温度不变。

（7）车辆匀速，路况良好，不考虑拥堵情况。

1.2.2 参数描述

根据假设定义如下变量：

配送点数设为M，配送中心编号是0，配送点依次为：1,2,3,4,…,M。

车辆编号为k，车辆数为n，最大载重为Q，配送点i需求量为qi。

对于两配送点之间组成的直线段（i,j）和车辆k有决策变量xijk。当xijk等于1，车辆k从配送点i行驶到配送点j，当xijk等于0，车辆k不从配送点i行驶到配送点j。

1.2.3 成本分析

（1） 固定成本

固定成本主要包括每辆车的购置费用，固定损耗以及员工工资等。固定成本以F1表示：

C1为车辆固定成本，单位为万元；n为配送中心自有的车辆数。

（2） 运输成本

运输成本主要为载货汽车燃料消耗成本。载货汽车燃料消耗成本与其行驶里程数成正比关系。载货汽车油耗成本以F2表示：

C2为车辆单位距离油耗成本，单位元/KM；dij为节点i与节点j之间的距离；为所有车辆行驶总距离。

（3） 制冷成本

制冷成本是指冷藏车行驶过程中由于需要保持低温而消耗制冷剂产生的成本。通过计算太阳辐射和车厢内外部温差产生的热负荷来确定消耗的制冷剂量。第k辆车产生的热负荷以Gk表示：

Β为车厢劣化程度；R为传热率；S为车辆受太阳辐射面积；Tw为外界温度；Tf为车厢内部温度。

因此，冷藏车在行驶过程中产生的制冷成本F3为：

C3为单位能量制冷成本，单位元/KJ；tk为车辆k行驶时间。

1.2.4 目标函数

基于以上分析，得出区域冷链物流配送模型目标函数为：

主要目标：

次要目标：

约束函数为：

区域冷链物流配送模型中，公式（7）表示每个客户点只能接受一次配送服务；公式（8）表示载货汽车完成客户服务后必须离开；公式（9）表示载货汽车完成任务后必须返回配送中心；公式（10）表示某路径上客户需求总量不超过装载汽车最大载量限制；公式（11）为决策变量，当车辆k从i前往j时取值1，反之取0。

2 算法分析

2.1 遗传算法的基本思想

遗传算法是借鉴生物界自然选择和自然遗传机制的随机化搜索算法。它是遵循生存竞争，适者生存的原则，模拟一个人工种群的进化过程。通过选择、交叉以及变异等机制，在每次迭代中都保留一组候选个体，重复此过程，种群经过若干代进化后，理想情况下其适应度达到近似最优。

2.2 遗传算法流程

（1） 确定种群规模M，随机生成M个个体作为初始种群X（0 ），设t=0；

（2） 计算X（t）中个体的适应值；

（3） 根据适应值的大小从X（t）中选择若干个个体作为进化群体X "（t）；

（4） 在群体X "（t）上按给定的概率进行交叉进化和变异进化，按给定的规则选择N个个体作为下一代种群X（t）；

（5）是否满足终止准则，如果满足，停止计算，否则，返回（2）。

遗传算法流程，如图1所示：

图1 遗传算法流程图

2.3 模型的遗传算法设计

2.3.1 编码和解码

冷链物流配送路径问题是特殊的车俩路径问题，是一种基于优化排序的组合问题。一般的编码方法为二进制编码或十进制编码。本次研究采用十进制编码。具体方法为：对m个配送点依次进行编号，用i1a,i2b,…,ikc表示，k代表车辆，a、b、c代表该辆车所途径配送点个数，配送中心用0表示。染色体编码串为： （0,i11,i12,…,i1a,0,i21,i22,…,i2b,0…0,ik1,ik2,…,ikc,0）。

其中，染色体长度为m+k+1。0为配送中心，编码串中两个0之间的数字表示一条配送路径。例如有15个配送点和4辆车配送的染色体编码串为（0→5→2→14→13→0→3→6→8→9→10→0→11→12→1→0→4→7→15→0），表示由4辆车对15个配送点完成配送服务，共有4条子路经。其对应的4条子路经为：

子路经1：5→2→14→13

子路经 2：3→6→8→9→10

子路经3：11→12→1

子路经4：4→7→15

2.3.2 遗传算子的设计

（1）本次研究采用比例选择法确定选择算子。比例选择法又称轮盘赌选择策略，是最基本的选择策略之一。将种群中所有个体的适应度值进行累加然后归一化，最终通过随机数对随机数落在的区域对应的个体进行选取，类似赌场里面的旋转的轮盘，例如种群大小为m，个体i的适应度为Fi，则个体i被选中遗传到下一代群体的概率Pi为：

（2）本次研究交叉算子采用部分匹配交叉法。部分匹配交叉法是随机定义两个交叉点之间的区域为匹配区域，交换两个父代的匹配区域，从而得到交叉后的个体。交叉概率取0.5。

（3）本次研究变异算子选择倒位变异算子。倒位变异算子是随机选择一条子路径，将这条子路径倒序排列成新的子路径，由此实现变异思想。因为变异在进化过程中发生的概率很小，所以变异概率取0.005。

2.3.3 适应度函数

由于川渝地区冷链物流优化模型目标函数是总时间最短和总成本最低，是求解最小值函数，因此采用倒数的方式将目标函数转化为适应度函数：

其中，Fi代表第i个染色体的适应度值，Ai为配送总成本值。目标函数越小，则适应度函数值越大，越符合模型优化目标。

3 算例分析

3.1 样本选择

x超市是川渝地区著名大型国有零售企业，目前已拥83家连锁超市，遍布川渝各个区县。现排除掉相对位置接近的13家门店，选取其中70家门店进行冷链配送路径优化研究，验证模型和算法的有效性。

3.2 相关数据

冷藏车从渝北配送中心出发向70家门店进行配送服务。配送产品为酸奶，运输过程中温度控制在4度，车辆内外温差为26度，车辆型号、车况、车速均一致，车辆载重为5吨，行驶速度为80公里/小时。

3.3 配送点相关信息

配送中心每两天向各配送点完成一次配送，配送出发时间在凌晨1：00～5：00，车辆出发时间与门店距配送中心距离有关，完成配送后返回配送中心。门店位置，需求量如表1所示：

表1 配送点极坐标表

4 结果分析

根据遗传算法的设计思路，采用Matlab2014b设计多目标区域冷链物流配送路径优化程序。根据上述分析，在CPU为Intel Core i5 5200U、内存为4GB、操作系统为Windows 7的计算机上运行 Matlab 2014b，求解上述模型。所得优化路径如表2所示：

最优计算结果表明，算例最优解为94.31小时，总成本为86 807.32元，完成一次配送所需6 807.32元。在第83次迭代时生成最优解，一共10条路径为最优路径组合。与原路径相比，优化路径时间更短，成本更低。经过验算，所有路径模型全部符合模型容量约束以及返回配送中心的要求。

5 研究结论与不足

5.1 研究结论

本次研究针对冷链物流的时效性，设计以总时间最短为主要目标，总成本最低为次要目标的路径优化模型，并通过遗传算法对模型进行求解。在求解过程中采用十进制编码确定运输路径，采用部分匹配交叉法确定交叉算子，采用倒位变异法选择变异算子，并用倒数的方式确定适应度函数。通过Matlab进行编程求解，在迭代83次后得出优化路径，与原路径相比，优化路径时间更短，成本更低。

5.2 研究的不足之处

由于此次研究考虑的仅仅是确定车型，确定车辆，单车场的路径问题，因此对多配送中心的车辆路径问题还有待进一步深入研究。在算法上，交叉算子变异算子的选择还有进一步提升空间，同时运用遗传算法和其他优化算法结合进行优化，或许能得到更优结果。

表2 优化路径表