基于混合蚁群算法的冷链物流配送路径优化研究

方文婷，艾时钟，王 晴，范君博

(西安电子科技大学经济与管理学院，陕西 西安 710126)

1 引言

随着生活质量的不断提高，人们对新鲜绿色生鲜产品的需求也在日益增加[1]。为满足市场需求、促进企业发展，冷链物流企业投入大量车辆在运输环节中，但是因冷链物流配送过程中产生的油耗与碳排放量远超于普通物流，企业降低运营成本以及汽车尾气对环境造成的负面影响的压力也在日益增加。据《中国物流与采购》的调查显示，近一半物流企业燃油费占运输成本的40%以上。据世界资源学院的统计结果可知，交通运输行业的碳排放量占全球总排量的20%。面对经济与环境的双重压力，节能减排对于冷链运输企业显得尤为重要[2]。企业通过推进节能减排，控制油耗量，一方面不仅压缩了油耗成本，而且随着我国政府不断加快碳排放交易体系的全面落实[3]，不久之后，很可能为企业减少关于碳交易的一项运营成本，增加企业利润，有利于企业发展。

另一方面，因碳排放量取决于油耗量，在减少燃油资源使用的同时也降低了对环境造成的碳污染，符合绿色物流发展概念。所以，为了冷链物流企业能够快速发展，寻求经济与环境双赢，将节能减排加入到冷链物流车辆路径问题中是十分重要的。

近年来，国内外学者在冷链物流领域中做了许多研究。徐松梅[4]探讨了配送车数、客户间需求量及配送时间相互作用对冷链配送总成本的影响，并用遗传算法求解了带有硬时间窗限制的冷链配送路径优化模型。De Armas和Melian-Batista[5]研究了动态多目标车辆的路径优化模型并用启发式算法求解，得到了较好的效果。Ding Qiulei等[6]探讨了带有时间窗的物流路径问题，并通过调整信息素对蚁群算法改进用于模型求解，通过算例分析对比验证了算法的有效性。Leung等[7]在传统路径模型基础上考虑了异质车队的情况并运用改进的模拟退火算法分析配送成本的差异。王淑云和孙虹[8]在构建冷链物流路径模型中考虑了客户需求种类的多样性问题，并设计一种将聚类、蚁群算法混合的算法求解模型。缪小红等[9]根据生鲜产品的易腐性，在成本中考虑了配送过程中的货损成本，在车载量、客户需求量约束下建立数学模型，并根据模型对传统遗传算法设计，用改进遗传算法对模型进行求解。随着政府对环境保护与可持续发展的要求越来越高，人们对节能减排的意识也越来越强，有学者将眼光投向了低碳冷链物流方面的研究。Bozorgi等[10]在建立冷链库存模型中，将碳排放作为成本因素融入模型，探索在碳排放和成本约束下的最优库存，开发了一种精确算法求解模型。康凯等[11]将碳排放转化为经济成本建立带有模糊时间的路径优化模型，并设计蚁群算法求解得到了较好的效果；潘茜茜和干宏程[12]、鲍春玲和张世斌[13]构建了同时考虑客户时间窗和碳排放的路径优化模型，并采用启发式算法对其模型进行求解。但上述研究文献仍有不足之处：学者大多是建立以固定成本、运输成本、制冷成本等总成本最小的数学模型，这样虽然能够清楚地表达出冷链配送过程中产生的总成本，但运输成本和制冷成本中都存在油耗成本，容易导致油耗成本的重复计算；虽然已有学者将碳排放作为成本融入模型，但是大多只考虑运输中的油耗而忽略了制冷油耗对碳排放量的影响。基于此，本文将油耗与碳排放量统一计量，企业在配送中所付出的油耗成本以及对造成的碳污染所付出的环境成本统一作为绿色成本考虑进入模型，以配送总成本最小来研究车辆配送路径策略，将更具有现实意义。此外，考虑节能减排的冷链物流配送路径研究成果并不多，本研究将填补此空缺。

