1、第2 9卷第8期计算机集成制造系统V o l.2 9N o.82023年8月C o m p u t e r I n t e g r a t e dM a n u f a c t u r i n gS y s t e m sA u g.2 0 2 3D O I:1 0.1 3 1 9 6/j.c i m s.2 0 2 3.0 8.0 3 0收稿日期:2 0 2 1-0 7-1 5;修订日期:2 0 2 1-0 9-1 3。R e c e i v e d1 5J u l y2 0 2 1;a c c e p t e d1 3S e p.2 0 2 1.基金项目:国家自然科学基金资助项目(7 1
2、7 0 2 0 1 6);重庆市教育委员会人文社会科学资助项目(1 7 S K J 0 3 4);重庆市教育委员会科学技术研究资助项目(K J QN 2 0 1 9 0 0 6 3 4,K J QN 2 0 1 9 0 0 6 2 5)。F o u n d a t i o ni t e m s:P r o j e c ts u p p o r t e db yt h eN a t i o n a lN a t u r a lS c i e n c eF o u n d a t i o n,C h i n a(N o.7 1 7 0 2 0 1 6),t h e H u m a n i t i
3、e sa n dS o c i a lS c i e n c eR e s e a r c hF o u n d a t i o no fC h o n g q i n g M u n i c i p a lE d u c a t i o nC o mm i s s i o n,C h i n a(N o.1 7 S K J 0 3 4),a n dt h eS c i e n c ea n dT e c h n o l o g yF o u n d a t i o no fC h o n g q i n g M u n i c i p a lE d u c a t i o nC o mm i
4、 s s i o n,C h i n a(N o.K J QN 2 0 1 9 0 0 6 3 4,K J QN 2 0 1 9 0 0 6 2 5).带有配额的在线旅行维修工问题蹇 洁,张景露,吴腾宇,何 林(重庆邮电大学 现代邮政学院,重庆 4 0 0 0 6 5)摘 要:为了将应急物资公平且迅速地送往受灾点,本文提出救援车辆装载能力有限且不必返回出发点的在线旅行维修工问题。使用在线算法分析求解,证明了该问题在正半轴网络和一般网络上的下界。分别对正半轴网络上的情形设计了B l i n d l yT u r nL e f t(B T L)算法,对一般网络上的情形设计了逆杠杆算法,给出上述在线
5、算法的竞争比并分析了其竞争性能,与前人研究的在线旅行维修工问题对比发现,逆杠杆算法的竞争性能更优。最后通过数值仿真对受灾网络规模、受灾点数量和配送车辆容量进行敏感性分析,研究得到逆杠杆算法更适用于网络规模、车辆容量和受灾点密度较大的情形。关键词:应急救援;在线算法;竞争分析;旅行维修工问题中图分类号:C 9 3 5 文献标识码:AO n l i n e t r a v e l i n gr e p a i r m a np r o b l e mw i t hQ u o t a sJ I ANJ i e,ZHANGJ i n g l u,WUT e n g y u,HEL i n(S c h
6、o o l o fM o d e r nP o s t s,C h o n g q i n gU n i v e r s i t yo fP o s t sa n dT e l e c o mm u n i c a t i o n s,C h o n g q i n g4 0 0 0 6 5,C h i n a)A b s t r a c t:T o t r a n s p o r t e m e r g e n c y s u p p l i e s t o t h e c r i s i s a t t a c k e d l o c a t i o n s f a i r l ya n
7、dq u i c k l y,a i m i n ga t t h e l i m i t e dc a-p a c i t ya n dn o m a d i cv e h i c l e,t h eo n l i n e t r a v e l i n gr e p a i r m a np r o b l e m w i t hq u o t a sw a s i n t r o d u c e da n ds o l v e dw i t ho n-l i n ea l g o r i t h m.L o w e r b o u n d s o f t h ep r o b l e m
8、o n t h ep o s i t i v eh a l f-l i n e a n dg e n e r a l n e t w o r k sw e r ep r o v e d.T h eB l i n d l yT u r nL e f t(B T L)a l g o r i t h m w a sd e s i g n e df o rm e t r i cs p a c eo fp o s i t i v eh a l f-l i n e,a n dt h e i n v e r s e l e v e r a g ea l g o r i t h mw a sp r e s e
9、 n t e df o rm e t r i cs p a c eo f g e n e r a lm e t r i c s p a c e.T h e nc o m p e t i t i v e r a t i ow a sg i v e nf o r t h e t w oa l g o r i t h m s r e-s p e c t i v e l ya n dc o m p e t i t i v ep e r f o r m a n c ew a sa n a l y z e d.C o m p a r e dw i t hap a p e rw h i c hs t u d
10、 i e dt h eo n l i n e t r a v e l i n gr e-p a i r m a np r o b l e m,t h e c o m p e t i t i v ep e r f o r m a n c eo f t h e i n v e r s e l e v e r a g ea l g o r i t h mw a sb e t t e r.T h e s e n s i t i v i t ya n a l y s i sf o r t h es c a l eo fd i s a f f e c t e dn e t w o r k,t h en u
11、 m b e ro fd i s a f f e c t e dp o i n t sa n dt h ec a p a c i t yo fd e l i v e r yv e h i c l e sw a sc a r r i e do u t b yn u m e r i c a l s i m u l a t i o n,a n d t h e r e s u l t s h o w e d t h a t t h e i n v e r s e l e v e r a g e a l g o r i t h mw a sm o r e s u i t a b l eu n-d e r
12、g r e a t e rn e t w o r k,c a p a c i t yo fv e h i c l e sa n dd i s a s t e rp o i n td e n s i t y.K e y w o r d s:e m e r g e n c yr e s c u e;o n l i n ea l g o r i t h m;c o m p e t i t i v ea n a l y s i s;t r a v e l i n gr e p a i r m a np r o b l e m0 引言全世界范围内频发的自然灾害对经济产生了严重的影响,威胁着各国人民的生命
13、。2 0 1 9年7月澳洲大火,造成3 3人死亡,25 0 0余间房屋被摧毁。2 0 0 4年末苏门答腊岛发生里氏9级地震,继而引发的印度洋海啸造成至少2 3万人丧生或失踪。灾害发生后,灾民的存活率随着时间的流逝而逐渐降低,如何将食物、水、药品等应急救援物资及时送达灾民的手中,即应急车辆路径规划问题已成为目前亟待计算机集成制造系统第2 9卷解决的问题。以往的车辆路径优化研究多考虑需求信息提前获知的情形,F AN C E L L O等1考虑了在工业灾害发生时,如何用应急车辆将伤员尽快运送到安全地点的问题,并在此基础上建立混合整数规划模型进行求解;AK D O GAN等2研究了应急车辆的定位问题,
14、用排队论对其进行建模,设计启发式算法进行求解;任腾等3在客户需求信息已知的前提下,改进蚁群算法提高搜索的效率,优化配送路径;孙华丽等4研究了受灾点物资需求量不确定的应急物流定位-路径问题;王付宇等5则研究了震后伤员运送车辆路径优化问题。上述研究均未考虑需求点位置的不确定性,而在现实的应急救援过程中,由于灾害初期通讯和交通的严重损坏,受灾点的信息是严重闭塞的,导致受灾人群出现的时间、地点等信息均是不确定的,往往在应急救援过程中才能够实时获取受灾区域的信息。现实应急救援还具有以下两种特征:容量限制,即应急救援车辆的容量是受限的;公平性,应急救援需要考虑到每个受灾点的等待时间。这种考虑容量限制和每个
15、受灾点等待时间的不确定性问题可 以 用 带 有 配 额 的 旅 行 维 修 工 问 题(Q u o t aT r a v e l i n gR e p a i r m a nP r o b l e m,Q u o t aT R P)来 刻画。旅 行 维 修 工 问 题 是 旅 行 商 问 题(T r a v e l i n gS a l e s m a nP r o b l e m,T S P)的一个延伸,在现有研究中也被称为最小等待时间问题6。本文研究的是根据车辆容量限制和受灾点信息(需求量和位置)判断如何进行路径规划使所有需求点加权等待时间之和最小。T S P及T R P问题中需求无法确定
16、的情形则可使用在线算法解决。A u s i e l l o等7最早研究了在线旅行商问题,并对正半轴与一般网络进行了竞争分析。部 分 学 者 研 究 了 在 线 旅 行 商(O n l i n eT r a v e l i n gS a l e s m a nP r o b l e m,O L T S P)的 其 他 变型,如P r i z e-C o l l e c t i n g旅行商问题8,具有预知信息的O L T S P9-1 0,非对称网络下的O L T S P1 1,带配额的O L T S P1 2和带有线性惩罚的O L T S P1 3。但O L T S P的目标函数主要考虑服务所
17、有需求点的时间,现实应急救援中需公平地关注每个服务需求点的时间。K RUMK E等1 4研究了在线旅行维修工(O n l i n eT r a v e l i n gR e p a i r m a nP r o b l e m,O L T R P)问题,目标是最小化需求的总加权服务时间;I R AN I等1 5研究了动态的O L T R P问题,目标是在截止日期前服务最多的需求;J A I L L E T等1 6加入预知信息并提出揭露时间的概念,提高了在线服务器与离线服务器对抗的能力。目前对于在线Q u o t aT R P问题的研究较少,其算法及下界都有待进一步的探究。本文研究的带有配额的在
18、线T R P问题(在线QT R P问题),是应急救援车辆容量受到限制且公平考虑每一个受灾点情形下,在线应急救援车辆的路径规划问题。如果不考虑每一个需求点的服务时间,仅关注最后的服务完成时间,本问题则转变成带有配额的在线T S P问题;如果不考虑配额,本文则转变成一般的O L T R P问题,而同时考虑服务时间和配额更符合现实应急救援的情形。本文在正半轴与一般网络上展开研究,受地震等自然灾害影响后正 半轴类似一 个单 向 的 直 线 网 络 路径,一般网络则为更大的网络空间。根据两种不同网络设计了B T L(b l i n d l yt u r nl e f t)与逆杠杆算法,证明了下界及竞争比
19、,最后对逆杠杆算法进行数值仿真分析,并与已有O L-T R P问题研究结果进行了对比。1 基本定义及问题描述假设存在网路图M,所有需求点均位于M上。需求点i表示为Ri(ti,li,qi),iN,其中N=1,2,n,n为需求点的总数量,ti为需求点i的揭露时间(揭露时间等于释放时间),在线服务器在时刻ti得到需求点i的信息,li表示需求点i在网络图中的位置,qi为需求点i的配额,即该点的需求量。假设服务器经过需求点即服务了需求。零时刻服务器的初始位置为原点,行驶速度为单位速度,配额累积达到m时停止(即到达容量限制)。本文的成本函数是最小化服务需求的配额与服务时间乘积的累加,目标为如何规划路径使总
20、成本最小。本文使用竞争分析法研究带配额的O L T R P问题,竞争分析法是考虑在线服务器在最不利的情形下的表现。竞争分析中,假设存在在线服务器、离线服务器和离线对手,离线服务器在0时刻获知所有的需求信息,其产生的成本为理论上的最优值,在线服务器则根据序贯到来的需求信息规划行驶路线,离线对手根据在线服务器与离线服务器的位置实时产生需求序列I(对于在线服务器最不利的需求组合),离线服务器使用最优离线算法服务需求产生的成本为Co f f l i n e,在线服务器使用算法o n l i n e服务需求产生的成本为Co n l i n e。若对于同一输入需求序列2782第8期蹇 洁 等:带有配额的在
21、线旅行维修工问题I,如存在常量和使得Co n l i n e(I)Co f f l i n e(I)+,称算法o n l i n e的竞争比为。文中不同的需求点分别定义为:配额服务点:离线服务器所服务的需求点,其集合为S;虚拟服务点:集合S之外的需求点。2 正半轴上带有配额的在线Q u o t aT R P问题2.1 正半轴上在线Q u o t aT R P问题的下界定理1 正半轴上的在线QT R P问题的竞争比下界为2-,为无穷小正数。证明 0时刻离线对手在点(1,0)处释放需求R1(0,1,q1),讨论以下不同的情形:(1)情形1 在线服务器立刻出发去服务需求R1。1)情形1.1。若在线服
22、务器于时刻1到达点(1,0),此时离线对手释放两个需求:R2(1,0,q2),R3(1,a,q3),且满足q2+q3m,q1+q2m,q1+q3m。讨论a的不同取值:当0a1),此时离线对手释放需求R4(t,0,q4),R5(t,x+1,q5)(x1),且满足q4+q5+q12。在线服务器先服务需求R4,当其到达原点时离线服务器已到达点(t+1,0),离线对手在此释放一个需求R7(t+1,t+1,q7),使q1+q7m。在线服务器的成本为t q1+(t+1)q4+(2t+2)(m-q4-q1),离线服务器的成本为q1+(m-q1)(1+t)。两 服 务 器 的 比 值 为Co n l i n
23、eCo f f l i n e=t q1+(t+1)q4+(2t+2)(m-q4-q1)q1+(m-q1)(1+t),当q7接 近m时,Co n l i n eCo f f l i n e=2-。(2)情形2 在线服务器等待第2个需求。离线服务器在1时刻到达R1,继续向前行驶至t时刻。离线对手在此释放需求R8(t,1+t,q8),使q1+q8m。在线服务器的成本为(2+t)q1+2(1+t)(m-q1),离线服务器的成本为q1+(t+1)(m-q1)。两 服 务 器 成 本 的 比 值 为Co n l i n eCo f f l i n e=1+m(1+t)q1+(1+t)(m-q1),当q1
24、取值接近m时,Co n l i n eCo f f l i n e=1+t。综上,正半轴网络的竞争比下界为2-。2.2 正半轴上在线Q u o t aT R P问题的算法分析B T L算法思想:为防止离线对手在原点及附近释放较大配额的需求,在线服务器依然右向行驶,因此要求左侧配额大于右侧时,服务器即转向,具体步骤如下:B e g i n(开始)I f(没有需求出现)P r i n t 在线服务器在原点等候E l s e i f(已揭露的需求配额量小于m)d o依次服务当前已释放服务序列,记录服务时间、配额和服务时间和配额的乘积3782计算机集成制造系统第2 9卷I f(ti时刻,在服务器向右行
25、驶&左侧未服务需求的配额之和大于右侧)P r i n t 在线服务器转向,服务左侧需求d o左侧需求为待服务需求序列,记录服务时间和配额的乘积E n d i fE l s e i f(已揭露的需求配额量大于或等于m&在线服务器已服务的配额未累积至m)d o所有已释放需求为待服务需求序列,并按照配额达到m且成本最小的路径服务P r i n t 服务结束,服务时间和配额的乘积E l s e i f(已揭露的需求配额量大于或等于m&在线服务器已服务的配额累积至m)P r i n t 服务结束,服务时间和配额的乘积E n dI f引理1 当离线对手已经释放完所有的配额服务点以后,新的虚拟服务点不会提高
26、竞争比。证明 释放完所有配额服务点时离线服务器成本为Co f f l i n e,在线服务器根据B T L算法服务需求点的成本等于Co f f l i n e+y。若此后离线对手依然释放虚拟服务点,则在线服务器会依据B T L算法判断是否服务该虚拟服务点,设离线服务器服务该点的成本等于Co f f l i n e+y。当yy 时,在线服务器会去服务该虚拟服务点,从而降低在线服务器的成本;若yy,在线服务器仍然会选择原路径行驶。因此离线对手释放完所有的配额服务点以后,释放新的虚拟服务点不会提高竞争比。引理2 第一个需求点的揭露时间为0时刻。证明 设R1=(r1,l1,q1)为第一个揭露的需求,在
27、线服务器在时刻r1出发,此后经过时间xk释放较大配额量的需求Rk(k为变量),在线服务器在r1+xk时刻后,又经过时间yk服务了此需求。因此在线服务器的成本为Co n l i n eqk.(r1+yk+xk)。而离线服务器的成本为Co f f l i n eqk.(r1+xn),此时可得Co n l i n eCo f f l i n er1+yk+xkr1+xk=1+ykr1+xk,为了使两个服务器 的 成 本 比 值 更 大,r1需 取 得 最 小 值,则r1=0。定理2 B T L算法的竞争比为2。证明 令第一个出现的需求为R1,R1距离原点l1,在线服务器在0时刻出发。假设最右侧的配额
28、需求点为Rz,其距原点的距离为lz,最左侧的配额需求点为Rj,其距离原点lj。当在线服务器出发以后:(1)情形1 离线服务器中途存在转向。离线服务器的转向点与原点的距离为lf。1)情形1.1。点(1,0)为配额服务点。在线服务器与离线服务器在l1时刻同时到达点(1,0),若离线服务器继续向前行驶服务新需求,则和在线服务器增加相同的成本,因此对离线服务器最有利的选择是在l1处转向。考虑l1不同的位置:当l1=lz,此情形离线服务器在点(1,0)左侧转向,此时对于在线服务器最坏的情形是右侧需求点使在线服务器向右侧行驶且最后不能服务。离线服务器行驶至点(l,0)(ll1)服务已释放的较大配额需求,此
29、时离线服务器成本最小为Co f f l i n e=(2l1-l)ql。根据B T L算法,在线服务器会立即转向服务此需求,所以在线服务器成本为Co n l i n e=(4l1-3l)ql。点(l,0)的竞争比为2-l2l1-l,显然竞争比为l的减函数,则点l位于原点时,竞争比最大且为2。若此时离线服务器选择继续右行驶,此后的服务点仅会增加离线服务器与在线服务器相同的成本或减小在线服务器的成本。此情形设置点l的配额接近m,则竞争比为Co n l i n eCo f f l i n e2。当ljl1lz。点Rz即为转向点,为使在线服务器返回路径最长,则lz=lj=0。在线服务器转向时刻为T,为
30、确保在线服务器不会服务虚拟服务点,设置l1远远大于T且q1=。根据B T L算法,若在T时刻前释放需求在线服务器会立即转向。离线对手会在T时刻释放配额为m的需求,此时离线服务器的成本为Co f f l i n e=Tm,在线服务器的成本为Co n l i n e=m2T,则竞争比为Co n l i n eCo f f l i n e=2。(2)情形2 离线服务器中途不存在转向。1)情形2.1。点(1,0)为配额服务点。在线服务器与离线服务器会同时到达点(1,0)。为使在线服务器与离线服务器成本差值最大,当离线对手释放大额需求点时,在线服务器应位于原点。4782第8期蹇 洁 等:带有配额的在线旅
31、行维修工问题此时最坏的需求序列为:0时刻于原点释放需求R1(0,0,q1),当离线服务器到达点z时,离线对手释放需求Rz(lz,lz,qz)。当q1为无穷小,qz取值接近m。此情形竞争比为Co n l i n eCo f f l i n e3+52,离线对手不会释放任何需求,离线服务器的成本为Co f f l i n e=1,在线服务器的成本为Co n l i n e=t,可得Co n l i n eCo f f l i n et。若2t3+52,离线对手t-1时刻于点(-t,0)处释放需求R2(t-1,-t,q2),q2=m。假设t-1时刻在线服务器到达点(x,0)(0 xQr i g h
32、tLr i g h t)d o在线服务器服务左侧需求,记录服务时间和配额的乘积E l s e i fQl e f tLl e f tQr i g h tLr i g h t()d o在线服务器服务右侧需求,记录服务时间和配额的乘积E l s ed o在线服务器继续按照当前方向行驶服务需求,记录服务时间和配额的乘积E n d i fE l s e i f(已揭露的需求配额量大于或等于m&在线服务器已服务的配额未累积至m)d o所有已释放需求为待服务需求序列,并按照配额达到m且成本最小的路径服务P r i n t 服务结束,服务时间和配额的乘积E l s e i f(已揭露的需求配额量大于或等于m
33、&在线服务器已服务的配额累积至m)P r i n t 服务结束,服务时间和配额的乘积E n dI f(2)重心:若需求R1,R2,R3位于同一侧,距支点的位置分别为L1,L2,L3,则3点的重心位置为L=q1.L1+q2.L2+q3.L3q1+q2+q3。定理4 逆杠杆算法的竞争比为3。证明 离线对手释放的需求序列会使得在线服务器尽可能晚地服务较大配额的需求。对于在线服务器,配额服务点集合S完全揭露的时间为T,而此时在线服务器离原点的最远距离也为T。将T时刻以后的情形分为两类:(1)情形1 在线服务器未服务需求点。若离线对手在T时刻后释放了新的虚拟服务点,在线车辆将在虚拟服务点和配额服务点中规
34、划出一条最优路径进行服务,而如果在线服务器服务了虚拟服务点,即相比释放前可以更早地服务更高配额的需求,则离线对手不会释放这些虚拟服务点。在线车辆的最坏情形便是先返回原点再服务配额服务点。(2)情形2 在线车辆已经服务了某些需求点。如果此时在线车辆已经服务了某些需求点,如5782计算机集成制造系统第2 9卷同上一种情形所分析的,最坏的情形仍然是在线车辆返回原点后再去配额服务点中的部分(总服务配额等于m即可),此情形相比情形1提前服务了一些配额,总成本必定小于情形1。综合以上两种情况,T时刻时在线车辆未服务任何需求点是最坏的情况,意味着离线对手释放的配额服务点距离原点不大于T,而虚拟服务点距离原点
35、大于T。为了保证在线服务器不选择服务虚拟服务点,则虚拟服务点R1释放的距离远远大于T,且q1qi(iS)。在这种情形下q1L1qiLi(iS),为了保证在线服务器不会转向,离线对手在离线服务器到达(-T,0)点前将不释放需求。因此,对于在线服务器来说,最坏的序列为:0时刻正半轴揭露一个距离原点非常远的虚拟服务点R1,T时刻于原点左侧T处揭露配额为m的需求点。在线服务器按照逆杠杆算法,T时刻立马转向去点(-T,0)服务,此时在线服务器的费用为Co n l i n e=3Tm,竞争比为Co n l i n eCo f f l i n e=3TmTm=3。本文研究结论与K r u m k e等1 4
36、结论的对比如表1所示。表1 研究结果对比上界下界O L T R P一般网络(1+2)21+2本文研究结果一般网络35+32正半轴22-与K r u m k e的研究相比,本文扩展了已有的研究,增加了配额这一约束使其更符合现实的应急救援情形。一般网络的下界从1+2提高到5+32,因为带有配额的O L-T R P问题相比O L-T R P问题是更加一般的情形。本文的逆杠杆算法的竞争比相比O L-T R P问题的竞争比也得到了降低,说明逆杠杆算法有着更好的竞争性能。4 数值仿真本章通过数值仿真在更大规模的一般网络上评估逆杠杆算法的表现,研究不同的网络大小、服务器容量、需求点密度下在线服务器与离线服务
37、器的竞争比变化。使用MAT L A B对逆杠杆算法编程,求得每种情形下在线服务器和离线服务器的成本,由此观察逆杠杆算法的表现及适用性。设定服务器的行驶速度为单位速度,按照服务器容量m=1 5 0,网络大小-5,5,每小时随机生成4 0个受灾点需求(即需求点密度)作为标准案例。调整服务器容量、网络大小、需求点密度3个参数:服务器容量m=1 0 0及m=2 0 0;网络大小增加到-1 0,1 0 作为较大的配送网络;需求点密度r=2 0及r=3 0。每次仿真计算出逆杠杆算法下的服务时间与需求点配额乘积的累加与离线最优成本的比值。每一种情形进行5 0次仿真后求得竞争比的平均值。将离线服务器成本的下界
38、,即为每个需求点的释放时间乘以配额之和作为仿真中离线服务器的成本。结果如表2所示。表2 不同服务器容量下的逆杠杆算法竞争比网络大小需求点密度r服务器容量m竞争比-5,54 01 0 03.3 4-5,54 01 5 02.2 2-5,54 02 0 01.2 1结论1 网络大小及需求点密度恒定时,随着在线服务器容量的增加,竞争比逐渐减小。对表2中数据进行分析,当网络大小为-5,5、需求点密度r=4 0时,随着在线服务器容量的增加,逆杠杆算法的表现越好,说明在线服务器的成本越发接近离线服务器的成本。仿真中由于服务器容量的增加,意味着需要服务更多的需求点,且需求点位置和配额均是随机产生,既减少了对
39、在线服务器不利的情形,又使得离线服务器达到容量限制需要花费更多的时间,产生更多的成本,而在线服务器根据逆杠杆算法判断行驶方向,使其不会盲目往一个方向行驶,从而逐渐降低两个服务器之间的比值。结果如表3所示。表3 不同网络大小下的逆杠杆算法竞争性比服务器容量m需求点密度r网络大小竞争比1 5 04 0-5,52.2 21 5 04 0-1 0,1 01.5 6结论2 服务器容量及需求点密度恒定时,随着网络大小的增加,竞争比逐渐减小。对表3中数据进行分析,当服务器容量m=1 5 0、需求点密度r=4 0时,随着网络规模的增加,逆杠杆算法的表现越好。当需求点数量保持不变且随机产生需求点位置时,增大网络
40、规模,使得需求点在6782第8期蹇 洁 等:带有配额的在线旅行维修工问题网络中的分布更加零散,离线服务器仅通过服务原点周围的需求达到容量限制的情形更少,则需要花费更多的时间去服务需求。在这种情形下,在线服务器通过需求点的位置和配额判断是否服务,避免了盲目前进带来的成本,从而使得两个服务器之间的成本降低。结果如表4所示。表4 不同需求点密度下的逆杠杆算法竞争比网络大小服务器容量m需求点密度r竞争比-5,51 5 02 02.9 4-5,51 5 03 02.7 4-5,51 5 04 02.2 2结论3 网络大小及服务器容量恒定时,随着需求点密度的增加,竞争比逐渐降低。对表4数据进行分析,当网络
41、大小为-5,5、服务器容量m=1 5 0时,随着需求点密度的增加,逆杠杆算法的表现越好。在仿真中更大的需求点密度则意味着在相同的时间内会有更多的需求点出现,同样由于需求点产生的随机性,直接减少了对在线服务器不利的情形出现。当网络规模不变时,需求点越密集,离线服务器达到容量限制的时间越短,但在线服务器达到容量限制的时间同样变短,且根据逆杠杆算法判断行驶方向,在线服务器减少了盲目往同一方向行驶的情形,从而使得在线服务器和离线服务器的比值减少。综上,在调整网络大小、服务器容量及需求点密度3个变量时,仿真结果均是随着变量的增大,算法的竞争比得到降低,这说明逆杠杆算法在网络规模较大、受灾点较多、车辆容量
42、较大的情形下表现更好,更适用。同时,因为仿真中的需求序列是随机产生的,而理论分析是假设在线服务器总是服务最坏情形下的需求序列,因此出现了仿真中的竞争比小于理论分析中的竞争比的情形。因此,现实的应急救援中可以增 加车辆的 容量及 覆 盖 更 大 的 救 援范围。5 结束语针对应急救援中受灾点的不确定性和车辆容量限制设计了实时优化算法,可以提升应急救援车辆为灾区进行物资配送的效率,并为应急救援指挥中心提供技术支持。本文针对应急救援物资配送过程中的快速性与公平性,提出了带有配额的在线T R P问题,证明了正半轴网络和一般网络的竞争比下界,针对两种网络设计B T L算法和逆杠杆算法,给出了两种算法的竞
43、争比。研究对比得到逆杠杆算法的竞争比小于O L T R P问题的竞争比,说明逆杠杆算法有更好的竞争性能。通过大量的数值仿真发现,当网络变大、需求点数量和车辆容量增加时,逆杠杆算法的表现逐渐变好,说明在现实的应急救援中,随着受灾点的增加和受灾范围变大,应急救援中心可采用逆杠杆算法,派遣容量更大的救援车辆服务受灾区域。带有配额的O L T R P问题研究的是单应急救援车辆的问题,在后续的研究中可以进一步讨论多应急救援车辆的情况。参考文献:1 F AN C E L L OG,MAN C I N IS,P AN IC,e t a l.A ne m e r g e n c yv e-h i c l e
44、sa l l o c a t i o nm o d e l f o rm a j o r i n d u s t r i a l d i s a s t e r sJ.T r a n s-p o r t a t i o nR e s e a r c hP r o c e d i a,2 0 1 7,2 5:1 1 6 4-1 1 7 9.2 AK D O GAN M A,B AYN D RZP,I Y I GUN C.L o c a t i n ge m e r-g e n c yv e h i c l e sw i t ha na p p r o x i m a t eq u e u i n
45、 gm o d e l a n dam e t a-h e u r i s t i cs o l u t i o na p p r o a c hJ.T r a n s p o r t a t i o nR e s e a r c hP a r tC:E m e r g i n gT e c h n o l o g i e s,2 0 1 8,9 0:1 3 4-1 5 5.3 R E NT e n g,C HE N Y u e,X I AN Gy i n g c h u n,e ta l.O p t i m i z a t i o no f l o w-c a r b o nc o l dc
46、 h a i nv e h i c l ep a t hc o n s i d e r i n gc u s t o m e r s a t-i s f a c t i o nJ.C o m p u t e rI n t e g r a t e d M a n u f a c t u r i n g S y s t e m s,2 0 2 0,2 6(4):1 1 0 8-1 1 1 7(i nC h i n e s e).任 腾,陈 玥,向迎春,等.考虑客户满意度的低碳冷链车辆路径优化J.计算机集成制造系统,2 0 2 0,2 6(4):1 1 0 8-1 1 1 7.4 S UN H u
47、a l i,C AO W e n q i a n,XU EY a o f e n g,e t a l.E m e r g e n c y l o-c a t i o n-r o u n t i n gm o d e lw i t hu n c e r t a i nd e m a n d s u n d e r p a t h r i s k sJ.O p e r a t i o n sR e a r c ha n dM a n a g e m e n tS c i e n c e,2 0 1 8,2 7(7):3 7-4 2(i nC h i n e s e).孙华丽,曹文倩,薛耀锋,等.考
48、虑路径风险的需求不确定应急物流定位-路径问题J.运筹与管理,2 0 1 8,2 7(0 7):3 7-4 2.5 WAN GF u y u,Y EC h u n m i n g,WAN G T a o,e ta l.R e s e a r c ho nt w os t a g ep l a n n i n gm o d e l a n da l g o r i t h mo fw o u n d e dr e s c u ev e-h i c l ea f t e re r a t h q u a k eJ.J o u r n a lo fM a n a g e m e n tS c i e
49、n c e si nC h i n a,2 0 1 8,2 1(2):6 8-7 9(i nC h i n e s e).王付宇,叶春明,王 涛,等.震后伤员救援车辆两阶段规划模型及算法研究J.管理科学学报,2 0 1 8,2 1(2):6 8-7 9.6 GO EMAN SM,K L E I N B E R G J.A ni m p r o v e da p p r o x i m a t i o nr a t i o f o r t h em i n i m u ml a t e n c yp r o b l e mJ.M a t h e m a t i c a lP r o-g r a
50、mm i n g,1 9 9 8,8 2(1):1 1 1-1 2 4.7 AU S I E L L OG,F E U E R S T E I N E,L E ONA R D IS,e ta l.A l g o-r i t h m s f o rt h eo n-l i n et r a v e l l i n gs a l e s m a nJ.A l g o r i t h m i c a,2 0 0 1,2 9(4):5 6 0-5 8 1.8 AU S I E L L OG,B ON I F A C IV,L AUR A L.T h eo n l i n ep r i z e-c o
