基于软时间窗的多车舱生鲜品配送路径优化

温廷新，李可昕，胡迎春

(辽宁工程技术大学 工商管理学院，辽宁 葫芦岛 123000)

0 引言

近年来，随着工业的不断发展、温室效应的不断加剧，以“低能源，低消耗，低排放”为基础的节能减排理念受到学者们的广泛关注。交通运输业的碳排放量在总碳排放量中占有很大的比例，为保持生鲜品的质量，冷链运输会排放更多的CO2。为此，冷链物流的路径优化研究变得更加有意义[1-2]，从绿色物流的视角看，采用多车舱的配送方式更加具有研究意义[3]。

在考虑碳排放的车辆路径优化研究上，国内外学者已针对低碳视角下的生鲜品冷链配送路径优化问题做出了相应的研究。韩飒[4]根据车联网技术，提出一种道路交叉口环保驾驶汽车路径优化控制模型；任慧等[5]根据车辆行驶状态定义道路拥堵情况，以不同时段下拥堵概率和预期拥堵距离作为路况决定因素，构建碳排放量和经济成本都最小的两目标模型；鲁建厦等[6]为了提升子母式飞梭集散仓库的运行效能，针对该集散仓库组合操作中的立体路线优化问题展开了研究；刘枚莲等[7]研究了带碳排放和时间窗双重约束的车辆路径优化问题；张旭等[8]针对需求与碳交易价格双重不确定下的多式联运路径优化问题建立了混合鲁棒随机优化模型；Guo等[9]考虑到车辆的负载和驱动距离，建造了相应的碳排放模型并将其设为优化目标。

此外，也有一些学者针对生鲜品的冷链运输问题展开研究。任腾等[10]以顾客满意度为指标，以车辆载重、顾客时间窗口、冷藏食品腐坏速率等为约束条件，建立了以最少碳排放为目标，以顾客服务时间为限的冷链运输路线优化模型；方文婷等[11]采用混合蚁群算法对总成本最小模型进行优化；余海燕等[12]针对线上到线下(Online to Offline，O2O)生鲜外卖订单动态性高和配送服务时效性强的特征，建立以配送距离最小为目标、带硬时间窗的O2O生鲜外卖即时配送路径优化模型；吕成瑶等[13]通过改进蚁群算法对冷链物流成本最小模型进行优化；姚源果等[14]为了更好地实现终端柔性配送并有效地减少整体配送费用，提出了在供应链中合理地布置接驳点，并以交通状况与接驳点为依据构建了农产品供应链的配送路线最优的数学模型；丁艳[15]针对传统多温共配冷链物流车辆配送路径优化方法提出一种新的多温共配冷链物流车辆配送路径优化方法；王旭坪等[16]以车辆能量消耗为切入点，研究多温度冷链物流车辆的碳排放测算方法并将其与时间和空间距离相结合，建立兼顾碳排放和时间空间距离的冷藏物流车辆运输路径优化模型，并设计两阶段启发式算法对其进行求解；唐燕等[17]利用薄板样条法插值分析动态环境温度与制冷变量关系，建立响应动态环境温度的扩展邻域搜索调度模型。

综上所述，许多学者在低碳物流及冷链物流方面作了诸多研究，但罕见学者对碳排放下的多车舱多温共配方式进行研究。本研究针对不同温层的生鲜品运输问题，从低碳和不同温层生鲜品货损2个角度进行分析，综合考虑配送车辆产生的碳排放量及货损问题，以带软时间窗的车辆路径优化模型为基础，构建一个成本及能耗最低的路径优化模型，采用知识型蚁群算法进行优化。

1 多车舱生鲜品路径优化模型建立

1.1 问题描述

本研究中的多车舱生鲜品多温共配问题是传统车辆路径优化研究的扩展类型，问题具体表述为：配送系统包含一个配送中心和多名顾客需求点，采用一般货车，在车上放置处于不同温层的蓄冷箱，配送冷冻及冷藏产品。各顾客点的需求及配送时间窗已知，对生鲜品冷链多温共配问题需要做出以下假设：

