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

陈 静，刘玒玒

(西安财经大学 管理学院，陕西 西安 710000)

近年来，我国冷链物流发展迅速，规模逐渐增长，2017—2020年，国家一直在强调建设冷链物流体系的必要性。随着相关政策密集化、系列化的出台，表明生鲜农产品冷链物流产业作为保障食品和民生安全的重要手段，已深度融入到各产业链的核心环节，整个生鲜农产品冷链产业的价值和地位愈发凸显[1]。虽然物流规模一直在增大，但不得不承认中国的冷链物流市场与美国、日本等国家相比，差距仍较大。其中，美国、日本的冷链发展已趋于成熟，渗透率在95%～99%之间，而且冷藏运输率已超过90%(数据来源中物联冷链委)。冷链物流作为国民经济发展的支撑力量，其基础设施建设还需进一步研究规划。基于此，针对冷链配送环节，综合考虑运输成本、制冷成本、损坏成本及绿色低碳成本，运用蚁群算法建立路径最优模型，减少配送成本，保持生鲜产品的新鲜度，提高顾客体验感[2]。

车辆路径问题(Vehicle Routing Problem， VRP)最早由Dantzig和Ramser在1959年首次提出[3]，传统的车辆路径问题，可理解为多辆车从一个点出发，对多个地理位置的客户提供产品运输服务，完成顾客需求，并在业务完成之后返回原点，同时实现运输车辆行驶距离最短、运输时间短、耗油量小、碳排放小等目的。

近年来，随着冷链物流的高速发展[4]，各国学者对其研究也越来越多，提出诸多冷链物流配送方案。段风华等[5]通过使用最佳插入和交换领域的禁忌搜索算法，求解基于碳排放和不同类型车辆的路径优化问题，根据使用车辆的碳排放系数和小车优先策略，按照实际情况及算法的初始解，确定最终的最优路径方案，使得车辆行驶成本和碳排放成本均有较大幅度下降。禁忌搜索算法实际上是基于邻域搜索算法的一个拓展，Demir等[6]在污染车辆路径问题中，建立车辆消耗燃料及整个路程行驶时间最短的两重目标函数及车辆路径优化模型，并应用改进的领域禁忌搜索算法求解。Brito 等[7]在带有时间窗的车辆路径研究中，运用混合蚁群算法结合模糊约束条件进行求解。Dearmas和Melián[8]使用启发式算法解决多目标车辆路径问题。Ding等[9]通过调整信息素对蚁群算法进行改进，研究带有时间窗的路径问题。Bozorgi等[10]将碳排放因素纳入到路径问题研究中，探索在碳排放和成本双重因素下的最优路径问题。向敏等[11]提出电子商务虽然加速了新鲜农产品的发展，但不可否认的是配送成本较高，制约了鲜活农产品的进一步发展，考虑到高效配送问题，提出利用改进的遗传算法减少物流配送成本。潘茜茜等[12]在普通冷链物流成本研究中加入碳排放成本，建立以碳排放为基础的数学模型，采用蚁群算法进行实证。姚臻等[13]提出以时间窗、客户满意度、碳排放为约束条件，建立以碳排放量为基础的总成本最小目标函数，并应用遗传算法求解数学模型，得出考虑碳排放成本不仅不会增加总成本、反而会约束碳排放量的结论，符合国家提出的绿色发展概念。胡玉晶等[14]通过分析BDS/GIS协同作业原理，建立基于此的车辆调度系统模型，并考虑交通路况对物流配送路径的实时影响，从而确定最优配送路径。缪小红等[15]在货物重量不超载的情况下，提出一个配送中心、多个顾客的数学模型，并运用改进遗传算法进行分析，得到最优配送路线。方文婷等[16]为践行绿色低碳的发展目标，将碳排放的绿色成本引入到路径最优化中，建立总成本最小的目标数学模型，采用A*算法和蚁群算法相结合，运用MATLAB软件进行仿真实验，得出最优路径。邓红星等[17]构建基于随机需求和软时间窗的最小配送成本函数模型，利用改进遗传算法进行求解。陈淑芳[18]针对农产品小批量、多批次的配送特点，应用联合配送策略解决多个配送中心及低车辆装载率问题。

但上述研究仍存在不足之处，虽然都建立了相应的成本最小数学模型，并应用多种算法确定最优路径，进而确定相应配送成本，但大都是一个配送中心、多个客户及多辆冷藏配送车，不符合当前几公里范围内就建立配送中心的实际情况。文中采用最近距离分配法确定多配送中心的冷链车辆调度问题，并采用蚁群算法，确认最优配送路径。

