混合蚁群算法的实况路网低碳冷链路径优化

高英腾，廖志高

广西科技大学 经济与管理学院，广西 柳州 545006

2020年突发疫情使得用户的消费行为向线上迁移，生鲜电商呈爆发式增长，当年冷链物流市场规模为4 698 亿元，同比增幅38.5%，冷链物流市场规模及同比增幅均创历史新高。生鲜产品有着易腐败的特质，在运输过程中极易产生损耗。同时，由于存在制冷环节，冷链运输产生的碳排放要远高于普通货物运输时产生的碳排放，随着配送路程及配送时间的增加，运输成本及碳排放量也会大大增加。为提高冷链运输效率，减少资源消耗，众多学者对冷链车辆路径问题展开了研究。

车辆路径问题最初以总路程最短为目标，运用贪婪算法[1]、模拟退火算法[2]等进行求解。随着研究的深入，葛斌等[3]在最短路径的基础上引入时间窗的概念，融合蚁群算法和遗传算法，为蚁群算法增加动态参数，提高了算法的收敛速度。易云飞等[4]则在此基础上引入软时间窗的概念，运用改进伊藤算法进行求解。宋芹[5]引入“油耗节约最大化”和“高载重路段延后”的思想，基于禁忌搜索法提出最大油耗节约算法，从最小油耗的角度对路径进行规划。为突出运输过程中碳排放对环境的影响，Bektaş等[6]提出了污染路径问题。王智忆等[7]建立了以碳排放量最低为目标的配送路径优化模型，并采用蚁群算法进行求解。Jabir等[8]则在综合考虑经济成本和碳排放成本的情况下，构造了多基地绿色车辆路径问题，提出了一种将可变邻域搜索与蚁群算法结合的混合算法，每只蚂蚁求出初始解后，通过可变邻域搜索再进行连续优化，不断提高解的质量。

相比于车辆路径问题，冷链车辆路径问题需要考虑的因素更多。Ahumada等[9]以生产者收益最大为优化目标，建立了带时间窗的冷链车辆路径问题优化模型。Shukla 等[10]以运输成本、腐烂程度为优化目标函数，构建数学模型来解决生鲜农产品冷链物流问题。梁承姬等[11]则从制冷成本的角度出发，将温度引入决策变量中，通过调节车厢温度来降低配送成本。王淑云等[12]考虑了不同产品的保存温度不同，建立了随机需求下带有时间窗的冷链多温共配路径优化模型。陈久梅等[13]在此基础上，综合考虑生鲜农产品多品种与小批量以及易腐性的特性，以车辆行驶成本最小为优化目标构建数学模型，设计了一种改进粒子群算法求解。

在某些场景中生鲜产品由配送时间产生的成本远高于由配送距离产生的成本，而路况的变化严重影响着运输时间。为了减小由路况问题导致的成本偏差，学者们开始在冷链运输路径问题中引入交通路况信息，考虑道路拥堵如何通过影响车辆行驶速度来影响道路选择。兰辉等[14]将配送路段的距离矩阵转化为运输时间矩阵，以总成本最小为目标构建了冷链物流车辆路径问题数学模型，设计遗传算法与2-opt 算法结合的混合遗传算法进行求解。Xu、Fan 等[15-16]考虑到实际情况中车速的变化是平滑的而不是阶梯状的变化，使用三角函数来替代阶梯变化的速度。Woensel等[17]考虑了车辆随机行驶时间，在考虑配送成本的同时引入农产品配送的服务质量，设计改进禁忌搜索算法寻找配送服务质量与配送成本之间的平衡点。

可以看到，随着研究不断深入，对车辆路径问题的研究逐渐由单一算法向混合算法过渡，算法所得结果越来越精确，对冷链车辆路径问题的研究也越来越贴合实际需求。但上述研究仅考虑配送点之间只有一条道路通行。在实际配送时由于市区道路的复杂性，车辆往往有多条道路可以选择，使得问题与传统的旅行商问题不同，除配送点外还存在许多可重复到达的转运节点。此时若采用蚁群算法，蚂蚁会在行驶成本较低的路段重复搜索，而采用贪心规则的Dijkstra算法计算量大，且易陷入局部最优。针对这一问题，本文尝试利用蚁群算法正反馈的特点以及Dijkstra 搜索能力强的特点设计蚁群-Dijkstra 混合算法，用蚁群算法选择下一配送点，通过Dijkstra 算法搜索两配送点之间的最短路径，并在每轮迭代后利用蚁群算法留下的信息素调整不同时刻的道路运输成本，使得贪心规则的Dijkstra 算法能考虑到总成本最低而不是当前路径的最低成本。同时预留修正成本文件，减少计算量，最终达到提高响应速率、优化行驶路径的目的。