车辆路径问题(VehicleRouting Problem, VRP)被学者定义为是NP-hard问题[14]，在该类型问题中，运用精确的数学解析方法难以求解。有学者将启发式算法用于求解VRP问题中[15]，实现了很好的效果。蚁群算法具有良好的鲁棒性、并行性，广泛用于求解VRP问题中[16]，因此本研究采用蚁群算法求解模型。因蚁群算法初始阶段，由于路径信息素的不足，容易导致算法初始阶段的盲目搜索，使收敛次数过大。针对这一问题，本研究提出了一种结合A*算法的混合蚁群算法对本研究模型进行求解。采用了A*算法求出优化解，并在此基础上对路径信息素初始化，达到缩短蚁群算法的收敛次数、减少收敛时间目的。同时根据本文中的研究内容将启发式因子、转移概率等进行改善，使混合蚁群算法更加符合本文所要研究的问题。

2 问题描述

现实中，冷链物流公司由于成本限制，不会设置太多配送中心[17]，所以结合实际情况，本文所研究单配送中心冷链物流的路径优化问题，即车辆从同一个配送中心出发在完成各个客户点提出的生鲜产品配送任务后又返回到同一个配送中心。

基于节能减排视角，如何根据已知资源，在客户需求量、时间窗和车辆最大承载量的限制下，为配送中心提供一个配送策略，使得车辆在从配送中心出发并满足所有客户点的产品配送要求这一过程中，固定成本、绿色成本、制冷成本、货损成本、以及软时间窗惩罚成本总成本最小是本文要解决的主要问题。具体假设如下：

(1)配送中心拥有足够多同种类型的冷藏车来满足客户的生鲜产品配送需求，并且车辆的载重量有限，每一个客户点的需求量均不超过单个车辆的最大载重量；

(2)各个客户点的位置、对生鲜产品需求量、所需的服务时间以及配送时间窗已知；

(3)同一个客户点只安排一辆冷藏车进行配送且能够保证提供满足客户点需求的服务，同一辆冷藏车可配送多个客户点但每一个客户点只允许一辆冷藏车出发和到达一次；

(4)若负责为某一客户点配送生鲜产品的冷藏车未按照与客户点约定的时间窗内送达，企业将为此行为付出罚金；

(5)冷藏车在为客户点提供配送的服务过程中，除为客户点服务时产生装卸生鲜产品的情况外不发生任何装卸产品的情况，即不接受任何其他的配送服务。冷藏车在完成配送任务后返回配送中心；

(6)所有用于冷链配送的司机，都是经过统一严格培训，具有相同的技术经验，油耗量不会因为主观因素而变化。

3 模型中已知参数及变量分析

3.1 已知参数

本文所研究的冷链物流路径优化模型已知参数如下：

N:配送中心所需服务的客户总数；

K:配送中心所有满足配送要求的车辆总数；

fk:使用冷藏车k的固定成本；

fuel:车辆配送过程中所产生的燃油量；

a:配送车辆在运输阶段制冷剂消耗系数；

b:配送车辆在装卸阶段制冷剂消耗系数；

qi:客户点i对生鲜产品的需求量；

P:配送车辆所运输生鲜产品的单位价格；

∂1:配送车辆在运输阶段生鲜产品的新鲜度衰减系数；

∂2:配送车辆在装卸阶段生鲜产品的新鲜度衰减系数；

Ti:配送车辆对客户点i的服务时间；

Qij:配送车辆由客户点i直接前往客户点j时所承载货物的重量；

Q:车辆的最大载重量；

ε1:配送车辆到达客户点的时间早于与客户约定时间窗上限的惩罚系数；

ε2:配送车辆到达客户点的时间晚于与客户约定时间窗下限的惩罚系数。

3.2 变量分析

3.2.1 决策变量分析

方便模型分析，将配送中心定为编号0，客户点由英文字母i,j表示(i,j=1,2,3，…,N)。

决策变量xijk的取值表示如下：

xijk=

当车辆k由客户点i直接驶向客户点j时，也是就车辆k经过路径(i,j)为1，否则xijk为0。决策变量yik的取值表示如下：

yik=

当车辆k为客户点i提供配送服务且客户点i的配送需求被车辆k所满足时为1，否则为0。

3.2.2 成本变量分析

(1)车辆配送过程中的固定成本(C1)

