欢迎您访问《智慧农业(中英文)》官方网站! English
智能管理与控制

时变多车型下的生鲜农产品配送路径优化模型

  • 刘思远 , 1, 2 ,
  • 陈天恩 , 2 ,
  • 陈栋 2 ,
  • 张驰 2 ,
  • 王聪 2
展开
  • 1. 广西大学 计算机与电子信息学院,广西 南宁 530004
  • 2. 国家农业信息化工程技术研究中心,北京 100097
陈天恩(1978-),男,博士,研究员,研究方向为农产品供应链全过程的物联网数据感知、处理和分析技术。电话:18611694863。E-mail:

刘思远(1997-),男,硕士研究生,研究方向为供应链配送路径优化。E-mail:

收稿日期: 2021-08-06

  修回日期: 2021-09-15

  网络出版日期: 2021-07-07

基金资助

北京市科技计划课题(Z191100004019007)

Time-Varying Heterotypic-Vehicle Cold Chain Logistics Distribution Path Optimization Model

  • LIU Siyuan , 1, 2 ,
  • CHEN Tian'en , 2 ,
  • CHEN Dong 2 ,
  • ZHANG Chi 2 ,
  • WANG Cong 2
Expand
  • 1. School of Computer, Electronics & Information, Guangxi University, Nanning 530004, China
  • 2. National Engineering Research Center for Information Technology in Agriculture(NERCITA), Beijing 10097, China

Received date: 2021-08-06

  Revised date: 2021-09-15

  Online published: 2021-07-07

本文亮点

针对农业供应链的运输环节中生鲜农产品配送模型存在的速度恒定、碳排放计算方法单一的问题,本研究结合路网时变特征和新的多车型碳排放计算方法,提出了考虑配送距离、多车型碳排放量、货物损耗和车辆固定成本等4个优化目标的生鲜农产品配送路径优化模型;并根据模型特点提出了一种改进的双策略种群协同蚁群算法(Double-Strategies Co-Evolutionary Ant Colony System,DC-ACS )。利用改进蚁群算法对Solomon数据集的C105算例进行了求解,在4个优化目标上分别取得最优解为937.94 km、4961.48元、4081.78元和7500.87元,证明了本研究提出的模型的有效性。在模型有效的基础上,通过试验结果证明,改进蚁群算法比基本蚁群算法在4个优化目标上的配送总成本平均降低幅度超过14%,证明改进蚁群算法更具有优越性。使用改进蚁群算法对集中、随机和混合3种不同分布的大规模算例进行求解,3种分布上分别求得最优总成本为19,939.53、24,095.00和24,397.58元。综上所述,所提模型和算法可以为冷链物流企业的城市配送路径决策提供良好的参考依据,对完善智慧农业供应链的配送路径优化模型和优化方法提供了新的思路,为企业进一步扩大规模提供了参考。

本文引用格式

刘思远 , 陈天恩 , 陈栋 , 张驰 , 王聪 . 时变多车型下的生鲜农产品配送路径优化模型[J]. 智慧农业, 2021 , 3(3) : 139 -151 . DOI: 10.12133/j.smartag.2021.3.3.202108-SA004

Highlights

In view of the problems of constant speed and single carbon emission calculation method in the distribution model of fresh agricultural products in the transportation link of agricultural supply chain, combined with the time-varying characteristics of road network and the new multi vehicle carbon emission calculation method, this study put forward the distribution route optimization model of fresh agricultural products with four optimization objectives, which were the distribution distance, multi vehicle carbon emission, goods loss and vehicle fixed cost. In this model, the calculation of fuel consumption and carbon emission in the model would be affected by many factors, among which the load is the most important factor: Firstly, the average fuel consumption per 100 km of different trucks was calculated, then the CO2 emission factors of various trucks were calculated according to the carbon balance principle, and finally the average value of the results of each truck was taken as the carbon emission factor of the vehicle. According to those characteristics of the model, an improved double strategies co-evolutionary ant colony system (DC-ACS) was proposed. In this study, the main method was used to transform the problem into a solvable single objective problem. Then, the ant colony algorithm combined the coevolution mechanism, adaptive pheromone update strategy and local search mechanism were used to improve the solution effect of the algorithm. Finally, an appropriate fitness calculation method and stagnation avoidance strategy were designed to enhance the ability of the algorithm to jump out of local optimization. The C105 example of Solomon dataset was solved by using the improved ant colony algorithm. The optimal solutions on the four optimization objectives were 937.94 km, 4961.48 CNY, 4081.78 CNY and 7500.87 CNY respectively, which proved the effectiveness of the model proposed in this study. Based on the effectiveness of the model, the experimental results showed that the total distribution cost of the improved ant colony algorithm reduced by more than 14% on average compared with the basic ant colony algorithm on the four optimization objectives, which proved that the improved ant colony algorithm had more advantages. The improved ant colony algorithm was used to solve large-scale examples with different distributions: centralized, random and mixed. The optimal total costs were 19939.53 CNY, 24095 CNY and 24397.58 CNY, respectively. To sum up, the proposed model and algorithm could provide a good reference for the urban distribution path decision-making of cold chain logistics enterprises, a new idea to improve the distribution path optimization model and optimization method of smart agricultural supply chain, and a reference for enterprises to further expand their scale.

1 引 言

