基于禁忌搜索算法的生鲜冷链物流配送路径优化研究

2023-10-24高万晨王宇楠

青岛理工大学学报 2023年5期

高万晨,王宇楠

(辽宁对外经贸学院经济学院,大连 116052)

近年来,我国居民对生鲜农产品的需求量逐年增长,冷链物流应运而生,企业如何降低配送成本,消费者如何尽快收到生鲜农产品并保证产品质量变得至关重要,也成为了研究热点。在配送过程中,应将节能减排、制冷、货损、惩罚成本等因素考虑到构建配送路径优化模型中,采用合理地算法进行求解,进而获取最优的配送路径,以达到综合效益最优。

就配送模型而言,DANTZIG于1959年首次提出车辆路径问题(VRP),即将需要配送的物品按照某种次序由1辆车进行配送作业且被准时送达。此类问题一般假设各节点的距离和位置坐标、车辆最大载重量等参数已知,以配送总成本最小为目标进行路径优化[1]。随着研究的不断深入,麻存瑞等基于车辆路径优化问题,建立了快递配送的路径优化模型,设计了考虑快递量、车辆最大载重量等约束的遗传算法,通过实际案例验证了所建模型和算法设计的有效性[2]。就算法而言,学者们采用了禁忌搜索[3]、改进遗传[4]、自适应大邻域搜索[5]、改进蚁群[6]、NSGA-II[7]、粒子群[8]等算法对模型进行求解。

VRP虽然在解决“最后一公里”配送问题上具有一定的优势,但目标函数考虑因素较少,以致所得配送路径不够好,因此,部分学者把时间窗因素考虑到VRP中,把问题转换成了考虑配送时间窗的VRP问题(VRPTW),即将各节点可接受的配送时间考虑到优化模型中,且各客户节点的时间窗上、下限均已知,车辆从配送中心出发向带时间窗约束的各客户节点进行物品配送,以获得总成本最优的配送路径。其中,各客户节点的时间窗可以分为硬时间窗与软时间窗。硬时间窗是车辆到达某一客户节点的时间超过了其可接受时间,将导致配送损失为无穷大[9],而软时间窗是将车辆早到或晚到各客户节点的惩罚予以适当增大[10]。

快递进行配送作业时车辆会产生一定的温室气体,是全球温室气体排放的来源之一,因此,将碳排放因素考虑到配送路径优化模型中具有一定的理论和现实意义[11]。邓红星等将碳排放考虑到生鲜农产品冷链物流配送路径优化模型中,分别计算不考虑碳排放和考虑碳排放的生鲜农产品冷链物流路径优化方案[12]。

目前,国内诸多生鲜农产品原产地的冷链物流存在基础设施建设不完善等问题,各环节比较容易出现农产品冷链脱节的现象,会引起农产品温度的变化,进而导致生鲜农产品有冷链保存的损害比没有更大。刘雨平基于农产品冷链物流基础设施等问题提出了解决对策[13]。在生鲜产品的运输和配送过程中,如果想让其有更好的保鲜周期,那么从卖家到买家必须全程冷链,部分学者仅在配送中心至买家过程中考虑冷链,将制冷成本[14]和货损成本[14-15]考虑到目标函数中,而忽视了从卖家到配送中心之间的成本。

综上所述,本文在研究单个配送中心的从配送中心到买家的生鲜冷链物流配送路径优化问题基础上,增加了从卖家到配送中心之间的成本,建立了考虑从卖家至买家全过程链的总成本最小的数学模型,运用禁忌搜索算法对其进行求解,寻找最优的配送路径,为快递企业的科学配送和制定降本增益管理策略提供理论依据和技术参考。

1 配送路径优化模型

1.1 问题描述

生鲜农产品具有不耐高温、易腐烂变质等特点,如果未采用科学合理的包装、运输和配送方式,将会造成损坏,进而导致客户的满意度降低,增加快递企业的运营成本。因此,研究单个配送中心的从卖家至买家全过程链的生鲜冷链物流配送路径优化问题具有重要意义,具体的物流系统如图1所示。

图1 全过程链的物流系统网络结构

1.2 假设条件