1 模型建立

本文研究基于市区实况路网的冷链车辆运输规划问题，考虑配送点之间有多条道路可以选择，综合考虑固定成本、时间变动成本、路程变动成本、时间窗惩罚成本及碳成本，以总成本最低为目标函数建立数学模型。

1.1 问题假设

为更好地界定研究问题，提出假设如下：（1）有且仅有一个配送中心，车辆从配送中心出发，在车内货物配送完毕后返回配送中心，且车辆仅负责送货，不负责取货。（2）配送中心车辆充足，每个零售商的需求量不会高于单次配送能力。（3）每个零售商的位置、需求量、服务时间以及时间窗已知，且所需货品为同一品类。（4）配送点与物流中心约定好货品送达时间窗，若车辆未按时间窗约定的时间送达，需要付出罚金。（5）运输车辆型号统一，能耗及油耗相同，司机均接受过相同的技能培训，油耗不会随主观因素变化。（6）车辆在每条道路上的行驶速度为该道路当前能够行驶的最大速度。

1.2 符号和变量

为方便研究描述，引入符号及相关含义如下：α为信息素启发因子；β为成本启发因子；λ为信息素挥发因子；N为配送点数量；K为所需车辆总数；fk为第k辆冷藏车的固定成本；a为运输时制冷成本系数；b为装卸时制冷成本系数；qj为客户j对产品的需求量；为车辆k选择从客户点i到客户点j的概率；P为产品单位价格；∂1为货物运输时的衰减系数；∂2为货物装卸时的衰减系数；为车辆k从配送中心出发时间；为车辆k对客户点j的服务时间；为车辆k从客户点i到客户点j时的载重；Q为车辆最大载重；ε1为车辆早于时间窗送达的惩罚系数；ε2为车辆晚于时间窗送达的惩罚系数；ρ0为车辆空载行驶时的燃油消耗率；ρQ为车辆满载行驶时的燃油消耗率；为车辆从客户i到客户j的运输距离；R为最高赔偿金额；为车辆k从配送点i到配送点j的行驶速度；Pf为单位体积的燃油价格；PC为碳排放价格；TC为单位燃料产生的碳排放量。

1.3 决策变量的制定

客户点由i、j表示(i,j=1,2,…,n)，决策变量xijk为0-1变量，取值如下：

决策变量yjk为0-1变量，取值如下：

1.4 成本分析

（1）固定成本C1

固定成本包括司机的工资，车辆折损、保养等费用。这部分成本仅与运输车辆的数量有关，故固定成本C1可表示为：

（2）路程变动成本C2

路程变动成本主要为车辆行驶产生的油耗，油耗的计算方式采用负载估计法[18]。车辆负载量为时的燃油消耗率ρM为：

则在车辆行驶过程中的总油耗fuel为：

路程变动成本等于油耗成本C2，表示为：

（3）时间变动成本C3

考虑时间变动成本时，需要考虑不同路况对运输时间的影响，车辆k从点i到点j所需的时间可表达为：

时间变动成本包括制冷成本及货损成本。制冷成本包括运输时消耗制冷剂的成本及制冷的油耗。考虑运输及装卸时车厢温度不同，对制冷剂及燃油的消耗不同，在模型中将二者系数分别合并为a、b，分别代表运输及装卸时的制冷成本系数。此时制冷成本C31可表达为：

由于生鲜产品的品质会随着运输时间的增长而不断下降，且随时间的增长，品质的下降程度呈指数型增长，故在此使用L(t)表示货物的衰减程度[19]：

卸货时，由于货物已经送达，此时货损仅计算卸货后剩余部分，则货物在运输过程中的货损成本为：

在装卸时的货损成本为：

货损成本C32可表达为：

（4）时间窗惩罚成本C4