随着生活水平的提高,人们对鲜肉、水产品和果蔬等生鲜农产品的需求不断增加,对生鲜易腐品的冷链配送服务的要求日益增加。但城市冷链配送易受天气和交通状况的影响,进而导致配送成本和运输时间增加。准确量化道路状况对速度的影响是城市配送模型建立中需要解决的问题。而客户订单数量的增多和分布的复杂化1使得冷链企业的运营成本进一步增加,过去单一车型的配送模式无法满足企业的要求。多车型配送模式的出现解决了这一问题2,计算配送过程中不同类型车辆的碳排放并最大化降低碳排放和企业成本成为研究的热点。对于冷链物流企业来说,无法准确量化复杂道路状况和多车型碳排放对配送成本的影响,制约了企业进一步发展,同时也影响高效、绿色的智慧农业供应链的建设3-5
针对模型中速度固定和车辆碳排放计算方法单一问题,国内外许多研究者进行了深入研究。陈久梅等6考虑了不同产品对冷冻温度和湿度的不同需求,建立了生鲜农产品多隔室车辆路径优化模型( Multi-Compartment Vehicle Routing Problem,MCVRP),接着将车辆路径规划问题(Vehicle Routing Problem,VRP)的国际标准算例改变后得到28个MCVRP标准算例,最后使用融合了邻域搜索算法的粒子群算法对模型求解,改进后的算法求得的总路径降低了2%。张倩等7建立了考虑配送成本、产品新鲜度、碳排放等因素的生鲜电商优化模型,其中计算产品新鲜度时考虑了距离和时间因素形成新鲜度公式,在计算碳排放时考虑了运输距离和负载,构建了包括总成本、产品新鲜度和碳排放的多目标优化模型,最后使用果蝇算法对该模型求解。上述研究虽然构建了考虑碳排放的模型,但忽视了车辆速度变化的现实情况,同时在碳排放计算方法上没有创新。肖建华等8提出了基于城市道路限行的多车型车辆路径优化模型,并使用变邻域搜索算法求解该模型,证明该模型可以降低物流成本、提升配送效率和改善城市环境。赵志学等9提出了考虑拥堵区域的多车型绿色车辆路径问题优化模型,求解结果表明不同的道路状况对物流配送成本有较大影响。李军涛等10提出了考虑拥堵指数的多车型冷链路径优化模型,并使用自适应遗传模拟退货算法求解,结果表明该模型和算法可以降低56%的碳排放量。Wang等11在2016年构建了总成本最低和最大新鲜度的多目标优化模型,并使用两阶段启发式算法求解,其中先使用K-means聚类方法生成初始解,接着使用可变邻域搜索和遗传算法对其进行进一步寻优。Ma等12在时间依赖车辆路径问题的基础上(Time Dependent Vehicle Routing Problem,TDVRP),建立了车辆灵活出发条件下的生鲜农产品配送模型。Liu等13在带时间窗的时间依赖车辆路径问题(Time Dependent Vehicle Routing Problem With Time Window,TDVRPTW)的基础上,提出了考虑固定成本、人力成本和燃油消耗的配送路径优化模型,并使用改进的蚁群算法对该模型求解。Hsiao等14利用改进遗传算法研究了视频类型和温度变化的路径优化问题。Byung等15比较了冷藏车和一般车型的配送成本,确认了冷藏车在生鲜农产品配送中的有效性。Alinaghian和Nadia等16采用大规模邻域算法和变邻域算法解决了多隔室和多中心的配送路径问题。Hiassat等17考虑易腐品特性,建立了配送中心-库存优化模型,并使用局部搜索改进的遗传算法求解。以上研究同时考虑了多车型和道路拥堵情况,但对于晴天时不同时间段的道路状况,没有建立起相应的车速特征模型。最后,部分研究6,9的算例客户点数量均在30个以下,且算例客户分布类型较为单一,没有考虑大规模客户在离散、集中与混合分布的这三种情况下的求解结果。
综上所述,当前有关冷链配送路径优化的研究中,在模型构建上,主要探讨了道路拥堵条件下的模型构建和求解,没有考虑到现实环境中车辆速度受时间影响而变化的实际情况18-20,冷链配送车辆碳排放计算方法也较为单一;在模型求解中,对大规模和不同客户分布类型算例的求解较少21,22。基于上述背景,本研究在传统的生鲜农产品配送路径优化模型的基础上,考虑了路网时变特征并采用了基于载重的多车型碳排放计算模型,提出综合考虑碳排放、车辆路径、货物新鲜度和车辆固定成本的多目标优化的车辆路径模型;通过设计改进蚁群算法来求解大规模生鲜农产品配送算例。为冷链物流企业的城市配送路径决策提供良好的参考依据。

2 问题描述与模型构建

2.1 问题描述和假设

本研究探索车辆速度随时间变化条件下的多车型物流配送车辆路径问题,具体描述为:物流配送中心具有多种类型的车辆,给位于城市不同地点的客户配送货物;客户点的货物需求量和位置确定,具有时间窗要求;随着时间的变化,道路状况会影响车辆的行驶速度。优化目标是在考虑车辆油耗、碳排放、车辆固定成本和货损成本的情况下,找出满足客户特定要求的车辆调度和路径安排方案。
为方便对问题分析和求解,做出以下假设:
(1)配送中心和客户点的位置坐标已知,车辆的起点和终点均为配送中心。
(2)配送中心有不同类型的配送车辆,且不同类型车辆的数量有限。
(3)车辆行驶在不同的时间段,速度不同。
(4)每个客户配送时间段固定,提前或者超过服务时间窗均要承担惩罚费用。
(5)每个客户由一辆车为其提供服务,客户的产品需求量确定,均小于配送车辆的最大承载能力。
(6)不同类型车辆的最大承载能力、固定成本费用、油耗和碳排放率不同。
(7)配送车辆在等待和服务期间,没有油耗和碳排放产生。

2.2 模型构建

2.2.1 车辆行驶时间分析

