有时间窗的车辆路径问题的近似算法研究[1]
第10卷第7期2004年7月
计算机集成制造系统
ComputerIntegratedManufacturingSystemsVol.10No.7Jul.2004
文章编号:1006-5911(2004)07-0825-07
有时间窗的车辆路径问题的近似算法研究
刘小兰,郝志峰,汪国强,符克强
(华南理工大学应用数学系,广东 广州 510640)
摘 要:为了克服原有大规模邻域搜索算法不能有效求解时间窗较宽的车辆路径问题的缺陷,介绍了有时间窗的车辆路径问题(VRPTW)的通用数学模型。通过分析各主要变量之间的关系,构造了一种简单、快速的确定性初始算法。通过引入”短路径优先策略”,构造了一种改进的大规模邻域搜索算法,该策略也可嵌入到求解时间窗比较窄的车辆路径问题中,达到加速搜索的目的。试验结果表明,改进的算法可以在较短的时间内有效地求得
VRPTW的优化解,是求解VRPTW的一个较好方案。
关键词:有时间窗的车辆路径问题;大规模邻域搜索算法;初始算法中图分类号:TP29 文献标识码:A
0 引言
车辆路径问题(VehicleRoutingProblem,VRP)是
邮政投递、校车接送学生等配送和交通运输系统的重要组成部分。自1959年DANTIGG等人[1]首先提出以来,至今已衍生出多种不同类型的问题。有时间窗的车辆路径问题(VehicleRoutingProblemwithTimeWindows,VRPTW)是在VRP的基础上加上客户要求访问的时间窗口。由于现实生活中许多问题都可归结为VRPTW来处理,所以对它的研究越来越受到人们的重视。事实证明,VRPTW是NP难题[2]。
目前求解VRPTW的方法很多,如遗传算法、禁忌搜索和模拟退火等。1998年PaulShaw提出的大规模邻域搜索算法(LargeNeighborhoodSearchAlgo2rithm,LNS)[3],以其算法框架简单、适用范围广等特点脱颖而出,但其也存在两个明显的缺点:①采用的初始解质量非常差,需要耗费很长时间进行优化;②不能有效解决时间窗比较宽的VRPTW。本文的改进LNS算法就是为了克服以上两个缺点而提出的,它继承了LNS算法的优点,同时克服了以上缺点。
收稿日期:2003-06-16;修订日期:2003-10-29。
1 问题的描述及数学模型
问题的描述:给定n个客户C={1,2,…,n}及其需求量di,k辆汽车V={1,2,…,k}及其最大负荷qi,问题是设计每辆汽车的行驶路线,要求满足如下约束:①每个客户恰好被服务一次;②每条路线起始于出发点0,终止于出发点n+1,记N={0,1,…,n+1};③每条路线的总负荷不能超过汽车的最大负荷;④每个客户必须在其时间窗口[ai,bi]内被服务,这个时间窗说明,汽车必须在bi之前到达客户i,在ai前汽车虽然可以到达客户i,但是汽车必须等待而不能马上为客户服务。最终目标通常有两个:①使所用的汽车数目最少;②使所有的汽车走过的总路程最短。其中,第一目标高于第二目标,也就是说,需要更少数目车的解总比需要更多车的解要好,而不管第二目标的值如何。这主要是由于多派一辆汽车的成本较大的缘故。
定义σi表示客户i需要的服务时间;tij表示汽车从客户i到客户j的行驶时间(正比于i和j之间的欧几里得距离);sik表示汽车k开始为客户i服务
基金项目:国家自然科学基金资助项目(19901009);广东省自然科学基金资助项目(000463,031360);教育部优秀青年基金资助项目;广东省“千
百十工程”优秀人才基金资助项目。
作者简介:刘小兰(1979-),女,江西人,华南理工大学应用数学系硕士研究生,主要从事算法设计与分析等研究。
E-mail:[email protected]。
826计算机集成制造系统第10卷
的时间,令s0k=0。如果汽车k没有为客户i服务,则sik没有任何意义。定义变量xijk:
1 汽车k为客户i服务
{2,3,4}表示第二条路径。
2 改进的大规模邻域搜索算法
211 LNS算法的优缺点
LNS是1998年由PaulShaw提出的。它从初始解出发,经过remove(从当前解σ中移走部分客户,
(1)(2)(3)
完后直接开往客户j。0 其他
则VRPTW的数学模型可以表示为[4,5]:
xijk=
(VRPTW)min
x0, ∑∑
min∑∑∑tx,
jk
k∈Vj∈N
ijijk
k∈Vi∈Nj∈N
s.t.
k∈Vj∈N
x∑∑
ijk
=1, Πi∈C;
)和re-insertion(将移走的客户重新插回σ得到σ′′
中)两个过程的不断优化,最终得到优化解。
通过实验,PaulShaw发现LNS具有以下几个优点:①LNS的搜索技巧与约束规划技术非常吻合,该
∑di
i∈Cj∈N
j∈N
x∑
ijk
≤qk, Πk∈V;
Πk∈V;
=0,
(4)(5)
∑x0jk=1, ∑xihk-i∈N
i∈N
j∈N
x∑
算法可以解决现实世界中约束非常复杂的问题;②LNS的算法框架非常简单,但它与运筹学中最好的Meta-heuristic算法相比,极具竞争力———不仅平均表现不错,而且产生了几个其他方法不能得到的更好解;③在每条路径含有的客户数不是很多的情况下,LNS可以同时优化第一和第二目标。因此,LNS求解时间窗比较窄的问题特别有效。然而LNS也存在如前所述的缺点。改进的LNS主要从克服以上两个缺点考虑,首先设计了一种简单、快速的确定性初始算法———基于“开始服务时间最早优先法”,然后提出了“短路径优先策略”来克服第二个缺点。212 基于“开始服务时间最早优先”的初始算法
由于VRPTW的复杂性,生成一个较好的初始
hjk
Πh∈C,Πk∈V;(6)Πk∈V;
(7)
∑xi,n+1,k=1,
sik+σi+tij-T(1-xijk)≤sjk,
Πi,j∈N,Πk∈V;
ai≤sik≤bi,
xijk∈{0,1},Πi,j∈N,Πk∈V。
(8)(10)
Πi∈N,Πk∈V;(9)
在上述表达式中,式(1)表示使需要的汽车数目最少;式(2)表示使所有的汽车走过的路程最短;式(3)表示每个客户仅能被访问一次;式(4)表示被调用的汽车都满足负载要求;式(5)～式(7)保证每辆汽车从出发点出发,访问客户后,最终回到出发点;式(8)表示汽车k在从客户i向客户j行驶的过程中,在时间sik+σi+tij之前不能到达客户j,其中T是一个较大的标量;式(9)表示汽车为客户i服务的时间必须在其时间窗口内;式(10)是整数化的约束。
该模型通用性很强,经过参数的不同设定,可以将其转换为其他组合优化问题的数学模型。例如,设定ai=0,bi=M(M是一个很大的数),则可以把约束式(8)和(9)去掉,这样VRPTW模型就变成了普通的VRP模型;如果只提供一辆汽车,则该问题就是TSP;如果有多辆汽车可利用,且附加条件t0j=1,
j∈C和tij=0,就得到了装箱问题的数学模型。
可行解很不容易,因此不少研究者选择随机产生初始解,而不管其可行与否。一些研究者把给每个客户都派一辆车服务作为初始解。这种处理的缺点是:搜索了很多不可行解区域或者初始解离最优解距离太远,增加了优化时间。还有一些研究者利用经典的节约法[6]来产生初始可行解。该算法虽可以产生较好的可行解,但其时间复杂度为O(n4)。所以,找一个快速的初始算法仍然具有很大的意义。
本文通过分析客户间的距离、客户的时间窗和开始为客户服务的时间等量之间的关系,构造了一种简单、快速的确定性算法产生可行解,其时间复杂度为O(n2log2n)。21211 算法步骤
VRPTW的解可以用一个整数序列来表示,例如
对于有5个客户的VRPTW。假设一个解为:第一辆
汽车按照1,5的顺序为客户服务,第二辆汽车按照2,3,4的顺序为客户服务,则可以用序列01502340来表示,其中,σ1={1,5}表示第一条路径,σ2=
算法采用路径直接构造法,即每次从还未加入
到路径中去的客户,按照“距离当前路径的最后一个客户开始服务时间最早优先”的规则,选一个加入到当前路径或作为一条新的路径的第一个客户。设当前路径σc={c1,…,cm},ci∈C,cm为当前路径的最后一个客户,U={u1,…,un}表示还未加入到路径的客户的集合。按照式(11)计算U中每个客户的
第7期刘小兰等:有时间窗的车辆路径问题的近似算法研究827
“最早开始服务时间”Stime(ui):
max(Stime(cm)+σ(cm)+tc
Stime(ui)=
m,u
i
,au)
i
if(Stime(cm)+σ(cm)+tc,u≤bu)。
mii
T if(Stime(cm)+σ(cm)+tc
m,u
i
(11)
>bu)
i
如果从当前路径的最后一个客户出发,到达客户ui的时间早于允许为客户ui服务的最早时间
aui,则必须等到aui才能为客户服务;而当到达客户ui的时间晚于最晚时间bui,则表示超过客户ui的
最早开始服务的客户作为新路径的第一个客户。
(3)重复上述步骤,直到U为空集。
排序采用快速排序法,通过分析,可以知道该算法的时间复杂度为O(n2log2n),n为客户数。21212 实验结果及分析本文采用Solomon的56个例子来测试算法的效果,并与节约法进行比较。56个例子可以在http://www.idsia.ch/～luca/macs-vrptw/problems/welcome.htm找到。每个例子都含有100个客户和一个出发点,分为6大类,其中,R1和R2中的客户是随机分布的,C1和C2中的客户有聚集趋势,RC1和RC2中的客户兼有R类和C类的特性。R1,C1和RC1类的每个例子的出发点具有较窄的时间窗,使得每辆车能够服务的客户数较少,最优解需要9～19辆汽车;而R2,C2和RC2类的每个例子的出发点具有较宽的时间窗,最优解只需要2～4辆汽车。
表1的数据是在联想PⅡ500,256M内存环境下用VC6.0实现的。其中,Data代表问题,NV代表需要的汽车数,TD代表汽车总的行驶路程,CT代表clock()/CLOCKS-PER-SEC算出的秒数,黑体代表本文算法的结果比节约法好。
时间窗,不能加入到当前路径,所以赋一个很大的值T以示区别。
算法的具体步骤是:
(1)按照式(11)计算U中每个客户的“最早开始服务时间”Stime(ui);
(2)将Stime(u1),…,Stime(un)由小到大排序为Stime(ui1),…,Stime(uin)。如果最小值≠T并且将客户ui1加入到当前路径后不会引起汽车超载,则将该客户加入到当前路径的最后;如果最小值≠T但将客户ui1加入到当前路径后会引起汽车超载,则依次验证第二小值的、第三小值的、…,直到找到一个符合条件的客户。极端情况下,U中所有客户都不满足条件,则从U中选择一个从出发点开始,能够
表1 与节约法的比较结果
DataR102R107R112C105节约法
NV25191212TD1762.011398.831086.68931.349CT[1**********]9本文的初始算法
NV
TD2340.721856.711457.712058.58CT0000DataR202R207C205节约法
NV1485TD1264.44943.53729.124CT222645本文的初始算法
NV
TD1909.211428.33744.218CT000
828计算机集成制造系统
续表1
DataRC104第10卷
节约法
NV13TD1272.40CT216本文的初始算法
NV
TD1671.16CT0DataRC204节约法
NV8TD927.998CT25本文的初始算法
NV
TD1429.39CT0 从表1可以得到如下结论:
(1)实验结果表明,本文的算法所需要的运行时间比节约法明显要少,证明是一种快速的算法。
(2)本文的算法在求解R2,C2,RC2等客户时间窗比较宽的问题时,可以得到明显比节约法好得多的结果;而在求解R1等客户时间窗比较窄的问题时,所得的结果比节约法稍差一些。这说明两种方法各有自己的适用范围。
(3)用本文的算法求解56个例子所得的第二目标值普遍比节约法的差,这是由于本文的算法侧重于产生一个可行的初始解,对这些目标没有花太多时间去进一步优化。下一节将对此初始解进行进一步优化。
213 改进的大规模邻域搜索算法
两个影响LNS搜索效果的关键因素为:①re2move过程中如何选出被移走的客户;②re-insertion
在同一条路径上时为0,否则为1。
也就是说,地理位置相距很近的两个客户的相关性比相距很远的要大;在同一条路径上的两个客户的相关性比不在同一条路径上的要大。这与笔者
的直观分析是一致的。但是按照式(12)选出的客户
c只能保证其与S中的某个客户相关性很大,而不
能保证与S中的其他客户相关性也很大。下一个将要被移走的客户最好是和S中的所有客户“总体相关性”最大的客户,这样在re-insertion中才会有更大可能产生更好的解。因此,笔者提出客户i和集合S的总体相关性的概念,其定义如下:
Relateness(i,S)=
Relateness(i,j)∑
|S|
。(13)
即客户i和集合S的总体相关性等于i和S中所有客户相关性的平均值。
如果仅根据相关性的大小来挑选客户,则极可能相同的客户会反复被选出。为了避免这种情况,PaulShaw在算法中加入了随机因素:Random([0,σ中剩余的客户数目,它的结果是相关性大1])B×
小序列中的某一个客户。参数B是可以调节的,它的值越大,越有利于相关性大的客户,这与笔者选出客户的大原则是一致的。移走的客户数p也是一个可调节的参数,一开始可以设为1,当迭代Itera2tion1次后仍不能得到改进的解,则p增加1,其上界
过程中如何快速地将客户插到能产生更好解的位
置。21311 remove过程
用符号σ表示当前解,c表示将要被移走的客户,S表示被移走的客户组成的集合,p表示移走的客户数目,σ′表示从σ中移走p个客户后剩余的部分解,则PaulShaw的策略如下:
首先,从σ中随机移走一个客户到S中,作为集合S中的第一个元素。剩下的p-1个元素按照如下的方法来选定:每次从集合S中随机选一个客户z,将σ中剩余的客户按照与z的相关性由小到大的顺序排列。从σ中选出与z的相关性最大的客户c,从σ中移走c,并把它加入到S中去。重复该过程p-1次,直到剩下的p-1个元素都选好。相关性的定义为:
(12)relateness(i,j)=′。
tij+vij
可设为30,因为p太大,耗费的运行时间会很长。为了克服第二个缺点,笔者提出一种短路径优
先策略。其思路是:当大多数路径含有的客户数较多时,按照上述remove过程,每次移走的p个客户来自同一条路径的可能性很小,这是LNS不能有效减少汽车数目的原因所在。如果优先将路径长度最短的那条路径上的所有客户都移走,则经过re-in2sertion过程后还是有可能产生比当前解的汽车数目
式中,t′ij=
tmaxtij
,其取值介于0与1之间;vij当i和j
减少1的解。当然,此策略执行有限次后将自动终止。设其迭代次数为Iteration2,可以将这个策略和
第7期刘小兰等:有时间窗的车辆路径问题的近似算法研究829
remove过程交叉执行:remove过程改进解的速度较
慢,其主要作用在于优化第二目标;而短路径优先策略在可以改进解的情况下,改进解的速度较快,其主要作用在于优化第一目标。具体实施时可以用迭代次数来控制两种策略的交叉运行。21312 re-insertion过程
re-insertion过程是将移走的客户集S重新插
回部分解σ′,以产生更好的解。当S中的客户数目较多时,S中的所有客户重新插回σ′中将会有很多种插入组合,因此,直接穷举出它们可能的插入组合是不可行的。下面给出文献[3]和文献[7]的算法框架。
首先计算S中每一个客户的最佳插入位置。将S中的客户c插回部分解σ′,在多个插入位置中,找出使目标值增加最少的那个位置即为其最佳插入位置,并记下对应的目标值。比较S中各个客户的最佳插入位置对应的目标值,从中选一个能使目标值增加最少的客户c。算法按照目标值递增的顺序,将c插回部分解σ′中,把c从S中移走,同时搜索将S中剩余的客户都插回σ′能得到的所有解NI(σ′,S)。重复以上过程,直到S为空集,表示当初被移走的客户都已经插回σ′。比较σ′与目前找到的最好解σ′比σ′替换σb,如果σb要好,则用σb,成为目前的最好解。
用记号minf(NI(σ′,S))表示解N1(σ′,S)所能达到的最小目标值。如果minf(NI(σ′,S))的下界大于目前最好解σb的目标值,则不用将S中的客户再插回σ′。只有当minf(NI(σ′,S))的下界小于目前最好解σb的目标值时,才继续搜索下去。因此,如果事先可以估计出minf(NI(σ′,S))的一个较好的下界,则可以大大地减少搜索的范围,提高搜索效率。
文献[7]提供了估计minf(NI(σ′,S))下界的框架,下面给出一种具体的估计方法。假设部分解σ′包含m条路径,则NI(σ′,S)就是在保持σ′中各条路径上的客户相对顺序的条件下,将S中的客户一一插回σ′中所能得到的解。如果将条件放宽,不必保持这些客户的相对顺序,直接寻找覆盖全部客户节点的K条最短路径(假设到当前时刻为止的最好解需要K辆汽车),就得到了minf(NI(σ′,S))的一个下界了。因此,minf(NI(σ′,S))的一个下界可以通过将问题松弛为寻找k棵不相交的生成树问题而得到解决。现在的关键点是插入图应该包括哪些
边。按照文献[7]的思路,插入图的边集来源于三部分:σ′中的边集,所有连接S和S中客户的边集,以及所有连接C和S中客户可行的边集。其确切定义如下:
定义1(插入图) 插入图G(C∪S,E)的边集E是按如下构造的:
+
E=Eσσ′∪ES∪EC,E′={(i,i)|i∈C},ES=
),j)|j∈{(i,j)|i,j∈S}EC={(pred(j,σ
)∈C&σ∈N1(σS&pred(j,σ′,{j})}∪{(j,succ(j,
σ))|j∈S&succ(j,σ)∈C&σ∈N1(σ′,{j})}。其中,i+表示与i相邻且位于j后面的节点,pred(j,σ)表示在σ中与j相邻且位于j前面的节点,succ(j,σ)表示在σ中与j相邻且位于j后面的节点。
下面借用Kruskal[8,9]算法来生成k棵生成树,具体步骤如下:
(1)把G的边按权的大小顺序排好,即要求ω(e1)≤ω(e2)≤…≤ω(em),j=1,i=0。
(2)若已生成的部分树T(ei,ei,…,ei)含有K
12i
条路径且j≤m,则退出,说明minf(NI(σ′,S))的下
界不会比当前最好解更好;否则,如果与已生成的部分树T(ei1,ei2,…,eii)不构成回路,则i++;T=T∪ej。
(3)j++;若j≤m,转(2);否则停止。再将起点0和终点n+1也考虑进去,进一步优化得到的界,按照与前面相同的方法构造边集,再添加上起始于0和终止于n+1的边。
(4)选择从0出发的K条最短边添加到T中,同时选择终止于n+1的K条最短边也添加到T中。计算T中所有边的权重之和即可作为minf(NI(σ′,S))的一个下界。
实验结果得到了与PaulShaw类似的结论:在大多数情况下,分枝定界re-insertion过程能够在很短的时间内对p≤15找到一个更好的解或证明没有更好的解。然而对某些问题,当p继续增大时,该过程却需要花费很长的时间。为了提高搜索效率,引进不完全搜索———有限偏差搜索(LimitedDiscrepan2cySearch,LDS)。LDS[10]是WilliamD.Harvey和MatthewL.Ginsberg于1995年首先提出的。它是建立在“手头上已经有求解某个问题的一种较好的启发式算法”的基础上的,其基本思想是:假设按照事先设计的启发式算法不能找到目标,则很有可能是算法在几个关键点上“出差错了”———本该朝东走的,却在朝西走了。如果允许算法在这些关键点上
830计算机集成制造系统第10卷
“犯错误”———背离算法在这些点的走向,转向其他方向,然后继续按照算法搜索下去,则极有可能找到目标,详细的介绍见文献[10]。运用到VRPTW,D=0表示S中全部的客户都插入到最佳的位置,记为(P1,P2,…,P|S|)=(0,0,…,0),其中,Pi表示第
i个插回的客户的插入位置,0表示插入到最佳位
|S|
21313 实验结果及分析
主要参数设置如下:remove过程和短路径优先策略交替执行的次数设为2,如果不能获得好的解,可以适当增加次数;remove的最大迭代次数Itera2tion1一般取为100,如果不能得到好的解,可增加到上限500;短路径优先策略的迭代次数Iteration2:对于时间窗比较窄的问题,一般取为35,如果不能获得好的解,则可以增加到上限50,而对于时间窗比较宽的问题,一般取为5;LDS搜索的偏差d一般取为4,如果不能获得好的解,则可以增加到上限10;
B取为15。
置,可以看出满足
i=1
∑P
i
=D=0;D=1表示S中只
有一个客户插入到其第二好的位置,其余的都插入
|S|
到最佳的位置,即满足
i=1
∑P
i
=D=1的位置,如(1,
0,…,0);D=2表示S中一个客户插入到其第三好
的位置,或者S中两个客户插入到其第二好的位置,
|S|
即满足
i=1
∑P
i
=D=2的位置,如(2,0,…,0),(1,1,
…,0),其余以此类推。笔者只使用一个阶段的LDS,D的上限d为一事先给定的值。
采用2.2节得到的初始解,运用改进的LNS算法求解Solomon的56个例子,并与目前已知的最优解(源自文献[7]的数据)进行比较,得到表2所示的结果。其中,N%表示第一目标与已知最优解的相对误差×100;T%表示第二目标与已知最优解的相对误差×100。
表2 与已知最优解的比较结果
节约法
DataR102R107R110R112C105RC101RC103RC106RC108
NV[**************]10
TD1486.121104.661124.40982.14828.941696.941261.671427.131139.82
改进的LNS
NV[**************]10
TD1545.801171.871154.061009.73828.941782.301275.431467.531165.92
相对误差
N%
T%
节约法
DataR202R207R210C205RC201RC203RC206RC208
NV32334333
TD1191.70914.39939.37588.881406.9401060.4501153.93829.69
改进的LNS
NV32334333
TD1195.12926.12968.90588.881512.631087.561197.63829.69
相对误差
N%
T%
010100009.00046.02.62.805.01.02.82.2
00000000
0.01.33.107.52.53.70
第7期刘小兰等:有时间窗的车辆路径问题的近似算法研究831
从表2可以得到如下几点结论:
(1)改进的LNS求得的结果或者达到已知最优解,或者非常接近已知的最优解(NV的平均相对误差为0.85%,TD的平均相对误差为2.3%),这说明改进的算法具有很强的寻优能力。
(2)为了进一步了解改进的LNS搜索到最优解的潜力,笔者还跟踪了运行时间与解的质量的关系。结果发现,改进的LNS能够在较短的时间内找到一个很接近最优解的解,如果需要进一步优化则需花费稍长一些的时间。最快的只需40～50秒左右,慢的最多十几分钟。可以相信,如果再增加一些运行时间,改进的算法还可以搜索到更好的解。
(3)通过加入短路径优先策略,改进的LNS算法能够很好地解决R2,C2,RC2等时间窗比较宽的问题,求得的第一目标与已知的最优解相吻合,有些第二目标也达到了已知的最优解,从而克服了原来的LNS算法的缺陷。参考文献:
[1] DANTZIGG,RAMSERJ.Thetruckdispatchingproblem[J\〗.
ManagementScience,1959,10(6):80-91.[2] SAVELSBERGMWP.Localsearchforroutingproblemwithtime
windows[J\〗.Ann.ofOperationsResearch,1985,16(4):285-
305.
[3]SHAWP.Usingconstraintprogrammingandlocalsearchmethodsto
solvevehicleroutingproblems[A].PrinciplesoftheFourthInterna2tionalConferenceonPrinciplesandPracticeofConstraintProgramming[C].1998.417-431.[4] LARSENJ.Parallelizationofthevehicleroutingproblemwithtime
windows[D].Denmark:TechnicalUniversityofDenmark,1999.[5] ZHANGLiping,CHAIYueting,CAORui.Improvedgeneticalgorithm
forvehicleroutingproblemwithtimewindows[J].ComputerIntegrated
ManufacturingSystems,2002,8(6):451-454(inChinese).[张丽
萍,柴跃廷,曹 瑞.有时间窗车辆路径问题的改进遗传算法[J].计算机集成制造系统,2002,8(6):451-454.][6] CLARKEG,WRIGHTJW.Schedulingofvehiclesfromacentralde2
pottoanumberofdeliverypoints[J].OperationsResearch,1964,12:568-581.[7] BENTR,HENTENRYCKVanP.Atwo-stagehybridlocalsearchfor
thevehicleroutingproblemwithtimewindows[R].USA:BrownU2niversity,2001.
[8] XIEZheng,LIJianping.Networkalgorithmandcomplexitytheory
[M].Changsha:NationalUniversityofDefenceTechnologyPublishHouse,1995(inChinese).[谢 政,李建平.网络算法与复杂性
理论[M].长沙:国防科技大学出版社,1995.]
[9] LIBangyi,YAOEnyu.Theconstrainedminimumspanningtreeprob2
lem:complexityandestimationofthebound[J].JournalofZhejiangofUniversity(SciencesEdition),2000,27(3):237-242(inChi2nese).[李帮义,姚恩瑜.约束最小支撑树(C-MST)问题:复杂
性和上下界估计[J].浙江大学学报(理学版),2000,27(3):237
-242.]
[10] HARVEYWD,GINSBERGML.Limiteddiscrepancysearch[A].
Proceedingsofthe14thInternationalJointConferenceonArtificialIn2
telligence[C].1995.
Improvedlargeneighborhoodsearchalgorithmforvehicleroutingproblemwithtimewindows
LIUXiao-lan,HAOZhi-feng,WANGGuo-qiang,FUKe-qiang
(Dep.ofAppliedMathematics,SouthChinaUniv.ofTech.,Guangzhou 510640,China)
Abstract:Thevehicleroutingproblemwithtimewindows(VRPTW)cannotbesolvedeffectivelybyusingtheexistingLargeNeighborhoodSearch(LNS)algorithm.AuniversalmathematicalmodelofVRPTWwasbuilt.Byanalyzingthere2lationofseveralmainvariables,asimple,fastdeterministicinitialalgorithmwasproposed.AnimprovedLNSalgorithmwasputforwardbasedontheshortestrouteprioritystrategy,whichcouldsolvetheproblemswithlongschedulinghorizoneffectively.Thestrategycouldalsobeappliedtosolvingtheproblemswithshortschedulinghorizontoacceleratesearch2ingprocess.ExperimentresultsshowthattheimprovedalgorithmcanfindtheoptimalornearoptimalsolutiontoVRPTWinshorttime.
Keywords:vehicleroutingproblemwithtimewindows;largeneighborhoodsearchalgorithm;initialalgorithm
Received16Jun.2003;accepted29Oct.2003.
Foundationitem:ProjectsupportedbytheNationalNaturalScienceFoundation,China(No.19901009),theNaturalScienceFoundationofGuangdongProvince,
China(No.000463,031360),theExcellentYoungTeachersProgramofMoE,China,andthe“Qian-Bai-Shi”TalentYoungFoundationofGuangdongProvince,China.