Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-27T23:25:27.217Z Has data issue: false hasContentIssue false
  • English
  • Français

A memetic algorithm for the vehicle routing problem with time windows

Published online by Cambridge University Press:  20 August 2008

Nacima Labadi ,
Christian Prins  and
Mohamed Reghioui
Nacima Labadi
Affiliation:
Inst. Charles Delaunay, Univ. Technologie Troyes, FRE CNRS 2848, BP 2060, 10010 Troyes Cedex, France; [email protected], [email protected], [email protected]
Christian Prins
Affiliation:
Inst. Charles Delaunay, Univ. Technologie Troyes, FRE CNRS 2848, BP 2060, 10010 Troyes Cedex, France; [email protected], [email protected], [email protected]
Mohamed Reghioui
Affiliation:
Inst. Charles Delaunay, Univ. Technologie Troyes, FRE CNRS 2848, BP 2060, 10010 Troyes Cedex, France; [email protected], [email protected], [email protected]
Get access

Abstract

This article deals with the vehicle routing problem with timewindows (VRPTW). This problem consists in determining a least-costset of trips to serve customers during specific time windows. Theproposed solution method is a memetic algorithm (MA), a geneticalgorithm hybridised with a local search. Contrary to most paperson the VRPTW, which minimize first the number of vehicles, ourmethod is also able to minimize the total distance travelled. Theresults on 56 classical instances are compared to those of thebest metaheuristics. The efficiency of the MA is similar for theclassical criterion, but it becomes the best algorithm availablefor the total distance, being much faster and improving 20best-known solutions.

Keywords

memetic algorithmvehicle routing problemtime window.
Type
Research Article
Information
RAIRO - Operations Research , Volume 42 , Issue 3 , July 2008 , pp. 415 - 431
Copyright
© EDP Sciences, ROADEF, SMAI, 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alvarenga, G.B., Mateus, G.R. and de Tomi, G., A genetic and set partitioning two-phase approch for the vehicle routing problem with time windows. Comput. Oper. Res. 34 (2007) 1561–1584. CrossRef
Berger, J., Barkaoui, M. and Bräysy, O., A route-directed hybrid genetic approach for the vehicle routing problem with time windows. Inf. Syst. Oper. Res. 41 (2003) 179–194.
J. Berger, M. Salois and R. Begin, A hybrid genetic algorithm for the vehicle routing problem with time windows. Lecture Notes in Artificial Intelligence 1418. Springer, Berlin (1998) 114–127.
J.L. Blanton and R.L. Wainwright, Multiple vehicle routing with time and capacity constraints using genetic algorithms, Proceedings of the Fifth International Conference on Genetic Algorithms. Morgan Kaufmann, San Francisco (1993) 452–459.
Bräysy, O., Dullaert, W. and Gendreau, M., Evolutionary algorithms for the vehicle routing problem with time windows. J. Heuristics 10 (2005) 587–611. CrossRef
Bräysy, O. and Gendreau, M., Vehicle routing problem with time windows – Part I: route construction and local search algorithms. Transportation Science 39 (2005) 104–118. CrossRef
Bräysy, O. and Gendreau, M., Vehicle routing problem with time windows – Part II: metaheuristics. Transportation Science 39 (2005) 119–139. CrossRef
Clarke, G. and Wright, J.W., Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12 (1964) 568–581. CrossRef
H. Gehring and J. Homberger, A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows, Proceedings of EUROGEN 99, University of Jyväskylä, Finland (1999) 57–64.
Gehring, H. and Homberger, J., Parallelization of a two-phase metaheuristic for routing problems with time windows. Asia-Pacific J. Oper. Res. 18 (2001) 35–47.
Gillett, B.E. and Miller, L.R., A heuristic algorithm for the vehicle dispatch problem. Oper. Res. 22 (1974) 340–349. CrossRef
J.H. Holland, Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor (1975).
Homberger, J. and Gehring, H., Two evolutionary metaheuristics for the vehicle routing problem with time windows. INFOR 37 (1999) 297–318.
Homberger, J. and Gehring, H., A two-phase hybrid metaheuristic for the vehicle routing problem with time windows. Eur. J. Oper. Res. 162 (2005) 220–238. CrossRef
S. Jung and B.R. Moon, A hybrid genetic algorithm for the vehicle routing problem with time windows, Proceedings of Genetic and Evolutionary Computation Conference. Morgan Kaufmann, San Francisco (2002) 1309–1316.
G.A.P. Kindervater and M.W.P. Savelsbergh, Vehicle routing: handling edge exchanges. edited by E.H.L. Aarts and J.K. Lenstra, Local search in combinatorial optimization. Wiley, Chichester (1997) 311–336.
D. Mester, An evolutionary strategies algorithm for large scale vehicle routing problem with capacitate and time windows restrictions, Working paper, Institute of Evolution, University of Haifa, Israel (2002).
P. Moscato, Memetic algorithms: a short introduction, edited by D. Corne, M. Dorigo and F. Glover, New Ideas in Optimization. McGraw-Hill, New York (1999) 219–234.
Potvin, J.Y. and Bengio, S., The vehicle routing with time windows – Part II: genetic search. INFORMS J. Comput. 8 (1996) 165–172. CrossRef
C. Prins, A simple and effective evolutionary algorithm for the vehicle routing problem, Comput. Oper. Res. 31 (2004) 1985–2002.
Rochat, Y. and Taillard, E.D., Probabilistic diversification and intensification in local search for vehicle routing. J. Heuristics 1 (1995) 147–167. CrossRef
Solomon, M.M., Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35 (1987) 254–265. CrossRef
Taillard, E., Badeau, P., Gendreau, M., Guertin, F. and Potvin, J.Y., Tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Science 31 (1997) 170–186. CrossRef
Tan, K.C., Lee, L.H. and Hybrid, K. Ou genetic algorithms in solving ehicle routing problems with time window constraints. Asia-Pacific J. Oper. Res. 18 (2001) 121–130.
K.C. Tan, L.H. Lee and K. Ou, A messy genetic algorithm for the vehicle routing problem with time window constraints, Proceedings of the 2001 Congress on Evolutionary Computation, IEEE, Piscataway (2001) 679–686.
Tan, K.C., Lee, L.H., Zhu, Q.L. and Heuristic, K. Ou methods for the vehicle routing problem with time windows. Artificial Intelligence in Engineering 15 (2001) 281–295. CrossRef
S. Thangiah, Vehicle routing with time windows using genetic algorithms. edited by L. Chambers, Application handbook of genetic algorithms: new frontiers, Vol II. CRC Press, Boca Raton (1995) 253–277.
Wee Kit, H., Chin, J. and Lim, A., A hybrid search algorithm for the vehicle routing problem with time windows. Int. J. Art. Intell. Tools 10 (2001) 431–449.