配送车辆的速度受到较多因素的影响,在传统的车辆路径优化配送模型中,道路状况和天气保持不变,进而配送车辆速度恒定;在实际的配送过程中,变化的行驶速度更符合实际。因此,本研究分析了在晴天状况时,早晚高峰对车辆行驶速度的影响。
文献[23]建立了考虑实时路况和接驳点的冷链物流配送路径优化模型,其中的实时路况采用道路实时路况系数表述;文献[21,24]根据天气状况的不同,建立了车速特征模型。本研究参考上述研究成果和相关监测数据25后,建立了晴天时与不同时间段下的车速特征模型,如公式(1)所示。在每天6:00—8:00和12:00—18:00时间段随着逐渐接近早晚高峰,车辆受影响程度不断增大;在8:00—12:00和18:00—22:00时间段,道路上车辆数减少的同时,对配送车辆的影响也逐渐降低;其他时间段无影响。
晴天时不同时段对车辆速度的影响率 ζ s u n表示为:
ζ s u n = 0 0 t < 6 22 t < 24 0.225 t - 1.35 6 t < 8 - 0.05 t + 0.85 8 t < 12 t 30 - 0.15 12 t < 18 - 0.1125 t + 2.475 18 t < 22
其中,t为车辆行驶时所在的时间点。
晴天时计算不同时段下的车辆速度 S v公式(2)
S v = S v ( 1 - ζ s u n )       
其中, S v是配送车辆的平均行驶速度,km/h。因此,配送车辆在从任意点 i j的行驶时间表示为:
t i j = d i j S v
其中, t i j为配送车辆从i点到j点需要花费的时间,h; d i j为任意客户点ij的距离,km。

2.2.2 考虑载重的油耗与碳排放计算

不同车型的营运车辆,在计算油耗和碳排放时会受到多种因素的影响,其中载重是最重要的影响因素。首先经过测算得到不同载重货车的百公里油耗均值,每种类型货车取不同数量,具体见表1
表1 试验车型信息

Table 1 Information of the test vehicles

车型 额定载重/t 数量/辆
小型车 2 40
中型车 4 10
大型车 8 29
接着根据碳平衡原理计算各类货车的CO2排放因子,最后取各货车的结果均值作为车辆的碳排放因子13,得到小型车、中型车和大型车的CO2排放因子分布为326.88、501.64和514.03 g/km。
因此,不同车型的营运车辆的碳排放成本C 2计算如公式(4)所示。
C 2 = m = 1 M i = 0 n j = 0 n x i j m E m L i j    
其中, x i j k m为0~1变量;若车型为m车辆ki点到j点,则 x i j k m = 1;否则 x i j m = 0 E m为车型m的碳排放因子,g/km。 L i j为任意客户点ij的距离,km。

2.2.3 货损成本计算

本研究货损成本分为在途货损成本和卸货货损成本14
(1)在途货损成本。指运输车辆向客户点行驶过程中,货物因为温度、湿度等原因造成损失而产生的成本。生鲜农产品的特征决定了它们的货损成本和时间成正比,所以假设运输过程中单位时间和重量货物的货损系数:
θ 1 = ( 1 - e - ε T i A - T i - 1 L )
其中, ε是产品的腐败率,%,值越大,单位时间产品的腐败程度越严重; T i A为客户点i的最早开始服务时间点,h; T i - 1 L为客户点i前一个点的最晚服务时间点,h。
在途货损成本 C 3 1的计算公式为:
C 3 1 = m = 1 M i = 0 n x i m p Q i θ 1          
式中, x i m为0~1变量:若客户i点由m车型的车辆服务,则 x i m = 1;否则 x i m = 0 p为生鲜货物的单价,元。 Q i为配送车辆抵达i点时的载荷量,%。
(2)卸货货损成本。指配送车辆到达客户点后,因为打开车厢门搬运货物等原因造成货物损耗而产生的成本。假设卸货时单位时间重量的货物的货损系数为:
θ 2 = ( 1 - e - ε T s i )
其中, T s i为客户点i的服务时间,h。
卸货时的货损成本 C 3 2公式(8),总货损成本 C 3计算为公式(9)
C 3 2 = m = 1 M i = 0 n x i m p θ 2 Q i - q i    
C 3 = C 3 1 + C 3 2    
其中, q i为客户点i的货物需求量,kg。

2.2.4 车辆固定成本计算

车辆的固定成本主要包括汽车的使用费用、行驶和卸货时的人力成本以及配送车辆的固定启用成本。车辆的固定成本C4公式为:
C 4 = m = 1 M k = 0 K i = 0 n j = 0 n x i j k m t i j μ k + P m + m = 1 M k = 0 K i = 0 n Y i k m s i μ k + P m + m = 1 M k = 0 K i = 0 n X 0 j k m ξ m
其中, μ k为车辆k的单位时间使用费用,元; P m为使用m类型车辆的单位时间人力成本,元; ξ m为车型m的固定发车费用,元; X 0 j k m为0~1变量:若车型为m的车辆k从配送中心到j点,则 X 0 j k m = 1,否则 X 0 j k m = 0 Y i k m为0~1变量:若车型为m的车辆k经过i点,则 Y i k m = 1,否则 Y i k m = 0

2.3 配送路径多目标优化模型建立

在考虑行驶速度、车辆碳排放和货损成本、时间窗、多车型等情况下,满足所有顾客的需求,以行驶距离 C 1、碳排放成本 C 2、货损成本 C 3和车辆固定成本 C 4最低为目标,综合考虑上述四个目标函数,生鲜电商配送路径优化的多目标联合优化模型如下所示:
m i n C 1 = i = 0 n j = 0 n k = 1 M d i j x k i j  
m i n C 2 = m = 1 M i = 0 n j = 0 n x i j m E K L i j                   
     m i n C 3 = C 3 1 + C 3 2 = m = 1 M i = 0 n x i m p Q i θ 1 T i A - T i - 1 L +                           m = 1 M i = 0 n x i m p θ 2 Q i - q i T s i   
m i n C 4 = m = 1 M k = 0 K i = 0 n j = 0 n x i j k m t i j μ k + P m + m = 1 M k = 0 K i = 0 n Y i k m s i μ k + P m + m = 1 M k = 0 K i = 0 n X 0 j k m ξ m  
其中, x k i j为0~1变量:若车辆ki点到j点,则 x k i j = 1,否则 x k i j = 0

3 改进蚁群算法设计

3.1 改进蚁群算法设计的基本思想

蚁群算法最初用于求旅行商问题(Traveling Salesman Problem,TSP)等单目标优化问题6,其良好的鲁棒性26、正反馈性27和分布式特点可较好地解决配送路径优化问题28,29。本研究通过采用主要目标法和新的编码方式,将该问题转换为可求解的单目标问题;接着在蚁群算法中融合协同进化机制、自适应信息素更新策略和局部搜索等机制来提高算法的求解效果;最后设计合适的适应度计算方法和停滞规避策略,增强该算法跳出局部最优的能力。