从配送中心出发用于向各个客户点提供配送服务的冷藏车的启用需要一定的固定费用，一般为驾驶员的工资、车辆的折旧费、保养费等费用，这部分费用仅与启用冷藏车的数量相关。可如式(1)所示：

(1)

其中x0jk当配送中心启用冷藏车辆k时为1，否则为0。

(2)车辆配送过程中的绿色成本(C2)

本研究中绿色成本为企业对冷藏车辆运输过程中产生的油耗而支出的油耗成本以及为运输过程中产生的碳排放造成环境污染而支付的环境成本。

油耗量采用负载估计法计算[18]。当冷藏车负载为零时，正常行驶单位距离燃料消耗率为ρ0，当冷藏车满载时，正常行驶单位距离燃料消耗率为ρ*，车辆负载与燃油消耗率成一定线性关系，当冷藏车载有货物重量为M时，正常行驶单位距离燃油量如式(2)所示：

(2)

其中Q为车辆的最大载重量。

从客户点i到客户点j所消耗的燃油量如式(3)所示：

ρ(Qij)dij

(3)

ρ(Qij)为载有重量为Qij的冷藏车由客户点i直接行使到客户点j单位距离的油耗量，dij为客户点i到客户点j的距离，

当车辆完成对所有客户点的配送服务时，在整个配送过程的燃油消耗量可如式(4)：

(4)

整个配送过程中油耗成本可如式(5)所示：

C21=cfuel

(5)

其中c为油价。

由Ottmar[19]研究可得碳排放量与油耗量成一定线性关系，碳排放量=燃料消耗量×CO2排放系数。整个配送过程中的环境成本可如式(6)所示：

C22=νωfuel

(6)

其中ν为碳税，ω为碳排放系数。

因油耗成本与环境成本都与油耗量成一定线性关系，故冷藏车辆运输过程中的绿色成本可如式(7)所示：

C2=C21+C22=(c+νω)fuel=γfuel

(7)

其中γ为绿色成本系数。

(3)车辆配送过程中的制冷成本(C3)

冷藏车配送过程中的制冷成本通常是为了维持车箱内温度而消耗的制冷剂的成本[16](制冷中所消耗的油耗量已在绿色成本中计算，故在此不考虑制冷产生的油耗量)。制冷剂的消耗量与车辆在行驶过程中承受的热负荷、车辆的裂化程度、热传率、车厢收到太阳辐射的面积、车箱外温度、车厢内温度有关系。由于在假设(1)中配送中心所拥有的车辆为同一类型，车辆劣化程度及车厢参数均为一致且车辆在行驶过程中内外环境相对稳定，则在车辆运输过程中的制冷成本可近似看成与车辆运行时间正相关。又由于在车辆到达客户点之后的装卸过程中车厢门有且只打开一次即可完成配送服务，车厢体积一致，装卸阶段的制冷成本也可近似看成与时间成正相关，由假设(2)可知各个客户点的配送时间。故车辆运输过程中制冷成本可如式(8)所示：

(8)

(4)车辆配送过程中生鲜产品的货损成本(C4)

货损通常与生鲜产品本身以及配送中碰撞、配送的时间、配送的方式等有关，但冷链配送选用冷藏车来使产品处于适宜的环境中，对产品的保护性较好，所以仅考虑生鲜本身和配送时间推移影响下的货损。产生货损的原因主要分为以下两个方面：一是由于在配送过程中，由于根据时间的推移和货物积累而造成的货损；二是由于在装卸产品时，由于周围环境变化，如含氧量、温度变化造成生鲜产品损失。

本研究引入生鲜产品新鲜度衰减函数

θ(t)=θ0e-∂t

(9)

式(9)表示产品在一定温度下的腐化比例[20]。其中θ(t)为生鲜产品在时刻t时的新鲜程度，θ0为产品从配送中心出发时的新鲜程度，∂1为车辆在运输过程中生鲜产品的新鲜度衰减系数，∂2为车辆在装卸过程中产品的新鲜度衰减系数。新鲜度衰减系数∂通常与货物周围温度、含氧量有关，由于在装卸过程车厢门打开使车厢内温度、含氧量等产生巨大变化，产品新鲜度衰减速率变快，因此有∂2>∂1。所以综上车辆配送过程中生鲜产品货损成本的表达方式如下：

