A hybrid algorithm for vehicle routing problem with time windows
B.Yu a ,Z.Z.Yang a ,*,B.Z.Yao b
a Transportation Management College,Dalian Maritime University,Dalian 116026PR China
b
School of Civil Engineering &Architecture,Beijing Jiaotong University,Beijing 100044,PR China
a r t i c l e i n f o Keywords:VRPTW
Ant colony optimization Neighborhood search Tabu search
a b s t r a c t
Vehicle routing problem with time windows (VRPTW)is a well-known combinatorial problem.Many researches have presented meta-heuristics are effective approaches for VRPTW.This paper proposes a hybrid approach,which consists of ant colony optimization (ACO)and Tabu search,to solve the problem.To improve the performance of ACO,a neighborhood search is introduced.Furthermore,when ACO is close to the convergence Tabu search is used to maintain the diversity of ACO and explore new https://www.doczj.com/doc/bc1423762.html,putational experiments are reported for a set of the Solomon’s 56VRPTW and the approach is com-pared with some meta-heuristic published in literature.Results show that considering the tradeoff of quality and computation time,the hybrid algorithm is a competitive approach for VRPTW.
ó2010Elsevier Ltd.All rights reserved.
1.Introduction
Vehicle routing problem (VRP)is found to be widely applicable to logistics distribution,school bus routing and mail etc.It has been studied for the last 40years.A typical VRP can be described as a weighted graph.Fig.1shows an example of VRP,where the de-pot is denoted as 0and the customers are denoted as 1through 10.The solution includes three routes:0–2–1–5–7–0,0–3–4–6–0and 0–8–9–10–0.
One of the most common extensions is vehicle routing problem with time windows (VRPTW)in practice.In VRPTW,vehicles ser-vice all the customers during a given interval without violating capacity constraints.The objective of the problem is to ?nd a set of minimum cost routes for vehicles from a central supply depot.Many researches have presented meta-heuristic approaches are strong tools to solve VRPTW,such as Simulated Annealing (Czech &Czarnas,2002;Li &Lim,2003),genetic algorithms (Alvarenga,Mateus,&de Tomi,2007;Berger &Barkaoui,2004;Br?ysy &Gend-reau,2001;Chen,Lee,&Ke,2001;Cheng &Wang,2009;Potvin &Bengio,1996;Tan,Lee,&Ou,2001a;Tan,Lee,Ou,&Lee,2001b;Ting &Huang,2004),Tabu search (Chiang &Russell,1997;Ho &Haugland,2004;Potvin,Kervahut,Garcia,&Rousseau,1996;Tail-lard,Badeau,Gendreau,Geurtin,&Potvin,1997),and ant colony optimization (Gambardella,Taillard,&Agazzi,1999;Gong,Liu,Zhang,&Fu,2007).Compared with Tabu search and genetic algo-rithm (GA),ACO is less applied in VRPTW.However,ACO has suc-cessfully been applied to solve capacitated vehicle routing problems,such as (Bullnheimer,Hartl,&Strauss,1999;Doerner
et al.,2002;Doerner,Hartl,Kiechle,Lucka,&Reimann,2004;Maz-zeo &Loiseau,2004;Yao &Yao,2007;Yu,Yang,&Yao,2009).The focus of this paper is to apply ACO in VRPTW.ACO ?nds good solution depending on the experience of proceeding ants.Sometimes,ACO tramps into local optimality.Therefore,it is fair and reasonable to introduce a method to prevent ACO into tramp-ing into local optimality.Furthermore,the diversity of ACO is low near the convergence.Tabu search is a meta-heuristic based on re-cency memory.Tabu search can explore good solutions around a given solution by using a local or neighborhood search procedure and a Tabu list.The ideas between ACO and Tabu search are very different.Tabu search does not rely on the ‘‘history”information from the preceding search but randomly to select the search direc-tion which can enlarge search space.Meantime,determining the initial solution of Tabu search is dif?cult.Considering the natures of ACO and Tabu search,this paper presents a hybrid algorithm integrating ACO and Tabu search to solve VRPTW.This paper is or-ganized as follows.The problem formulation of VRPTW is intro-duced in Section 2.Section 3describes the hybrid algorithm.Section 4validates the proposed hybrid algorithm by Solomon’s benchmark test problems (Solomon,1987).Lastly,conclusions are given in Section 5.
2.Problem formulation
The difference between VRPTW and VRP is the introduction of the time windows constraint.The time windows constraint is de-noted a time interval between the earliest arrival time and the lat-est arrival time.In this study,if a vehicle arrives before the earliest arrival time the service cannot start until the time windows begins.The formulation of VRPTW is described as the following:
0957-4174/$-see front matter ó2010Elsevier Ltd.All rights reserved.doi:10.1016/j.eswa.2010.06.082
*Corresponding author.
E-mail address:Yangzhongzhen@https://www.doczj.com/doc/bc1423762.html, (Z.Z.Yang).
Min
X N
i?0X N
j?0;j–i
X K
k?1
c ij x ijk
P K k?1P N
j?1
x ijk6K for i?0ea
P N j?1x ijk?
P N
j?1
x jik61for i?0k2f1;...;K geb
P K k?1
P N
j?0;j–i
x ijk?1for i2f1;...;N gec
8 >>> >>> >>> >>> >>> >>> >>> >>> >>> >>
x ijk?
1the link from customer i to j is visited by vehicle k 0otherwise
t i is the arrival time at customer i;w i is the wait time at customer i; K is the total number of vehicles;N is the depot and customers set;
c ij is the length on the link from customer i to j;t ij is travel time be-tween customer i an
d j;q i is th
e quantity o
f the goods to be deliv-ered at customer i;Q is the capacity of a vehicle;e i is the earliest arrival time at customer i;l i is the latest arrival time at customer i;s i is the service time at customer i;T k is the maximum route time allowed for vehicle k.
The objective is to minimize the total travel length under sev-eral constraints:(a)the maximum number of routes constraint, (b)travel constraints,(c and d)service constraints,(e)the capacity constraint,(f)the maximum travel time constraint and(g–i)the time windows constraints.For more details see(Tan et al.,2001a, 2001b).3.ACO–Tabu
3.1.Improved ACO for VRPTW
Ant colony optimization is a meta-heuristic technique inspired from the behavior of real ants searching food.ACO was?rstly pre-sented by Dorigo,Maniezzo,and Colorni(1996)and it has success-fully been applied as a solution tool to some classic compounding optimization problems(Colorni,Dorigo,Maniezzo,&Trubian, 1994;Dorigo et al.,1996;Gambardella et al.,1999;Schoonderw-oerd,Bruten,Holland,&Rothkrantz,1996;Yu et al.,2009;Yu, Yang,&Xie,2009).
3.1.1.Solution construction
In the VRPTW,each ant starting at the central depot and it con-structs a route by incrementally selecting customers under some
Fig.1.A typical vehicle routing problem.
Fig.2.Sequence code of the solution from Fig.1. Fig.3.Exchanging two customers between two routes.
Fig.4.Inserting a customer into anther route.
Fig.5.Routes of the solution from Fig.4.
constrains until its quantity is empty.The process is performed repeatedly until all customers are served,and a feasible solution can be attained.
Let U(k)denotes the set of unvisited nodes of ant k and the ant located at customer i.Thus,to select the next customer in the con-struction graph,the ant k uses the following probabilistic rule:
ij ekT?
?s ij a??g ij b
P
h R UekT
?s ih a??g ih b
j R UekT
0otherwise
8
<
:e2
where,p(k)is the probability of choosing to combine customers 3.1.2.Neighborhood search
When using a heuristic for combinational problems,local search is always considered as a ef?cient way to improve the solu-tion.In this study,a neighborhood search algorithm is introduced to enlarge the local search ability of the ACO.The2-opt exchange (Bullnheimer et al.,1999)is also used to improve the solution.
The neighborhood search is conducted by changing customer nodes of one or two routes in a solution.In order to describe the neighborhood search,an example of the solution is shown in Fig.2,which is a sequence codes transformed from the solution in Fig.1.There are two strategies to select neighbors.
(1)Exchanging customers between two routes(Fig.3)
Firstly,randomly select two routes from the solution,e.g., 0–2–1–5–7–0and0–8–9–10–0.Then,a customer is picked up from each selected route satisfying the capacity con-strain,respectively, e.g.,customer7and customer8.
Through exchanging the two customers a new solution can be acquired.
(2)Inserting customers between two routes(Fig.4)
Firstly,randomly select a route(e.g.,0–2–1–5–7–0)and a cus-tomer from the route(e.g.,customer7).Then,the customer is ran-domly inserted into anther route satisfying the capacity constrains
Fig.6.Routes using2-opt exchange.
Fig.7.The?owchart of ACO–Tabu.
Applications38(2011)435–441437
solutions.In ACO algorithms,after each iteration the pheromone trails of the tour are updated by
s new ij
?q ?s old
ij t
X K k
p L k q 2e0;1T
e3T
where,s new ij is the pheromone on the link (i ,j )after updating;s old ij is the pheromone on the link (i ,j )before updating;and q is the parameter that controls the speed of evaporation,here q =0.8;k =the No.of the route;K is the number of the vehicles in the solu-tion,K >0;p is a constant,here p =1000.L k is the total length of the routes in the solution.
3.2.Tabu search algorithm
Tabu search is a memory-based meta-heuristic ?rstly presented by Glover and Laguna (1997).The idea of Tabu search is to con-struct an initial solution and attempts to exploit neighborhoods of the solution and improve optimization.It has successfully been applied in solving real life problems (Augugliaro,Dusonchet,&Sanseverino,2002;Bortfeldt,Gehring,&Mack,2003;Falco,Del Ba-lio,Tarantino,&Vaccaro,1994;Ho &Haugland,2004;Talbi,Ha?di,&Geib,1998).
In this study,the determination of the initial solution in the Tabu search is to use the current optimal solution in ACO pro-
Table 2
Comparison among different heuristics (NV:the number of vehicles;TD:total distance).Data set Best result Potvin–Bengio (1996)Taillard (1997)Chiang–Russell (1997)Schulze–Fahle (1999)Br?ysy–Gendreau (2002)C1NV 101010
10
10
10
TD 826.7838828.45828.38828.94828.38C2NV 3
3
3
3
3
3
TD 589.24589.90590.30591.42589.93589.86R1NV 12.6712.6012.2512.1712.5011.92TD 1156.361296.831216.701204.191268.421222.12R2NV 2.82 3.00 3.00 2.73 3.09 2.73TD 932.351117.70995.38986.321055.90975.12RC1NV 11.8812.1011.8811.8812.2511.50TD 1368.231446.201367.511397.441396.071389.58RC2NV 3.38 3.40 3.38 3.25 3.38 3.25TD 1075.671360.601165.621229.541308.311128.38All
NV 419
422416411423405TD
55836.57
62572
57993
58502
60651
57710Gambardella et al.(1999)
Lau et al.(2003)Tan,Chew,and Lee (2006)Tan et al.(2001a,2001b)This work C1NV 10.0010
10
10
10
10
TD 828.38828.38828.38832.13828.74841.92C2NV 3.003
3
3
3
3.3TD 589.86589.86589.86589.86590.69612.75R1NV 12
12
12
12.1612.9213.1TD 1217.731217.731217.731211.551187.351213.16R2NV 2.73 2.73 2.733
3.51
4.6TD 967.75967.75967.751001.12960.83952.3RC1NV 11.6311.6311.6312.2512.7412.7TD 1382.421382.421382.421418.77135
5.371415.62RC2NV 3.25 3.25 3.25 3.37 4.25 5.6
TD 1129.191129.191129.191170.931068.261120.37All
NV 408408408418441470TD
59597
59597
59597
58476
56391
57799
Potvin–Bengio (1996):(Potvin &Bengio,1996);Taillard (1997):(Taillard et al.,1997);Chiang–Russell (1997):(Chiang &Russell,1997);Schulze–Fahle (1999):(Schulze &Fahle,1999);Br?ysy–Gendreau (2002):(Br?ysy &Gendreau,2002).
Gambardella et al.(1999):(Gambardella et al.,1999);Lau et al.(2003):(Lau et al.,2003);Tan et al.(2006):(Tan et al.,2006);Tan et al.(2001):(Tan et al.,2001a,2001b ).
Table 1
Comparison between optimal solutions and our heuristic strategies.Data set C1C2R1R2RC1RC2Best-known –
826.7589.241156.36932.351368.231075.67ACO Average Total distance 881.44641.251383.201098.221211.121209.44Computation time(s)11289405395204188ACO-N Average Total distance 851.47628.471296.551007.581168.351165.87Computation time(s)177111578557282214Tabu-N Average Total distance 844.22609.111233.65960.251422.181121.39Computation time(s)157010855400540029112221ACO–Tabu
Average Total distance 843.55611.121241.24961.111419.141119.24Computation time(s)
210
142
698
655
317
407
438 B.Yu et al./Expert Systems with Applications 38(2011)435–441
posed in the previous subsection.The neighborhood search de-scribed in the previous subsection is also used to select neighbor solutions in the Tabu search.In search process,some customers are in the Tabu status,e.g.,a customer that leaves a route cannot change it status during a given number of iterations.The length of the Tabu interval can in?uence the search quality.Since the initial solution of the Tabu search originates from ACO,the solu-tion is better than an initial solution randomly generated.There-fore,the large Tabu interval,the half of the number of customers,is chosen to attentively explore the solution space around the ini-tial solution in this study.Sometimes,the Tabu status of a move can be overruled if the move can produce a better solution than the current best solution,or if all candidate solutions are part of the Tabu list.
In order to apply the information of the moves in the Tabu search to further instruct ACO,the pheromone will still be updated after each move.The updating process is like pheromone updating in ACO.The Tabu algorithm continues until the maximum total
Table3
Comparison between optimal solutions and our heuristic solutions(NV:the number of vehicles;TD:total distance).
Data set Best-known result Source This work
NV TD NV TD
C1-0110827.3Desrochers,Desrosiers,and Solomon(1992)10828.93 C1-0210827.3Desrochers et al.(1992)10828.937 C1-0310826.3Tavares,Pereira,Machado,and Costa(2003)10828.06 C1-0410822.9Tavares et al.(2003)10828.2 C1-0510827.3Tavares et al.(2003)10828.9 C1-0610827.3Desrochers et al.(1992)10828.937 C1-0710827.3Tavares et al.(2003)10828.937 C1-0810827.3Tavares et al.(2003)10830.939 C1-0910827.3Tavares et al.(2003)10829.22
C2-013589.1Cook and Rich(1999)3591.58 C2-023589.1Cook and Rich(1999)3591.56 C2-033591.17Li and Lim(2003)3593.25 C2-043590.6Potvin and Bengio(1996)3595.55 C2-053588.88De Backer,Furnon,Kilby,Prosser,and Shaw(2000)3588.88 C2-063588.49Lau et al.(2003)3588.49 C2-073588.29Rochat and Tailard(1995)3588.88 C2-083588.03Tan et al.(2006)3588.03
R1-01181607.7Desrochers et al.(1992)191655.03 R1-02171434Desrochers et al.(1992)181491.18 R1-03131175.67Lau,Lim,and Liu(2001)141243.22 R1-0410974.2Tan et al.(2006)10982.01 R1-05151346.12Kallehauge,Larsen,and Madsen(2006)161380.44 R1-06131234.6Cook and Rich(1999)131265.36 R1-07111051.84Kallehauge et al.(2006)111100.25 R1-0810954.03Tan et al.(2006)9958.66 R1-09121013.2Chiang and Russell(1997)121101.99 R1-10121068Cook and Rich(1999)121119.53 R1-11121048.7Cook and Rich(1999)121091.11 R1-1210953.63Rochat and Tailard(1995)10974.73
R2-0181198.15Tan et al.(2001a,2001b)71214.22 R2-0261077.66Tan et al.(2001a,2001b)51105.2 R2-035933.286Tan et al.(2001a,2001b)4960.14 R2-043789.72Tan et al.(2006)4771.47 R2-053994.42Rousseau,Gendreau,and Pesant(2002)41050.26 R2-063833Thangiah,Osman,and Sun(1994)4954.85 R2-073814.78Rochat and Tailard(1995)3870.33 R2-082731.23Homberger and Gehring(1999)3777.72 R2-093855Thangiah et al.(1994)3934.21 R2-103954.12Berger and Barkaowi(2004)5949.02 R2-112892.71Bent and Hentenryck(2004)4877.55
RC1-01151619.8Kohl,Desrosiers,Madsen,Solomon,and Soumis(1999)141650.14 RC1-02131470.26Tan et al.(2006)131514.85 RC1-03121196.12Tan et al.(2001a,2001b)111277.11 RC1-04101135.48Cordeau,Laporte,and Mercier(2001)101159.37 RC1-05141589.91Tan et al.(2006)151617.88 RC1-06131371.69Tan et al.(2006)131387.63 RC1-07111222.16Tan et al.(2006)111280.01 RC1-08111133.9Tan et al.(2006)111157.44
RC2-0161134.91Tan et al.(2006)51279.65 RC2-0251130.53Tan et al.(2006)51157.02 RC2-0341026.61Tan et al.(2006)61046.33 RC2-043799.12Homberger and Gehring(1999)4847.33 RC2-0551295.46Tan et al.(2006)51334.55 RC2-0641139.55Tan et al.(2006)51112.2 RC2-0741040.67Tan et al.(2006)51078.52 RC2-083829.69Rousseau et al.(2002)3911.15
Desrochers et al.(1992):(Desrochers et al.,1992);Kallehauge et al.(2006):(Kallehauge et al.,2006);Lau et al.(2003):(Lau et al.,2003);Rousseau et al.(2002):(Rousseau et al.,2002);Tan et al.(2006):(Tan et al.,2006);Tan et al.(2001a,2001b):(Tan et al.,2001a,2001b);Tavares et al.(2003):(Tavares et al.,2003);Thangiah et al.(1994): (Thangiah et al.,1994).
B.Yu et al./Expert Systems with Applications38(2011)435–441439
number of iterations or the maximum number of iterations with-out improvement of the best-known feasible solution.
3.3.Hybrid algorithm(ACO–Tabu)
The process of the ACO–Tabu is as follows(Fig.7):
Step1.Initialization of ACO.Set parameters in ACO and initial-ize the pheromone of the network.
Step2.Route construction.Each ant starts from the depot and constructs routes according to the transition rule.
Step3.Local search.After each ant constructing a solution,the neighborhood search is used to explore neighbor solutions.The 2-opt exchange is used to improve the neighbor solutions.If a neighbor solution is better than the current solution,the neigh-bor solution will substitute the current solution.
Step4.Pheromone updating.The pheromone increment can be computed according to the quality of the solution and phero-mone on links can be updated.
Step5.Tabu status.In our algorithm,the Tabu search is merely permitted to use once.When ACO acquires the solutions of three successive searches are the same,we consider the solu-tion near the optima or the local optima.If the Tabu search has not been used,goto step6;otherwise goto step8.
Step6.Tabu search.The current best solution in ACO will be transformed the initial solution of the Tabu search.Then,search neighbor solutions,move to the best neighbor solution and update pheromone on links in ACO.
Step7.Tabu search termination.Check the Tabu search termi-nation conditions.If satisfying termination conditions,goto step 2and continue ACO;otherwise goto step6and continue Tabu search.
Step8.ACO termination.Check the ACO termination conditions.
If satisfying termination conditions,ACO is terminated;other-wise goto step2and continue ACO search.
4.Numerical analysis
The heuristics described in the previous sections is coded in Vi-sual C++.Net2003and executed on a PC equipped with512MB of RAM and a Pentium processor running at1000MHz.It is estimated by some well-known Solomon’s VRPTW instances(Solomon, 1987),which are divided into six data sets R1,R2,C1,C2,RC1 and RC2.In sets R1and R2customers are uniformly distributed, in sets C1and C2customers are clustered in groups and in sets RC1and RC2customers are semi-clustered.In addition,there are small time windows and small vehicle capacity in sets R1,C1 and RC1,while there are large time windows and large vehicle capacity in sets R2,C2and RC2.The characteristics of optimal solu-tions and our heuristic strategies can be seen in Table1.
The contribution of the improved strategies proposed in this pa-per to the global performance of the ACO–Tabu is?rstly quanti?ed by some experiments.In the section,the algorithm denoted by ACO–Tabu in this paper is compared with a standard ant colony optimization(denoted by ACO),Tabu with the neighborhood search presented in the Section3(denoted by Tabu-N)and ACO with the neighborhood search(denoted by ACO-N).For the four algorithms,each Solomon instance is repeated to compute10 times.The average results of six sets are used to quantify the con-tribution of each strategy and the results are as shown in Table2. Rows3,5,7and9present the average total distance of10calcula-tions of each approach for each set.Rows4,6,8and10present the average computation time of10calculations of each approach for each set.
It can be observed that ACO-N can always provide better perfor-mance than ACO.This indicates that the introduction of the neigh-borhood search can greatly improve the qualities of the solutions compared with ACO.Furthermore,the performances of ACO–Tabu are better than the ones of ACO and ACO-N.This can be attributed that when ACO is close to the convergence,Tabu search can diver-sify the ant colony,explore new possible solution space and pre-vent the algorithm from trapping in local optimization.In addition,Tabu-N can achieve the similar quality of solutions to ACO–Tabu.As to computation time,it is obvious that the computa-tion time of ACO is always less than the ones of the other ap-proaches for each set and the convergence speed of ACO-N is also faster than the ones of ACO–Tabu and Tabu-N.Especially, the computation time of Tabu-N is almost10times that of ACO-N.This indicates that Tabu search always need large computation time to achieve good solution.However,ACO–Tabu need less com-putation time than Tabu search while it possesses comparable quality with Tabu.Considering the tradeoff of quality and compu-tation time,ACO–Tabu is the best approach among the four meth-ods and ACO-N is also a competitive approach with Tabu-N.
Then,ACO–Tabu is compared with nine other meta-heuristic approaches in the papers proposed by Br?ysy and Gendreau (2002),Chiang and Russell(1997),Gambardella et al.(1999),Lau, Sim,and Teo(2003),Potvin and Bengio(1996),Schulze and Fahle (1999),Taillard et al.(1997),Tan,Chew,and Lee(2006),Tan et al.(2001a,2001b).The comparison of the total distance of each approach for each instance is shown in Table2.
Our algorithm can achieve the solutions close to the best-known solutions for the cluster problem set C1and C2.Also,our algorithm can obtain the comparable solutions for the problem set R1,R2,RC1and RC2compared with other meta-heuristics. However,our algorithm requires more vehicle for most sets.This can be attributed that our aim is to minimize the total distance for VRPTW,i.e.,there is no additional cost as adding a vehicle.
The detail results of our algorithm for all the instances are shown in Table3.Our algorithm achieves41best-known solutions out of56instances.Furthermore,for the problem set R2and RC2, our algorithm can achieve better solution than the published best-known solution,e.g.,R204,R210,R211and RC206.
5.Conclusions
This paper presents a hybrid approach based on ACO and Tabu search.ACO?rst searches solutions.When ACO is close to optima or local optima,Tabu search,which uses the current best solution from ACO as the initial solution,is used to maintain the diversity of ACO and explore new solutions.Solomon’s56VRPTW is used to validate our algorithm.Results show that compared with some meta-heuristic published in literature ACO–Tabu is a effective tool for VRPTW.
Acknowledgments
This research is?nanced by the National Science Foundation for Post-doctoral Scientists of China20080440168,the Doctoral Program Foundation for Young Scholar of Institutions of Higher Education of China through project20070151013and the Special Fund for Basic Scienti?c Research of Central Colleges,Dalian mar-itime university2009QN094.The authors would also like to thank Dr.SUN Jian from School of Transportation Engineering,Tongji University for supporting their efforts for this paper.
References
Alvarenga,G.B.,Mateus,G.R.,&de Tomi,G.(2007).A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows.
Computers&Operations Research,34(6),1561–1584.
440 B.Yu et al./Expert Systems with Applications38(2011)435–441
Augugliaro,A.,Dusonchet,L.,&Sanseverino,E.R.(2002).An evolutionary parallel Tabu search approach for distribution systems reinforcement planning.
Advanced Engineering Informatics,16(3),205–215.
Bent,R.,&Hentenryck,P.V.(2004).A two-stage hybrid local search for the vehicle routing problem with time windows.Transportation Science,38(4),515–530. Berger,J.,&Barkaoui,M.(2004).A parallel hybrid genetic algorithm for the vehicle routing problem with time https://www.doczj.com/doc/bc1423762.html,puters&Operations Research,31(12), 2037–2053.
Bortfeldt,A.,Gehring,H.,&Mack,D.(2003).A parallel Tabu search algorithm for solving the container loading problem.Parallel Computing,29(5),641–662.
Br?ysy,O.,Gendreau,M.(2001).Genetic algorithms for the vehicle routing problem with time window.Internal report.STF42A01021.
Br?ysy,O.,&Gendreau,M.(2002).Tabu search heuristics for the vehicle routing problem with time windows.TOP,10(2),211–237.
Bullnheimer,B.,Hartl,R.F.,&Strauss,C.(1999).An improved ant system algorithm for the vehicle routing problem.Annals of Operations Research,89,319–328. Chen,T.K.,Lee,L.H.,&Ke,O.(2001).Hybrid genetic algorithm in solving vehicle routing problem with window https://www.doczj.com/doc/bc1423762.html,-Paci?c Journal of Operational Research,18(1),121–130.
Cheng,C.B.,&Wang,K.P.(2009).Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm.Expert Systems with Applications,36(4),7758–7763.
Chiang,W.C.,&Russell,R.A.(1997).A reactive Tabu search meta-heuristics for the vehicle routing problem with time https://www.doczj.com/doc/bc1423762.html,RMS Journal on Computing, 9(4),417–430.
Colorni,A.,Dorigo,M.,Maniezzo,V.,&Trubian,M.(1994).Ant system for job-shop scheduling.Jorbel–Belgian Journal of Operations Research Statistics and Computer Science,34(1),39–53.
Cook,W.,Rich,J.L.(1999).A parallel cutting plan algorithm for the vehicle routing problem with time https://www.doczj.com/doc/bc1423762.html,putational and applied mathematics.Technical report.Houston,TX:Rice University.
Cordeau,J.F.,Laporte,G.,&Mercier,A.(2001).A uni?ed Tabu search heuristic for vehicle routing problems with time windows.Journal of the Operational Research Society,52(8),928–936.
Czech,Z.J.,Czarnas,P.(2002).A parallel simulated annealing for the vehicle routing problem with time windows.In:Proceedings10th Euromicro workshop on parallel,distributed and network-based processing(pp.376–383).Canary Islands, Spain.
De Backer,B.,Furnon,V.,Kilby,P.,Prosser,P.,&Shaw,P.(2000).Solving vehicle routing problems using constraint programming and meta-heuristics.Journal of Heuristics,6(4),501–523.
Desrochers,M.,Desrosiers,J.,&Solomon,M.(1992).A new optimization algorithm for the vehicle routing problem with time windows.Operational Research,40(2), 342–354.
Doerner,K.F.,Gronalt,M.,Hartl,R.F.,Reimann,M.,Strauss,C.,&Stummer,M.
(2002).Savings ants for the vehicle routing problem,applications of evolutionary computing.Lecture Notes in Computer Science,2279,73–109. Doerner,K.F.,Hartl,R.F.,Kiechle,G.,Lucka,M.,&Reimann,M.(2004).Parallel ant systems for the capacitated vehicle routing problem.Lecture Notes in Computer Science,3004,72–83.
Dorigo,M.,Maniezzo,V.,&Colorni,A.(1996).Ant system:Optimization by a colony of cooperating agents.IEEE Transactions on Systems,Mans and Cybernetics,26(1), 29–41.
Falco,D.,Del Balio,R.,Tarantino,E.,&Vaccaro,R.(1994).Improving search by incorporating evolution principles in parallel Tabu search.IEEE Conference on Evolutionary Computation,2,823–828.
Gambardella,L.M.,Taillard,E.,&Agazzi,G.(1999).MACS-VRPTW:A multiple ant colony system for vehicle routing problems with time windows.In:New ideas in optimization(pp.63–76.)
Glover, F.,&Laguna,M.(1997).Tabu search.Dordrecht:Kluwer Academic Publishers.
Gong,W.,Liu,X.,Zhang,J.,&Fu,Z.(2007).Two-generation ant colony system for vehicle routing problem with time windows.International conference on wireless communications,networking and mobile computing(pp.1917–1920).
Ho,S.C.,&Haugland,D.(2004).A Tabu search heuristic for the vehicle routing problem with time windows and split https://www.doczj.com/doc/bc1423762.html,puters&Operations Research,31(12),1947–1964.
Homberger,J.,&Gehring,H.(1999).Two evolutionary meta-heuristic for the vehicle routing problem with time https://www.doczj.com/doc/bc1423762.html,rmation Systems and Operational Research,37(1),297–318.Kallehauge,B.,Larsen,J.,&Madsen,O.B.G.(2006).Lagrangian duality applied on vehicle routing with time https://www.doczj.com/doc/bc1423762.html,puters&Operations Research,33(5), 1464–1487.
Kohl,N.,Desrosiers,J.,Madsen,O.B.G.,Solomon,M.M.,&Soumis,F.(1999).Two-path cuts for the vehicle routing problem with time windows.Transportation Science,33(1),101–116.
Lau,H.C.,Lim,Y.F.,&Liu,Q.Z.(2001).Diversi?cation of search neighborhood via constraint-based local search and its applications to VRPTW.In:3rd international workshop on integration of AI and OR techniques(CP-AI-OR)(pp.
1–15).Kent,United Kingdom.
Lau,H.C.,Sim,M.,&Teo,K.M.(2003).Vehicle routing problem with time windows and a limited number of vehicles.European Journal of Operational Research, 148(3),559–569.
Li,H.,&Lim,A.(2003).Local search with annealing-like restarts to solve the VRPTW.
European Journal of Operational Research,150(1),115–127.
Mazzeo,S.,&Loiseau,I.(2004).An ant colony algorithm for the capacitated vehicle routing.Electronic Notes in Discrete Mathematics,18(1),181–186.
Potvin,J.Y.,&Bengio,S.(1996).The vehicle routing problem with time windows, Part II:Genetic https://www.doczj.com/doc/bc1423762.html,RMS Journal on Computing,8(2),165–172. Potvin,J.Y.,Kervahut,T.,Garcia,B.L.,&Rousseau,J.M.(1996).The vehicle routing problem with time windows,Part I:Tabu https://www.doczj.com/doc/bc1423762.html,RMS Journal on Computing,8(2),158–164.
Rochat,Y.,&Tailard,E.D.(1995).Probabilistic diversi?cation and intensi?cation in local search for vehicle routing problem.Journal of Heuristic,1(1),147–167. Rousseau,L.M.,Gendreau,M.,&Pesant,G.(2002).Using constraint-based operators to solve the vehicle routing with time windows.Journal of Heuristics,8(1), 43–58.
Schoonderwoerd,R.,Bruten,J.L.,Holland,O.E.,&Rothkrantz,L.J.M.(1996).Ant-based load balancing in telecommunications networks.Adaptive Behavior,5(2), 169–207.
Schulze,J.,&Fahle,T.(1999).A parallel algorithm for the vehicle routing problem with time window constraints.Annals of Operations Research,86, 585–607.
Solomon,M.M.(1987).Algorithms for the vehicle routing and scheduling problems with time window constraints.Operations Research,35(2), 254–265.
Taillard,E.,Badeau,P.,Gendreau,M.,Geurtin,F.,&Potvin,J.Y.(1997).A Tabu search heuristic for the vehicle routing problem with time windows.Transportation Science,31(2),170–186.
Talbi,E.G.,Ha?di,Z.,&Geib,J.M.(1998).A parallel adaptive Tabu search approach.
Parallel Computing,24(14),2003–2019.
Tan,K.C.,Chew,Y.H.,&Lee,L.H.(2006).A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows.
Computational Optimization and Applications,34(1),115–151.
Tan,K.C.,Lee,L.H.,&Ou,K.(2001a).Arti?cial intelligence heuristics in solving vehicle routing problems with time window constraints.Engineering Applications of Arti?cial Intelligence,14(6),825–837.
Tan,K.C.,Lee,T.H.,Ou,K.,&Lee,L.H.(2001b).A messy genetic algorithm for the vehicle routing problem with time window constraints.IEEE Congress on Evolutionary Computation,1,679–686.
Tavares,J.,Pereira,F.B.,Machado,P.,&Costa,E.(2003).On the in?uence of GVR in vehicle routing.In:Proceedings of the2003ACM symposium on applied computing (pp.753–758).
Thangiah,S.R.,Osman,I.H.,&Sun,T.(1994).Hybrid genetic algorithm,simulated annealing and Tabu search methods for vehicle routing problems with time windows.Working paper UKC/IMS/OR94/4.Canterbury,UK:Institute of Mathematics and Statistics,University of Kent.
Ting,C.J.,&Huang,C.H.(2004).An improved genetic algorithm for vehicle routing problem with time windows.International Journal of Industrial Engineering, 12(3),218–228.
Yao,J.B.,&Yao,B.Z.(2007).A parallel ant colony optimization for multi-depot vehicle routing problem.In:Proceedings of the2007international conference on computational intelligence and security workshops table of contents(pp.
240–243).
Yu,B.,Yang,Z.Z.,Xie,J.X.(2009).A parallel improved ant colony optimization for multi-depot vehicle routing problem.Journal of the Operational Research Society, in press,doi:10.1057/jors.2009.161.
Yu,B.,Yang,Z.Z.,&Yao,B.Z.(2009).An improved ant colony optimization for vehicle routing problem.European Journal of Operational research,196(1), 171–176.
B.Yu et al./Expert Systems with Applications38(2011)435–441441