Comparing descent heuristics and metaheuristics for the vehicle routing problem. (English) Zbl 0976.90018
Summary: Three improvement heuristics for the vehicle routing problem are considered: a descent heuristic and two metaheuristics; Simulated Annealing and Tabu Search. In order to make an in-depth comparison of the performance of these improvement heuristics, their behavior is analyzed on a heuristic, time-sensitive level as well as on a parametric level. The design and the results of the experiments are outlined. The external validity of the conclusions is discussed.
MSC:
| 90B20 | Traffic problems in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90B40 | Search theory |
References:
| [1] | Lenstra, J.; Rinnooy Kan, A., Complexity of vehicle routing and scheduling problems, Networks, 11, 221-227 (1981) |
| [2] | Croes, A., A method for solving traveling salesman problems, Operations Research, 5, 791-812 (1958) · Zbl 1414.90303 |
| [3] | Lin, S., Computer solutions to the traveling salesman problem, Bell System Technical Journal, 44, 2245-2269 (1965) · Zbl 0136.14705 |
| [4] | Lin, S.; Kernighan, B., An effective heuristic algorithm for the traveling salesman problem, Operations Research, 21, 498-516 (1973) · Zbl 0256.90038 |
| [5] | Or I. Traveling salesman-type combinatorial optimization problems and their relation to the logistics of regional blood banking. Ph.D. Thesis, Northwestern University, Evanston, IL; 1976.; Or I. Traveling salesman-type combinatorial optimization problems and their relation to the logistics of regional blood banking. Ph.D. Thesis, Northwestern University, Evanston, IL; 1976. |
| [6] | Osman I. Metastrategy simulated annealing and tabu search algorithms for combinatorial optimization problems. Ph.D. Thesis, The Management School, University of London, 1991.; Osman I. Metastrategy simulated annealing and tabu search algorithms for combinatorial optimization problems. Ph.D. Thesis, The Management School, University of London, 1991. |
| [7] | Osman, I.; Laporte, G., Metaheuristics: a bibliography, Annals of Operations Research, 63, 513-623 (1996) · Zbl 0849.90097 |
| [8] | Laporte, G.; Osman, I., Routing problems: a bibliography, Annals of Operations Research, 61, 227-262 (1995) · Zbl 0839.90032 |
| [9] | Gendreau M, Laporte G, Potvin J-Y. Metaheuristics for the vehicle routing problem. Technical Report G-98-52, Les Cahiers du GERAD, Montréal, Quebec, Canada, 1998.; Gendreau M, Laporte G, Potvin J-Y. Metaheuristics for the vehicle routing problem. Technical Report G-98-52, Les Cahiers du GERAD, Montréal, Quebec, Canada, 1998. |
| [10] | Savelsbergh M. Computer Aided Routing. Ph.D. Thesis, Centrum voor Wiskunde en Informatica, Amsterdam, 1988.; Savelsbergh M. Computer Aided Routing. Ph.D. Thesis, Centrum voor Wiskunde en Informatica, Amsterdam, 1988. · Zbl 0793.90019 |
| [11] | Potvin J-Y, Kervahut T, Garcia B, Rousseau J.M. A tabu search heuristic for the vehicle routing problem with time windows. Technical Report CRT-855, Centre de Recherche sur les Transports, Université de Montréal, Montréal, Canada, 1992.; Potvin J-Y, Kervahut T, Garcia B, Rousseau J.M. A tabu search heuristic for the vehicle routing problem with time windows. Technical Report CRT-855, Centre de Recherche sur les Transports, Université de Montréal, Montréal, Canada, 1992. · Zbl 0866.90057 |
| [12] | Dror, M.; Levy, L., A vehicle routing improvement algorithm comparison of a greedy and a matching implementation for inventory routing, Computers and Operations Research, 13, 1, 33-45 (1986) · Zbl 0614.90061 |
| [13] | Osman, I., Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Annals of Operations Research, 41, 421-451 (1993) · Zbl 0775.90153 |
| [14] | Kirckpatrick, S.; Gelatt, C.; Vecchi, M., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162 |
| [15] | Cerny, V., A thermodynamical approach to the travelling salesman problem: an efficient simulation algorithm, Journal of Optimization Theory Application, 45, 41-51 (1985) · Zbl 0534.90091 |
| [16] | Metropolis, N.; Rosenbluth, A.; Rosenbluth, M.; Teller, A.; Teller, E., Equation of state calculations by fast computing machines, Journal of Chemical Physics, 21, 1087-1092 (1953) · Zbl 1431.65006 |
| [17] | Van Laarhoven P, Aarts E. Simulated Annealing: Theory and Practice. Dordrecht: Kluwer Academic Publishers, The Netherlands, 1987.; Van Laarhoven P, Aarts E. Simulated Annealing: Theory and Practice. Dordrecht: Kluwer Academic Publishers, The Netherlands, 1987. · Zbl 0643.65028 |
| [18] | Aarts E, Korst J. Simulated annealing and Boltzmann machines. Chichester: Wiley, 1989.; Aarts E, Korst J. Simulated annealing and Boltzmann machines. Chichester: Wiley, 1989. · Zbl 0674.90059 |
| [19] | Collins, N.; Eglese, R.; Golden, B., Simulated annealing — an annotated bibliography, American Journal of Mathematical and Management Sciences, 8, 209-307 (1988) · Zbl 0669.65047 |
| [20] | Eglese, R., Simulated annealing: a tool for operational research, European Journal of Operational Research, 46, 271-281 (1990) · Zbl 0699.90080 |
| [21] | Johnson, D.; Aragon, C.; McGeoch, L.; Schevon, C., Optimization by simulated annealing: an experimental evaluation; part i: Graph partitioning, Operations Research, 37, 865-892 (1989) · Zbl 0698.90065 |
| [22] | Golden, B.; Skiscim, C., Using simulated annealing to solve routing and location problems, Naval Research Logistics Quarterly, 33, 261-279 (1986) · Zbl 0593.90054 |
| [23] | Teodorovic, D.; Pavkovic, G., A simulated annealing technique approach to the vehicle routing problem in the case of stochastic demand, Transportation Planning and Technology, 16, 261-273 (1992) |
| [24] | Thangiah S, Osman I, Sun T. Hybrid genetic algorithm, simulated annealing and tabu search methods for vehicle routing problem with time windows. Technical Report SRU-CpSc-TR-94-27, Computer Science Department, Slippery Rock University, Slippery Rock, PA. 1994.; Thangiah S, Osman I, Sun T. Hybrid genetic algorithm, simulated annealing and tabu search methods for vehicle routing problem with time windows. Technical Report SRU-CpSc-TR-94-27, Computer Science Department, Slippery Rock University, Slippery Rock, PA. 1994. |
| [25] | Thangiah, S.; Osman, I.; Vinayagamoorthy, R.; Sun, T., Algorithms for vehicle routing problems with time deadlines, American Journal of Mathematical and Management Sciences, 13, 3-4, 325-355 (1994) · Zbl 0808.90064 |
| [26] | Robusté, F.; Daganzo, C.; Souleyrette, R., Implementing vehicle routing models, Transportation Research B, 24, 263-286 (1990) |
| [27] | Alfa, A.; Heragu, S.; Chen, M., A 3-opt based simulated annealing algorithm for vehicle routing problems, Computers and Industrial Engineering, 21, 635-639 (1991) |
| [28] | Janssens G, Van Breedam A. A simulated annealing post-processor for the vehicle routing problem. In: V. Rayward-Smith, Editor Applications of Modern Heuristics, Chapter Case studies, 1995, p. 175-91. Alfred Waller Ltd.; Janssens G, Van Breedam A. A simulated annealing post-processor for the vehicle routing problem. In: V. Rayward-Smith, Editor Applications of Modern Heuristics, Chapter Case studies, 1995, p. 175-91. Alfred Waller Ltd. |
| [29] | Van Breedam, A., Improvement heuristics for the vehicle routing problem based on simulated annealing, European Journal of Operational Research, 86, 3, 480-490 (1995) · Zbl 0914.90107 |
| [30] | Glover, F., The general employee scheduling problem: an integration of management science and artificial intelligence, Computers and Operations Research, 15, 563-593 (1986) |
| [31] | Hansen P. 1986. The steepest ascent mildest descent heuristic for combinatorial programming. In: Presented at the Congress on Numerical Methods in Combinatorial Optimization, Capri, Italy.; Hansen P. 1986. The steepest ascent mildest descent heuristic for combinatorial programming. In: Presented at the Congress on Numerical Methods in Combinatorial Optimization, Capri, Italy. |
| [32] | Glover F., Laguna M. Tabu search. Kluwer Academic Publishers, 1997.; Glover F., Laguna M. Tabu search. Kluwer Academic Publishers, 1997. · Zbl 0930.90083 |
| [33] | Pureza V, França P. Vehicle routing problems via tabu search metaheuristic. Technical Report CRT-747, Centre de Recherche sur les Transports, Université de Montréal, Montréal, Canada, 1991.; Pureza V, França P. Vehicle routing problems via tabu search metaheuristic. Technical Report CRT-747, Centre de Recherche sur les Transports, Université de Montréal, Montréal, Canada, 1991. |
| [34] | Potvin, J.-. Y.; Kervahut, T.; Garcia, B.-. L.; Rousseau, J.-. M., The vehicle routing problem with time windows. part i: tabu search, INFORMS Journal on Computing, 8, 2, 158-164 (1996) · Zbl 0866.90057 |
| [35] | Garcia, B.-. L.; Potvin, J.-. Y.; Rousseau, J.-. M., A parallel implementation of the tabu search heuristic for the vehicle routing problem with time window constraint, Computers and Operations Research, 21, 1025-1033 (1994) · Zbl 0815.90067 |
| [36] | Taillard, E., Parallel iterative search methods for vehicle routing problems, Networks, 23, 661-673 (1993) · Zbl 0804.90045 |
| [37] | Semet, F.; Taillard, E., Solving real-life vehicle routing problems efficiently using taboo search, Annals of Operations Research, 41, 469-488 (1993) · Zbl 0775.90156 |
| [38] | Gendreau, M.; Hertz, A.; Laporte, G., A tabu search heuristic for the vehicle routing problem, Management Science, 40, 1276-1290 (1994) · Zbl 0822.90053 |
| [39] | Stewart W, Kelly J, Laguna M. Solving vehicle routing problems using generalized assignments and tabu search. Technical report, College of Business Administration, University of Colorado, Boulder, CO, 1992.; Stewart W, Kelly J, Laguna M. Solving vehicle routing problems using generalized assignments and tabu search. Technical report, College of Business Administration, University of Colorado, Boulder, CO, 1992. |
| [40] | Van Breedam A. An analysis of the behavior of heuristics for the vehicle routing problem for a selection of problems with vehicle-related, customer-related and time-related constraints. Ph.D. Thesis, University of Antwerp — RUCA, Belgium, 1994.; Van Breedam A. An analysis of the behavior of heuristics for the vehicle routing problem for a selection of problems with vehicle-related, customer-related and time-related constraints. Ph.D. Thesis, University of Antwerp — RUCA, Belgium, 1994. |
| [41] | Kaufman L, Rousseeuw P. Finding groups in data. An introduction to cluster analysis. New York: Wiley, 1989.; Kaufman L, Rousseeuw P. Finding groups in data. An introduction to cluster analysis. New York: Wiley, 1989. · Zbl 1345.62009 |
| [42] | Morgan, J.; Sonquist, J., Problems in the analysis of survey data and a proposal, Journal of the American Statistical Association, 58, 415-434 (1963) · Zbl 0114.10103 |
| [43] | Sonquist J, Baker E, Morgan J. Searching for structure. Survey Research Center, University of Michigan, Ann Arbor, 1971.; Sonquist J, Baker E, Morgan J. Searching for structure. Survey Research Center, University of Michigan, Ann Arbor, 1971. · Zbl 0256.62003 |
| [44] | Pirlot, M., General local search heuristics in combinatorial optimization: a tutorial, Jorbel, 32, 2, 7-67 (1992) · Zbl 0768.90062 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