1) 配送中心具有一定数量同一种型号的冷藏车。

2) 冷藏车需要从配送中心出发,当完成某次配送任务后,需要返回配送中心。

3) 各客户节点(买方)只能接受1辆冷藏车为其进行配送,且需求量不能超过冷藏车的最大载荷。

4) 各客户节点的地理坐标、时间窗上下限、产品需求量等均已知。

5) 卖方节点之间距离较近,近似为一个综合的卖方节点。

6) 村庄快递点、区域汇总点、分拨中心和配送中心的个数均唯一。

7) 卖方节点至村庄快递点、村庄快递点至区域汇总点、区域汇总点至分拨中心、分拨中心至配送中心之间路径唯一,且距离已知。

8) 配送中心前序节点的成本只考虑运输成本,装卸成本忽略不计。

1.3 模型

综上,可以构建一个考虑碳排放、燃油消耗、制冷、货损和违反各客户节点配送时间窗的惩罚成本的生鲜冷链物流配送优化模型,该模型以总成本最小为目标,主要包括从卖方节点到配送中心之间的成本和配送中心到买方节点间的成本,具体如下。

1.3.1 配送中心至买方节点之间的成本

1) 碳排放与燃油消耗成本C1。冷藏车在行驶的过程中,将会产生一定的碳排放和燃油消耗成本,二者均与燃油消耗量有一定的联系。本文采用负载估计法计算燃油消耗量,见式(1)。

(1)

式中:ρ(M)为冷藏车载有货物质量为M时的单位距离的燃油消耗量;ρ0为冷藏车空载时每千米消耗的燃油量;ρ*为冷藏车满载时每千米消耗的燃油量;M为货物质量;Q为冷藏车辆的最大载荷。

设快递员驾驶冷藏车完成所有客户节点的配送作业后的总燃油消耗量为f,基于式(1),构建总燃油消耗成本,见式(2)。

(2)

式中:i,j为节点,V为节点集合,i,j∈V,i,j=1,…,m,…,N,其中,1为配送中心,m为卖方综合节点;V’为客户节点集合,V’=V/{1,m};K为冷藏车辆集合,k为冷藏车辆,k=1,…,K;xijk为0-1变量,冷藏车从客户节点i至客户节点j时值为1,否则值为0;Qij为客户节点i到客户节点j时的生鲜货物载重量;Dij为客户节点i与客户节点j之间的距离。

基于式(1)和式(2),得到碳排放与燃油消耗成本,见式(3)。

C1=αf+υωf=(α+υω)f

(3)

式中:α为燃油(柴油)价格;υ为碳税;ω为碳排放系数。

2) 制冷成本C2。冷藏车辆在运输和配送过程中,具有可靠性、安全性等特点,能尽量保障生鲜农产品不受损坏。冷藏车的制冷成本主要由运输阶段与装卸阶段两部分构成,配送阶段的总制冷成本见式(4)。

(4)

式中:η1为在运输过程中冷藏车制冷剂消耗系数;η2为在装卸过程中冷藏车制冷剂消耗系数;tij为客户节点i到客户节点j的行驶时间;Ti为冷藏车在客户节点i的服务时间;yik为0-1变量,客户节点i的需求被冷藏车k满足时值为1,否则值为0。

3) 货损成本C3。生鲜农产品在运输和装卸的过程中容易造成产品的损坏或破损,因此,将生鲜农产品在运输和装卸过程中因产品损坏所造成的成本称之为货损成本,并将其考虑到目标函数中,为企业在运输和装卸搬运阶段制定生鲜农产品货损成本控制策略、提升配送质量等提供科学依据。生鲜农产品的总货损成本见式(5)。

(5)

式中:P为生鲜农产品的单位价格;qi为客户节点i的需求量;ti为冷藏车到达客户节点i的时间;t1为冷藏车从配送中心出发的时间;Q′i为冷藏车驶离客户节点i所剩余的生鲜货物质量;σ1为在运输过程中生鲜货物新鲜程度的衰减系数;σ2为在装卸过程中生鲜货物新鲜程度的衰减系数。