(10)

(11)

C4

(12)

其中式(10)为车辆配送阶段的货损成本，式(11)为车辆装卸阶段的货损成本，Qin为车辆离开客户点i时车上所剩余货物的重量。

(5)车辆配送过程中违反与客户约定时间窗的惩罚成本(C5)

客户会与配送中心约定一个时间窗(Ej,Lj)用于接收生鲜产品。Ej、Lj分别为客户点j能够接受配送车辆最早和最晚的到达时间，tj表示车辆k到达客户点j的时间点。客户点j可以接受不在时间窗内的服务，但是(假设(4))企业要为不遵守在约定时间内服务的行为付出罚金，整个配送过程中的惩罚成本可如式(13)所示：

(13)

其中ε1为配送车辆到达客户点的时间早于与客户约定时间窗上限的惩罚系数，ε2为配送车辆到达客户点的时间晚于与客户约定时间窗下限的惩罚系数。

4 构建冷链配送路径优化模型

基于以上描述，本研究构建冷链物流配送路径优化数学模型，如式(14)所示，建立以冷链物流车辆配送过程中的固定成本、绿色成本、制冷成本、生鲜产品的货损成本、违反与客户约定时间窗的惩罚成本总成本最小为目标函数的数学模型。

minZ=C1+C2+C3+C4+C5=

(14)

(15)

(16)

(17)

(18)

(19)

xijk,yik=0or1，∀k,i,j

(20)

(21)

tj=ti+Ti+tij,∀i,j

(22)

式(15)表示每一辆车的载重量都不超过车辆的最大载重量；式(16)表示每一个客户点只能够访问一次；式(17)表示车辆从配送中心出来后又返回到配送中心；式(18)、(19)表示对任意一个客户点只能允许车辆出发到达一次；式(20)为约束条件；式(21)的目的是消除子回路;式(22)表示为配送的连续性。

5 混合蚁群算法求解模型

蚁群算法因其具有正反馈性、鲁棒性强等优点在路径优化问题的到了广泛运用，但是没有规定道路上的信息素，所以在初始阶段由于信息素缺失盲目寻找使得收敛速度变慢[21]。为了缩短蚁群算法的搜索时间，加快收敛速度，本研究采用A*算法与其结合的方式。A*算法具有快速的全局搜索能力，在寻优时不遍历整个搜索空间 ,而是根据所选择的启发式函数朝着最有希望的方向前进，搜索速度快。两种算法形成优势互补，首先利用A*算法的全局收敛性、快速性对产生优化解对应的路径进行初始信息素分布，后充分利用蚁群算法的正反馈性以及求解效率高等优点寻找最优路径。

5.1 初始信息素的设置

A*算法的启发式函数为：

f(n)=g(n)+h(n)

(23)

其中f(n)为客户点n的估价函数，g(n)当前客户点n到配送中心的实际代价，h(n)当前客户点n到目标客户点的预估代价。为了保证研究的可行性，本研究将客户点之间的欧式距离当做客户点之间的配送距离(dij=dji)。g(n)表示第k辆车从配送中心到客户点n这一段路径的成本之和，如式(23)所示：

(24)

其中h(n)表示当前客户点距下一个选择客户点的成本值。将配送中心位置定为D，并把所有客户点放入open表中，调用上述启发函数，以配送中心为中心点出发,在open表中取估价函数值最小的客户点放入S[k]中，并在open表中删除此客户点，再以此客户点为中心，累计循环上述步骤，在循环中加入载重量约束，若超过车辆最大载重量，车辆返回配送中心，配送中心改派另一辆车为客户点配送，直到所有客户点的配送任务完成。此时从前往后连接各个车辆S[k]表中节点集，所生成的路径为优化解。并对此路径进行初始信息素进行赋值为τRbest=λτc，其中(λ>1)。其他路径的信息素设为τc。

具体步骤如下：

①对变量进行初始化，k=1，V为open表；

②初始化S[k]=φ,Q(k)=0，将a赋值为D；

③若V为空集，则转⑩结束，否则继续步骤④；

④调用启发式函数搜索从a点出发找到估价函数值最小的客户点i；

⑤判断，Q(k)=Q(k)+qi≤Qk若为真则转⑥，否则车辆返回配送中心转⑨；