1 冷链物流成本模型

1.1 问题描述

生鲜农产品配送模型是一种以冷链为基础的物流配送问题。在一定区域内，存在多个配送中心、多个客户及多辆配送冷藏车，在合理的车辆安排及约束条件下，把货物从配送中心送到顾客手中。优化目标是依据客户的需求点情况，构建数学模型，采用合适算法，寻找最佳配送策略：从确定的配送中心出发，安排冷藏车的装车规模和行驶路线，使冷藏车在从配送中心出发直至完成沿线所有服务过程中，发生的运输成本、制冷成本、损坏成本及绿色低碳成本等总成本最小。如图1所示。

图1 冷链物流配送

基本假设条件：

1)已知每个配送中心的地理位置坐标，且不存在车辆不足问题；

2)每个顾客需求量确定，且货物可以在满足车载条件下混装，每位顾客的货物只能由一辆冷藏车运输；

3)冷藏车有重量限制，并且由配送中心出发，最终回到起点；

4)配送中心到顾客的距离及顾客到顾客的距离通过坐标计算得到，为已知条件;

5)每个配送方案所需路程总长度不大于配送车辆每箱油的最大行驶路程。

1.2 参数说明

在整个模型中，M为配送中心；V={1,2,3,…,n}为客户的节点集合，i和j为客户点；k为车辆序号，m为车辆总数；D为冷链物流总成本；Ck为第k辆车的固定费用；p为运输冷藏车辆所使用柴油的单价;q为每公里耗油量;dijk为第k辆车由客户i点到达客户j点距离;a1为车辆在行驶过程中的制冷系数;t1为冷藏车运行途中经历的时间;v为匀速行驶速度；a2为卸货过程中制冷系数;t2为打开车厢门的时间;b1为货物在匀速行驶过程中新鲜度损坏系数;b2为打开车厢门，货物与外界接触时新鲜度损坏系数;r为碳税;f为碳排放系数;gi为客户i的需求量;T为冷藏车最大车载量。

1.3 多目标数学模型的建立

由于配送货物为生鲜农产品，需要冷链物流进行配送，因此，在建立模型时要考虑冷藏车辆运输成本、制冷成本、生鲜农产品损坏成本以及绿色低碳成本等多重目标成本。

1.3.1 决策变量分析

为便于模型分析冷链物流成本，假设配送中心为M1，M2，M3，…，客户需求点为(Vi，Vj)(i，j=1，2，3，…，n)，决策变量Xijk=1为第k辆车由客户i点到达客户j点，Xijk=0为第k辆车未出发。

1.3.2 成本变量分析

1)运输成本分析

车辆行驶过程中的运输成本由固定成本和变动成本组成，固定成本D11通常为司机固定工资、福利、车辆保险及定期维修费用等其他费用。

(1)

变动成本D12与冷藏车辆油耗量q、使用燃料单价p及行驶距离dijk有关。

(2)

因此,运输成本为

D1=D11+D12

(3)

2)制冷成本分析

(4)

(5)

冷藏车的制冷成本通常是为了保持生鲜农产品的质量而付出的成本，通常与冷藏车的型号、空间、质量、种类、车厢内外温度等因素有关。为简化计算，前文已经假设产品种类相差不大、统一车辆，且处于室外温度恒温的状态下，所以，文中只考虑冷藏车匀速行驶时间段车厢关闭及卸货时间的制冷成本。车厢行驶过程中的制冷成本与制冷系数a1、运输时间t1有关；卸货时间的制冷成本与制冷系数a2、开门时间t2有关，并且假设卸货时间段只打开车厢一次，不存在多次关闭现象，为计算简便，假设打开车厢时间t2为0.2 h。

3)生鲜农产品损坏成本分析

(6)

生鲜农产品的损坏成本通常与货物包装、货物与货物碰撞、车厢温度、货物本身随时间推移的损坏程度、与外界高温接触的损坏程度等因素有关。文中的成本假设条件是车厢内温度恒定、货物几乎不存在由碰撞产生的货损成本，因此，损坏成本与行驶运输途中的损坏系数b1、打开车厢的损坏系数b2及时间t1和t2有关。

4)绿色低碳成本分析

(7)

