路径长度受限的随机需求VRP的节省算法及其策略分析
第28卷第5期2006年9月
南 京 工 业 大 学 学 报
JOURNALOFNANJINGUNIVERSITYOFTECHNOLOGY
Vol
.28No.5
Sep12006
路径长度受限的随机需求VRP的节省算法
及其策略分析
钱小燕
1,2
,程 浩,刘 浩
22
(11南京航空航天大学理学院,江苏南京210016;21南京工业大学理学院,江苏南京210009)
摘 要:在保证每条路径长度限制,至多只能服务失败一次和不允许部分服务的策略下,定义了一个新的节省路径,给出了一个精确的节省算法,对中等规模和大规模问题进行了数值试验,。对所采用的策略进行了分析,得到了一些理论结果。
关键词:路径长度受限;随机需求;VRP;节省算法;服务失败;中图分类号:O24;U116 文献标识码:A 文章编号-(0033-04
VehicleRoutingProblem简称个服务中心(服务,,辆,,要求服务所需费用最少或行程最短。固定需求的VRP已有很多研究,如文献[1-4]等。随机需求VRP问题的研究较少,尤其是路径长度受限的随机需求VRP问题研究更少。但日常生活、企业管理、运输问题中有着大量的路径长度受限的随机需求VRP问题,如公交班车路径和计划、银行运钞、运输公司发送货物等。研究路径长度受限随机需求VRP问题能节约费用,为用户提供优质服务,直接带来经济效益。
随机需求VRP(VehicleRoutingProblemwithStochasticdemand,简记为SVRP)叙述为:设有一个中心(depot设为结点0)和n个服务结点(costumernodes)。中心拥有充分多的容量为C的车辆,所有车辆均从中心出发为服务结点提供服务,然后返回中心。设各结点之间以及结点与中心之间的最短距离为dij(i,j=0,1,2,…,n)且满足三角不等式,即对任意结点i,j,k有dij+djk≥dik。设已知结点i的需求量ξi(i=1,2,…,n)的概率分布,每个结点在车辆
次,求解目标是求出完成服务费用最小的派车方案。它是NP2hard的组合优化问题。其中的容量和最大行程是广义的,不一定是物理意义上的容量和路程。 人们处理SVRP的一般方法是假设车辆匀速行驶,在允许一定次数的服务失败和是否允许部分服务的策略下,生成一定服务次序结点的路径,不考虑车辆的最大行程限制。实际上在现实生活和生产中因为车辆的燃油不足、驾驶员需要休息或者是需要服务的结点对等待服务的时间难以承受等原因,必须考虑车辆的行程限制。设所有车辆的最大行程限制为L,文献[5]考虑了车辆行程限制的随机需求VRP(记为PSVRP),给出了PSVRP的随机整数规划
模型,提出了一个基于扫描算法的一步启发式算法。遗憾的是文献[5]的算法是一个局部算法,它不可能求得问题的最优解,甚至某些问题的解不能作为近似最优解。笔者采用同文献[5]一样的策略,定义了一种新的路径节省,得出一个精确节省算法,并对采用的策略进行了分析,得出了一些理论结果。采用所给出的算法对中等规模和大规模的PSVRP问题进行了数值试验。
3收稿日期:2005-09-12
基金项目:航空基础科学基金(97J52091)
作者简介:钱小燕(1976-),女,江苏如东人,讲师,主要研究方向为计算数学。E2mail:[email protected]
34南 京 工 业 大 学 学 报 第28卷
1 问题的分析
假设各结点的需求量的分布密度函数或分布函
数已知,b(整数)是各结点的最大需求量,而这个b可以通过结点的统计数据得到。设C≥b和最大行程L≥maxi{2di0},这样才能保证车辆至少可以服务一个结点。当车辆服务各结点时货物在车辆上堆积,因为需求为随机的,而在车辆未到达某个结点前没有此结点的任何确定的需求信息,且假设车辆不允许为结点提供部分服务,即当剩余的车容量已装不下此结点的全部货物时,车辆必须返回中心,卸掉货物,再返回此结点继续服务。 因b(整数)是各结点的最大需求量,故ξi∈[0,b],记
m=[C/b]
设在服务过程中,服务失败;t个结点,则显然有≤tmpjj:
j-1
j
i
i
2 算法和数值试验
2.1 算 法
算法起始于向每个顾客提供一辆车的非可行性解决方案,通过合并两个顾客的用车,可以达到降低费用的目的。因问题中有n个服务点需要服务,初始时假设需要n辆车,即视为每一个结点有一辆车单独对其服务,然后通过算法把由多辆车进行的服务合并为一辆车来服务,这样最终服务的车辆数将不断减少,同时平均总路程也将下降。
第0步 存在初始路径i,…,it},设每辆车的最大行程限制为L。
第 k,若k的节省路径为负,3步,否则计算假设k合并入初始路径后的路径总长度L,若L>L,转第3步;否则,结点k合并入路径。
第2步 按第1步的方法不断合并新结点,若当前路径上的结点数超过2m,转第3步;否则,不断合并新结点,直到L>L,结束当前路径的合并。
第3步 如果还存在没有加入路径中的服务结点,选择一个还未被合并的结点作为新的初始路径,转第1步。2.2 数值试验 对文献[6]中50个结点、一个服务中心的例子,在所有结点的需求量服从B(b,015)、最大行程限制为L=300长度单位下,作了数值试验,得到如下的派车方案:
Route1=[[***********]];
Route2=[[***********]8];Route3=
[[**************]55];Route4=[[***********]7];Route5=[[***********]]。
pj=ξ≤C,∑ξ>C
i=1
i=1j
根据中心极限定律Mj=
∑ξ服从正态分布,则服
i
i=1
务失败的概率容易计算。详细计算方法见参考文献[6]。 设可行方案中一条有t个结点的路径由以下结点组成:
{i1,i2,…,it}并以L表示该路径的平均路径长度,为了保证车辆的行程不大于最大行程,要求
L≤L
则
d0i1+di1i2+…+dit-1it+dit0, t≤m;
Ld0i1+di1i2+…+dit-1it+dit0+
Pim+1(dim+10+d0im+1)+
总平均路径长度为114612,总共需要5辆车完成一次服务。与文献[6]中在没有最大行程的限制,需求量为[0,C/5]的均匀分布条件下的结果总平均路径长度为2203184,并且需要7辆车才能完成一次服务相比,虽然两者服务结点的需求分布不同,但由计算可知,由于服务失败所引起的路径增加是相当小的。这表明模拟退火算法虽然是一个概率1收敛到全局最优解的算法,但并不能
…+Pit(dit0+d0it), t>m
对服务结点i,j定义节省量如下:
d0i+d0j-dij, i
d0m+d0m+1-dij-pm+1(d0m+1+dm+10),
Sij i=m,j=m+1或反之
d0i+d0j-dij-pi(d0i+di0)-pj(d0j+dj0),
i>m,j>m
第5期钱小燕等:路径长度受限的随机需求VRP的节省算法及其策略分析35
保证全局最优化的算法一定能够求得最优化问题的全局最优解。同文献[5]的结果总平均长度160215和6辆车完成一次服务相比,有了相当大的改进。表1列出了利用文献3的生成器,随机产生不同规模的PSVRP,设它们服从B(bi,015)采用本文中所给出的算法进行计算的结果。从计算的时间和问题的规模来看,笔者提出的算法应该是比较有效的。
表1 算法的计算结果
Table1 Computationresultofproposedalgorithm
规模 50
100
[***********][1**********]
车辆容量
[***********]200200200
最大需求量
555444444路径长度限制
8001200
[***********]000028000时间/s总平均路径长度
[***********][1**********]180
[***********][***********][***********]2013
使用车辆数
[1**********]
注:PC,用Matlab编程实现。当规模大于3000,计算时间
m。
δ1=0,
3 策略分析
采用的策略考虑了服务失败,给出了多条路径,实际上是给出了一个先验顺序,现在来分析所给出的先验顺序的期望路径长度。设{1,2,…,n}的某一个排列是所给的先验顺序,C为正整数,P{ξi=k}=pi(k)是结点i的需求ξ。i=k的概率,k=0,1,…,b
定理1 如果所给的先验顺序为τ=(0=n+1,1,2,…,n,n+1),设δi为在结点i恰好服务失败的概率(车辆在服务后,不剩余容量),而γi为在结点i超出车容量的概率。则
n
n
ii+1
[ib/C]b-1b
i
δi=
q=1
∑p(r)f(i-1,qC-k)
k=1
r=k+1
,
2≤i≤n
f(m,r)表示1,2,…,m的结点服务总需求量恰
好为r,
min(b,r)
f(m,r)=
k=0
∑
pm(k)f(m-1,r-k),
m=2,…,n,r=0,…,bmf(m,r)的初始值为
f(m,r)=0,r>bm,f(1,r)0,否则
pi(r) 0≤r≤b
E[RPSVRP]=
∑d
i=0
+
∑[δT
i
i=1
ii
+γiTii+1]
其中
Tij=d0i+d0j-dij
证明:由C≥b,L≥maxi{2di0}和δi,γi的定义可以得到
δ1=0,γ1=0现在考虑在结点i≥2的情况,
如果在结点i服务完
毕后路径限制仍然满足且恰好服务失败,则前i-1
γ1=0,
[ib/C]
b
γi=
q=1
∑
k=1
pi(k)f(i-1,qC-k),
2≤i≤n
个结点已经服务过,而且它们的需求所占用的车容
量应为qC-k,k为结点i的需求,q=1,2,…,[ib/C]中某一个,k=1,2,…,b。故
3LiFY,GoldenB,WasilE.Verylarge2scalevehiclerouting:newtestproblems,algorithms,andresults.Computer&OperationsResearch,to
appear.
36
[ib/C]
b
南 京 工 业 大 学 学 报 第28卷
γi=
q=1
∑
k=1
pi(k)f(i-1,qC-k),2≤i≤n
还可以采用允许服务失败多次和允许部分服务的策
略等设计算法来求解PSVRP。参考文献:
[1] ClarkeG,WrightJ.Schedulingofvehiclesfromacentraldepotto
anumberofdeliverypoints[J].OperationsResearch,1964,12:568-581.
[2] FisherM,JaikumarR.Ageneralizedassignmentheuristicforve2
hiclerouting[J].Networks,1981,11:109-124.
[3] BodinL,GoldenB.Classificationinvehicleroutingandschedu2
ling[J].Networks,1981,11:97-108.
[4] BodinL,GoldenB,AssadA,etal.Routingandschedulingofve2
hiclesandcrews:thestateoftheart[J].ComputersandOpera2tionsResearch,1983,10:169-[5] 刘浩,.VRP的模型和算法
[J].:,2005,27(3):36-38.[6]D,Asimulatedannealingtechniqueap2
routinginthecaseofstochasticdemand[J].portationPlanningandTechnology,1992,16:261-273.
如果在加入结点i后满足路径限制但不是恰好服务
失败,则前i-1个结点的需求仍为qC-k,q=1,2,…,[ib/C]中某一个,但在服务结点i时,因为所剩车容量仅能装下容量为k的货物,所以此时有0
[ib/C]
b-1
b
i
δ i=
q=1
∑∑p(r)f(i-1,qC-k)
k=
1
r=k+1
,
2≤i≤n
至于递推关系和初始条件是显然的。证毕
4 结 论
在保证路径长度限制,至多只有一次服务失败和不允许部分服务的策略下,给出了PSVRP,从计算时间和计算问题的规模来看Modifiedsing-algorithmandstrategyanalysisforpathlengthconstrained
vehicleroutingproblemwithstochasticdemand
QIANXiao2yan
1,2
,CHENGHao,LIUHao
22
(1.CollegeofSciences,NanjingUniversityofAeronauticsandAstronautics,Nanjing210016,China;
2.CollegeofSciences,NanjingUniverstiyofTechnology,Nanjing210009,China)
Abstract:Underthestrategyofkeepingpathlengthconstrainedtightlyandonlyonetimeroutingservicefailureandnopartservice,anewrouting2savingpathwasdefinedandasaving2algorithmisproposed.Thealgorithmwastest2edundermiddleandlarge2scalePSVRPnumerically;numericalresultindicatedthealgorithmisvalid.Thestrategyanalysiswasdiscussedandtheoreticalresultswereobtained.
Keywords:pathlengthconstraint;stochasticdemand;vehicleroutingproblem;saving2algorithm;routingfailure;
strategy
2analysis