基于蚁群算法的低碳冷链物流配送路径优化

郑娟毅, 付姣姣, 程秀琦

(西安邮电大学 通信与信息工程学院， 陕西 西安 710121)

随着经济发展和人民生活水平的提高，人们对生鲜产品的需求不断增加，进而促使生鲜物流服务需求与日俱增。生鲜物流的核心是冷链配送环节[1],车辆路径(vehicle routing problem,VRP)问题是冷链物流服务的关键，其旨在满足约束条件下,选择最优的配送路线，完成对配送点运输服务[2]。在生鲜产品的物流配送过程中会产生大量碳排放，不仅会污染环境，而且会增加物流公司的配送成本，故合理减少配送过程中的碳排放值得关注。

对冷链物流路径的相关研究，大多采用遗传算法[3]和蚁群算法[4]进行求解。如文献[5]采用遗传算法研究冷链物流配送路径，但未考虑卸载时间带来的货物损坏问题；文献[6]基于改进混合遗传算法对冷链物流配送中心选址进行优化，但未考虑碳排放问题；文献[7]考虑碳排放因素，提出了一种采用遗传算法求解的城市配送车辆路径问题，但未考虑碳排放成本中碳税因素。通常遗传算法的计算量大，且具有早熟现象，容易过早收敛到局部最优解。相对而言，蚁群算法具有较强的鲁棒性且具有正反馈机制，更适合于研究车辆路径问题。如文献[8]采用蚁群算法求解生鲜农产品冷链物流低碳配送路径，但未考虑货损成本中的卸载时间因素。文献[9]将细菌觅食-蚁群算法用于求解冷链低碳物流配送路径模型，但在计算货损成本时没有考虑卸载时间，且在总成本中未考虑时间惩罚成本。

根据生鲜产品冷链物流的特性及成本，本文拟提出一种基于蚁群算法的低碳冷链物流配送路径优化方法。首先，在考虑生鲜产品冷链物流的运输成本、固定成本、制冷成本和时间惩罚成本的同时，引入行驶距离、车载量的碳排放成本和因卸载时间差异引起生鲜产品损坏的成本来构建数学模型。其次，对蚁群算法进行改进，在状态转移概率中引入负荷因子，在全局信息素更新策略中引入向导策略,并采用非线性方式对达到一定迭代次数要求的信息素总量进行自适应调整。最后，利用改进后的蚁群算法对所建立的低碳冷链物流配送模型求解，以期实现冷链物流的低碳配送路径优化。

1 蚁群算法

蚁群算法是一种路径寻优智能算法[10]。算法中蚂蚁以较大概率选择信息素浓度高的路径并释放一定量的信息素，增强该路径上的信息素浓度，形成一个正反馈，最终蚂蚁会找到觅食路径中的最短路径。对基本蚁群算法做如下描述。

1)设蚁群数量为m，节点i和节点j间的距离为dij,t时刻路径(i,j)的信息素浓度为τij。

2)每只蚂蚁的爬行方向由信息素浓度确定，用禁忌表存储在i节点的所有蚂蚁下一步行动节点集合。

3)在路径搜索过程中，通过状态转移概率公式计算蚂蚁选择下一节点的概率。

蚂蚁根据每条路径上的信息素浓度选择下一个觅食点，假设蚂蚁k在t时刻从节点i出发以一定概率选择节点j的状态转移概率[10]表达式为

其中：τij表示i,j节点间信息素浓度；ηij表示i,j节点间距离的启发信息；α表示信息素所占的比重；β表示启发因子；Ak表示处于节点k的蚂蚁 下一步选择访问的节点集合。

4)当蚂蚁完成一次遍历，对路径上的信息素浓度进行调整。t+1时刻信息素浓度更新[10]公式为

τij(t+1)=(1-ρ)τij(t)+Δτij(t,t+1)。

其中：Δτij(t,t+1)表示在(t,t+1)时段内，所有蚂蚁在路径(i,j)上的信息素增量；ρ为信息素挥发系数，其大小影响路径规划效率，ρ越大，算法的全局搜索能力越强，但收敛速度越慢；ρ越小，收敛速度越快，但全局搜索能力越弱。