⑥Q(k)=Q(k)+qi，a=i；

⑦将客户点i放入S[k]中，并从V中删除；

⑧返回步骤③；

⑨k=k+1转步骤②；

⑩结束。

其中车辆k所经历的客户点的集合为S[k]，S[k]中的元素的顺序，就是车辆k访问客户点的顺序。Qk为车辆k的最大载重，qi为每个客户点的需求量。

5.2 启发式因子设计

启发式因子为蚂蚁从客户点i转移到客户点j的期望，对于整个蚁群算法来说，启发式因子ηij是核心组成部分，也是蚂蚁选择下一个节点的关键。本文研究内容是为配送中心提供一种总成本最小的配送策略，只用距离作为启发式因子将影响最优配送策略。因此，本研究将启发式因子设计如(24)所示：

(25)

将总成本作为启发式因子分母的设计是为了车辆由客户点i选择下一个客户需求点j的期望是总成本，增大总成本小的客户点的转移概率，使车辆为总成本小的客户点优先配送。

5.3 移动概率选择规则

蚂蚁从客户点i通过一定的概率选择规则来选择下一个客户点j转移。传统的蚁群算法当中[22]，移动概率选择规则表示为式(25)所示：

(26)

式(25)中Jk(i)为蚂蚁k经过客户点i后可以选择的客户点的集合，α和β为两个参数值，分别表示蚂蚁在运动过程中所积累的信息和启发信息的重要程度。

为了防止算法陷入局部最优，避免过早陷入停滞状态，本研究引入一个事先设定的[0,1]之间的算法参数q0，当第k只蚂蚁选择下一个客户点时，算法将会产生一个[0,1]的随机数q1，通过这个随机数与q0相比来选择进行转移的下一个客户点。具体的选择公式如式(26)所示：

j

(27)

当q1≤q0时蚂蚁选取当时信息素和启发信息乘积最大的客户点；当q1>qo此时蚂蚁选择下一个点类似于遗传算法中轮盘赌的方法。

如果只是将q0设置为一个定值，那q0的取值对最后的结果影响较大。为了使蚁群算法更加适应搜索环境，本研究用本次迭代的最小成本与上一次迭代的最小成本之差与上次迭代的最小成本的比值将q0进行动态调整。当下一次迭代的最优解小于本次迭代的最优解时，说明下一次的迭代找到了比这次好的配送策略，q0值就会变大，将对此搜索区域加大搜索力度，相反，若下一次的迭代没有找到比这次好的配送策略，要为找到最优解扩大搜索范围,则q0的值就会变小。为避免几次迭代出现相同结果而导致的局部最优，为这种情况设置一个最大迭代次数Nmax，当连续停滞的次数num大于时Nmax，应减小q0值，使蚂蚁能够跳出局部加强其他区域的搜索范围。具体设置如式(27)所示：

(28)

5.4 信息素更新策略

为了使搜索过程更具有指导性，在所有蚂蚁都形成它们的路径之后，对所建立的路径进行全局更新，只有找到全局最优路径的蚂蚁所处的路径才会进行信息素的更新。更新规则为：

(29)

(30)

其中Q为经过最优路径蚂蚁留下的信息素总量，Lbest为当前总成本最小所对应的路径长度。

对当前最优路径的边(i,j)信息素更新规则为：

(31)

对不是最优路径的边(i,j)，更新规则为：

τij(t+n)=(1-ρ)τij(t)

(32)

ρ为信息素挥发因子。

6 实例求解与分析

为了验证算法的有效性，本文采用西安市某冷链物流有限公司提供的数据，该物流公司是一家专业的冷链物流服务企业，为门店、超市提供冷藏、冷冻等冷链服务。选取该物流公司服务的15家商超门店进行数据采集。该物流公司用载重量为3.7吨的冷藏车为15家商超门店低温配送鲜肉，冷藏车8点从配送中心出发，行驶速度为40公里/小时，鲜肉通过转运筐运输，每筐鲜肉10千克，冷藏温度在0-2℃。冷藏车的固定成本为150元，空载和满载正常行驶每公里耗油分别为0.18升和0.41升；车辆的运输和装卸阶段的制冷剂消耗系数分别为5元/小时和12元/小时，此过程中产品的新鲜度衰减系数分别为0.03和0.06。当前的鲜肉单价为18元/千克，柴油单价为5.41元/升，碳排放量为2.669千克/升，碳税为30元/吨。配送中心编号为0，各个客户门店的编号为1,2...，15。企业为配送车辆早于和晚于与客户约定时间窗到达的行为的罚金为50元/小时和100元/小时。客户点具体地址和需求量、需求时间如表1所示。

