zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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:
90B20Traffic problems
90C59Approximation methods and heuristics
Software:
OR-Library; VRP
WorldCat.org
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. Meta-heuristics: theory and applications (1996) · 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. Application handbook of genetic algorithms: new frontiers, 253-277 (1995)
[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. ICANNGA’97, Vienna, 234-237 (1998)
[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] B., E. Gillett; 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.