3.1.1 主要目标法

多目标模型的求解通常有两种:第一种是通过线性加权法或主要目标法将多目标优化问题转换为单目标问题;第二种是通过Pareto方法进行多目标同时优化,得到一个最优解集。行驶距离最短、生鲜农产品新鲜度和碳排放量存在悖反关系7。对于冷链企业来说,针对不同的订单情况需要采取不同的优化目标,以实现成本最小和盈利最大。因此,本研究采用主要目标法,分别以配送总成本最小、货损成本最小、车辆碳排放和车辆固定成本最小之一作为主要目标,其余目标满足企业的要求即可。基于上述分析,将多目标优化问题转化为单目标优化问题,当行驶距离为主要优化目标时:
m i n   C 1 s . t .       { ζ i C i δ i , i = 2 , . . . , 4 }
其中, δ 2 ζ 2是生鲜农产品的货损成本的最高和最低约束; δ 3 ζ 3是车辆配送过程中的碳排放量的最高和最低约束; δ 4 ζ 4是车辆模型对配送过程中,车辆固定成本的最高和最低约束。

3.1.2 种群编码和解码

在利用蚁群算法求解物流路径优化问题时,确定解的表示方法是一项非常关键的工作。目前普遍使用的编码方式有二进制编码和自然数编码。由于本研究涉及到多车型的表示问题,采用自然数编码方式。改进蚁群算法编码采用如下设计:假设一个配送中心为n个客户点提供配送,其中配送中心有M种类型车辆供选择,每类车辆数目为K辆。采用n维实数向量表示种群中每个个体的状态,使用m维实数向量来表示配送车辆类型,因此,当进行解码操作时,首先按顺序从m维向量中取得车辆型号,接着根据该型号车辆的载重确定该车辆需要服务的客户点。
车辆选择和客户分配步骤如下:
(1)得到初始路径;
(2)选取最大承载重量车辆执行配送任务;
(3)判断当前车辆剩余容量能否满足当前客户点需求,若能,转步骤(4),否则转步骤(5);
(4)将当前客户点分配给当前车辆,若仍有客户未服务,转步骤(3),否则输出路径分配结果,算法结束;
(5)选取次容量作为配送车辆,转步骤(3)。

3.1.3 种群协同进化机制

为进一步提高算法的求解效果,本研究引入蚁群系统(Ant Colony System,ACS)和最大最小蚁群系统(Max-Min Ant System,MMAS )种群交流机制30。协同进化机制可以使两个种群从算法开始到结束完全联系在一起,不再单独地进行解的生成和迭代,而是形成两类蚂蚁种群相互学习和共同促进的局面,使得算法能以较少的迭代次数找到最优解。
对于协同种群的信息素交流,当采取固定的交流间隔时,会导致种群多样性下降,产生的结果和一个种群类似;当信息交流间隔过长时,会减少两类蚁群协同进化的效果。因此,本研究采用基于相似度的交流频率策略31,对交流频率进行自适应调节,具体如下。
当两类蚁群算法完成本次迭代,并更新自身信息素后,首先将两类蚁群算法的全局最优路径取交集,得到两类蚁群算法的相似度。当相似度较低时,两类蚁群的多样性较好,不必进行交流。当相似度过高时,两类蚁群路径趋于一致,多样性较差,陷入局部最优,应进行信息素交流,将两类蚁群的信息素进行交换30。根据公式(16)判断是否进行交流。
L =   1     S A B < S 0        e l s e                                        
其中,L为判断是否进行信息素交流的逻辑值; S A B是两类种群最优解的相似度; S是进行交流的阈值。

3.1.4 公共路径奖励机制

公共路径可以看作是全局最优解的组成部分,因此可以充分利用这个因素,在算法前期,增加奖励的信息素,达到加快收敛速度的目的;在算法后期,随着迭代次数的增多,增加的信息素会越来越少,从而增加算法后期的多样性。
当两类种群进行交流时,对种群的公共路径的信息素按照公式(17)进行更新:
τ i j ( t + 1 ) = ( 1 - ρ ) τ i j ( t ) + Δ τ i j + ( 1 n ) e - i t e r  
其中,n为客户点的总数量,个;iter为当前迭代次数,次; ρ为蚁群信息素的蒸发率。

3.1.5 局部搜索(2-opt)机制

本研究中采用该算子来加快收敛速度。因为在不同车辆的配送路径间进行2-opt优化时,可能会发生超载现象。因此本研究采用路径内2-opt优化方式32。优化方法如图1所示。完成每次操作后,计算该条配送路径是否变短,若路径得到改进,则更新路径。如此重复,直到对该条线路内所有客户都进行2-opt操作。
图1 2-opt优化示意图

Fig. 1 Schematic diagram of 2-opt optimization

3.1.6 适应度计算

适应度是个体在种群生存的优势程度度量,使用适应度函数来进行计算,在个体进化过程中起着重要的推动作用,适应度太大会导致算法过早收敛,太小则会使求解过程缓慢33,因此,选择合适的适应度值很重要。在求解车辆路径优化问题时,目的是使得总目标函数最小且非负,因此为了使所求优化目标函数最小,则应使适应度值最大。
在蚁群算法的求解中,个体被保留的可能性与适应度值呈正相关,适应度值较大的个体越有可能被保存下来,所以适应度 F和模型总成本的关系应为倒数。本研究以 C i代表第i条路径所产生的总成本,适应度值计算如公式(18) 12
F = 1 C i

3.1.7 停滞规避策略