5)当搜索次数达到最大时，找到最短路径。

2 冷链物流模型的建立

2.1 基本假设

假定配送中心能够合理安排服务车辆和配送路线，使得配送成本达到最低，需要满足的条件如下：

1)只有1个配送中心，且配送中心和多个配送点的位置坐标已知。

2)配送车辆从配送中心出发后必须返回配送中心。

3)配送车辆类型一致，每辆车的车载量尽量达到满载，但不能超过车容量限制。

4)车辆只进行送货服务，不涉及取货服务。

基于以上假设，本文研究的生鲜农产品冷链服务配送问题可以描述为：在满足目标函数最优的情况下，仅有一个生鲜农产品配送中心通过冷藏货车进行冷链服务配送。

2.2 模型建立

由于配送货物为生鲜产品，因此在数学建模时要考虑冷藏车辆运输成本、固定成本、制冷成本、货物运输过程中的损坏成本、运输车辆的时间惩罚成本以及碳排放成本等多重目标。

1)运输成本

运输成本通常与配送产品价格和配送车辆的耗油因素相关，车辆行驶的距离越长配送成本越高。设运输成本为

其中：k=1,2,…,m表示车辆数；i,j=1,2,…,n分别表示配送点；dij表示配送点i,j之间的距离；w1表示产品价格；xijk表示与车辆k运输成本相关的配送状态系数，xijk=1表示车辆k完成从配送点i到j配送，xijk=0表示车辆k未完成配送。

2)固定成本

冷链服务固定成本是一个定值，通常与驾驶司机的工资和配送车辆损耗因素相关，设固定成本为

其中ck表示第k辆车的固定配送成本。

3)制冷成本

制冷的主要目的是保持一个恒定温度来保证生鲜产品的新鲜度。设制冷成本主要包括配送车辆在运输过程中为保证车厢温度恒定所产生的成本E31、配送车辆早到等待的成本E32和配送车辆迟到的成本E33，则制冷成本为

E3=E31+E32+E33。

其中

式中：s表示每小时车辆的制冷成本；[Ei,Li]表示配送点i的配送时间窗，Ei表示最早可接受时间，Li表示最迟可接受时间；Ti表示对配送点i的实际配送完成时间。

4)货物损坏成本

冷链服务的货物是生鲜产品，容易受到空气温度、氧气浓度和卸载时间等因素的影响。本文主要从温度和卸载时间两个因素进行分析。配送过程中，农产品的温度会发生变化，导致产品的质量下降，出现货物损坏成本。

假设在运输过程中冷藏车温度不变，生鲜产品的腐烂率λ1为一个定值，则运输过程产生的货损成本为E41；当配送车辆到达配送点进行货物卸载时，需要打开车门，致使生鲜产品所处温度发生变化，腐烂率会随着温度的增加而变大，设腐烂率变为λ2(λ2>λ1)，并且卸载时间Tx越长货物损坏情况越严重，令卸载过程产生的货损成本为E42。则货物损坏成本可以表示为

5)时间惩罚成本

配送时间惩罚成本与配送车辆是否满足配送点时间窗有关，当配送车辆在配送点所需时间窗之前到来时，产生早到等待的损失费用E51；当配送车辆在配送点所需时间窗之后到来，产生延迟惩罚费用E52。则时间惩罚成本为

其中：w2表示单位时间等待成本；w3表示单位时间延迟成本。

6)碳排放成本

碳排放成本主要是指在冷链物流中冷藏车辆产生的碳排放量成本。碳排放量为耗燃量与CO2排放系数[11]之积。车辆的油耗与车辆的载重量和行驶距离有关，运输车辆单位距离耗油量与车载量的关系[12]可以表示为

其中：ρ0表示运输车辆空载时单位距离油耗；ρ*表示运输车辆满载时单位距离油耗；D表示车满载量；vij表示车辆在配送点i到配送点j之间的货运量。

则碳排放成本为

其中：θ表示碳税；w4表示碳排放系数。

综上所述，物流冷链服务的目标函数为

minE=E1+E2+E3+E4+E5+E6。

(1)

约束条件为

(2)

(3)

(4)

