×

A two-phase hybrid metaheuristic for the vehicle routing problem with time windows. (English) Zbl 1132.90378

Summary: The subject of this paper is a two-phase hybrid metaheuristic for the vehicle routing problem with time windows and a central depot (VRPTW). The objective function of the VRPTW considered here combines the minimization of the number of vehicles (primary criterion) and the total travel distance (secondary criterion). The aim of the first phase is the minimization of the number of vehicles by means of a \((\mu,\lambda)\)-evolution strategy, whereas in the second phase the total distance is minimized using a tabu search algorithm. The two-phase hybrid metaheuristic was subjected to a comparative test on the basis of 356 problems from the literature with sizes varying from 100 to 1000 customers. The derived results show that the proposed two-phase approach is very competitive.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
90B06 Transportation, logistics and supply chain management
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ablay, P., Optimieren mit Evolutionsstrategien, Spektrum der Wissenschaft, 7, 104-115 (1987)
[2] Chiang, W. C.; Russell, R. A., Simulated annealing metaheuristics for the vehicle routing problem with time windows, Annals of Operations Research, 63, 3-27 (1996) · Zbl 0849.90054
[3] Chiang, W. C.; Russell, R. A., A reactive tabu search metaheuristic for the vehicle routing problem with time windows, INFORMS Journal on Computing, 9, 417-430 (1997) · Zbl 0901.90088
[4] Clarke, G.; Wright, J. W., Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12, 568-581 (1964)
[5] Gambardella, L.M., Taillard, E., Agazzi, G., 1999. MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. Technical Report IDSIA-06-99, Lugano, Switzerland; Gambardella, L.M., Taillard, E., Agazzi, G., 1999. MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. Technical Report IDSIA-06-99, Lugano, Switzerland
[6] Gehring, H., Homberger, J., 1999. A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows. In: Miettinen, K., Mäkelä, M.M., Toivanen, J. (Eds.), Proceedings of EUROGEN99-Short Course on Evolutionary Algorithms in Engineering and Computer Science, 57-64. Reports of the Department of Mathematical Information Technology, No. A 2/1999, University of Jyväskylä, Finland; Gehring, H., Homberger, J., 1999. A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows. In: Miettinen, K., Mäkelä, M.M., Toivanen, J. (Eds.), Proceedings of EUROGEN99-Short Course on Evolutionary Algorithms in Engineering and Computer Science, 57-64. Reports of the Department of Mathematical Information Technology, No. A 2/1999, University of Jyväskylä, Finland
[7] Gietz, M., Computergestützte Tourenplanung mit zeitkritischen Restriktionen, Physica (1994)
[8] Glover, F., Future paths for integer programming and links to artificial intelligence, Computers and Operations Research, 13, 533-549 (1986) · Zbl 0615.90083
[9] Glover, F.; Kelley, J. P.; Laguna, M., Genetic algorithms and tabu search: Hybrids for optimization, Computers and Operations Research, 22, 111-134 (1995) · Zbl 0813.90093
[10] Hansen, P.; Mladenovic, N., An introduction to variable neighbourhood search, (Voss, S.; Martello, S.; Osman, I. H.; Roucairol, C., Meta-Heuristics-Advances and Trends in Local Search Paradigms for Optimization (1999), Kluwer: Kluwer Boston), 431-458
[11] Hoffmeister, F.; Bäck, T., Genetic algorithms and evolution strategies: Similarities and differences, (Schwefel, H.-P.; Männer, R., Parallel Problem Solving from Nature-1st Workshop. Parallel Problem Solving from Nature-1st Workshop, PPSN I, Dortmund, Germany, October 1-3, 1990, Proceedings (1991), Springer: Springer Berlin), 447-461
[12] Homberger, J.; Gehring, H.; Laporte, G.; Semet, F., Two evolutionary metaheuristics for the vehicle routing problem with time windows, Metaheuristics for Location and Routing Problems. Metaheuristics for Location and Routing Problems, Information Systems and Operational Research, 37, Special issue, 297-318 (1999) · Zbl 07677595
[13] Kilby, P.; Prosser, P.; Shaw, P., Guided local search for the vehicle routing problem with time windows, (Voss, S.; Martello, S.; Osman, I. H.; Roucairol, C., Meta-Heuristics-Advances and Trends in Local Search Paradigms for Optimization (1999), Kluwer: Kluwer Boston), 473-486 · Zbl 0985.90019
[14] Kontoravdis, G.; Bard, J. F., A GRASP for the vehicle routing problem with time windows, ORSA Journal on Computing, 7, 10-23 (1995) · Zbl 0822.90055
[15] Lenstra, J.; Rinnooy Kan, A., Complexity of vehicle routing and scheduling problems, Networks, 11, 221-227 (1981)
[16] Lin, S., Computer solutions of the traveling salesman problem, Bell System Technical Journal, 44, 2245-2269 (1965) · Zbl 0136.14705
[17] Liu, F.; Shen, S., A route-neighbourhood-based metaheuristic for vehicle routing problem with time windows, European Journal of Operational Research, 118, 485-504 (1999) · Zbl 0945.90007
[18] Neitzel, W., 1977. Tourenplanung-Problemdarstellung und Lösungsverfahren für Ein-Depot-Probleme. Peter Lang, Frankfurt/M; Neitzel, W., 1977. Tourenplanung-Problemdarstellung und Lösungsverfahren für Ein-Depot-Probleme. Peter Lang, Frankfurt/M
[19] Or, I., 1976. Traveling salesman-type combinatorial problems and their relation to the logistics of blood banking. Ph.D. thesis, Department of Industrial Engineering and Management Science, Northwestern University, Evanston, IL; Or, I., 1976. Traveling salesman-type combinatorial problems and their relation to the logistics of blood banking. Ph.D. thesis, Department of Industrial Engineering and Management Science, Northwestern University, Evanston, IL
[20] Osman, I. H., Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Annals of Operations Research, 41, 421-451 (1993) · Zbl 0775.90153
[21] Osman, I. H.; Kelly, J. P., Meta-heuristics: An overview, (Osman, I. H.; Kelly, J. P., Meta-Heuristics-Theory and Applications (1997), Kluwer: Kluwer Boston), 1-21 · Zbl 0877.90065
[22] 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
[23] Potvin, J. Y.; Rousseau, J. M., An exchange heuristic for routing problems with time windows, Journal of the Operational Research Society, 46, 1433-1446 (1995) · Zbl 0843.90043
[24] 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, 158-164 (1996) · Zbl 0866.90057
[25] Russell, R. A., Hybrid heuristics for the vehicle routing problem with time windows, Transportation Science, 29, 156-166 (1995) · Zbl 0860.90052
[26] Savelsbergh, M. W.P., Local search in routing problems with time windows, Annals of Operations Research, 4, 285-305 (1985)
[27] Savelsbergh, M. W.P., The vehicle routing problem with time windows: Minimizing route duration, ORSA Journal on Computing, 4, 146-154 (1992) · Zbl 0780.90105
[28] Schulze, J.; Fahle, T.; Beasley, J. E.; Sharaiha, Y. M., Parallel algorithm for the vehicle routing problem with time window constraints, Combinatorial Optimization: Recent Advances in Theory and Praxis. Combinatorial Optimization: Recent Advances in Theory and Praxis, Special issue of Annals of Operations Research, 86, 585-607 (1999) · Zbl 0922.90059
[29] Schwefel, H. P., Numerical Optimization of Computer Models (1981), John Wiley & Sons: John Wiley & Sons Chichester
[30] Semet, F.; Taillard, É. D., Solving real-life vehicle routing problems efficiently using tabu search, Annals of Operations Research, 41, 469-488 (1993) · Zbl 0775.90156
[31] Shaw, P., Using constraint programming and local search methods to solve vehicle routing problems, (Maher, M.; Puget, J. F., Principles and Practice of Constraint Programming-Proceedings of the 4th International Conference, Pisa, Italy (1998), Springer: Springer Berlin), 417-431
[32] Solomon, M. M., Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research, 35, 254-265 (1987) · Zbl 0625.90047
[33] Solomon, M. M.; Desrosiers, J., Time window constrained routing and scheduling problems, Transportation Science, 22, 1-13 (1988) · Zbl 0638.90052
[34] Taillard, E.; Badeau, P.; Gendreau, M.; Guertin, F.; Potvin, J. Y., A tabu search heuristic for the vehicle routing problem with soft time windows, Transportation Science, 31, 170-186 (1997) · Zbl 0886.90070
[35] Thangiah, S. R.; Nygard, K. E.; Juell, P. L., GIDEON: a genetic algorithm system for vehicle routing with time windows, (Proceedings of the 7th Conference on Artificial Intelligence for Applications, Miami, FL (1991), IEEE Press: IEEE Press New York), 322-328
[36] Thangiah, S.R., Osman, I.H., Sun, T., 1995. Hybrid genetic algorithms, simulated annealing and tabu search methods for vehicle routing problems with time windows. Technical Report UKC/OR94/4, Institute of Mathematics and Statistics, University of Kent, Canterbury, UK; Thangiah, S.R., Osman, I.H., Sun, T., 1995. Hybrid genetic algorithms, simulated annealing and tabu search methods for vehicle routing problems with time windows. Technical Report UKC/OR94/4, Institute of Mathematics and Statistics, University of Kent, Canterbury, UK
[37] Van Landeghem, H. R.G., A bi-criteria heuristic for the vehicle routing problem with time windows, European Journal of Operational Research, 36, 217-226 (1988) · Zbl 0643.90035
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.