基本蚁群算法在迭代一定次数后,可能会陷入局部最优,并在较差路径上积累较多信息素,进而出现停滞现象34。但基本蚁群算法本身缺乏跳出局部最优的能力,因此本研究针对该问题,采取了一种停滞检测和跳出策略31
算法停滞检测办法是计算更优解的次数。当在一定迭代次数内,仍未出现较优解,则判定算法陷入局部最优,具体检测判断公式如下:
L = 1     c o u n t > T 0        e l s e                                   
其中,L是判断算法是否停滞的0~1布尔值;count是判断算法停滞的阈值。
针对算法停滞的具体措施如下:当检测到算法中全局最优值陷入停滞时,首先将两类蚁群中所有路径上的信息素置为初始值,接着筛选出两类蚁群停滞前所产生最优路径的公共路径,最后奖励公共路径上的信息素,公式如下:
τ i j ( t + 1 ) = τ 0 + Δ τ i j                   
Δ τ i j =    1 L g b    i f ( i , j ) B e s t T o u r 0                   e l s e                              
其中, τ 0为每条路径上的起始信息素浓度; Δ τ i j是两类蚁群分别由公式(21)得出的信息素增量。强化公共路径的信息素会增强算法停滞后再次运行的导向性,并可以使算法的搜索侧重点放在非公共路径的城市序列中,使得算法易于发现更优的路径,保证算法在后续的循环中能有效跳出局部最优。

3.2 改进蚁群算法步骤

改进蚁群算法的流程见图2图2具体步骤如下:
图2 改进蚁群算法流程图

Fig. 2 Flow chart of improved ant colony algorithm

(1)参数初始化。
(2)将种群划分为两组,分别按照最大最小蚁群算法和普通蚁群算法更新信息素,求解种群的适应度。
(3)进入协同交流阶段,计算两类蚁群的路径相似度,接着根据公式(17)判断是否进行交流,若是,转步骤(4),否则转步骤(5)。
(4)进入种群交流阶段,找出种群的公共路径,按照公式(20)奖励公共路径的信息素。
(5)根据公式(19)对算法是否陷入局部最优进行检查,若是,转步骤(6),否则转步骤(7)。
(6)根据公式(20)对算法陷入局部最优做出相应处理。
(7)交换信息素,达到跳出局部最优的效果。
(8)判断当前迭代次数是否大于或等于最大迭代次数,若是,输出最优解,算法结束,否则转到步骤(2)。

4 数值模拟

为验证本研究提出的生鲜农产品配送路径优化模型和改进的蚁群算法,将带时间窗的车辆路径问题(Vehicle Routing Problems With Time Windows,VRPTW)的Solomon数据集算例35进行改造,使用Matlab2010进行仿真实验。设有一个生鲜农产品配送中心和100个客户,各客户点服务时间、时间窗如原本算例35所述,配送中心的冷链配送车辆的载重量分别为2、4和8 t,各类型车辆数量分别为5、3和2辆。假设配送货车以35 km/h的速度匀速行驶。

4.1 参数设置

改进模型和算法实验以Solomon数据库的C105、R105和RC105为例,算例C105属于集中分布,R105的客户坐标属于随机分布,RC105属于混合分布。参考其他研究结果9,36,并经过大量实验后,参数设置如下:令客户需求量的一个重量单位为10 kg,最终总配送重量为57 t,更符合实际需求;为简化计算,此次数值计算假设生鲜农产品类型单一,其中产品腐败率ε=0.06,货物单价为1 元/kg。计算固定成本时,冷链配送车辆的人力成本、启用成本和管理成本如表2所示,碳税计算价格为Cem=0.05 元/kg 。通过反复实验,改进蚁群算法的参数分别设置为蚂蚁数m为50个,信息素重要程度启发因子α=1,启发函数重要程度因子β=3,信息素挥发因子ρ为0.85,控制转移规则参数r 0为0.5。迭代次数设置为100次。
表2 车辆的人力、启用和管理成本

Table 2 Labor, start-up and management costs of vehicles

