×

zbMATH — the first resource for mathematics

A genetic algorithm for the vehicle routing problem. (English) Zbl 1026.90013
Summary: This study considers the application of a genetic algorithm (GA) to the basic vehicle routing problem (VRP), in which customers of known demand are supplied from a single depot. Vehicles are subject to a weight limit and, in some cases, to a limit on the distance travelled. Only one vehicle is allowed to supply each customer. The best known results for benchmark VRPs have been obtained using tabu search or simulated annealing. GAs have seen widespread application to various combinatorial optimisation problems, including certain types of vehicle routing problem, especially where time windows are included. However, they do not appear to have made a great impact so far on the VRP as described here. In this paper, computational results are given for the pure GA which is put forward. Further results are given using a hybrid of this GA with neighbourhood search methods, showing that this approach is competitive with tabu search and simulated annealing in terms of solution time and quality.

MSC:
90B20 Traffic problems in operations research
90C59 Approximation methods and heuristics in mathematical programming
Software:
GIDEON; OR-Library; VRP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Laporte, G., The vehicle routing problem: an overview of exact and approximate algorithms, European journal of operational research, 59, 345-358, (1992) · Zbl 0761.90034
[2] Laporte, G.; Osman, I.H., Routing problems: a bibliography, Annals of operations research, 61, 227-262, (1995) · Zbl 0839.90032
[3] Taillard, É., Parallel iterative search methods for vehicle routing problems, Networks, 23, 661-673, (1993) · Zbl 0804.90045
[4] Rochat, Y.; Taillard, É., Probabilistic diversification and intensification in local search for vehicle routing, Journal of heuristics, 1, 147-167, (1995) · Zbl 0857.90032
[5] Osman, I.H., Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Operations research, 41, 421-451, (1993) · Zbl 0775.90153
[6] Gendreau, M.; Hertz, A.; Laporte, G., A tabu search heuristic for the vehicle routing problem, Management science, 40, 1276-1290, (1994) · Zbl 0822.90053
[7] Rego, C.; Roucairol, C., A parallel tabu search algorithm using ejection chains for the vehicle routing problem, () · Zbl 0877.90034
[8] Barbarosoglu, G.; Ozgur, D., A tabu search algorithm for the vehicle routing problem, Computers & operations research, 26, 255-270, (1999) · Zbl 0941.90017
[9] Hiquebran, D.T.; Alfa, A.S.; Shapiro, A.; Gittoes, D.H., A revised simulated annealing and cluster-first route-second algorithm applied to the vehicle routing problem, Engineering optimization, 22, 77-107, (1994)
[10] Renaud, J.; Boctor, F.F.; Laporte, G., An improved petal heuristic for the vehicle routing problem, Journal of the operational research society, 47, 329-336, (1996) · Zbl 0851.90032
[11] Bullnheimer, B.; Hartl, R.F.; Strauss, C., An improved ant system algorithm for the vehicle routing problem, Annals of operations research, 89, 319-328, (1999) · Zbl 0937.90125
[12] Gambardella LM, Taillard É, Agazzi G. A multiple ant colony system for vehicle routing problems with time windows. In: Corne D. Dorigo M, Glover F, editors. New ideas in optimization. New York: McGraw-Hill, 1999. p. 63-76 [Chapter 5].
[13] Thangiah SR, Nygard PL, Juell PL. GIDEON: a genetic algorithm system for vehicle routing with time windows. In: Proceedings of the Seventh IEEE Conference on Artificial Intelligence Applications, Miami, FL, 1991. p. 322-8.
[14] Blanton JL, Wainwright RL. Multiple vehicle routing with time and capacity constraints using genetic algorithms. Proceedings of the Fifth International Conference on Genetic Algorithms 1993:452-459. Los Altas, CA.
[15] Thangiah SR, Gubbi AV. Effect of genetic sectoring on vehicle routing problems with time windows. In: Proceedings of the IEEE International Conference on Managing Intelligent System Projects, Washington, DC, 1993. p. 146-53.
[16] Thangiah SR, Vinayagamoorthy R, Gubbi AV. Vehicle routing with time deadlines using genetic and local algorithms. In: Proceedings of the Fifth International Conference on Genetic Algorithms. Los Altas, CA: Morgan Kaufmann, 1993. p. 506-15.
[17] Schmitt LJ. An empirical computational study of genetic algorithms to solve order-based problems: an emphasis on the TSP and the VRP with time constraints. Ph.D. dissertation, Fogelman College of Business and Economics, University of Memphis, 1994.
[18] Thangiah, S.R., Vehicle routing with time windows using genetic algorithms, (), 253-277
[19] Thangiah SR. An adaptive clustering method using a geometric shape for vehicle routing problems with time windows. In: Proceedings of the Sixth International Conference on Genetic Algorithms. Los Altas, CA: Morgan Kaufmann, 1995. p. 536-43.
[20] Potvin, J.Y.; Bengio, S., The vehicle routing problem with time windows—part II: genetic search, INFORMS. journal on computing, 8, 165-172, (1996) · Zbl 0866.90058
[21] Potvin, J.Y.; Duhamel, C.; Guertin, F., A genetic algorithm for vehicle routing with backhauling, Applied intelligence, 6, 345-355, (1996)
[22] Salhi, S.; Thangiah, S.R.; Rahman, F., A genetic clustering method for the multi-depot vehicle routing problem, (), 234-237
[23] Thangiah SR, Nygard PL. School bus routing using genetic algorithms. In: Proceedings of the SPIE Conference on Applications of Artificial Intelligence X: Knowledge Based Systems, Orlando, FL, 1992. p. 387-97.
[24] Potvin, J.Y.; Dubé, D.; Robillard, C., A hybrid approach to vehicle routing using neural networks and genetic algorithms, Applied intelligence, 6, 241-252, (1996)
[25] Reeves CR, editor. Modern heuristic techniques for combinatorial problems. Oxford: Blackwell Scientific Press, 1993. · Zbl 0942.90500
[26] Chu, P.C.; Beasley, J.E., A genetic algorithm for the generalised assignment problem, Computers & operations research, 24, 17-23, (1997) · Zbl 0881.90070
[27] Fisher, M.L.; Jaikumar, R., A generalized assignment heuristic for vehicle routing, Networks, 11, 109-124, (1981)
[28] Baker, B.M.; Sheasby, J.E., Extensions to the generalised assignment heuristic for vehicle routing, European journal of operational research, 119, 147-157, (1999) · Zbl 0934.90006
[29] Gillett B, E.; Miller, L.R., A heuristic algorithm for the vehicle dispatch problem, Operations research, 22, 340-349, (1974) · Zbl 0274.90013
[30] Beasley, J.E.; Chu, P.C., Constraint handling in genetic algorithms: the set partitioning problem, Journal of heuristics, 4, 323-357, (1998) · Zbl 1071.90573
[31] Beasley, J.E., OR-library: distributing test problems by electronic mail, Journal of the operational research society, 41, 1069-1072, (1990)
[32] Ayechew MA. Genetic algorithms and Lagrangean based heuristics for vehicle routing. Ph.D. thesis, Coventry University, UK, 2000.
[33] Dongarra JJ. Performance of various computers using standard linear equations software. Working Paper, Computer Science Department, University of Tennessee, USA, 2001, http://www.netlib.org/benchmark/performance.ps.
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.