在实际情况中，配送点和配送中心约定时间窗(Ei,Li)，商品j应在时间窗内送达。若商品提前送达，需赔偿配送点由于未做好接货准备而造成的损失，若商品延迟送达，则需赔偿由延误造成的损失。但是由于商品价值有限，该成本不会无限量地增加，故在此设定赔偿上限R，使得赔偿成本不会高于R值。时间窗惩罚成本C4可表示为：

（5）碳排放成本C5

车辆运行中所产生的碳排放主要分为两部分，一部分是车辆行驶的燃油消耗成本，另一部分则来自制冷所消耗的燃油及制冷剂。考虑到制冷剂消耗量较少，以制冷成本消耗的燃油代替计算相应的碳排放量。这两部分成本见式（5）及式（8），则车辆行驶中的碳排放主要由燃油燃烧产生。

2021年全国碳排放市场上线交易启动，若企业总碳排放未超出碳配额，可以交易出售；反之则需购买超排数量。此时碳配额可看作企业已有收益，产生的碳排放需以碳市场价格支付成本，故此处以碳市场价格描述单位碳排放成本。故碳排放成本C5可表示为：

综上所述，总成本C的表达式为：

式（16）表示每个客户都被服务且仅被服务一次。式（17）表示车辆服务于客户时其货物数量能够满足客户需求。式（18）表示每辆车从配送中心出发，返回配送中心。

2 模型求解

首先尝试采用蚁群算法求解。在算法初期，由于路径之间的信息素相同，蚂蚁较大概率选择两点之间成本较低的节点，而经过中转节点时，该节点不被列入禁忌表，也不会触发时间窗惩罚成本，因此蚂蚁会在某些抵达成本较低的节点中来回走动。Dijkstra算法能够避免重复搜索问题，故拟利用蚁群算法选择下一配送点，通过Dijkstra 算法搜索两配送点之间的最短路径，并在每轮迭代后利用蚁群算法留下的信息素调整不同时刻的道路搜索成本，使得贪心规则的Dijkstra 算法能考虑到总成本最低而不是当前路径的最低成本。

2.1 启发式因子设计

启发式因子是蚂蚁选择下一目的地的重要依据，通常随目的地的重要程度增大而增大。算法以总成本最低为目标，故以成本因素作为启发式因子。因此设计启发式因子ηij为：

其中，Cij代表车辆从点i到点j的成本。

2.2 信息素更新

蚂蚁在经过的道路上会留有信息素，并通过信息素的含量判断该道路是否重要。为防止算法陷入局部最优，在交通拥堵时找到更好的代替配送路径，在每轮所有蚂蚁巡回完毕后，同时选择所有轮次总成本最低以及当前轮次总成本最低的蚂蚁经过路径更新信息素。

最优路径上信息素更新规则为：

非最优路径上信息素更新规则为：

其中，λ为信息素挥发因子，目的是减少最初搜索时残留信息素的影响。但为了使得算法在交通变动时仍能选出次优路径，该值不宜过小。

为防止算法过快收敛，在此引入一个不断增大的q0(q0∈[0,1])，在每次蚂蚁选择下一个配送点时会先产生一个随机数qi，将q0与qi进行比较，根据比较结果来选择下一配送点。具体表达式如下：

当qi小于等于q0时，在可选路径中选择修正成本最高（实际成本最低）的路径。反之按照轮盘赌的方式进行选择。

2.3 混合算法流程设计

考虑到运输过程中需要根据交通变化情况实时调整路线，而Dijkstra算法计算量较大，故将算法分为两阶段进行求解计算。第一阶段为预处理过程，此时算法以蚁群算法为主，通过反复迭代更新不同时刻不同道路上的信息素含量，得到初始配送路径及修正成本地图。预处理阶段混合算法流程如图1所示。

图1 预处理阶段的混合算法流程Fig.1 Hybrid algorithm flow in preprocessing stage

当途经路况发生变化时，无需全部重新计算，通过已有的修正成本地图，修正对应时刻的道路成本，然后按照贪心规则的Dijkstra算法搜索即可。此时算法流程如图2所示。

图2 路况变动时混合算法流程Fig.2 Hybrid algorithm flow when road conditions change

3 实证分析

3.1 数据获取

