×
Prins, Christian

A simple and effective evolutionary algorithm for the vehicle routing problem. (English) Zbl 1100.90504

Comput. Oper. Res. 31, No. 12, 1985-2002 (2004).
Summary: The vehicle routing problem (VRP) plays a central role in the optimization of distribution networks. Since some classical instances with 75 nodes resist the best exact solution methods, most researchers concentrate on metaheuristics for solving real-life problems. Contrary to the VRP with time windows, no genetic algorithm (GA) can compete with the powerful tabu search (TS) methods designed for the VRP. This paper bridges the gap by presenting a relatively simple but effective hybrid GA. In terms of average solution cost, this algorithm outperforms most published TS heuristics on the 14 classical Christofides instances and becomes the best solution method for the 20 large-scale instances generated by Golden et al.

Cited in 150 Documents

MSC:

90B10 Deterministic network models in operations research
90C59 Approximation methods and heuristics in mathematical programming

Software:

VRP
PDF BibTeX XML Cite
\textit{C. Prins}, Comput. Oper. Res. 31, No. 12, 1985--2002 (2004; Zbl 1100.90504)
Full Text: DOI

References:

[1] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L., Introduction to algorithms (1990), MIT Press: MIT Press Cambridge, MA · Zbl 1158.68538
[2] Toth, P.; Vigo, D., Exact solution of the vehicle routing problem, (Crainic, T. G.; Laporte, G., Fleet management and logistics (1998), Kluwer: Kluwer Dordrecht), p1-31 · Zbl 0966.90009
[3] Laporte, G.; Gendreau, M.; Potvin, J. Y.; Semet, F., Classical and modern heuristics for the vehicle routing problem, International Transactions in Operational Research, 7, 285-300 (2000)
[4] Christofides, N.; Mingozzi, A.; Toth, P., The vehicle routing problem, (Christofides, N.; Mingozzi, A.; Toth, P.; Sandi, C., Combinatorial optimization (1979), Wiley: Wiley New York), p315-p338
[6] Golden, B. L.; Wasil, E. A.; Kelly, J. P.; Chao, I. M., The impact of metaheuristics on solving the vehicle routing problem: algorithms, problem sets, and computational results, (Crainic, T. G.; Laporte, G., Fleet management and logistics (1998), Kluwer: Kluwer Dordrecht), p33-p56
[12] Potvin, J.-. Y., Genetic algorithms for the traveling salesman problem, Annals of Operations Research, 63, 339-370 (1996) · Zbl 0851.90130
[13] Potvin, J.-. Y.; Bengio, S., The vehicle routing problem with time windows—Part IIgenetic search, INFORMS Journal on Computing, 8, 165-172 (1996) · Zbl 0866.90058
[15] Prins, C., Competitive genetic algorithms for the open-shop scheduling problem, Mathematical Methods of Operations Research, 52, 3, 389-411 (2000) · Zbl 1023.90030
[16] Lacomme, P.; Prins, C.; Ramdane-Chérif, W., A genetic algorithm for the Capacitated Arc Routing Problem and its extensions, (Boers, E. J.W.; etal., Applications of evolutionary computing. Applications of evolutionary computing, Lecture Notes in Computer Science, vol. 2037 (2001), Springer: Springer Berlin), p473-p483
[17] Beasley, J. E., Route-first cluster-second methods for vehicle routing, Omega, 11, 403-408 (1983)
[19] Moscato, P., Memetic algorithms: a short introduction, (Corne, D.; Dorigo, M.; Glover, F., New ideas in optimization (1999), McGraw-Hill: McGraw-Hill New York), p219-p234
[20] Clarke, G.; Wright, J. W., Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12, 568-581 (1964)
[21] Mole, R. H.; Jameson, S. R., A sequential route-building algorithm employing a generalized savings criterion, Operational Research Quaterly, 27, 503-511 (1976)
[22] Gillett, B. E.; Miller, L. R., A heuristic algorithm for the vehicle dispatch problem, Operations Research, 22, 340-349 (1974) · Zbl 0274.90013
[23] Cheung, B. K.S.; Langevin, A.; Villeneuve, B., High performing evolutionary techniques for solving complex location problems in industrial system design, Journal of Intelligent Manufacturing, 12, 5-6, 455-466 (2001)
[26] Xu, J.; Kelly, J., A network flow-based tabu search heuristic for the vehicle routing problem, Transportation Science, 30, 379-393 (1996) · Zbl 0879.90086
[28] Glover, F.; Laguna, M.; Martí, R., Scatter search, (Ghosh, A.; Tsutsui, S., Advances in evolutionary computing: theory and applications (2002), Springer: Springer Berlin) · Zbl 1079.90178
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.