基于混合启发式算法的快递末端选址路径优化研究.pdf

基于混合启发式算法的快递末端选址路径优化研究*孙睿男1,初 翔1,陈 昱2,闫明宁1(1.大连海事大学航运经济与管理学院,辽宁 大连 1 1 6 0 2 6;2.大连海事大学综合交通运输协同创新中心,辽宁 大连 1 1 6 0 2 6)摘 要:传统快递末端配送模式存在快递网点建设冗余、派送路径重叠等问题,而共同配送模式可有效解决此类问题,因此对共同配送模式下同时收派件且收件需求为不确定情形的快递末端网点选址路径问题进行研究。首先,建立了两阶段数学优化模型,引入随机机会约束来处理收件量不确定的问题。其次,设计基于遗传算法和自适应大邻域搜索算法的混合启发式算法。最后,通过数值实验表明:所设计的混合算法比传统遗传算法具有较快的收敛速度和较好的求解质量;决策者对随机需求下的优化方案风险接受程度过高或过低都会导致成本上升;随客户收派量之比的增加,快递末端配送成本呈先降低后增高的趋势;采用最近网点返回策略可有效降低企业配送成本。关键词:共同配送;选址路径问题;遗传算法;自适应大邻域搜索算法;快递网点中图分类号:T P 1 8文献标志码:Ad o i:1 0.3 9 6 9/j.i s s n.1 0 0 7-1 3 0 X.2 0 2 4.0 1.0 1 7R e s e a r c h o n p a t h o p t i m i z a t i o n o f e x p r e s s t e r m i n a l l o c a t i o n b a s e d o n h y b r i d h e u r i s t i c a l g o r i t h mS UN R u i-n a n1,CHU X i a n g1,CHE N Y u2,YAN M i n g-n i n g1(1.S c h o o l o f S h i p p i n g E c o n o m i c s a n d M a n a g e m e n t,D a l i a n M a r i t i m e U n i v e r s i t y,D a l i a n 1 1 6 0 2 6;2.C o m p r e h e n s i v e T r a n s p o r t a t i o n C o l l a b o r a t i v e I n n o v a t i o n C e n t e r,D a l i a n M a r i t i m e U n i v e r s i t y,D a l i a n 1 1 6 0 2 6,C h i n a)A b s t r a c t:T h e t r a d i t i o n a l e x p r e s s t e r m i n a l d i s t r i b u t i o n m o d e h a s p r o b l e m s s u c h a s r e d u n d a n t c o n-s t r u c t i o n o f e x p r e s s o u t l e t s a n d o v e r l a p p i n g d e l i v e r y p a t h s,a n d t h e j o i n t d i s t r i b u t i o n m o d e l c a n e f f e c-t i v e l y s o l v e t h e s e p r o b l e m s.T h e r e f o r e,t h i s p a p e r s t u d i e s t h e l o c a t i o n p a t h o f e x p r e s s t e r m i n a l o u t l e t s i n t h e c a s e o f s i m u l t a n e o u s r e c e i v i n g a n d d i s p a t c h i n g a n d u n c e r t a i n r e c e i v i n g d e m a n d u n d e r t h e j o i n t d i s-t r i b u t i o n m o d e l.F i r s t l y,a t w o-s t a g e m a t h e m a t i c a l o p t i m i z a t i o n m o d e l i s e s t a b l i s h e d t o d e a l w i t h t h e p r o b l e m o f u n c e r t a i n r e c e i p t v o l u m e b y i n t r o d u c i n g r a n d o m c h a n c e c o n s t r a i n t s.S e c o n d l y,a h y b r i d h e u-r i s t i c a l g o r i t h m b a s e d o n g e n e t i c a l g o r i t h m a n d a d a p t i v e l a r g e n e i g h b o r h o o d s e a r c h a l g o r i t h m i s d e-s i g n e d.F i n a l l y,n u m e r i c a l e x p e r i m e n t s s h o w t h a t t h e d e s i g n e d h y b r i d a l g o r i t h m h a s a f a s t e r c o n v e r-g e n c e s p e e d a n d b e t t e r s o l u t i o n q u a l i t y t h a n t h e t r a d i t i o n a l g e n e t i c a l g o r i t h m.T o o h i g h o r l o w r i s k a c-c e p t a n c e o f t h e o p t i m i z a t i o n s c h e m e i n t h e r a n d o m d e m a n d e n v i r o n m e n t w i l l l e a d t o t h e i n c r e a s e o f c o s t.W i t h t h e i n c r e a s e o f t h e r a t i o o f c u s t o m e r r e c e i v i n g a n d d i s p a t c h i n g v o l u m e,t h e c o s t o f e x p r e s s t e r m i n a l d i s t r i b u t i o n f i r s t d e c r e a s e s a n d t h e n i n c r e a s e s,T h e n e a r e s t o u t l e t r e t u r n s t r a t e g y c a n e f f e c t i v e l y r e d u c e t h e d i s t r i b u t i o n c o s t o f e n t e r p r i s e s.K e y w o r d s:j o i n t d i s t r i b u t i o n;l o c a t i o n r o u t i n g p r o b l e m;g e n e t i c a l g o r i t h m;a d a p t i v e l a r g e n e i g h b o r-h o o d s e a r c h a l g o r i t h m;e x p r e s s o u t l e t s*收稿日期:2 0 2 2-0 4-0 4;修回日期:2 0 2 2-1 0-1 2通信地址:1 1 6 0 2 6 辽宁省大连市大连海事大学航运经济与管理学院A d d r e s s:S c h o o l o f S h i p p i n g E c o n o m i c s a n d M a n a g e m e n t,D a l i a n M a r i t i m e U n i v e r s i t y,D a l i a n 1 1 6 0 2 6,L i a o n i n g,P.R.C h i n a C N 4 3-1 2 5 8/T PI S S N 1 0 0 7-1 3 0 X 计算机工程与科学C o m p u t e r E n g i n e e r i n g&S c i e n c e第4 6卷第1期2 0 2 4年1月 V o l.4 6,N o.1,J a n.2 0 2 4 文章编号:1 0 0 7-1 3 0 X(2 0 2 4)0 1-0 1 5 9-1 11 引言近年,快递数量快速增长,给快递末端网点及末端配送环节带来了巨大的压力。目前,快递配送末端由于各自为政的配送模式,导致配送成本居高不下,而共同配送模式可以有效降低末端配送成本1。因此,在共同配送模式下,合理规划快递网点选址及配送路径问题具有重要的研究意义。有关选址路径问题研究中,王琪瑛等2研究了电动车辆选址路径问题;胡大伟等3研究了两阶段的选址路径问题;A r s l a n4从客户覆盖范围的角度研究了选址路径问题。K i n a y等5对充电站选址问题进行了研究。O z b a y g i n等6对动态路径问题进行了研究。上述选址路径研究多假设客户需求为已知的情况,而在快递实际配送过程中,一般其派件量为已知,而收件量为不确定的情形,关于随机选址路径问题相关文献也较为丰富,如需求不确定型7 9、时间不确定型1 0、距离不确定型1 1、场景不确定型1 2及多重因素不确定型1 3。针对末端快递选址路径的研究文献也较为丰富,如d e G i o v a n n i等1 4针对快递货运路径规划问题进行研究,建立了综合考虑车辆容量、时间窗约束的数学模型。B e r g m a n n等1 5对城市配送最后一公里问题进行研究,建立了考虑车辆容量的数学模型。许闯来等1 6对快递配送网络进行研究,在建立模式时考虑了配送车辆载荷约束。裴利奇等1 7研究了快递中转站选址问题,建立了考虑快递中转站容量和配送车辆载荷约束的数学模型。L i等1 8对快递企业配送包裹问题进行了研究,在建模时加入了载具容量约束。Y a n等1 9建立了城市动态快递调度模型,在模型中也考虑了容量约束。姬杨蓓蓓等1 9针对快递末端配送网络优化,建立了考虑车辆载荷约束的选址路径模型。可以看出,以上对快递末端网点配送的研究都只考虑配送车辆的载重约束,均未考虑快递配送与物流配送之间的差异。快递配送与物流配送之间的区别主要有以下2点:(1)快递配送除了对快件重量有限制之外,对快件的体积也有一定的约束。如贺冰倩等2 1对快递收派路径规划问题进行了研究,在建立模型时同时考虑了快件容量和体积约束。(2)在物流配送中,末端配送基本使用轻型厢式货车作为配送载具;而快递配送方式大多为快递员进行末端配送,配送成本多为人工成本。梳理上述文献可知,相关研究已取得一定成果,但还存在以下几点不足:(1)大部分文献并未考虑到快递同时收派件,且需求随机的情况;(2)配送车辆返回策略均为返回原出发网点,该返回策略易造成较高的配送成本;(3)所建模型大部分未考虑快递末端配送的实际特性,即快递配送与物流配送之间的差异性。因此,基于以上几点,本文结合共同配送模式特点,考虑快递配送与物流运输之间差异性,以人工成本为目标函数,引入随机机会约束解决需求随机问题,基于最近网点返回策略,建立包含快件重量、体积以及配送员最大时长等约束的数学规划模型;并设 计基于遗传 算法和自适 应大邻域搜 索A L N S(A d a p t i v e L a r g e N e i g h b o r h o o d S e a r c h a l-g o r i t h m)算法的混合启发式算法,对随机需求下快递网点选址路径问题进行研究。所得结论可为快递企业提供相应管理启示,并为后续对随机需求选址路径研究提供方法参考。2 共同配送随机L R P模型建立2.1 问题描述本文所研究问题可描述为在某区域内存在多家快递企业的快递网点,后文简称为网点,客户点和网点的位置已知,所有节点集合A=WC,网点集合为W=1,2,n,si为网点i的建设成本,1in,网点最大容量为Qw(wW),实际容量为Qi,客户点集合为C=n+1,n+2,n+m。每个客户点派件量是确定的,收件量为不确定的情况,dw j和dv j分别为客户点j(n+1jn+m)的派件重量和体积,rw j和rv j分别为客户点j的收件重量和体积,假设每个客户的收件量相互独立且均服从相同泊松分布,E(rw j)和E(rv j)分别为收件重量和体积的期望值。di j为任意网点i和客户点j之间的距离,dj(j+1)为任意客户点j和客户点j+1间的距离,其余变量均用此方法表示。K=1,2,为配送车辆集合,V为配送车辆行驶速度。假设配送时,车辆一直保持匀速行驶,Qk和Vk分别为配送车辆k(1ka)的最大容量和最大体积,Qi j k为配送车辆k在网点i和客户点j之间的载量,Vi j k为车辆k在网点i和客户点j之间的配送体积。cd和cr分别为配送员派件和收件的单位人工成本,cs为单位时间配送的人工成本,Tp为配送员单次最大配送时长。决策变量Zi0,1,若Zi=1,表示在网点i建立快递网061C o m p u t e r E n g i n e e r i n g&S c i e n c e 计算机工程与科学 2 0 2 4,4 6(1)点,否则相反;决策变量Yi j0,1,若Yi j=1,表示客户点j被网点i服务,否则相反;决策变量Xi j k0,1,若Xi j k=1,表示配送车辆k从网点i经过客户点j,否则相反。快递员从网点出发进行派送,派送完成后返回距离最近的网点。如何合理地选择快递网点及安排派送路径是本文研究核心,主要目的是降低成本,因此以网点选址路径总成本为目标函数,建立两阶段双层规划模型。第1阶段中上层模型考虑网点选址成本最低,包含建设成本和人工成本,下层模型考虑配送距离最短。因客户点收件量为不确定的随机变量,所以有可能出现第1阶段所选网点容量无法满足客户点的实际需求量或配送车辆容量和体积无法满足客户点的需求量的情况,从而导致预优化阶段方案失效。此时就需要第2阶段重新优化,重优化阶段采用失败点前序点重优化策略,以此确定末端快递网点建设及配送路径规划,减少物流整体配送成本。2.2 数学模型2.2.1 上层模型假设某一预优化方案中客户点集合C,均由某一网点对其派送,在服务完前j-1个客户点后,现要确定客户点j+1是否也由该网点进行派送,采用随机机会约束机制进行判断,此时该网点的剩余载荷量Qj=Qw-(dw1+dw2+dw j)-(rw1+rw2+rw j),因收件量rj为随机变量,此时通过随机机会约束机制判断是否由该网点服务客户点j,即Prw jQj-dw j,为预先设定的风险偏好值,其表示决策者在不确定情况下对风险的可接受程度。若决策者对风险的接受程度不高,更想保证预方案的成功率,则应取较高值;反之,应取较低值,(0,1,dj和rj分别为客户点j的派件量和收件量。式(1)表示上层模型目标函数,包含了快递网点的建设成本和人工成本;式(2)表示网点建设数量的约束条件;式(3)表示网点载荷量的随机规划约束;式(4)表示决策变量,为0-1变量。目标函数式中Z、Y和X均为所求的决策变量。M i nZi,Yi j,Xi j kF1=iWsiZi+cdiWjCdjYi j+criWjCrjYi j+csiwjCdi jVXi j k+dj(j+1)VXj(j+1)k (1)s.t.iWZi1(2)Prw jiWYi jQj-dw j,jC(3)Yi j0,1,Zi0,1,iW,jC(4)2.2.2 上层模型随机机会约束等价处理上层规划模型中,约束条件式(3)可以推导为确定型等价形式,式(3)可变为:Prw jQi-dw j=P iWjCrw jYi jQi-iWjCdw jYi j(5)因收件量rj为随机变量,且相互独立,由中心极限定理可知网点服务的客户收件量之和近似服从正态分布,期望值Ev=iWjCE(rw j)Yi j,标准差Sv=Ev,令Qi-iWjCdw jYi j=T,则式(5)可转化为:PiWjCrw jYi j-EvSvT-EvSv (6)假设常数为的分位点,则式(6)可转化为:PiWjCrw jYi j-EvSv =(7)因此,由式(5)和式(7)可知:Sv+EvT(8)T=Q-iWjCdw jYi j(9)将期望和标准差均代入式(8),得:iWjCE(rw j)Yi j+EvT(1 0)因收件重量rw j服从泊松分布,其期望值等于方差值,所以存在常数Q,使式(1 0)转化为式(1 1):iWjCE(rw j)Yi jQ(1 1)Q值可由式(1 2)求得:Q=1/2(2T+2-4+4T2)(1 2)2.2.3 下层模型同样地,车辆k按顺序对客户进行配送,现判断客户点j+1是否由车辆j服务,则车辆在客户点j和客户点j+1之间的实际载荷量Qj(j+1)=jCQ0j k-(dw1+dw2+dw j)-(rw1+rw2+rw j),其中jCQ0j k为车辆k初始载荷和体积,即车辆所需配送的所有点派件量之和。此时,若车 辆 继 续 对 客 户j进 行 服 务 需 满 足rw jQj(j+1)k-Qo j k+dw j,引 入 随 机 机 会 约 束,即161孙睿男等:基于混合启发式算法的快递末端选址路径优化研究Prw jQj(j+1)k-Qo j k+dw j,(0,1。同理,其体积随机约束为Prv jVj(j+1)k-Vo j k+dv j。式(1 3)为下层规划目标函数,以总配送距离最小为目标;式(1 4)和式(1 5)分别表示配送车辆的载荷与体积的随机机会约束;式(1 6)表示配送员最长配送时间约束;式(1 7)表示每个客户仅被服务一次;式(1 8)表示避免网点之间相互配送;式(1 9)表示每个客户仅被一个快递网点服务;式(2 0)表示节点流量平衡约束;式(2 1)表示配送车辆从网点出发时的负载量等于该网点所服务客户的派件需求总和;式(2 2)表示配送车辆在各节点负载量;式(2 3)表示配送车辆回到快递网点时的负载量等于该网点所服务客户的收件量需求总和;式(2 4)和式(2 5)表示车辆负载量约束;式(2 6)和式(2 7)为决策变量之间的关系,分别表示当点i被选为建设快递网点,则必有客户点j由网点i配送和只要存在客户点j由网点i配送,则网点i必被选为建设快递网点;式(2 8)表示决策变量,为0-1变量。M i nXi j k F2=kKiWjC(di jXi j k+dj(j+1)Xj(j+1)k)(1 3)s.t.Prw jiWjC(Xi j kQi j k+Xj(j+1)kQj(j+1)k)-Q0j k+dw j,kK(1 4)Prv jiWjC(Xi j kQi j k+Xj(j+1)kQj(j+1)k)-Q0j k+dv j,kK(1 5)iWjC Xi j kdi jV+Xj(j+1)kdj(j+1)V Tp(1 6)iWkK(Xi j k+Xj(j+1)k)=1,jC(1 7)iWXi(i+1)k=0,kK(1 8)iWYi j=1,jC(1 9)jCXi j k=jCXj i k,iW,kK(2 0)kKjCQi j kXi j k=jCYi jdw j,iW(2 1)jCkK(Qi j k+Qj(j+1)k)-dw j=jCkK(Qi j k+Qj(j+1)k)-rw j,iW(2 2)jCkKQj i kXj i k=jCYi jrw j,iW(2 3)0Qi j kQkXi j k,iW,jC,kK(2 4)0Qj(j+1)kQkXi(j+1)k,jC,kK(2 5)jCYi jZi,iW(2 6)Yi jZi,iW,jC(2 7)Xi j k,Xj(j+1)k0,1,iW,jC,kK(2 8)2.2.4 下层模型随机机会约束等价处理随机约束规划式(1 4)可转化为:Prw jQk-iW(Xi j kQi j k+Xj(j+1)kQj(j+1)k)+dj=P iWjCrw jXi j kQk-jCQ0j k+iW(Xi j k+Xj(j+1)k),jC,kK(2 9)推导过程与上层模型推导过程中式(5)式(1 2)同理,快件重量的随机机会约束确定型等价形式可转化为:iWjCE(rw j)Xi j kQ(3 0)T=Qk-jCQ0j k+iW(Xi j kdw j+Xj(j+1)kdw j)(3 1)同理,快件体积的随机机会约束确定型等价形式可转化为:iWjCE(rv j)Xi j kQ(3 2)T=Vk-jCV0j k+iW(Xi j kdv j+Xj(j+1)kdv j)(3 3)2.2.5 重优化阶段重优化阶段中,对于选址问题网点容量无法满足的情况,选择添加新的网点进行后续配送,而现有对随机需求路径问题失败点处理方法主要有失败点返回策略、失败点前序点返回策略和失败点重优化策略3种。如图1所示,A、B为快递网点,图中实线为预优化阶段路径,虚线为重优化阶段路径,8个客户点中,客户点2,4和6为失败点,预优化阶段路径如图1 a所示。(1)失败点返回策略,如图1 b所示,配送车辆在客户点2,4和6不满足条件无法配送时,车辆返回原快递网点,再按预优化安排进行后续配送。(2)失败点前序点返回策略,如图1 c所示,配送车辆在失败点4的前序点1,预先对车辆剩余载荷能否满足失败点4的需求进行判断,若车辆剩余载荷能满足后序点需求则对其服务,否则,在失败261C o m p u t e r E n g i n e e r i n g&S c i e n c e 计算机工程与科学 2 0 2 4,4 6(1)F i g u r e 1 F a i l u r e p o i n t r e t u r n p o l i c y图1 失败点返回策略点前序点就返回原配送网点再继续配送,这种情况下,其配送路径长度一定小于失败点返回策略。(3)失败点重优化策略,如图1 d所示,配送车辆在失败点返回原出发网点,对于失败点及其预优化方案中后续客户点进行重新统一规划,设计配送方案生成重优化路径,再按重优化阶段路径方案进行配送。总结以上几种返回策略中,失败点返回策略操作最为简单,但其配送路径距离较长,前序点返回策略未考虑到后续点的统一优化,无法保证整体路径最优。因此,将失败点前序点返回策略和失败点重优化策略相结合组成失败点前序点重优化策略,并在返回规则上进行改善,结合共同配送模式特点,配送车辆在返回网点时,无需返回原配送网点,选择距离最近的网点返回,可缩短配送路径的距离。如图1 e所示,配送车辆在失败点4的前序点7通过判断其后序点无法满足配送需求时进行返回,统计所有失败点及其后续点,重新设计后续客户点配送方案,生成重优化阶段路径安排。3 混合自适应大邻域搜索遗传算法针对双层模型解空间大、计算复杂等特性,本文设计混合自适应大邻域搜索遗传算法进行求解。将自适应大邻域搜索算法嵌入遗传算法中,每一代进化时先用遗传算法寻优;再将遗传算法种群中最优个体作为自适应大邻域搜索算法的初始解进行求解;最后,通过“个体替换”操作将自适应大邻域搜索算法所得的新解替换掉遗传算法种群中适应度最低的解,生成新一代种群,以达到改善种群质量的目的,以此不断迭代,直至算法结束。本文所设计的混合自适应大邻域搜索遗传算法结合了2种算法的优点,即通过遗传算法的选择算子、交叉算子和变异算子等来提升自适应大邻域搜索算法的全局搜索能力,降低算法陷入局部最优解的概率;而自适应大邻域搜索算法的破坏算子和修复算子也可以加强遗传算法的局部搜索能力,并通过引入自适应机制,自适应更新算子权重,使其在每次迭代的时候都可以选择当前最优的算子进行解的变换,强化每一代的求解质量。改进后的混合自适应大邻域搜索遗传算法可以更好地在全部解空间中寻优,得到更满意的解。具体的算法流程如图2所示。F i g u r e 2 F l o w c h a r t o f h y b r i d a d a p t i v e l a r g e n e i g h b o r h o o d s e a r c h g e n e t i c a l g o r i t h m 图2 混合自适应大邻域搜索遗传算法流程361孙睿男等:基于混合启发式算法的快递末端选址路径优化研究3.1 编码及解码方式算法采用整数编码的方式,将全部客户需求编号点打乱顺序存入染色体编码方案列表中,作为配送的服务顺序。解码过程包括2步:第1步根据随机机会约束机制及快件的重量、体积约束将客户分配给配送员,如不满足该约束条件,则为该需求点增加新的快递员进行服务,直至为所有需求点都分配好快递员;第2步根据每辆配送车辆首尾客户到快递网点的距离确定车辆的出发网点和返回网点。具体以图3为例,其中11 0为客户需求点,a、b和c为3个配送网点,将客户点打乱顺序加入列表中,即为染色体编码方案;解码首先根据编码方案列表中的顺序为配送员分配客户,当分配到第4个客户,即客户6时,发现不满足约束条件,为客户6及后续客户点安排新的配送员进行配送服务;将已分配好的配送路径1,3,2 以列表的形式加入二维列表r o u t e中,并根据配送路径中起始客户和末尾客户,选择最近的网点作为其始末网点,加入二维列表d e p o t中,确定最终的始末配送中心,即配送员从网点a出发进行派送,先后服务客户点1,3和2后返回最近网点b;以此类推,确定最终的染色体解码方案。F i g u r e 3 C o d i n g a n d d e c o d i n g m o d e s图3 编码及解码方式3.2 初始种群生成随机生成一个种群规模为p o p e s i z e的初始种群,p o p e s i z e为预先设定好的数值,通过计算每个个体的适应度,将适应度最大的个体作为自适应大邻域搜索算法的初始解,对该个体进行邻域搜索。全部初始种群就作为遗传算法的初始解进行迭代,再通过个体替换,即将自适应大邻域搜索算法所得的新个体替换掉遗传算法所得新种群中适应度最小的个体,生成新一代种群。3.3 适应度函数先给出上层选址模型的初始解,将其代入下层模型进行求解,得出的配送路径规划方案再反馈到上层模型中,以上层模型的目标函数式(1)的倒数作为算法个体的适应度函数fs,如式(3 4)所示:fs=1F1(3 4)由式(3 4)可知,目标函数值F1越优,其染色体个体适应度fs越大。3.4 遗传操作遗传操作在整体算法中起到全局搜索的作用,通过选择、交叉和变异等操作,可以避免整体算法陷入局部最优解的情况:(1)选择算子:采用二元锦标赛选择策略,即每次在父代种群中随机选择2个不同的个体,通过比较2个个体的适应度大小,将适应度较大的个体加入新的种群中,重复n_s e l e c t次数。(2)交叉算子:需考虑到子代染色体中是否包含重复基因,考虑到该因素,下层模型采用O X交叉法。即随机选择2个染色体作为父代染色体,选择其中一个染色体的一串基因直接复制到子代染色体相同位置,再从另外一个父代染色体中按顺序将不同于子代染色体中已有的基因复制到子代染色体中,所得的新染色体即为子代染色体。该方法巧妙地避免了子代中出现重复基因的情况。(3)变异算子:在变异过程中,同样考虑子代染色体重复基因的情况,采用二元突变的方式,即随机从种群中选取一个染色体作为父代染色体。在已选择的父代染色体中随机选择2个不处于相同位置的基因点,然后交换该2点的基因值,得到的新染色体即为子代染色体。3.5 自适应大邻域搜索操作自适应大邻域搜索算法主要是增强算法的邻域搜索能力,其中邻域搜索算子有很多种,本文引入2种破坏算子及3种修复算子,通过不断地破坏和修复个体来搜索邻域解。(1)破坏算子。随机破坏算子:即在个体染色体中随机选取宽度在d_m i n,d_m a x 中的一段基因序列,存入r e m o v e_l i s t中,以备修复操作时使用。461C o m p u t e r E n g i n e e r i n g&S c i e n c e 计算机工程与科学 2 0 2 4,4 6(1)最差破坏算子:即移除一定范围引起目标函数增大的需求点,通过分别计算移除每一个需求点后目标函数的减少量,对需求点进行排序,按照一定比例移除需求点集合。(2)修复算子。随机修复算子:与随机破坏算子原理相同,即在已破坏个体中,随机将r e m o v e_l i s t中的基因序列插入到个体中,形成新解。贪婪修复算子:根据r e m o v e_l i s t中需求点顺序,依次将列表中需求点插入使目标函数增量最小的位置,直至r e m o v e_l i s t列表为空。后悔修复算子:计算r e m o v e_l i s t中需求点插入到待插入个体序列中L个次优位置时目标函数的变化,选择使目标函数变化最大的需求节点及其最优位置。(3)算子权重更新策略。每次迭代都更新权重在处理大规模问题时所需时间太长,可以通过合理设置p的值来平衡求解时间和权重更新的及时性之间的关系。因此,每迭代p次更新一次算子权重作为混合大邻域搜索遗传算法的权重更新策略。权重更新表达式如式(3 5)所示:W()=(1-p)W()+pS()t(),t()0(1-p)W(),t()=0 (3 5)其中,W()表示算子每次更新权重;p表示算子更新衰降系数;S()表示算子的总奖励得分,与算子的被选择次数和使用该算子后产生的邻域解的质量有关;t()表示算子被选择的次数。4 数值实验与实例分析4.1 算法参数及性能对比(1)参数确定。本文研究的随机选址路径问题目前没有统一的标准通用算例,因此选择P r o d h o n提出的经典选址路径问题标准测试集(h t t p:/p r o d h o n c.f r e e.f r/I n s t a n c e s/i n s t a n c e s_u s.h t m)中部分算例对算法参数及性能进行测试。分别选取测试集中名称为c o o r d 2 0-5-1(算例包含2 0个客户点,5个备选中心)、c o o r d 5 0-5-1(算例包含5 0个客户点,5个备选中心)和c o o r d 1 0 0-5-1(算例包含1 0 0个客户点,5个备选中心)的算例对算法进行参数分析,通过调整参数取不同的值,用算法对上述3个算例分别求解5次,对3个算例中最优解对应的参数求平均数,取该平均数作为最终的参数值。最终确定的参数最优值如表1所示。表1中包含以下参数:PC为交叉算子概率;PM为选择算子概率;N_s e l e c t为进行选择操作时,选择种群的比例;R a n d_d_m a x为随机破坏算子的最大上限,R a n d_d_m i n为随机破坏算子的最低下限;W o r s t_d_m a x为最坏破坏算子的最大上限,W o r s t_d_m i n为最坏破坏算子的最低下限;R e g r e t_n为后悔修复算子中取次优位置的个数。T a b l e 1 O p t i m a l v a l u e s o f p a r a m e t e r s表1 参数最优值参数最佳参数值PC0.6PM0.2N_s e l e c t0.6R a n d_d_m a x0.4R a n d_d_m i n0.1W o r s t_d_m a x0.4W o r s t_d_m i n0.1R e g r e t_n3 (2)算法性能对比。为了测试混合算法性能,设置目标函数包含配送中心和车辆的固定成本及运输成本,分别用自适应大邻域搜索(A L N S)算法、传统遗传算法GA(G e n e t i c A l g o r i t h m)以及本文设计的混合自适应大邻 域 搜 索 遗 传 算 法A L GA(A d a p t i v e L a r g e n e i g h b o r h o o d s e a r c h a n d G e n e t i c A l g o r i t h m)运行5次,对运行结果进行对比。所得结果如表2所示,其中,B S表示已知最优解,B e s t表示算法运行5次的最优解,G a p表示当前算法所得结果与最优解之间的差距,A v e表示平均数据。由表2可知,本文所设计的A L GA算法在客户规模为2 0时可找到最优解;对比各算法的G a p值衡量算法性能,A L GA算法的G a p值平均为1.5 0%,相对于GA算法的2.4 0%和A L N S算法的2.8 9%,说明A L GA算法性能相对其他2种启发式算法更优。(3)算法收敛性对比。为了分析算法的收敛情况,选取c o o r d 2 0-5-1算例,记录每一代种群最优解并绘制算法收敛图,进行算法收敛性分析。从图4可以看出,在5 0代以内,GA算法和A L GA算法收敛速度相近,但其在5 0代后陷入了局部最优解;A L N S算法虽然一直稳步收敛,但整561孙睿男等:基于混合启发式算法的快递末端选址路径优化研究T a b l e 2 A l g o r i t h m p e r f o r m a n c e c o m p a r i s o n 表2 算法性能对比算例名称B SA L N SB e s t G a p/%GAB e s t G a p/%A L GAB e s t G a p/%c o o r d 2 0-5-15 4 7 9 35 5 2 6 20.8 55 5 7 1 91.6 95 4 7 9 30.0 0c o o r d 2 0-5-24 8 9 0 85 0 2 6 92.7 85 0 4 2 93.1 04 8 9 0 80.0 0c o o r d 5 0-5-19 0 1 1 19 1 9 5 32.0 49 2 0 5 02.1 59 0 6 3 20.5 7c o o r d 5 0-5-28 8 2 9 88 9 0 7 60.8 89 0 2 5 82.2 18 8 7 8 60.5 5c o o r d 1 0 0-5-12 7 5 9 9 32 8 9 2 3 64.7 92 8 6 3 7 03.7 52 8 1 9 4 42.1 5c o o r d 2 0 0-1 0-14 7 9 4 2 55 1 0 6 3 96.5 15 0 6 8 2 05.7 15 0 2 9 0 84.5 9A v e1 7 2 9 2 1.31 8 1 0 2 7.72.8 91 7 9 6 2 2.32.4 01 7 8 6 4 7.21.5 0体迭代速度较慢;本文提出的A L GA算法 结合GA和A L N S 2种算法的优点,不仅在求解初期迭代速度快,并且全程持续稳步收敛,在4 0 0代附近找到最优解。相比于改进前的算法,本文的A L-GA算法收敛到最优解的速度最快。F i g u r e 4 C o m p a r i s o n o f a l g o r i t h m c o n v e r g e n c e s图4 算法收敛对比图