4) 惩罚成本C4。当冷藏车进行配送作业前,需要与客户商定一个可接受的时间范围,即时间窗。时间窗的左、右侧分别代表客户最早和最晚接收货物的时间。若快递员没有按照客户可接收货物时间窗的范围进行送货,将给予一定的惩罚,见式(6)。

(6)

式中:Ei为各客户节点可接受的时间窗下限;Li为各客户节点可接受的时间窗上限;ξ1为冷藏车到达各客户节点的时间早于各客户节点所能接受的时间窗下限时对应的惩罚系数;ξ2为冷藏车到达各客户节点的时间晚于各客户节点所能接受的时间窗上限时对应的惩罚系数。

1.3.2 卖方节点至配送中心之间的成本C5

由于生鲜农产品从卖家至村庄快递点、村庄快递点至区域汇总点、区域汇总点至分拨中心、分拨中心至配送中心这个过程中已经产生了运输成本,因此,需要将此过程成本加入到目标函数中,使总成本计算更加科学、合理。此过程的成本主要包括燃油消耗和碳排放成本、制冷成本和货损成本三部分,见式(7)。

(7)

1.3.3 目标函数

综上,在运输和配送过程中,基于上述成本构建目标函数,并给予各成本一个系数λi,λi为0-1变量,以便目标函数适用于不同应用场景,具体如下所示。

minZ=λ1C1+λ2C2+λ3C3+λ4C4+λ5C5=

1.3.4 约束条件

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

第1、第2个约束条件为各客户节点仅能允许某辆冷藏车出发和到达1次;第3个约束条件为冷藏车辆从配送中心出发在完成配送作业后回到配送中心;第4个约束条件为各客户节点仅能被某辆冷藏车访问1次;第5个约束条件为消除子回路;第6个约束条件为冷藏车从某一客户节点到另一客户节点应该满足的时间条件;第7个约束条件为冷藏车的载重容量限制。

2 算法设计

2.1 禁忌搜索算法设计过程

禁忌搜索算法(简称TS)的基本求解思想如图2所示。算法中涉及到的初始化、初始解构建、邻域解、禁忌表、藐视准则、适应度值计算等如下所示。

图2 禁忌搜索算法基本求解思想

2.1.1 算法初始化

读取所有数据,同时初始化每一条路径Ri(Ri∈E,i=1,…,n),将路径的末端节点VN设定为配送中心,且配送中心的起始节点V1的最早与最晚时间均为配送中心的最早到达时间E1,末端节点均为配送中心的最晚到达时间L1,同时计算任意两节点之间的欧氏距离。编码方式如下:配送路径节点集合V包含配送中心在内一共N个,起始节点和终止节点均用“1”表示,其余各节点分别用2至N-1表示,如图3所示。

图3 算法初始化过程

2.1.2 初始解构建

由于冷藏车容量有限制,因此,以满足冷藏车容量约束为目的进行随机初始化,即随机选取一个节点i插入到第R条路径中。如果超过冷藏车的容量限制约束,则将当前节点i插入到第R+1条路径,且插入路径的位置由该条路径中已经存在的各个节点的最早到达时间的升序所决定,如图4所示。

图4 初始解构建过程

2.1.3 邻域解

基于当前解x,采取插入算子产生所有邻域解,选取当前解中2条路径为例介绍具体插入操作:从第R条路径中随机选择节点i,再选择路径R+1,保证节点i插入路径R+1后,路径R+1满足冷藏车的容量约束,然后在路径R+1中,找到节点j,使得节点j满足Ej≤Ei≤Ej+1,如图5所示。

图5 邻域解求解过程

2.1.4 禁忌表与藐视准则

图6 禁忌表与藐视准则

2.1.5 适应度值计算

将模型中的目标函数值作为适应度值计算的依据,因此,把当前解xi带入模型中,将计算结果作为当前解的适应度值,适应度值越小,则表示解的质量越高。

2.2 禁忌搜索算法求解步骤

Step1:参数和算法初始化。输入优化模型中所需要qi,f,ti,M,α,ω等参数值,迭代次数I=0,最大迭代次数I_max=1000,禁忌长度T_L=20,禁忌表T=Φ。

Step2:随机产生初始解x,令最优解x*=x,最优值Z(x*)。