(1)配送车辆都是从分配中心出发并最后返回该配送中心；

(2)每个车舱只能装对应温层的生鲜品；

(3)物品的配送流向为单向；

(4)每名顾客的需求量已知且只被服务一次，切忌不可重复服务，同时不可遗漏顾客；

(5)运输工具为K辆车，所有客户由K辆车共同配送，每条配送路线都只有一辆车配送，不可中途换车；

(6)每辆车的不同温层的装载量不能超过不同温层的最大载重量；

(7)每辆车装载量不可超过车辆的运输能力，须大于单向顾客总需求量；

(8)每名顾客都有自己的配送时间窗，配送车辆要在限定的配送时间窗内配送；

(9)各个节点的距离已知。

1.2 配送成本及碳排放计算

1.2.1 配送成本计算

本研究中的多车舱生鲜品路径优化问题对运输车辆的配送成本进行了全面分析，包括固定成本、运输成本、货损成本、时间窗的机会与惩罚成本、制冷成本。

(1)配送车辆的固定成本

在生鲜品配送过程中，配送车辆会产生一部分固定成本，包括蓄冷箱的购买及损耗成本、车辆折旧费、车辆派遣费用、司机驾驶费、装卸工人工资等。

C1=H×f，

(1)

式中，H为车辆总数；f为车辆的单位固定成本。

(2)配送车辆的运输成本

车辆的运输成本，即车辆在物流配送过程中从一名顾客到下一名顾客途中所产生的费用，与车辆行驶的距离成正比，使用V代表配送网络，其中G={0，1，2，…，m}表示网格中的节点，{0}表示配送中心。

(2)

式中，h为第h辆车；B为车辆的单位运输成本；Bijh为第h辆车在路段(Gi，Gj)行驶的单位运输成本；Xijh为0-1变量，若车辆h在路段(Gi，Gj)行驶即Xijh=1，否则Xijh=0；dij为(Gi，Gj)之间的距离。

(3)配送车辆在运输过程中所产生的货损成本

配送车辆在运输过程中会产生两部分的货损：一部分是在车辆正常行驶过程中产生的货损，另一部分是由于配送车辆在服务顾客过程中打开蓄冷箱时导致温度骤然升高，使生鲜品的新鲜程度降低，导致品质下降产生一定的货损。

P2yjh(w2dij+w4tj2)，

(3)

式中，P1为冷冻区货物的价格；P2为冷藏区货品的价格；yjh为0-1变量，表示第h辆车服务j顾客；w1，w2分别为在运输过程中冷冻区和冷藏区的单位货损比例；w3，w4为在服务顾客过程中冷冻区和冷藏区的单位货损比例；tij为配送车辆从客户i到客户j的时间；tj1，tj2分别为车辆为顾客j服务时冷冻区和冷藏区所产生的时间；

(4)配送时间窗的机会成本及惩罚成本

配送车辆要在特定时间范围内进行配送以保证生鲜品的质量，在时间窗之前到达则会产生部分的机会成本，而在时间窗之后到达会产生部分惩罚成本。

(4)

式中，α，β分别为时间窗的机会成本和时间窗的惩罚成本；Sj为配送车辆到达时间；(L，T)为客户的配送时间窗；

(5)配送车辆的制冷成本

配送车辆采用蓄冷箱进行冷藏及冷冻产品运输。蓄冷箱由蓄冷板构成，采用充电的方式进行蓄冷。蓄冷箱在运输过程中损失掉多少的冷量，就相当于蓄冷箱在之前要储存多上的冷量，而蓄冷需要消耗很多的电，所谓的制冷成本也就是蓄冷箱蓄冷时所耗的电。

C5=Q·E·P3，

(5)

tj1+b2×tj2)，

(6)