车辆类型 小型车 中型车 大型车
人力成本/(元·km-1 20 30 40
启用成本/(元·次-1 300 400 500
管理成本/(元·次-1 60 80 100

4.2 算法性能对比

4.2.1 不同优化目标结果比较

为验证模型的有效性,以本研究提出的模型为基础,采用改进后的Solomon数据集中的C105算例,使用改进蚁群算法求解模型,分别以总路径最短,产品新鲜度最大,碳排放以及车辆固定成本最小为主要目标,其他目标转为约束进行求解,具体结果如表3所示。
表3 不同优化目标的结果比较

Table 3 Comparison of results of different optimization objectives

主要优化目标 路径总长度 碳排放 产品新鲜度 车辆固定成本
总路径/km 937.94 968.91 1105.79 965.02
碳排放/元 5136.02 4961.48 6150.46 5095.24
产品货损成本/元 6126.35 5986.93 4081.78 5875.46
车辆固定成本/元 7739.21 7573.20 8219.79 7500.87
表3中可以看出,当选择不同的主要优化目标时,该模型均能在该目标求得最优解:尤其对冷链配送的关键指标产品新鲜度有了很大提升,最高降幅达到36%;以路径总长度为优化目标时,取得的结果接近算例最优解;以多车型的碳排放计算为目标时,最多减少了19%的碳排放;对于车辆固定成本,降幅最高达到了5%。同时几组解的结果证明客户规模较大情况下,车辆固定成本、生鲜农产品新鲜度和碳排放量存在悖反关系,多个优化目标很难同时达到最优。例如,若满足其产品货损成本最低,与最优值相比,使得碳排放增幅23%,车辆固定成本增加10%;从配送成本的构成比例来看,占比最高的车辆固定成本平均比例达到39%,其次是产品新鲜度平均占比27%。因此,上述数值计算表明,改进模型可以在对应的优化目标上取得最优结果,该模型有效;对于冷链电商企业,在面对大规模订单时很难同时在多个优化目标取得最优,决策者应根据自身战略的需要和市场与客户不同要求,选择特定主要目标进行优化,进而得出适合的配送方案。

4.2.2 不同算法的结果比较

将本研究提出的算法与基本蚁群算法进行对比实验,算例选取改编后的C105算例,实验参数不变,且分别以改进蚁群算法和基本蚁群算法对其进行求解,分别以路径总长度、碳排放、产品新鲜度和车辆固定成本为主要优化目标,结果如表4所示。
表4 不同算法求解算例计算结果

Table 4 Calculation results of examples solved by different algorithms

主要优化目标 路径总长度 碳排放(调整) 产品新鲜度 车辆固定成本
改进ACS 基本ACS 改进ACS 基本ACS 改进ACS 基本ACS 改进ACS 基本ACS
路径总长度/km 937.94 1025.02 968.91 1051.46 1105.79 1127.91 965.02 1066.76
碳排放/元 5136.02 6115.47 4961.48 6051.10 6150.46 6670.16 5095.24 6307.41
产品货损成本/元 6126.35 7573.59 5986.93 7984.48 4081.78 6597.01 5875.46 6824.19
车辆固定成本/元 7739.21 8380.63 7573.20 8353.51 8219.79 8433.54 7500.87 8079.81
以路径长度为主要优化目标时,碳排放和货损成本降幅最大,达到16%和19%,总配送成本降低13%;以碳排放为主要优化目标时,碳排放和货损成本在总配送成本减少量中贡献最多,所占比例分别为50%和27%,总配送成本降幅16%;以货损成本和车辆固定成本为主要优化目标时,总配送成本分别降低14%和12%;不同优化目标的总配送成本平均降幅达到14%,改进蚁群算法结果更优。综上所述,本研究的改进蚁群算法可以降低冷链配送成本。

4.2.3 不同客户分布算例结果比较

为进一步验证本研究生鲜农产品配送路径优化模型的有效性,采用多类型算例C105、R105和RC105分别进行试验,三种客户分布分配的车辆数量和类型一致,其他试验参数也一致,以路径总长度为主要优化目标,试验结果如表5所示,三种分布路线如图3~图5所示。
表5 不同客户分布算例计算结果

Table 5 Calculation results of different customer distribution examples

分布类型 路径总长度/km 碳排放/元 产品货损成本/元 车辆固定成本/元

总成

本/元

C105 937.94 5136.02 6126.35 7739.21 19,939.53
R105 1129.97 6659.98 7633.96 8671.55 24,095.47
RC105 1185.22 6928.16 7615.82 8668.36 24,397.58
图3 C105算例配送路径示意图

Fig. 3 C105 example distribution path diagram

图4 R105算例配送路径示意图

Fig. 4 R105 example distribution path diagram

图5 RC105算例配送路径示意图

Fig. 5 RC105 example distribution path diagram

表5可以看出,C类算例的配送距离、车辆固定成本、货损成本和碳排放量在所有类型中最低。主要由于C类客户分布点主要集中分布在几个区域,行驶距离较短,因此碳排放量相对较低,并且货物中途货损成本保持在一个较低值。但R类和RC类总配送距离、车辆固定成本、货损成本等均大于C类,主要由于这两种类型客户均随机分布,使得车辆配送距离增大,而且总行驶时间较长,总配送成本也随着分布复杂度的增加而增加。从最终结果对比来看,所有类型的成本里面,碳排放和货损成本占比相对较高,两类成本占比均达到68%以上。碳排放随着分布的复杂化涨幅最高,平均涨幅16.5%。说明无论客户的分散程度如何,车辆固定成本和产品货损成本应是企业主要关注的目标。因此要降低总物流成本,最主要就是合理规划配送策略,适当增加配送中心,减少客户的分散度。合理降低生鲜农产品货损。

4.3 灵敏度分析

为了分析腐败率和车辆速度对冷链配送成本的影响,选择货损成本作为主要优化目标,在保持其他条件不变的前提下,令各参数以倍数递增(减)两次,记录每次的主要优化目标值并分析。

4.3.1 腐败率对成本的影响

腐败率变化对结果的影响如图6所示。当腐败率变化时,对产品的货损成本影响最明显;腐败率越高,产品的货损成本越高,当腐败率每增长10%时,货损成本增加11%。虽然腐败率和配送总成本无明显的比例关系,但腐败率每增(减)10%时,配送总成本均增加。因此,货损成本并不是越低越好,对于企业来说,应以货损成本为主要优化目标,使货损成本保持在一个合理的水平,配送总成本最低。
图6 腐败率变化对货损和总成本的影响

Fig. 6 Impact of speed change on cargo damage cost and total cost

4.3.2 车辆速度变化对成本的影响

车辆速度增减对优化目标的影响如图7所示。随着速度的增加,配送车辆的在途时间缩短,使得碳排放减少,最终总成本呈下降趋势;碳排放与速度增减有明显的比例关系,随着速度增加而降低。但在速度增加后期总成本出现边际效应,总配送成本减少放缓。因此,冷链企业可以通过适当提高速度来减少碳排放量和配送成本。
图7速度变化对碳排放和总成本的影响

Fig. 7 Impact of speed change on carbon emission cost and total cost

5 结论与展望

本研究以VRPTW模型为基础,提出了基于载重的多车型碳排放和车辆速度计算模型,建立带有车辆启动固定成本、路径长度和货损成本的生鲜农产品配送模型,并设计了基于协同进化思想的改进蚁群算法。数值模拟结果证明:
(1)相比单车型配送模式,本研究改进后的模型可以有效降低碳排放成本和配送总成本。根据生鲜农产品的腐败率、客户重要程度、配送场景的不同,采用相应的优化目标,可以使企业、客户的利益最大化。
(2)改进的蚁群算法与基本蚁群算法相比,可以有效求解大规模客户算例,配送总成本平均降幅达14%,进一步降低企业配送成本。
(3)对于不同分布类型的客户订单,客户集中分布时的配送成本最低,部分集中时需要的成本最高,企业应通过增加配送中心等方法来降低成本,提高配送效率。
(4)对于腐败率不同的生鲜农产品,货损成本最低并不能保证总配送成本最低,应使货损成本保持在一个合适的区间。
(5)车辆速度越高,配送总成本不一定越低,应选择合适的速度降低总成本。
本研究通过提供了多种优化目标的选择,使得企业可以根据自身需要和发展战略,权衡不同优化目标的利弊,得出适合的配送方案;同时为智慧农业供应链的配送路径规划体系提供了新的理论和数据支撑,有较强的应用价值和理论价值。
本研究仅考虑了天气较好情况下的车辆速度变化,没有考虑其他天气情况下对配送效率的影响。同时只研究了单温度和单配送中心下的冷链配送车辆路径问题,没有研究多温共配和多配送中心的农产品配送问题20,37;且仅仅使用主要目标法求解多目标模型,没有考虑其他方法。因此,以上问题将是下一步的研究内容。
1
陈栋, 陈天恩, 姜舒文, 等. 基于订单位置聚类的雏鸡配送车辆调度优化模型[J]. 智慧农业(中英文), 2020, 2(4): 137-148.

CHEN D, CHEN T, JIANG S, et al. Optimal model of chicken distribution vehicle scheduling based on order clustering[J]. Smart Agriculture, 2020, 2(4): 137-148.

2
杨珍花, 赖平仲, 汤洋, 等. 冷藏车多车型混合配送调度优化[J]. 系统工程, 2015, 33(10): 28-36.

YANG Z, LAI P, TANG Y, et al. Mix distribution dispatch optimization by multi-type refrigerated trucks[J]. Systems Engineering, 2015(10): 28-36.

3
李义华, 吕名锐, 孙凤英. 生鲜农产品智慧冷链物流体系优化研究[J]. 中南林业科技大学学报(社会科学版), 2018, 12(6): 63-67, 80.

LI Y, LYU M, SUN F. Fresh agricultural products wisdom cold chain logistics system optimization research[J]. Journal of Central South University of Forestry& Technology (Social Sciences), 2018, 12(6): 63-67, 80.

4
李干琼, 李欣, 赵龙华, 等. 农业供应链管理研究进展综述及展望[J]. 农业大数据学报, 2020, 2(3): 2-12.

LI G, LI X, ZHAO L, et al. A review of agricultural supply chain management and its prospects for the future[J]. Journal of Agricultural Big Data, 2020,2(3): 2-12.

5
赵春江, 李瑾, 冯献. 面向2035年智慧农业发展战略研究[J]. 中国工程科学, 2021, 23(4): 1-9.

ZHAO C, LI J, FENG X. Development strategy of smart agriculture for 2035 in China[J]. Strategic Study of CAE, 2021, 23(4): 1-9.

6
陈久梅, 周楠, 王勇. 生鲜农产品多隔室冷链配送车辆路径优化[J]. 系统工程, 2018, 36(8): 106-113.

CHEN J, ZHOU N, WANG Y. Optimization of multi-compartment cold chain distribution vehicle routing for fresh agricultural products[J]. Systems Engineering, 2018, 36(8): 106-113.

7
张倩, 熊英, 何明珂, 等. 不确定需求生鲜电商配送路径规划多目标模型[J]. 系统仿真学报, 2019, 31(8): 1582-1590.

ZHANG Q, XIONG Y, HE M, et al. Multi-objective model of distribution route problem for fresh electricity commerce under uncertain demand[J]. Journal of System Simulation, 2019, 31(8): 1582-1590.

8
肖建华, 王超文, 陈萍,等. 基于城市道路限行的多能源多车型车辆路径优化[J]. 系统工程理论与实践, 2017, 37(5): 1339-1348.

XIAO J, WANG C, CHEN P, et al. The multi-energy heterogeneous fleet vehicle routing optimization under urban traffic restriction[J]. Systems Engineering-Theory & Practice, 2017, 37(5): 1339-1348.

9
赵志学, 李夏苗, 周鲜成. 考虑拥堵区域的多车型绿色车辆路径问题优化[J]. 计算机应用, 2020, 40(3): 883-890.

ZHAO Z, LI X, ZHOU X. Green vehicle routing problem optimization for multi-type vehicles considering traffic congestion areas[J]. Journal of Computer Applications, 2020, 40 (3): 883-890.

10
李军涛, 刘明月, 刘朋飞. 生鲜农产品多车型冷链物流车辆路径优化[J]. 中国农业大学学报, 2021, 26(7): 115-123.

LI J, LIU M, LIU P. Route optimization of multi-vehicle cold chain logistics for fresh agricultural products[J]. Journal of China Agricultural University, 2021, 26(7): 115-123.

11
WANG X, WANG M, RUAN J, et al. The multi-objective optimization for perishable food distribution route considering temporal-spatial distance[J]. Procedia Computer Science, 2016, 96: 1211-1220.

12
MA Z, YAO W, YING D. A combined order selection and time-dependent vehicle routing problem with time widows for perishable product delivery[J]. Computers & Industrial Engineering, 2017, 114: 101-113.

13
LIU C, KOU G, ZHOU X, et al. Time-dependent vehicle routing problem with time windows of city logistics with a congestion avoidance approach[J]. Knowledge-Based Systems, 2019, 188: ID 104813.

14
HSIAO Y, CHEN M, CHIN C. Distribution planning for perishable foods in cold chains with quality concerns: Formulation and solution procedure[J]. Trends in Food Science & Technology, 2017, 61: 80-93.

15
BYUNG D S, YOUNG D K. A vehicle routing problem of both refrigerated-and general-type vehicles for perishable food products delivery[J]. Journal of Food Engineering, 2016, 169: 61-71.

16
ALINAGHIAN M, NADIA S. Multi-depot multi-compartment vehicle routing problem, solved by a hybrid adaptive large neighborhood search[J]. Omega, 2018, 76: 85-99.

17
HIASSAT A, DIABAT A, RAHWAN I. A genetic algorithm approach for location-inventory-routing problem with perishable products[J]. Journal of Manufacturing Systems, 2017, 42: 93-103.

18
王金妹, 尹显龙. 乳制品冷链物流配送中心选址及配送路径优化[J]. 福州大学学报(哲学社会科学版), 2020, 34(1): 45-53.

WANG J, YIN X. Enhancing strategies of tourism accommodation capacity of Beijing location and routing optimization for cold chain logistics distribution of dairy products[J]. Journal of Fuzhou University (Philosophy and Social Sciences), 2020, 34(1): 45-53.

19
AMORIM P, ALMADA-LOBO B. The impact of food perishability issues in the vehicle routing problem[J]. Computers & Industrial Engineering, 2014, 67(1): 223-233.

20
张凯庆, 嵇启春. 速度时变的多中心半开放式车辆路径问题研究[J/OL]. 系统仿真学报: [2021-09-15]. DOI: 16182/j.issn1004731x.joss.20-0907.

ZHANG K, JI Q. Research on multi-depot half-open vehicle routing problem with time-varying speed[J/OL]. Journal of System Simulation: [2021-09-15]. DOI: 16182/j.issn1004731x.joss.20-0907.

21
王恒, 徐亚星, 王振锋, 等. 基于道路状况的生鲜农产品配送路径优化[J]. 系统仿真学报, 2019, 31(1): 126-135.

WANG H, XU Y, WANG Z, et al. Distribution routing optimization of fresh agricultural products based on road conditions[J]. Journal of System Simulation, 2019, 31(1): 126-135.

22
杜琛, 李怡靖. 基于客户满意度和最小损耗的冷链配送路径问题研究[J]. 工业工程与管理, 2020, 25(6): 163-171.

DU C, LI Y. Research on cold chain distribution routing problem based on customer satisfaction and minimum loss[J]. Industrial Engineering and Management, 2020, 25(6): 163-171.

23
姚源果, 贺盛瑜. 基于交通大数据的农产品冷链物流配送路径优化研究[J]. 管理评论, 2019, 31(4): 240-253.

YAO Y, HE S. Research on optimization of distribution route for cold chain logistics of agricultural products based on traffic big data[J]. Management Review, 2019, 31(4): 240-253.

24
BIE Y, QIU T, ZHANG C, et al. Introducing weather factor modelling into macro traffic state prediction[J]. Journal of Advanced Transportation. 2017, 17(1): 1-5.

25
龚大鹏, 宋国华, 黎明, 等. 降雨对城市道路行程速度的影响[J]. 交通运输系统工程与信息, 2015, 15(1): 218-225.

GONG D, SONG G, LI M, et al. Impact of rainfalls on travel speed on urban roads[J]. Journal of Transportation Systems Engineering and Information Technology, 2015, 15(1): 218-225.

26
唐慧玲, 唐恒书, 朱兴亮. 基于改进蚁群算法的低碳车辆路径问题研究[J]. 中国管理科学, 2021, 29(7): 118-127.

TANG H, TANG H, ZHU X. Research on low-carbon vehicle routing problem based on modified ant colony algorithm[J]. Chinese Journal of Management Science, 2021, 29(7): 118-127.

27
万杰, 耿丽, 田喆. 基于改进的蚁群算法求解多目标生鲜农产品车辆路径[J]. 山东农业大学学报(自然科学版), 2019, 50(6): 1080-1086.

WAN J, GENG L, TIAN Z. Solution for the vehicle route of multi-objective fresh agricultural products based on the improved ant colony algorithm[J]. Journal of Shandong Agricultural University (Natural Science Edition), 2019, 50(6): 1080-1086.

28
BATISTA Z, JOÃO B Q, et al. Multi-objective topology optimization with ant colony optimization and genetic algorithms[J]. Computer-Aided Design and Applications, 2015,12(6): 674-682.

29
SKINDEROWICZ R. Ant colony system with a restart procedure for TSP[C]// International Conference on Computational Collective Intelligence. Berlin, German: Springer, 2016.

30
朱宏伟, 游晓明, 刘升. 协同过滤策略的异构双种群蚁群算法[J]. 计算机科学与探索, 2019, 13(10): 1754-1767.

ZHU H, YOU X, LIU S. Heterogeneous dual population ant colony algorithm based on cooperative filtering strategy[J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(10): 1754-1767.

31
刘一凡, 游晓明, 刘升. 基于动态重组和协同交流策略的蚁群优化算法[J]. 计算机科学与探索, 2021, 15(8): 1511-1525.

LIU Y, YOU X, LIU S. Ant colony optimization algorithm based on dynamic recombination and cooperative communication strategy[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(8): 1511-1525.

32
贺亦甲, 符强, 朱俊杰, 等. 一种求解TSP问题的改进鸟群算法[J]. 计算机时代, 2019(5): 56-60.

HE Y, FU Q, ZHU J, et al. An improved bird swarm algorithm for solving TSP problem[J]. Computer Era, 2019(5): 56-60.

33
段雪凝. 带时间窗的冷链物流车辆路径多目标优化问题研究[D]. 沈阳: 东北大学, 2014.

DUAN X. Research on multi-objective optimization vehicle routing problem with time windows of cold chain logistics[D]. Shenyang: Northeastern University, 2014.

34
叶仕通, 万智萍. 一种基于改进全局信息素更新效率的蚁群算法及仿真[J].计算机应用与软件, 2014, 31(1): 176-179.

YE S, WAN Z. An ant colony algorithm based on improving global pheromone update efficiency and its simulation[J]. Computer Applications and Software, 2014, 31(1): 176-179.

35
VRPTW BENCHMARK PROBLEMS. [2021-09-15].

36
付朝晖, 刘长石. 生鲜电商配送的开放式时变车辆路径问题研究[J]. 计算机工程与应用, 2021, 57(1): 271-278.

FU Z, LIU C. Research on open time-dependent vehicle routing problem of fresh food e-commerce distribution[J]. Computer Engineering and Applications, 2021, 57(1): 271-278.

37
张济风, 杨中华. 时变路网环境下多温冷链配送路径优化研究[J]. 重庆师范大学学报(自然科学版), 2020, 37(1): 119-126.

ZHANG J, YANG Z. Research on distribution path optimization of multi-temperature cold chain in time-varying road network environment[J]. Journal of Chongqing Normal University (Natural Science), 2020, 37(1): 119-126.

文章导航

/