考虑冷链-常温货品混合配送的路径优化问题.pdf

第 39 卷第 2 期2024 年 4 月系 统 工 程 学 报JOURNAL OF SYSTEMS ENGINEERINGVol.39 No.2Apr.2024考虑冷链常温货品混合配送的路径优化问题邓发珩1,梁卓斌2,秦虎1,王恺3(1.华中科技大学管理学院,湖北 武汉 430074;2.深圳大学土木与交通工程学院,广东 深圳 518060;3.武汉大学经济与管理学院,湖北 武汉 430074)摘要:针对冷链常温货物混合配送问题,建立了以总配送成本最小为目标的车辆路径优化模型,模型综合考虑了区域客户拥挤度,多车型,多服务时间窗的现实情况.提出了带有两种邻居解评价机制的禁忌搜索算法对问题进行求解,机制 1 综合解的各个指标为其设置了一个目标值向量,机制 2 则在目标值向量上增加了一个惩罚目标值.实验结果表明,禁忌搜索+机制 2 的优化效果最好,冷链混合配送模式能有效降低配送总成本.提出的模型和算法对于电商企业构建更低成本更高质量的新型冷链混合配送网络有一定指导作用.关键词:混合配送;车辆路径问题;禁忌搜索;多车型;多时间窗中图分类号:TP273文献标识码:A文章编号:10005781(2024)02025814doi:10.13383/ki.jse.2024.02.008Vehicle routing optimization for the mixed distribution of refrigeratedand ambient productsDeng Faheng1,Liang Zhuobin2,Qin Hu1,Wang Kai3(1.School of Management,Huazhong University of Science and Technology,Wuhan 430074,China;2.College of Civil and Transportation Engineering,Shenzhen University,Shenzhen 518060,China;3.Economics and Management School,Wuhan University,Wuhan 430074,China)Abstract:This paper focuses on a new mixed distribution problem of cold-chain and normal-temperatureproducts.In this problem,customers with multiple time windows in different congested areas are served byrefrigerated and non-refrigerated vehicles.The goal is to minimize the total cost of distribution.A tabu searchheuristic algorithm with two neighbor evaluation rules is proposed to solve the problem.The first evaluationrule considers an objective vector composed of several attributes of the solution,while the second one considersa penalty cost in addition to the objective vector.Computational experiments indicate that the tabu searchalgorithm with the second evaluation rule performs better than other proposed approaches,and cold chainmixed distribution mode can effectively reduce the total distribution cost.The proposed model and algorithmcan help e-commerce enterprises build a new cold chain mixed distribution network with lower cost and higherquality.Key words:mixed distribution;vehicle routing problem;tabu search;multi-type fleet vehicles;multi-timewindows收稿日期:20210312;修订日期:20240311.基金项目:国家自然科学基金资助项目(71821001;71971090;72171179).第 2 期邓发珩等:考虑冷链常温货品混合配送的路径优化问题2591引引引言言言近年来,我国冷链物流行业发展迅速,规模不断扩大.冷链产品配送的主要关注点在于如何有效缩短易腐食品从生产到交付的时间,从而最大化冷链物流公司的利润1.目前而言,冷链车辆主要应用在生鲜果蔬等易腐货品的运输配送上,而普通的常温货品则使用非冷链车辆进行运输.在实际的走访调研中也发现,目前大部分企业实行的都是常温货品与冷链货品分开配送的策略.而随着经济发展,在新场景下使用冷链车辆运输常温货品的混合配送模式也逐渐显现出合理性及优越性.一方面是由于用户端需求不再是单一的常温或者冷链货品.在对某知名快餐企业的物流供应进行调研时,员工谈到,其门店需求的货物一般有冷冻冷藏类如蔬菜、薯条、肉类和蛋糕等,而常温类则有清洁用品和玩具等.另一方面是单一的配送模式可能造成资源的浪费,例如,某物流供应商的相关负责人曾提到,目前很多配送的门店并不集中,需求又极具多样化,经常出现冷链车刚服务完某偏远门店,又需要派遣常温车为其配送常温货物的情况.这不仅导致多次出车造成资源浪费,还可能因为一个订单的多次配送导致客户满意度下降.此外,随着冷链运输技术的发展,多温车越来越普及,该类冷链车能够同时运行多种温度的货品,为混合配送模式提供了硬件基础.因此,本文对新场景下的冷链常温混合配送问题进行了研究,并探讨了混合配送模式的合理性及优势,重点解决以下问题:结合实际的物流服务场景,利用运筹优化的方法与思路,如何构建一套新型的多温物流混合配送解决方案,从而帮助企业降低物流运营成本.冷链路径优化问题是近年来车辆路径规划(vehicle routing problem,VRP)研究的热点,Song 等1以最大化客户满意度与最低运输成本为目标,研究了兼顾多车型和多类型易腐食品的冷链路径优化问题.Sahinyazan 等3研究了移动献血系统的冷链车辆路径问题,目标是将血液及时送回配送中心进行保存.Saif等4综合考虑了冷供应链中高能耗和制冷剂泄漏等因素可能对全球气温变暖带来的影响,提出了一种新型的混合仿真优化方法.方文婷等5对考虑节能减排的冷链物流路径优化进行了研究.冷链物流的研究大多集中在冷链单方面的物流配送问题,少有学者研究混合车型与冷链常温货品混合配送的 VRP 问题.文献2虽然在其研究中考虑了冷链车型与常规车型,且对比了两种车型下的客户满意度,但却没有考虑冷链车与常规车型的车辆成本.相比较文献中单一的冷链配送模式,本研究考虑了冷链产品与常温货物的混合配送模式.目前也有很多学者聚焦于混合车队车辆路径问题(multi-type fleet vehicle routing problem,MTFVRP),该问题同时考虑了车队规模与车型选择等因素,其中不同车型间的容量和购置成本不同,确定各车型的数量和对应尺寸是其关注的焦点.MTFVRP 问题一种常见的变种是考虑多配送中心、多车型和多产品的混合车辆路径问题6,7.另一方面,针对带时间窗的 VRP 问题(vehicle routing problem with time windows,VRPTW)的研究主要围绕最小化车辆行驶距离和最大化客户时间满意度来展开的.侯玉梅等8以缩短行驶里程,最小化车辆总行驶成本为目标建立了汽车整车物流 VRPTW 模型.Ali 等9则考虑最小化车辆行驶距离的同时最大化客户满意度,提出了带优先级的多目标 VRPTW 问题.基于同样的目标,VRPTW 问题还被应用到特殊电子废弃物的转运当中10.作为延伸,还有一部分学者在定向问题(oriented problem,OP)和团队定向问题(team oriented problem TOP)上考虑多时间窗的因素,通过融合 OP,TOP 和 VRP 的问题特点,考虑了多周期和多时间窗等因素,对多时间窗下的多周期定向问题进行求解11.上述文献从不同角度分别研究了混合车队和多时间窗的 VRP 问题,从研究对象看,少有文献同时考虑多车型和多时间窗两方面的因素;在模型纵向研究方面也没有综合考虑车辆油耗成本和客户地区密集程度的实际情况,而实际中面对区域客户分配不平衡问题,如何选调合适的车型避免过高油耗应当在优化模型中给予考虑.对比上述文献,本研究在问题模型中同时考虑了多车型、多时间窗以及客户地区密集程度等因素.在求解上述车辆路径优化问题的方法中,有精确类算法12,13和启发式算法14,15.精确类算法在面对大规模问题时,存在计算时间过长,消耗资源过多等问题;启发式算法中禁忌搜索算法(tabu search,TS)则在解260系 统 工 程 学 报第 39 卷决各类 VRP 问题上有着良好的表现.比如结合 TS 和列生成方法求解固定混合车队下的 VRP 问题16.融合变邻域搜索和 TS 的优势,设计混合算法用于求解多时间窗下 VRP 问题17.也有研究基于博弈的思想,采用混合变邻域禁忌搜索启发式方法,从满足 Nash 均衡条件的解的搜索空间中选择 Pareto 非占优解,该方法在处理最小化总旅行成本,最大化最小的客户效用,最大化最小的司机效用的多目标 VRP 问题上有着良好表现18.其它较多被用于 VRP 各类变种问题求解的方法还有局部搜索(local search,LS)19,自适应大邻域搜索(adaptive large neighborhood search,ALNS)20和 TS 嵌入遗传算法(genetic tabu search algorithm,GTSA)21等.现有的启发式算法更多考虑了如何加速局部搜索的速度,基于这种思想能较好地加快求解速度,但对于所得解的质量评价机制构建却难以更进一步.因此,本研究针对混合配送模式下的多车型 VRP 问题改进设计了禁忌搜索算法进行求解,提出了两种邻域评价机制,提高了搜索效率,并避免过早陷入局部最优或者随机漫游的现象.本研究在前人研究的基础上综合考虑了客户拥挤度、服务时间、配送车型以及货品特性等因素,提出了多车型、多时间窗和带客户拥挤度的冷链常温混合配送路径优化问题.本文首先建立问题的数学模型,然后基于禁忌搜索改进设计了两种算法机制对问题进行求解.最后,基于现实数据,采用不同规模的算例和多种方法的对比实验对算法的性能进行了验证.实验结果还表明本研究提出的混合配送模式能更好降低企业配送成本.2问问问题题题描描描述述述及及及数数数学学学模模模型型型图 1 一个配送方案的示例Fig.1 An example of the distribution solution现有一个冷链配送服务网络G=(N,E),其中N=0,n+1C为节点集合,E=(i,j)|i N,j N为边集合.车辆从配送中心0出发,服务完集合C中的所有客户后回到配送中心n+1.客户需求的货品有常温及冷链货品两种,冷链货品具有易腐性特点,运输只能采用专用的冷链车辆,常温货物则不受车辆类型限制.同时,某些客户处于拥挤区域,因道路及交通管制,需要安排小型车辆进行配送.基于以上考虑,客户又可细分为以下四个类型:非拥挤区域常温货品需求客户(Ca),拥挤区域常温货品需求客户(Cb),非拥挤区域冷链货品需求客户(Cc),拥挤区域冷链货品需求客户(Cd),其中C=CaCbCcCd.客户i C的货品需求量和卸货所需时间分别为di和si.同时,基于工作与休息的时间安排,客户有一个或者多个可服务的时间窗.客户i的时间窗集合为Ti,其中(ali,bli)Ti为客户i的第l个时间窗,ali(bli)则为该时间窗的最早(最晚)开始服务时间.此外,客户i Cc Cd需求的冷链货品存在保质期Li,冷链货品需要在保质期第 2 期邓发珩等:考虑冷链常温货品混合配送的路径优化问题261内送达.配送车队的车辆集合K由不同类型的车辆组成,包括:微型常规车辆(Ka),大型常规车辆(Kb),微型冷链车辆(Kc),大型冷链车辆(Kd),其中K=Ka Kb Kc Kd.不同车型之间的载重量与单位时间行驶成本也有所不同,车辆k K的最大载重为qk,其行驶单位时间的油耗成本为ok,一般而言,同尺寸下冷链车型油耗成本比常规车型高.记车辆行驶过边(i,j)的时间为tij,那么车辆k行驶过边(i,j)时耗油量所带来的行驶成本为ckij=oktij.物流企业需要依据客户拟定的服务时间窗,合理调度常温车辆和冷链车辆服务特定对象并规划车辆的行驶路径,确保在不晚于客户最晚时间窗的前提下尽可能降低车队油耗总成本.在问题描述中,单一客户可同时有常温和冷链货品的需求,本文在建模时,通过增加虚拟点的方式把这类客户看成是处于同一地理位置的两个客户,一个购买常温货品,一个购买冷链货品.图 1 给出了一个合法配送方案的图示,图中客户3+和 4 实际上为同一地理位置的两个客户,客户3+或者 4 为建模需要而新增的一虚拟点,两点行驶时间为 0,其中客户3+需求常温货品,客户 4 需求冷链货品.定义决策变量:xkij为 0-1 变量,在车辆k行驶过边(i,j)时为 1,否则为 0;wki为实数变量,表示车辆k开始服务客户i的时间点;yli为 0-1 变量,在车辆服务客户i且选用时间窗l时为 1,否则为 0.基于以上的定义,构建问题的数学模型为MinkKiNjNckijxkij,(1)s.t.kKjNxkij=1,i C,(2)iCjNdixkij6qk,k K,(3)jNxk0j=1,k K,(4)iNxkihjNxkhj=0,h C,k K,(5)iNxki,n+1=1,k K,(6)wki+tij+si wkj6(1 xkij)M,i,j N,k K,(7)aliyli6wki6bliyli+(1 yli)M,l Ti,i N,k K,(8)lTiyli=1,i N,(9)iCcCdjNxkij=0,k Ka Kb,(10)iCbCdjNxkij=0,k Kb Kd,(11)wki6Li,k K,i Cc Cd,(12)xkij 0,1,i,j N,k K,(13)yli 0,1,i N,l Ti,(14)wki R,i N,k K.(15)在上述模型中,M为充分大的正数,目标函数(1)表示最小化总的车辆行驶成本,即行驶过各边的不同类型车辆油耗成本之和.约束(2)表示每个客户节点的出度为 1,确保每个客户仅被一辆车服务一次.约束(3)确保每辆车运输的货物总重量不超出其容量.约束(4)保证了车辆从配送中心 0 出发.约束(5)表示车辆访问完一个客户后必须从该客户处出发访问下一个点.约束(6)保证车辆在服务完后最终回到配送中心n+1.约束(7)保证车辆在上一个客户点的开始服务时间加上在该客户处的服务时间以及两点之间的行驶时间必262系 统 工 程 学 报第 39 卷须小于等于下一个客户的开始服务时间,如果车辆没有经过该边,那么该约束将被大M松弛.约束(8)保证了货物在客户的某个时间窗内被配送完毕.约束(9)确保车辆只能在客户的多个时间窗内选择一个进行服务.约束(10)确保常规车辆不能运送冷链货品.约束(11)确保大型车辆不能派送处于拥挤地区的客户.约束(12)确保冷链货品在其保质期内送达.约束(13)约束(15)规定了各个决策变量的取值范围.3算算算法法法设设设计计计带客户拥挤度的多车型多时间窗冷链常温货物混合配送路径优化问题是一个 NP-hard 问题,禁忌搜索算法(tabu search)在各类组合优化问题的求解当中有很好的表现,例如带时间窗的车辆路径问题22,23、仓库选址、路径规划问题24和混合流水车间调度优化问题25等.因此提出了带有两种邻居解评价机制的禁忌搜索算法以有效求解多车型多时间窗的冷链常温货物混合配送路径优化问题.本研究中提出的禁忌搜索算法主要由初始解生成、邻域操作、禁忌表、禁忌准则以及邻居解评价机制等组成.3.1插插插入入入构构构造造造法法法生生生成成成初初初始始始解解解受 Li 等10的启示,本研究采用插入构造法生成初始解.在混合配送模式中,为使得常温货品能够被冷链车辆配送,而常温车辆无法运输冷链货品,以及大型车辆无法进入拥挤地区,本研究提出了“货物相容性”的概念.初始定义,如果路径rk上的车辆k能对客户i进行服务,那么就称rk与客户i相容.例如,微型冷链车辆的路径与有冷链货品需求的客户是相容的,而大型车辆的路径与拥挤地区的客户是不相容的.对于初始解s0的一条路径rk,其车辆为k,载重为l(rk),将客户i插入rk上的位置p后s0的行驶总成本变化量为c(rk,i,p).插入构造法按顺序不断地从未插入客户集合Uc里取出一个客户,并将其插入到合适的位置,如图 2 所示.具体步骤如下:步骤 1取出Uc中的第一位客户i.步骤 2遍历所有与客户i相容的路径,找出第一条满足l(rk)+di6qk的路径rk.如果能找到,跳到步骤 4;否则,进入下一步.步骤 3在所有与客户i相容的路径中选择一条路径rk,使得l(rk)+di qk最小.步骤 4遍历rk中所有位置,选择一个位置p,使得c(rk,i,p)最小,将客户插入位置p.步骤 5重复步骤 1步骤 4,直至Uc为空.图 2 插入构造法图例Fig.2 An example of cheapest insertion heuristic3.2邻邻邻域域域结结结构构构和和和邻邻邻域域域生生生成成成本研究的禁忌搜索算法改进设计了 4 个邻域操作17,26,分别为 Relocate,Exchange,2-OptExchange 和 2-Opt.Relocate 操作对客户重定位.对于解sc,移除其路径rk上的客户j后,将客户j插入到另一条路第 2 期邓发珩等:考虑冷链常温货品混合配送的路径优化问题263径rl的位置p时,sc的目标值变化量为f(rk,j,rl,p).原路径rk客户j如图 3(a)所示;(a)为原路径rk和rl,(b)为 Relocate(j,rl)操作后得到的新路径rk和rl,算法评估被插入路径rl所有位置,选出位置p使得f(rk,j,rl,p)最小,插入客户j,生成邻居解,如图 3(b)所示.Exchange 操作交换两条路径上的两个客户以生成一个邻居解.原路径为rk和rl,如图 4(a)所示;交换两条路径上的客户i和j,得到的新路径rk和rl,如图 4(b)所示.2-OptExchange 和 2-Opt 是针对一条路径的邻域操作,其中 2-OptExchange 仅交换同一条路径上的两个客户.原路径rk及客户i和j如图 5(a)所示,对客户i和j执行 2-OptExchange 操作后,客户i和j位置互换,如图 5(b)所示.2-Opt 操作交换同一条路径上的两个客户i和j,并将处于客户i和j之间的客户进行翻转.原路径rk如图 5(a)所示;对客户i和j执行 2-Opt 操作后,新路径rk如图 5(c)所示.图 3 Relocate 算子Fig.3 Relocate operator图 4 One-point exchange 算子Fig.4 One-point exchange operator图 5 2-OptExchange 算子和 2-Opt 算子Fig.5 2-OptExchange operator and 2-Opt operator表 1 邻域操作集合生成Table 1 Generations of neighborhood operation邻域操作生成的邻域操作集合合法性约束Relocate1=(i,rl)|i rk,rk sc,rl sc,rk=rli 与 l 相容Exchange2=(rk,i,rl,j)|i rk,j rl,rk sc,rl sc,rk=rli,j 分别与 rl,rk相容2-OptExchange3=(rk,i,j)|i,j rk,p(i,rk)+p(j,rk)=n(rk)+1,rk sc2-Opt4=(rk,i,j)|i,j rk,p(i,rk)+p(j,rk)=n(rk)+1,rk sc定义一个邻域操作合法是指经过该操作后的路径与客户是相容的,否则为不合法.注意到在生成 Relocate 和 Exchange 操作的过程中有可能会出现路径和客户不相容的情况,例如 Relocate 操作有可能将某个处于拥挤地区的客户插入到了大型车辆的路径上,Exchange 操作有可能将有冷链货品需求的客户交换到常规车辆的路径上.而 2-OptExchange 和 2-Opt 操作的都是同一路径上的客户,不存在上述的相容性问题.算法在生成邻域操作时,只生成合法的邻域操作,这样能极大地降低邻域操作的生成数量,从而减少邻域操作的评估时间,加快算法运行的速度.在当前解sc中,用p(i,rk)表示客户i在路径rk中的位置(从 1 开始),264系 统 工 程 学 报第 39 卷n(rk)表示路径rk的客户总数.各邻域操作生成的集合如表 1 所示,合法性约束保证了生成操作的合法性.值得注意的是,随着客户数的增长,Exchange 操作的邻域规模将会变得非常巨大,生成邻域的过程需要消耗大量时间.为了加快速度,算法按照一定比例对生成的 Exchange 操作集合2进行随机采样得到2,采样的比例设置为.同时,采样机制能增加算法的随机性,避免算法过早陷入局部最优,增加算法的全局寻优能力.最后,算法根据1 2 3 4生成当前解sc的邻域 neighborsPool(sc).由于不同解中客户的服务顺序有可能不同,因此同一个客户所使用的时间窗在不同解中有可能不同.3.3禁禁禁忌忌忌表表表和和和藐藐藐视视视准准准则则则为了防止算法过早陷入局部最优,禁忌搜索算法允许使用一个或者多个禁忌表.针对各个不同的邻域操作,本文的禁忌搜索算法共设计了两个禁忌表.禁忌表 1 用于禁忌 Relocate 操作,它禁忌了那些在禁忌步长内试图将移除的客户再次插入到原路径的 Relocate 操作.禁忌表 2 用于禁忌 Exchange,2-OptExchange和 2-Opt 这 3 个邻域操作,它禁忌了在禁忌步长内对两个客户再次执行相同的邻域操作,禁忌的步长用参数tbTe表示.藐视准则允许解除对一个操作的禁忌,当经过该操作以后获得了一个比当前解更优的邻居解时,藐视准则生效,对该操作的禁忌解除.3.4邻邻邻居居居解解解评评评价价价机机机制制制当前解在经过邻域操作(如 Relocate,Exchange 等)可能会形成不可行的邻居解(车辆超载或未在时间窗内送达),因此在评价邻居解时,本文通过对不可行解的目标值增加相应的惩罚(超载惩罚和时间窗惩罚),设计了两种评价机制.对于解的集合s而言,定义c(s)表示解s中路径的行驶总成本,q(s)表示解s中路径的车辆超载总量,w(s)表示解s中路径的时间窗违背总量,rk表示解s中的一条路径,其车辆为k;t(rk)表示rk的车辆行驶时间;ck表示rk上车辆的单位时间行驶成本;T(i)表示车辆实际到达客户i的时间点.总油耗成本为c(s)=rkst(rk)ck.(16)货物超载惩罚为q(s)=rksmax0,irkdi qk.(17)时间窗违背惩罚为w(s)=rksmax0,irkmax0,T(i)minbli,Li,(18)其中l为车辆在T(i)下选择的时间窗违背量最小的时间窗,如果存在多个违背量相等的时间窗,则l取最早的时间窗,Li为货品i的保质期.令f(s)为解s的目标值,表达式为f(s)=c(s)+q(s)+w(s),其中和是初始值分别为0和0的动态参数,它们会在每一次迭代中更新.如果q(s)=0,/(1+);如果q(s)0,(1+).如果w(s)=0,/(1+);如果w(s)0,(1+).其中为小于 1 的固定参数,如果或者超过上界,那么重置其值为.注意到本研究的禁忌搜索算法并没有将解空间限制在可行的范围内进行搜索,而是通过对目标值增加惩罚值,使算法不断朝着降低目标值的方向进行搜索,这样做有助于增加搜索的多样性,从而找到更高质量的解.评价机制 1 的设定如下,算法为每一个解s设置了一个目标值向量f(s),c(s),q(s),w(s),在比较两个解s1和s2时,首先比较f(s1)和f(s2),如果相等,再比较c(s1)和c(s2),以此类推.为了增加算法搜索的多样性,参照 Cordeau 等27的做法,本文在评价机制 1 的基础上,为每一个解s增加了一个惩罚目标值p(s),设计了评价机制 2.假设当前解为s,其经过一个邻域操作opt0后得到邻居解 s.第 2 期邓发珩等:考虑冷链常温货品混合配送的路径优化问题265如果f(s)6p(s),那么p(s)=f(s);如果f(s)p(s),则p(s)=f(s)+|K|+|C|f(s)B(s,opt0),其中为惩罚系数,|K|和|C|分别表示可用车辆总数和客户总数,B(s,opt0)表示对解s总共执行邻域操作opt0的次数.评价机制 2 在 1 的基础上为解s的目标值向量增加了惩罚目标值,即p(s),f(s),c(s),q(s),w(s).比较两个解s1和s2的规则和评价机制 1 相同.特别地,当s为初始解时,令p(s)=+.在禁忌搜索中,每一次迭代算法选取一个邻居解并将当前解转移到邻居解上,评价机制能够找出在目标值一样的情况下,具有较高潜力的邻居解进行转移,最终找到更高质量的解.遍历邻域,寻找最优邻居解的过程如下:步骤 1取出当前解邻域 neighborsPool(sc)中的第一个邻居解s0,sb s0.步骤 2从 neighborsPool(sc)取出一个邻居解s,使用评价机制判断,如果s比sb更优,则跳到步骤 3;否则,跳到步骤 4.步骤 3如果sb没有被禁忌但是s被禁忌了,丢弃s;否则,sb s.步骤 4如果sb被禁忌了但s没有被禁忌,sb s;否则,丢弃s.步骤 5重复步骤 2步骤 4,直至 neighborsPool(sc)为空.3.5算算算法法法终终终止止止条条条件件件对于算法终止条件,求解过程不固定算法最终的迭代次数,而是采取最优改进增加迭代的方式.初始时,设置禁忌搜索算法的迭代次数为 4 000,如果算法在最后的 500 次内能将最优解改进提高 0.1%,则让算法总的迭代次数由初始迭代次数自动增加 1 000 次.4实实实验验验结结结果果果及及及分分分析析析4.1实实实验验验说说说明明明本研究的测试算例基于现实数据生成,首先,本文选取了武汉市的某些区域作为服务网络,以区域内的便利店作为客户,再利用百度地图换算出各个客户之间的真实路线距离以及车辆行驶时间.生成算例时,首先随机指定 30%的客户需求为冷链货品,再随机令30%的客户处于拥挤地区.配送中心的工作时间均为 8h.每个客户最多拥有 3 个时间窗,且拥有 1,2,3 个时间窗的客户比例分别为60%,30%10%,每个时间窗均在区间0,480,同一客户的多个时间窗不能重叠,客户需求量在区间1,50内随机生成,客户服务时间取 50 min.算例中设置了 4 种类型的车辆,分别为微型常规车、大型常规车、微型冷链车和大型冷链车.表 2 Tabu search 参数设置Table 2 Initial parameter value of tabu search参数可选值最终取值参数说明20%,60%,100%30%Exchange 邻域采样比例00,1,10 000 0001 的初始值00,1,10 000 0001 的初始值0.001,0.005,0.01,0.050.005固定参数10 000 00010 000 000 和 上限0,0.1,0.5,10.1 和 重置值0,0.1,0.5,10.5固定参数tbTe5,10,1510禁忌步长研究提出的禁忌搜索算法采用 JAVA 单线程的模式实现,测试环境配置为 Intel(R)Core(TM)i5-7300HQ2.50 GHz CPU,8 GB RAM.为了评测算法的效果,同时设计了自适应大邻域搜索算法(ALNS),用以和本文的禁忌搜索算法(TS)进行对比.由于算法存在随机因素,因此所有测试均运行 10 次取平均值,CPLEX 的运行时间上限设置为 1 h.266系 统 工 程 学 报第 39 卷4.2实实实验验验结结结果果果分分分析析析Tabu Search 的算法参数设置如表 2 所示,相关参数在候选值中通过 irace 训练确定28.对于不同客户数下的 20 组小规模算例,分别对采用两种不同评价机制的 Tabu Search 进行了测试,并将测试结果与 CPLEX和 ALNS 的测试结果进行比较.小规模算例的实验结果如表 3 所示,加*号表示 CPLEX 在规定时间内找到的可行解,空值表示无法找到可行解.GAP1 列表示 ALNS 与 CPLEX 解的偏差,GAP2 列表示 Tabu Search+评价机制 1(简称 TS1)解与 CPLEX 解的偏差,GAP3 列表示 Tabu Search+评价机制 2(简称 TS2)解与 CPLEX 解的偏差.表 3 小规模算例的实验结果Table 3 Comparison results on proposed algorithm instances(small scale)算例名称 客户数CPLEXALNSGAP1TS1GAP2TS2GAP3最优解时间/s满意解 时间/s满意解 时间/s满意解 时间/sHSN066248.430.09248.430.510.00%248.430.070.00%248.430.130.00%JHN066205.510.49205.510.540.00%205.510.060.00%205.510.110.00%HSN088365.550.34365.550.650.00%365.550.110.00%365.550.130.00%HSN1010376.272.05378.381.020.56%378.940.220.71%376.270.210.00%WCN1010262.880.33262.880.930.00%262.880.190.00%262.880.190.00%HSN1212452.231.19452.231.120.00%452.230.290.00%452.230.280.00%HSN1414470.8212.38470.821.350.00%522.390.3510.95%470.820.320.00%JHN1414336.407.23337.521.360.33%336.400.330.00%336.40.330.00%HSN1616603.0622.33604.381.490.22%643.360.436.68%603.060.480.00%WCN1616444.7523.84444.751.520.00%444.750.370.00%444.750.360.00%HSN1818686.80190.86687.381.800.08%686.800.430.00%690.970.460.61%JHN1818416.731 058.88418.531.660.43%426.290.462.29%416.730.480.00%HSN2020862.04*3 600.00866.142.040.48%871.490.561.10%862.040.590.00%WCN2020587.37933.80589.792.120.41%0.55587.370.510.00%HSN30301 449.53*3 600.00 1 437.403.660.84%1 497.281.263.29%1 435.601.380.96%WCN3030609.10*3 600.00613.793.790.77%622.941.222.27%609.101.140.00%HSN40401 956.29*3 600.00 1 893.635.553.20%2 014.812.042.99%1 892.652.33.25%JHN4040769.41*3 600.00769.805.460.05%813.732.075.76%763.862.050.72%HSN50502 466.33*3 600.007.773.172 318.993.645.97%JHN50501 306.00*3 600.007.903.531 250.853.044.22%从表 3 可以看出,在 20 个小规模算例中,CPLEX 在规定的时间内求得 13 个算例的最优解,而其余 7 个算例只找到了可行解.从对比结果中可以看出,TS2 的总体表现要优于 ALNS 和 TS1.在 20 个算例中,TS2除了算例 HSN18 比 CPLEX 稍差外,其余算例均与 CPLEX 持平或者优于 CPLEX;而 TS1 在 8 个算例中与 CPELX 持平,有 3 个算例找不到可行解,其余 9 个算例比 CPLEX 差;ALNS 有 9 个算例与 CPLEX 持平或者更优,其余 11 个算例中有 9 个比 CPLEX 差,2 个找不到可行解.从表 3 的求解时间可以看出,随着问题规模的增加,CPLEX 的求解时间几乎呈指数式增长,而本文的算法,无论是使用评价机制 1 还是评价机制 2,其时间增长都是均匀的线性增长.此外,对于除算例 HSN06 外的其他算例,两种机制下的算法求解时间均低于 CPLEX 和 ALNS 的求解时间.上面的对比结果验证了本文的 Tabu Search+评价机制 2 对于小规模问题是可靠且有效的.再次用 TS1 和 TS2 对中等和大规模的算例进行了测试,算法的参数设置和表 2 一致,算法的测试结果如表 4 所示,CPLEX 列表示 CPLEX 在 1 h 内求得的可行解.GAP4 列表示 ALNS 解与 TS2 解的偏差,GAP5 列表示 TS1 解与 TS2 解的偏差,GAP6 列表示 CPLEX 解与 TS2 解的偏差.从表 4 中可以看出,在测试的算例中,除个别算例 ALNS 和 TS1 无法找到可行解外,其余算例 TS2,ALNS 和 TS1 的求解结果均优于 CPLEX,而 TS2 总体上要优于 ALNS 与 TS1.ALNS 在 4 个算例中取得了比 TS2 更优的结果(偏差5%以内),有 3 个算例无法找到可行解,其余 14 个算例的解均比 TS2 差.TS1 有 1 个算例无法找到可行解,其第 2 期邓发珩等:考虑冷链常温货品混合配送的路径优化问题267余 20 个算例的结果均比 TS2 更差,但由于 TS2 使用了惩罚机制,使搜索更加多样化,其求解时间相对 TS1也更长.表 4 中等和大规模算例的测试结果Table 4 Comparison results on proposed algorithm instances(medium and large scale)算例名称客户数TS2ALNSGAP4TS1GAP5CPLEXGAP6满意解时间/s满意解时间/s满意解时间/sHSN60601 844.887.921 850.1310.390.28%2 024.737.129.75%2 194.1618.93%JHN6060970.518.801 011.4310.184.22%1 023.80