文中的绿色低碳成本是指运输过程中因使用冷藏车而产生的CO2排放量，这部分成本是企业承担的环境成本，与碳税r、碳排放系数f及耗油量q相关。

综上所述，文中建立的成本数学模型为

minD=D1+D2+D3+D4

(8)

约束条件

(9)

(10)

(11)

(12)

(13)

(14)

式(9)为车辆由客户点i到达客户点j；式(10)为车辆未出发；式(11)、式(12)为车辆只允许出发和到达一次；式(13)为车载量不允许超过冷藏车最大车载量；式(14)为车辆从配送中心出发，最终回到配送中心。

2 蚁群算法模型求解

以生鲜农产品配送的总成本最小为目标，建立4重目标数学模型，并应用蚁群算法寻找最优配送路径。蚁群算法[19-20]在影响因素和约束条件较多的情况下，具有较好的鲁棒性，具有搜索时间快、效率高的特点。蚁群算法是一种随机搜索算法，模仿蚁群觅食行为，寻找最短路径，在车辆调度问题中应用广泛，且后期被优化应用于集成电路设计、任务分配、通信网络等领域。因此，文中使用蚁群算法求解多配送中心的冷链物流路径优化问题。

2.1 确定配送中心问题的描述

对于多配送中心问题，如果物流配送方根据传统方式确定配送中心，会造成资源无法共享，配送路径只能达到局部最优效果。为更好地规划物流配送路径，节约成本，建立了一个虚拟车场，用来停放冷藏车，并假设配送中心和车场之间的往返不产生任何费用，距离为0。确定配送中心以后，对需求点进行分类汇总，将需求点分别放入属于每一个配送中心的集合中，冷藏车完成任务后，回到配送中心后再回到车场(见图2)。

图2 多配送中心联合配送方式

图2中编号1、2、3表示配送中心，编号0表示车场，编号4、5、6、7、8、9、10表示客户需求点。以图2 为例，按照最近距离分配法将车场和配送中心匹配，得到配送路线为：0-1-4-5-3-0-1-10-9-8-2-7-6-2-0；车场和配送中心距离为0，在图2中用虚线表示，可以得到最终实际配送路线为：1-4-5-3，1-10-9-8-2，2-7-6-2。

2.2 蚁群算法

(15)

式中：α为蚂蚁残留在路径上的信息素对后面蚂蚁选择此路径的影响大小；β为启发因子，为可预见度对蚂蚁选择下一路径的影响程度；Jk(i)为蚂蚁下一步选择客户的坐标点；τij(t)为信息素浓度；ηij(t)为蚂蚁在t时刻从客户点i到客户点j的期望程度。

当所有蚂蚁完成一次迭代后，采用2-opt的方法对最优解进行更新。根据转移概率确定的路线，每2个需求点进行交换，计算新路径的长度，与交换前相比，如果优化就更新路径，否则，路径不变,并对各个路径上的信息素进行更新。

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

(16)

式中：ρ为信息挥发系数，在0～1之间，Δτij为信息素增量，考虑到蚁群算法全局收敛性和搜索能力，文中的算法模型为

(17)

式中：Q为常数，表示信息素强度；Lk为蚂蚁k在本次迭代中经过的需求点长度。

2.3 算法基本步骤

1)初始化各个参数。设开始时间t=0，NC(迭代次数)=0,选取最大迭代次数NC=200，每条路径上的信息素浓度为τij(t)=C(C为常数)。设置α，β，ρ的初值，蚂蚁数量为m，初始时刻的Δτij(t)为0。

2)在禁忌表中设置s等于1，并将其各自起点放置到各自禁忌表中。

3)判断禁忌表是否已满。

5)计算所有蚂蚁走过的周游长度Lk，更新当前的最优路径。

7)终止条件是否满足，满足输出最优路径，否则返回步骤2)。

3 仿真实验

3.1 案例概述

为验证算法的有效性，选取西安市某冷链物流公司数据进行仿真实验。该物流公司为顾客配送生鲜农产品服务，选取22家小型超市售卖点进行数据采集。配送冷藏车载重为9 t，容积为10 m3，冷藏车每天5:00从各个配送中心出发，匀速行驶速度为35 km/h，冷藏温度为0～3 ℃。使用一辆冷藏车的固定成本为300元，平均每公里耗油量0.5 L。冷藏车在运输途中的制冷成本为8元/h，卸载货物的制冷消耗成本为15元/h。货物在运输过程中的损坏成本为8元/h，卸载过程的损坏成本为12元/h。柴油单价为5.07元/L，碳排放量2.63 kg/L，碳税35元/t。应用最近距离分配法，得出配送中心编号为8和10。顾客的具体坐标、需求量和货物容积量如表1所示。