表1 各客户点的详细情况

6.1 结果分析

根据本文算法和实例数据对模型进行求解。将蚂蚁数量定为10，α=1，β=3，ρ=0.5，Nmax=5，λ=1.8，η=0.99,信息素总量为100，蚁群算法最大迭代次数为100，应用MATLAB编程求解，在个人计算机上运行10次的最优配送策略如图所示：

图1 车辆配送路线图

由图1可知，本研究模型算法是有效的，此时的配送策略为，从配送中心出发3辆车，第一辆按顺序为第8、13、11、10、12、6、15客户点服务，第二辆车为第1、4、5、2、9客户点服务，第三辆车为第3、7、14客户点服务，随后三辆车返回配送中心。此策略下配送总成本为1159元。

6.2 初始化信息素的蚁群算法与未初始化信息素的蚁群算法对比

将初始化信息的蚁群算法与未初始化信息素的蚁群算法进行对比，利用上述参数，将算法随机运行10次后的对比结果如表2所示：

表2 初始化信息素的对比结果

由表2可以看出，通过对蚁群算法初始化信息素后，减少了算法的收敛次数，加快了收敛速度。而且通过A*算法与蚁群算法的结合也对运行的结果进行了优化，降低了企业的配送成本，增加企业收益，有利于企业发展。

6.3 算法对比

为了进一步验证算法有效性，针对本文实例，假设蚂蚁数量为10，信息素总量为100，η=0.99，α=1，β=3，ρ=0.4,q0=0.6,迭代次数为100，初始化信息素倍数为1.8，对A*算法(A)、基本蚁群算法(B)、混合蚁群算法(C)进行6次随机试验，实验结果如表3所示。

最优结果见表4和表5。表4列出了各算法的最小配送成本以及相应的配送策略，表5给出了各算法在最小配送成本下的成本构成。

表3 实验对比结果

表4 各算法对应的最优配送策略

表5 各算法运行最优配送策略下的成本构成

从实验结果上来看，对于考虑节能减排的冷链物流路径优化问题中，本文提出的混合蚁群算法的结果优于A*算法和基本蚁群算法。配送总成本相较于A*算法、基本蚁群算法分别减少了约15.9%、8%。从最优结果中成本构成中看出，相比于原A*算法，混合蚁群算法由于利用了蚁群算法的正反馈性、并行性等优势对结果进行优化，成本降低明显，减少企业运营成本、有利于企业发展。而且由于绿色成本和货损成本的大幅度降低，节约资源、保护环境的同时保证了产品的质量。相比于基本蚁群算法虽然总成本降低不明显，但是混合蚁群算法得到的绿色成本和惩罚成本都低于基本蚁群算法，减少了环境资源的使用以及对环境造成的碳污染，节约资源、保护环境响应了绿色物流和可持续发展理念，同时违反时间窗的惩罚成本降低意味着配送准时率增高，提高了客户满意度。

7 结语

随着可持续发展理念的持续推进，绿色物流成为未来物流业发展的趋势。本文基于节能减排视角下，将节能减排转化为成本因素考虑进模型，在时间窗、客户需求、车辆载重等约束条件下建立以固定成本、绿色成本、制冷成本、生鲜产品的货损成本、违反与客户约定时间窗的惩罚成本总成本最小的路径优化模型。针对蚁群算法开始由于信息素不足而盲目搜索导致收敛速度慢的问题，结合A*算法初始化蚁群算法的信息素，缩短蚁群算法的收敛时间,提出了混合蚁群算法求解模型。为验证模型以及算法的有效性，采用实例对算法仿真并进行算法对比，通过结果可以看出算法和模型是有效的，可以为以后企业寻找发展和绿色物流概念的落实提供方法支持。