(5)

Ti+ti+t′+tij=Tj,

(6)

(7)

其中：ti表示在配送点i的等待时间；t′表示卸载时间；tij表示从配送点i到配送点j的运行时间；Tj表示车辆从配送中心经配送点i到配送点j的时间；xi0k表示车辆k从配送中心出发到达节点i；xojk表示车辆k从节点j返回配送中心。

式(1)是冷链物流配送所需费用最低的目标函数，其中配送所需费用与路径成正比例关系；式(2)-(3)保证每个配送点仅有一辆车进行配送服务；式(4)保证每辆车的负荷量不超过其自身最大负荷量；式(5)保证每辆车的轨迹路线必须为一个闭环，且每辆车必须从配送中心出发；式(6)保证满足配送点时间窗要求。

3 改进算法的物流配送优化

3.1 算法流程

改进算法的思想是将模拟退火算法[13]得到的解作为蚁群算法的初始解，然后采用邻域算法[14]对蚁群算法得到的路径进行交换得到一个新的路径，并对蚁群算法和邻域算法相应路径的值进行比较获得全局最优解。改进算法流程如图1所示。

图1 改进算法流程

首先对模拟退火参数初始化，将模拟退火算法得到的解作为蚁群算法的初始信息素，并对参数进行初始化。将各个蚂蚁放在配送中心，根据改进后的状态转移规律选择下一个节点，得到当前最优解。在当前最优解的邻域中通过邻域算法的交换方式找到另一个解，比较2个解的大小，并判断是否接受新解作为当前解。对路径上的信息素浓度进行更新。判断是否达到最大迭代次数，若达到输出最优解，否则继续循环。

3.2 利用模拟退火算法调整初始解

模拟退火算法的冷却过程[13]可以表示为

Ta+1=hTa,a=1,2,…,A-1。

其中：Ta表示第a次迭代的温度；h表示降温系数；A表示模拟退火算法的总迭代次数。

模拟退火算法的冷却过程容易受降温系数的影响，降温系数较小，搜索的最优解精度低，收敛速度快；降温系数较大，收敛速度慢，算法求解精度高。为了提高算法的求解精度和收敛速度，本文对降温过程进行自适应调整。在冷却过程引入回火机制，即自行设置回温过程，以较高的概率选择所有解集里较差的解重新加入最新解集，避免算法陷入局部最优。将回火温度设置为区间[T1,T2]，当温度T下降到T1时，回火机制立即将其回升到T2。设置最大回火次数G，当回火次数Gs达到最大回火次数即停止回火。

3.3 利用状态转移概率选择配送点

状态转移概率是蚂蚁选择下一节点的关键步骤，直接影响算法的求解速度和精度。一方面，考虑车载量的影响，将生鲜产品的需求量引入到状态转移概率中，使得在选择下一节点时会考虑油耗量。另一方面，物流配送需要考虑交通拥堵的情况，引入交通工程学中的道路阻抗系数。

假设有m辆车n个配送点，每辆车从配送中心出发，在t时刻以一定概率选择下一个配送点，此时状态转移概率可以表示为

(8)

其中：λij表示路径(i,j)的道路阻抗系数；q表示在单位时间内通过路径(i,j)的车辆数；y表示单位时间内车辆的成本；e和b为阻滞系数，e∈(0.1,0,2),b∈(1,4)。

为了避免出现停滞现象，本文采用蚁群系统[15](ant colony system, ACS)的状态转移概率，其公式为

(9)

其中：q0是设定的阈值；q∈[0,1]为随机值，当q>q0时采用式(8)进行搜索。

3.4 采用信息素更新策略调整信息素浓度

为避免蚁群算法在完成一次遍历后过早收敛于局部最优解，在全局信息素更新策略中引入向导因子，动态地更新全局信息素。算法初期每条路径上的信息素浓度较低，此时向导因子应该较小，保证所有蚂蚁以一个公平的概率去选择下一个觅食点，不易陷入局部最优；随着路径上的信息素浓度逐渐增加，向导因子应相应增大，加快全局收敛速度。第t+1时刻的全局信息素表达式为

τij(t+1)=(1-ρ)τij(t)+
Δτij(t,t+1)δ,