表1 客户点坐标

3.2 数值仿真实验分析

在Windows10 Intel(R) Core(TM) i5-1035G1 CPU@1.00 GHz环境下，利用MATLAB R2016a软件进行仿真计算。设置各个参数：m=35，NC=200，α=1，β=3，Q=15，ρ=0.4。经过10次仿真实验，得出最佳路径为39.06 km，全部统计结果如表2、图3、图4所示。

图4 最优路径长度变化

从表2、图3可以看出，最优路径为第7次计算结果：本次仿真结果利用最近距离分配法确定需求点8和10为配送中心，需求点8所需产品由路径4进行配送，需求点10所需产品由路径2进行配送。路径1：10-9-15-18-22-16-10，运输距离7.41 km，运输量为8.4 t；路径2：10-2-4-20-1-10，运输距离6.24 km，运输量7.8 t；路径3：10-6-14-17-12-11-3-10，运输距离14.94 km，运输量6.5 t；路径4：8-7-19-13-21-5-8，运输距离10.47 km，运输量8 t。从图4可以看出，当迭代为10次时，最优路径长度已趋于稳定。

表2 10次路径距离计算结果

图3 路径最优配送

由于在应用蚁群算法时，各参数选取会对最优路径起到决定性作用，因此，针对m，α，β，ρ进行一些参数变化，探讨其对最终结果的影响程度。

不同蚂蚁数量的仿真结果如表3所示，蚂蚁数量越多，得到的最优距离越短，当蚂蚁数量选取为客户点数量的1.5倍时，能够得出最优解。通过表4中参数的不同取值变化，可看出适当选取参数值有利于得出最优距离，因此，针对不同的现实问题，应根据实际情况选取相应的参数数值。经过数次仿真模拟，得出较优组合为m=35，α=1，β=3，ρ=0.4，此时最优路径距离为39.06 km，需使用4辆车，整个过程的成本为1 437.48元。

表3 m数值变化对仿真结果影响

表4 α，β，ρ数值变化对仿真结果影响

3.3 算法鲁棒性测试

为验证本研究设计算法的鲁棒性，将客户21的坐标改为(0，-2)，新的客户坐标点与表1类似，未列出。再次使用原代码运行程序，可得到以下结果：最佳运输总距离为39.76 km，配送中心更改为编号7和10，需要5辆冷藏车，各辆车的行驶路线如下：路径1：10-2-20-4-21-10；路径2：10-9-15-18-22-10；路径3：10-1-3-11-12-17-14-10；路径4：10-16-6-10；路径5：7-8-5-13-19-7。从以上结果可以看出，更改一个客户坐标，配送中心和最佳配送路径都会发生变化，说明本研究设计的蚁群算法可根据不同情况规划最优路线，具有较好的鲁棒性。新配送路径线路如图5所示。

图5 鲁棒性测试路径最优配送

3.4 算法高效性测试

此外，为证明选取的蚁群算法在路径优化方面具有较好优势，选取具有代表性的禁忌搜索算法和遗传算法[21]。对选取的案例进行算法求解，遗传算法和禁忌搜索算法都采用最基本的算法结构进行实际编程，以上2种算法与蚁群算法的最优解比较如表5所示。

表5 3种算法最优解比较

从表5可以看出，虽然蚁群算法运行时间不是最短，但规划的路径行驶距离却最短，在节约配送成本方面也最优，这就证明蚁群算法在解决多配送中心冷链物流配送路径方面具有优势，使用该算法可有效解决物流配送路径的成本问题。

4 结 论

随着低碳环保、可持续发展理念的持续深入，从物流配送路径优化问题出发，结合加快终端生鲜农产品物流配送速度及保证产品质量目的，考虑建立以运输成本、制冷成本、损坏成本及绿色低碳成本为目标的总成本最小路径优化模型。采用蚁群算法对多配送中心的生鲜农产品进行研究，通过局部优化处理，提升算法的适应性，以期能够更快、更有效地对车辆调度问题进行优化处理。为验证算法相对于其他算法的优势，通过MATLAB仿真可以看出：采用蚁群算法能有效规划“最后一公里”物流配送路径，节约成本，提高服务质量，保证生鲜农产品新鲜度，为物流企业寻求高效发展提供方法。