式中，Q为损失掉的热量；E为每单位热量需要的电；P3为单位用电价格；a1，a2分别为在运输过程中冷冻区和冷藏区单位时间冷量损失；b1，b2分别为在服务顾客时单位时间冷量损失；

1.2.2 碳排放计算

传统的冷链运输中碳排放有两部分，一部分是正常行驶过程中产生碳排放，另一部分是冷藏车为保持车辆内部温度不变，需要不断地进行冷气输入，这时也会产生一部分碳排放。然而，该方案中采用一般货车进行配送，制冷部分采用蓄冷箱完成大幅减少碳排放的产生。

CE=λ×Z，

(7)

C6=P4×Z，

(8)

Z=(R1+φ(R2-R1))dij，

(9)

式中，CE为碳排放量；Z为总耗油量；R1为车辆空载时单位距离油耗量；R2为车辆满载时单位距离油耗量；φ为车辆货物装载率；λ为单位油耗量产生的碳排放因子；P4为单位油耗的价格。

1.3 模型建立

建立多车舱生鲜品多温共配路径优化模型：

minc=c1+c2+c3+c4+c5+c6。

(10)

确保车辆的装载量不会超出自身最大装载量：

(11)

式中q为车辆自身最大装载量。接下来，确保全部顾客得到了服务，无一遗漏：

(12)

仅对每一名顾客提供一次服务，并且没有多次提供的情况：

(13)

仅有一部车辆为每位顾客提供服务：

(14)

为顾客提供的服务应在顾客所能承受的范围内：

Lj≤Sj≤Tj，j=1，2，3，…m。

(15)

2 算法设计

传统蚁群算法是以人为方式对蚂蚁觅食的过程进行仿真，即个体间的沟通和合作，最后在食物和栖息地之间找出一条最短的路线。若将传统的蚁群算法运用到本研究的路径优化模型中求最优解，对局部最优解的优化能力较差，影响最优解的质量。本研究为了改善算法的品质，在传统的蚁群算法中加入了知识模型，使得该算法能得到高品质的优化结果。与此同时，为了增强蚁群算法的局部优化能力，进而提升算法的收敛速度[18]，将知识型精英策略下的禁忌搜索算子融入到其中。

2.1 编码方式

本研究根据多车舱冷链物流配送路径优化模型采用自然数编码方式，每只蚂蚁由多位自然数编码组成，其中“0”表示物流配送中心，“1，2，3，…，n”表示顾客节点编码。例如：

(1)当n=4时，路径为0-4-2-1-3-0，表示为配送车辆从配送中心出发进经过4，2，1，3，最后回到配送中心；

(2)当n=5时，路径为0-3-1-5-2-4-0，表示为配送车辆从配送中心出发进经过3，1，5，2，4，最后回到配送中心；

(3)当n=7时，路径为0-3-1-5-7-6-4-2-0，表示为配送车辆从配送中心出发经过3，1，5，7，6，4，2，最后回到配送中心。

2.2 知识模型指导下的禁忌搜索算子设计

在传统的蚁群算法对当代个体求解后，设置禁忌搜索对象S为算法的最优解，并初始化搜素计数器C，然后生成邻域，选取较为合适的解对比，更新禁忌表和操作对象。当计数器C达到最大时，输出找到的最优解，当算法找到最优解时，将计数器初始化并继续搜索。在此基础上，提出了一种新的优化方法，并利用该方法引导禁忌搜索算法对该方法进行了求解。它的指导性作用主要体现在两方面：所记录的历史最优解将大概率在搜索过程中作为搜索对象，历史最优解以动态选择概率替换较差邻域解。

2.3 算法流程

本研究在传统的蚁群算法基础上融入了知识型精英决策下的禁忌搜索算子，所设计的知识型蚁群算法的优化分析流程见图1。

图1 多车舱路径优化模型算法流程图Fig.1 Flow chart of algorithm for multi-compartment routing optimization model