(10)

(11)

其中：di表示配送中心到节点i的距离；dj表示节点j到配送中心的距离；Lbest表示当前循环次数中最优解的路径长度。

3.5 利用邻域算法优化最优解

为提高算法收敛速度，利用邻域算法[14]对蚁群算法每次迭代产生的可行解进行优化。寻找邻域解有插入、逆转和交换三种方式。本文采用交换方式寻找邻域解，即首先获得蚁群算法每一次迭代产生的解，然后在得到解的路径中随机选择第n1、n2次访问的配送点交换两者的位置，进行随机扰动并重新计算得到新解。若新解优于原解，则更新解，否则保持不变。重复上述操作，直到达到最大迭代次数时获取最优解。

4 仿真结果及分析

为验证算法和模型的性能，利用实际冷链物流配送数据和Solomon标准算例进行验证，分别设置模型参数和算法参数如下。

将模型参数设置为生鲜产品价格w1=3 000 元/吨，单位时间等待成本w2=150 元/小时，单位时间延迟成本w3=200 元/小时，配送车辆最大载重量D=10 吨，配送车辆运行固定成本c=70 元，运输途中的单位货损成本P=5 元/千米，运输中的腐坏率λ1=0.02，卸货中的腐坏率λ2=0.04，制冷成本s=200 元/小时，空载油耗ρ0=1 升/千米，满载油耗ρ*=2 升/千米，碳排放系数w4=2.61 千克/升，碳税θ=20 元/千克。

将算法参数选择为信息素重要程度α=1，启发因子β=1，信息素挥发系数ρ=0.95，蚂蚁数量m=30，最大迭代次数umax=100，信息素释放总量为100，回火温度设置为[500,1000]，降温系数h=0.9，最大回火次数G=4，阻滞系数e,b分别取值0.15和3，采用交换方式寻找邻域解。

在Window10操作系统和Matlab2016a的运行环境中，进行仿真验证。

采用西安市某市场生鲜供应商的实际冷链配送数据验证算法。该供应商为西安市区24个配送点实施冷链配送。已知各个配送点的需求量和时间窗要求，算法运行结果如图2所示。其中0代表配送中心。

(a) 实际地图中的配送点位置

(b) 各个配送点位置的坐标点

(c) 算法的路径

(d) 算法的迭代次数与最低成本图2 算法运行结果

由图2可知，迭代次数为15时，本文算法趋于稳定，最优值为3 143元。

为证明算法的有效性和稳定性，选用Solomon算例中21组数据，结合冷链物流配送过程进行实验分析。将本文算法、标准蚁群算法和文献[16]的遗传算法进行比较，其结果如图3所示。

图3 3种算法的仿真结果对比

由图3可知，本文算法在迭代次数为15时趋于稳定，最优值为2 125元；文献[16]的算法迭代次数为26时趋于稳定，最优值为2 168元；标准蚁群算法迭代次数为42时趋于稳定，最优值为2 178元。本文算法的最优值与收敛速度相比于文献[16]的算法和标准蚁群算法均有一定的改进。这是因为，在蚂蚁数量大的环境中，标准蚁群算法容易陷入局部最优。同时，由于其搜索路径复杂，会造成搜索次数增多，收敛速度不稳定等问题。文献[16]算法具有早熟现象，影响算法收敛速度。而本文算法的收敛速度和解的质量之所以高于其他两种算法，是因为引入模拟退火算法和在状态转移概率中引入蚁群系统，提高了解的质量；对达到一定迭代次数要求的信息素总量采用非线性方式进行自适应调整，提高了收敛速度。

5 结语

针对冷链物流车辆路径问题，建立了包含冷链配送服务的固定成本、运输成本、货物损坏成本、制冷成本、时间惩罚成本和碳排放成本在内的冷链物流车辆路径模型。对标准蚁群算法的状态转移概率和全局信息素更新策略进行改进。利用改进后的蚁群算法求解冷链物流最优车辆路径。仿真结果表明，相比于遗传算法和标准蚁群算法，改进的算法可以提高解的质量和算法的收敛速度，能够应用到冷链物流配送中。