Step3:若G(x)-T=Φ,则停止计算,否则,令I=I+1,若I>I_max,则停止计算,输出x*和Z(x*)。其中,G(x)为x的邻域解集。

Step4:若Z(gI(x))=min{Z(g(x))∣g(x∈G(x)-T)},令x=gI(x),更新Z(x),Z(x)是当前邻域的最优目标函数值,其中,gI(x)为第I次迭代不在T中的邻域中的最优解。

Step5:若Z(gL(x))

Step6:若Z(x)

Step7:更新T表,转至Step3。

3 算例验证与结果分析

A快递公司位于辽宁省大连市,是一家以配送、运输为主体的第三方生鲜冷链物流公司,选择A快递公司其中一个配送中心B作为研究对象,B配送中心拥有10台同一种型号的冷藏车。该公司主要以运输和配送樱桃为主,每天将樱桃从卖方节点运送到配送中心,再由配送中心将货物尽可能保质保量地准时送到买方手中。目前,公司在运营过程中的基本参数信息见表1。

表1 具体参数信息

考虑到成本与配送路径选择有关,所以对车辆的路径进行合理规划,各客户节点位置、可接受时间窗、需求量等参数见表2和图7,配送中心序号为“1”,坐标位置为(40,50)。冷链物流企业根据实际到达配送中心的产品数量确定配送中心需要进行配送作业的冷藏车数量。由表2知,用户需求量为390 kg,因此,运输和配送阶段均需要2辆冷藏车辆即可完成此次配送任务。企业为了追求总成本最优,需要在卖方节点至配送中心、配送中心至各客户节点之间按照预先规划好的优化路径进行配送作业。

表2 配送小区位置

基于已构建的优化模型,采用禁忌搜索算法进行求解,运用C++编程求解,最优配送路径如图8所示,每次迭代的目标函数变化情况如图9所示。经计算,采用2辆冷藏车进行配送作业的最优配送方案的总路径长度为610.1 km,总成本为6585.1元,各分项成本见表3,其中,违反各客户节点时间窗的惩罚成本最大,占总成本的55.6%,制冷成本最少,占比1.1%。对比各次迭代下的目标函数(图9),可以发现在迭代初期,目标函数变化较大,得到解的质量较差,但随着迭代次数的增加,目标函数波动较小,逐渐平稳,逐渐接近最优解。

由于在配送阶段采用2辆冷藏车进行配送作业导致总成本过高,尤其是违反各客户节点时间窗的惩罚成本占总成本一半以上,因此,将导致顾客满意度严重降低,客户可能不再选用此公司进行配送,进而造成企业营业额的损失。因此,企业应调整产品配送方案,在客户需求不变的情况下,运输阶段仍采用2辆冷藏车,当产品运至配送中心后,应充分合理地运用配送中心已有冷藏车,模型、算法及其参数设置同上。经计算,最优配送路径如图10所示,由图10知,采用6辆冷藏车进行配送作业,可以使总成本达到最优。

经计算,采用6辆冷藏车进行配送作业的最优配送方案的总路径长度为760.5 km,总成本为4319.5元,各分项成本见表3,其中,碳排放与燃油消耗成本最大,占总成本的37.1%,同样,制冷成本最少,占比2.0%。对比各次迭代下的目标函数(图9),可以发现在迭代初期,目标函数变化较大,但是较2辆冷藏车的收敛速度快,随着迭代次数的增加,目标函数能够较快地接近最优解。

由表3知,在运输阶段,由于卖方(乡村)至配送中心道路为公路且路径唯一,客户需求不变,所采用冷藏车数量相同,因此从卖方节点至配送中心之间的运输成本相同。由于冷藏车增加了4辆,使得违反客户节点时间窗的成本较采用2辆冷藏车成本降低了77.7%,制冷成本增加了18.0%,货损成本降低了2.2%,碳排放与燃油消耗成本增加了59.7%,总成本降低了34.4%。虽然在配送阶段选择配送的冷藏车数量增加了,但是总成本降低了,对企业和客户而言,优势大于劣势。由于到达客户节点的准时率得到提升,客户的满意度进一步提高,进而提升了企业竞争力和利润。