3 实例求解及分析

3.1 算例验证

以某物流中转站为例，为20名顾客配送货物，配送中心及顾客的节点位置已知。 编号1～20为顾客节点，编号0为物流配送中心，共4辆车参与配送，车辆总载重为60 t，每个区域的最大载重为20 t，冷冻区的温度保持在-18～-20 ℃，冷藏区保持在3～5 ℃，常温区随室外温度变化(本研究限定常温为20 ℃)，在运输途中保证货物不串味，车辆的行驶速度为45 km/h，在满足车辆不超载的约束条件下合理安排路线。各个客户点位置及限定的时间窗见表1，每名顾客在不同温层的需求量及装卸时间见表2，相关参数设置见表3。

表1 各节点位置(单位：km)Tab.1 Positions of each node(unit：km)

表2 顾客的需求量及装卸时间Tab.2 Customer demand and loading-unloading time

表3 相关参数Tab.3 Related parameters

3.2 结果分析

3.2.1 试验1

为验证多车舱多温共配运输方式的有效性，经过与传统运输方式进行对比，通过程序进行实证分析，最大迭代次数为200次，借助Matlab软件进行优化得出多车舱生鲜品路径优化模型的最优配送路线(见表4)，最终得出最优成本为4 057.24元，该方案产生的碳排放量为17.05 kg(见表5)。

表4 最优配送路线Tab.4 Optimal distribution routes

表5 不同运输方式的成本及碳排放量Tab.5 Costs and carbon emissions of different transport modes

由表4～5可知，多车舱多温共配方式与传统运输方式相比较，避免了车辆重复路径，减少了车辆的配送总路程，提高了配送时效性。在配送成本及碳排放量方面，多车舱多温共配方式是传统运输方式的1/3，极大程度上降低了配送的总成本，减少了碳排放的产生。由此可见，多车舱多温共配是一种既节能又节约的运输方式。

3.2.2 试验2

为了检验本研究所提出的知识蚁群算法的正确性，将知识蚁群算法、改进蚁群算法和蚁群算法应用于多车舱多温共配运输路线优化问题，并对该问题的收敛性进行了比较和分析(见表6)。

表6 算法收敛对比Tab.6 Algorithm convergence contrast

由表6可知，改进的蚁群算法在25 s时已经完成算法收敛，而知识型蚁群算法和蚁群算法分别在75 s和130 s才完成算法收敛。但是从运输总成本上看，知识型蚁群算法的总成本为最小，改进蚁群算法和蚁群算法的总成本均高于知识型蚁群算法。由此可以看出，知识型蚁群算法虽然在收敛速度上比改进蚁群算法慢，但是所求得的总成本是最低的。

4 结论

本研究为了解决不同温层生鲜品的物流配送问题，针对多车舱生鲜品多温共配方式展开研究，基于低碳及不同温层生鲜品的角度建立一种基于软时间窗的总成本及能耗最低的路径优化模型，将知识蚂蚁算法应用于最优解，得到如下结论：

(1)提出了一种由传统车辆路径优化模型拓展的多车舱多温共配路径优化模型。在配送成本及碳排放量方面，多车舱多温共配方式的总成本近似于传统的运输方式总成本的1/3。可见，采用多车舱多温共配的运输方式是一种既环保又节省成本的运输方式。

(2)本研究介绍了一种知识型蚁群算法优化。这种算法是对已有蚁群算法的一种改进，避免了原有算法的局部最优、收敛性较差等缺点。知识型蚁群算法虽然在收敛速度上比改进蚁群算法慢，但是所求得的总成本是最低的。由此可见，根据多车舱多温共配路径优化模型的特点，提出的知识型蚁群算法有效地提高了求解性能，验证了该算法的有效性和实用性。

(3)当前研究中未考虑交通拥堵、极恶劣天气影响、零碳排放等方面问题，未来将进一步对这些情况展开研究。