高德开放平台提供了API接口，可以查询指定区域内所有道路的交通态势。反馈内容包括当前时间、道路名称、道路坐标、道路速度以及当前拥堵情况。数据获取间隔为5 min，得到2020年9月至2020年12月共三个月的交通态势信息，根据获取到的道路坐标绘制出街道道路图如图3所示。

图3 市区街道道路图Fig.3 Urban street map

3.2 车速预测

车速使用BP 神经网络方法进行预测，设输出层有m个神经元，BP网络的实际输出为y，期望输出为y′，则损失函数ε为：

权值的修正值为：

考虑到坐标点较多，对每个点的速度进行预测计算量极大，故对同一道路速度取平均值，预测整条路的速度。综上，将当前时间、道路名称以及道路速度三个因素作为输入值，确定输入节点数为3，输出值为预测道路名称及道路所对应的速度。经处理，共有115 条道路，即输出层所对应的节点数为115。隐藏层选为4 层，节点数分别为64、128、256、128。网络结构如图4 所示。经检验，日均速度误差为4.24%，预测结果在可接受范围内。

图4 车速预测神经网络结构Fig.4 Neural network structure of vehicle speed prediction

通过数据清洗，剔除外围高速、高架等道路，以交通路口为节点，根据主城区交通布局得到路口节点分布及其连通情况。

3.3 参数设计

在算法运行时，考虑到希望算法在初期能够尽可能扩大搜索范围，避免陷入局部最优，而在后期则能够较好收敛，设置随机数q0与当前搜寻次数相关，随着搜寻次数的增加而增大。

其中，l为当前轮次，lmax为总轮次，此处取50。其余参数设置：信息素启发因子α=3，成本启发因子β=2，蚂蚁数量m=15，为在搜索后期保留更多次优路径以供路况发生拥堵时选择，信息素挥发因子λ=0.9。冷藏车以福田祥菱M1后双轮冷藏车为原型，空车燃油消耗系数ρ0=1.2，满载燃油消耗系数ρQ=2.4，空车重量Qk=3 385 kg，满载重量Qm=4 880 kg。考虑装载时货物不能填满空间，设载质利用系数Ψ=0.92，货物单价P=20 元/kg，运输时衰减系数∂1=0.03，装卸时衰减系数∂2=0.06，早到惩罚系数ε1=0.002，晚到惩罚系数ε2=0.005，运输时制冷成本系数a=0.01，装卸时制冷成本系数b=0.02，油价Pf=7.62 元/L，公路运输中单位燃料燃烧产生的碳排放量通常为2～5 kg/L，综合考虑载重、配送距离、坡度等因素确定单位燃料的碳排放成本为2.67 kg/L[20-21]。2021年首批全国碳交易市场中碳交易价格为50 元/T，算得单位碳排放价格PC=0.138 元/L。

各节点分布及连通情况如图5所示，其中蓝色点为交通节点，橙色点为配送点，绿色点为配送中心，连线表示两节点之间可以通行（连线长度不代表两点之间实际距离，实际距离为获取数据中道路真实长度）。

图5 各节点分布及连通情况Fig.5 Distribution and connectivity of nodes

考虑到市区规划，模拟出各配送点的坐标及其配送需求如表1所示。其中点（14，4）为配送中心，其余点为配送点。

表1 配送点坐标及需求（情景1）Table 1 Coordinates and demand of point（Scene 1）

3.4 对比分析

情景1配送需求如表1所示。

（1）交通情况正常

交通情况正常时，单独使用蚁群算法，在算法运行过程中蚂蚁会在运输成本较低的节点中循环往复，即使将最近经过的若干节点引入禁忌表依然无法收敛。

交通情况正常时，单独使用Dijkstra 算法得到的运行轨迹如图6所示，算法之间运算结果对比如表2所示。

表2 交通正常时各算法对比（情景1）Table 2 Comparison of algorithms in normal traffic（Scene 1）

图6 交通正常时Dijkstra算法车辆A-B行驶路线Fig.6 Vehicle A-B route in normal traffic when using Dijkstra algorithm

相同情况下，使用蚁群-Dijkstra 混合算法得到运行轨迹如图7所示。

图7 交通正常时混合算法车辆A-B行驶路线Fig.7 Vehicle A-B route in normal traffic when using hybrid algorithm

（2）交通发生拥堵

模拟5：40某路段发生交通事故造成拥堵且拥堵在40 min 后恢复时，单独使用Dijkstra 算法时得到运行轨迹如图8所示。

图8 交通拥堵时Dijkstra算法车辆A-B行驶路线Fig.8 Vehicle A-B route in traffic congestion when using Dijkstra algorithm

相同情况下，使用蚁群-Dijkstra 混合算法得到运行轨迹如图9所示，运算结果对比如表3所示。

图9 交通拥堵时混合算法车辆A-B行驶路线Fig.9 Vehicle A-B route in traffic congestion when using hybrid algorithm

表3 交通拥堵时各算法对比（情景1）Table 3 Comparison of algorithms in traffic congestion（Scene 1）

情景2配送需求如表4所示。

表4 配送点坐标及需求（情景2）Table 4 Coordinates and demand of point（Scene 2）

（1）交通情况正常

交通情况正常时，单独使用Dijkstra 算法得到运行轨迹如图10所示，算法之间运算结果对比如表5所示。

表5 交通正常时各算法对比（情景2）Table 5 Comparison of algorithms in normal traffic（Scene 2）

图10 交通正常时Dijkstra算法车辆A-B-C行驶路线Fig.10 Vehicle A-B-C route in normal traffic when using Dijkstra algorithm

相同情况下，使用蚁群-Dijkstra 混合算法得到运行轨迹如图11所示。

图11 交通正常时混合算法车辆A-B-C行驶路线Fig.11 Vehicle A-B-C route in normal traffic when using hybrid algorithm

（2）交通发生拥堵

模拟5：40某路段发生交通事故造成拥堵且拥堵在40 min 后恢复时，单独使用Dijkstra 算法得到运行轨迹如图12所示。

图12 交通拥堵时Dijkstra算法车辆A-B-C行驶路线Fig.12 Vehicle A-B-C route in traffic congestion when using Dijkstra algorithm

相同情况下，使用蚁群-Dijkstra 混合算法得到运行轨迹如图13所示，运算结果对比如表6所示。

图13 交通拥堵时混合算法车辆A-B-C行驶路线Fig.13 Vehicle A-B-C route in traffic congestion when using hybrid algorithm

可见，在城市交通网络内蚁群算法无法完成搜寻任务。相比于Dijkstra算法，混合算法通过预留信息素，综合考虑需求时间窗、惩罚成本等因素，缓解了在纯贪心规则下由于选择当前道路成本最低而提高整体成本的问题。同时，由于在每轮搜索时在当前成本最低和总成本最低的路径上同时留下信息素，使得当总成本最低路径出现拥堵时，也能较好找到次优解。

在情景1与情景2中，当路径出现拥堵时，若采用贪心Dijkstra 算法进行计算，所得路径总成本较使用贪心Dijkstra 算法计算且交通情况不拥堵时分别增加了16.76%、11.01%；若采用混合算法进行计算，所得路径总成本较混合算法进行计算且交通情况不拥堵时分别仅增加了11.51%、8.38%；而当路径出现拥堵时，采用混合算法进行计算较Dijkstra 算法相比，所得路径总成本降低了14.89%、8.02%。同时，由于预留了成本修正地图，在交通情况发生变化时不需要重新计算所有路径成本，只需计算交通情况变化路段的成本，因此计算时间大大缩短，由原先的124.03 s分别降低到了34.17 s、41.03 s。

通过对比分析，混合算法能够有效降低搜寻路径成本，同时通过预留修正成本地图，减少计算量，提高搜寻效率，进而提高反应速度。

4 结束语

本文以城市局部网络模型为对象，利用历史数据对未来一段时间内不同道路的车辆运行速度进行预测，并在此基础上，分别用蚁群算法、Dijkstra 算法以及蚁群-Dijkstra混合算法进行求解。实例证明：（1）在城市内交通网络复杂的情况下，混合算法能够有效改善蚁群算法无法有效收敛、Dijkstra算法易陷入局部最优的问题，得到较优结果。（2）通过预留修正成本文件，能够大幅降低算法计算时间，提高应对交通异常时的响应速率。（3）计算电脑配置为Intel Xeon Processor（Skylake，IBRS）2.30 GHz（4处理器），考虑到单台电脑计算能力有限，若使用边缘云计算有望能提高运算速度，达到实时处理交通异常问题的能力。