Vehicle Routing Problem with Time Windows, Part II: Metaheuristics

References

• Aarts J., Korst H. M., Van Laarhaven P. J. M., Aarts E., Lenstra J. K. Simulated annealing. Local Search in Combinatorial Optimization (1997) (John Wiley and Sons, Chichester, UK) 91–120Google Scholar
• Alander J. T. An indexed bibliography of genetic algorithms in operations research. (2000) . Technical Report 94-1-OR, University of Vaasa, Finland. Available via anonymous ftp site ftp.uwasa.fi directory cs/report94-1 file gaORbib.ps.ZGoogle Scholar
• Anderson D., Anderson E., Lesh N., Marks J., Mirtich B., Ratajczak D., Ryall K. Human-guided simple search. (2000) . Working paper, Mitsubishi Electric Research Laboratory, Cambridge, MAGoogle Scholar
• Bachem A., Hochstättler W., Malich M. The simulated trading heuristic for solving vehicle routing problems. Discrete Appl. Math. (1996) 65:47–72Crossref, Google Scholar
• Badeau P., Gendreau M., Guertin F., Potvin J.-Y., Taillard E. A parallel tabu search heuristic for the vehicle routing problem with time windows. Transportation Res. C (1997) 5:109–122Crossref, Google Scholar
• Beasley J. E. A Lagrangian heuristic for set covering problems. Naval Res. Logist. (1990) 37:151–164Crossref, Google Scholar
• Bent R., Van Hentenryck P. A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Sci. (2004) 38(4):515–530Link, Google Scholar
• Benyahia I., Potvin J.-Y. Generalization and refinement of route construction heuristics using genetic algorithms. Proc. 1995 IEEE Internat. Conf. Evolutionary Comput. (1995) (IEEE Service Center, Piscataway, NJ) 39–43Crossref, Google Scholar
• Berger J., Barkaoui M., Bräysy O. A route-directed hybrid genetic approach for the vehicle routing problem with time windows. Inform. Systems Oper. Res. (2003) 41:179–194Google Scholar
• Berger J., Salois M., Begin R. A hybrid genetic algorithm for the vehicle routing problem with time windows. Lecture Notes Artificial Intelligence (1998) 1418:114–127Google Scholar
• Blanton J. L., Wainwright R. L., Forrest S. Multiple vehicle routing with time and capacity constraints using genetic algorithms. Proc. 5th Internat. Conf. Genetic Algorithms (1993) (Morgan Kaufmann Publishing, San Francisco, CA) 452–459Google Scholar
• Brandão J., Voss S., Martello S., Osman I. H., Roucairol C. Metaheuristic for the vehicle routing problem with time windows. Metaheuristics—Advances and Trends in Local Search Paradigms for Optimization (1999) (Kluwer Academic Publishers, Boston, MA) 19–36Crossref, Google Scholar
• Bräysy O. Fast local searches for the vehicle routing problem with time windows. Inform. Systems Oper. Res. (2002) 40:319–330Google Scholar
• Bräysy O. A reactive variable neighborhood search for the vehicle routing problem with time windows. INFORMS J. Comput. (2003) 15:347–368Link, Google Scholar
• Bräysy O., Gendreau M. Vehicle routing problem with time windows, Part I: Route construction and local search algorithms. Transportation Sci. (2005) 39(1):104–118Link, Google Scholar
• Bräysy O., Dullaert W., Gendreau M. Evolutionary algorithms for the vehicle routing problem with time windows. J. Heuristics (2004a) 10:587–611Crossref, Google Scholar
• Bräysy O., Hasle G., Dullaert W. A multi-start local search algorithm for the vehicle routing problem with time windows. Eur. J. Oper. Res. (2004b) 159:586–605Crossref, Google Scholar
• Carlton W. B. A tabu search approach to the general vehicle routing problem. (1995) . Ph.D. thesis, University of Texas, Austin, TXGoogle Scholar
• Caseau Y., Laburthe F. Heuristics for large constrained vehicle routing problems. J. Heuristics (1999a) 5:281–303Crossref, Google Scholar
• Caseau Y., Laburthe F., Silverstein G., Jaffar J. A meta-heuristic factory for vehicle routing problems. Principles and Practice of Constraint Programming—CP’99, Lecture Notes in Computer Science (1999b) (Springer-Verlag, New York) 144–158Crossref, Google Scholar
• Chiang W. C., Russell R. A. Simulated annealing metaheuristics for the vehicle routing problem with time windows. Ann. Oper. Res. (1996) 63:3–27Crossref, Google Scholar
• Chiang W. C., Russell R. A. A reactive tabu search metaheuristic for the vehicle routing problem with time windows. INFORMS J. Comput. (1997) 9:417–430Link, Google Scholar
• Christofides N., Beasley J. The period routing problem. Networks (1984) 14:237–246Crossref, Google Scholar
• Clarke G., Wright J. W. Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. (1964) 12:568–581Link, Google Scholar
• Cordeau J.-F., Laporte G., Mercier A. A unified tabu search heuristic for vehicle routing problems with time windows. J. Oper. Res. Soc. (2001) 52:928–936Crossref, Google Scholar
• Cordeau J.-F., Gendreau M., Laporte G., Potvin J.-Y., Semet F. A guide to vehicle routing heuristics. J. Oper. Res. Soc. (2002) 53:512–522Crossref, Google Scholar
• Czech Z., Czarnas P. Parallel simulated annealing for the vehicle routing problem with time windows. Proc. 10th Euromicro Workshop Parallel Distributed Network-Based Processing (2002) Canary Islands, Spain:376–383Crossref, Google Scholar
• De Backer B., Furnon V. Meta-heuristics in constraint programming experiments with tabu search on the vehicle routing problem. Proc. Second Internat. Conf. Metaheuristics (MIC’97) (1997) (Sophia Antipolis, France) 1–14Google Scholar
• De Backer B., Furnon V., Kilby P., Prosser P., Shaw P. Solving vehicle routing problems using constraint programming and metaheuristics. J. Heuristics (2000) 6:501–523Crossref, Google Scholar
• De Jong K. A. An analysis of the behavior of a class of genetic adaptive systems. (1975) . Ph.D. thesis, University of MichiganGoogle Scholar
• Dongarra J. Performance of various computers using standard linear equations software. (1998) . Report CS-89-85, Department of Computer Science, University of Tennessee, TNGoogle Scholar
• Dorigo M., Di Caro G., Gambardella L. M. Ant algorithms for discrete optimization. Artificial Life (1999) 5:137–172Crossref, Google Scholar
• Faigle U., Kern W. Some convergence results for probabilistic tabu search. ORSA J. Comput. (1992) 4:32–37Link, Google Scholar
• Fogel D. B.Evolutionary Computation: Toward a New Philosophy of Machine Intelligence (1995) (IEEE Press, New York) Google Scholar
• Fox B. L. Integrating and accelerating tabu search, simulated annealing and genetic algorithms. Ann. Oper. Res. (1993) 41:47–67Crossref, Google Scholar
• Gambardella L. M., Taillard E., Agazzi G., Corne D., Dorigo M., Glover F. MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. New Ideas in Optimization (1999) (McGraw-Hill, London, UK) 63–76Google Scholar
• Garcia B.-L., Potvin J.-Y., Rousseau J.-M. A parallel implementation of the tabu search heuristic for vehicle routing problems with time window constraints. Comput. Oper. Res. (1994) 21:1025–1033Crossref, Google Scholar
• Gehring H., Homberger J., Miettinen K., Mäkelä M., Toivanen J. A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows. Proc. EUROGEN99 (1999) (University of Jyväskylä, Finland) 57–64Google Scholar
• Gehring H., Homberger J. Parallelization of a two-phase metaheuristic for routing problems with time windows. Asia-Pacific J. Oper. Res. (2001) 18:35–47Google Scholar
• Gendreau M., Glover F., Kochenberger G. A. An introduction to tabu search. Handbook of Metaheuristics (2003) (Kluwer Academic Publishers, Boston, MA) Crossref, Google Scholar
• Gendreau M., Hertz A., Laporte G. A new insertion and postoptimization procedures for the traveling salesman problem. Oper. Res. (1992) 40:1086–1093Link, Google Scholar
• Gendreau M., Hertz A., Laporte G. A tabu search heuristic for the vehicle routing problem. Management Sci. (1994) 40:1276–1290Link, Google Scholar
• Gendreau M., Hertz A., Laporte G., Stan M. A generalized insertion heuristic for the traveling salesman problem with time windows. Oper. Res. (1998) 46:330–335Link, Google Scholar
• Gillett B., Miller L. R. A heuristic algorithm for the vehicle dispatch problem. Oper. Res. (1974) 22:340–349Link, Google Scholar
• Glover F. Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. (1986) 13:533–549Crossref, Google Scholar
• Glover F. Tabu search—Part I. ORSA J. Comput. (1989) 1:190–206Link, Google Scholar
• Glover F. Tabu search—Part II. ORSA J. Comput. (1990) 2:4–32Link, Google Scholar
• Glover F. Multilevel tabu search and embedded search neighborhoods for the traveling salesman problem. (1991) . Working paper, College of Business & Administration, University of Colorado, Boulder, COGoogle Scholar
• Glover F., Balci O., Sharda R., Zenios S. New ejection chain and alternating path methods for traveling salesman problems. Computer Science and Operations Research: New Developments in Their Interfaces (1992) (Pergamon Press, Oxford, UK) 449–509Crossref, Google Scholar
• Glover F., Laguna M.Tabu Search (1997) (Kluwer Academic Publishers, Boston, MA) Crossref, Google Scholar
• Goldberg D.Genetic Algorithms in Search, Optimization, and Machine Learning (1989) (Addison Wesley Publishing Company Inc., New York) Google Scholar
• Golden B. L., Stewart W. R., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B. Empirical analysis of heuristics. The Traveling Salesman Problem (1985) (John Wiley and Sons, Chichester, UK) 207–249Google Scholar
• Hertz A., Taillard E., de Werra D., Aarts E., Lenstra J. K. Tabu search. Local Search in Combinatorial Optimization (1997) (John Wiley and Sons, Chichester, UK) 121–136Google Scholar
• Holland J. H.Adaptation in Natural and Artificial Systems (1975) (University of Michigan Press, Ann Arbor, MI) Google Scholar
• Homberger J., Gehring H. Two evolutionary metaheuristics for the vehicle routing problem with time windows. Inform. Systems Oper. Res. (1999) 37:297–318Crossref, Google Scholar
• Homberger J., Gehring H. A two-phase hybrid metaheuristic for the vehicle routing problem with time windows. Eur. J. Oper. Res. (2005) 162:220–238Crossref, Google Scholar
• Hopfield J. J., Tank D. W. Neural computation of decisions in optimization problems. Biological Cybernetics (1985) 52:141–152Google Scholar
• Ibaraki T., Imahori S., Kubo M., Masuda T., Uno T., Yagiura M. Effective local search algorithms for routing and scheduling problems with general time window constraints. Transportation Science (2002) . ForthcomingGoogle Scholar
• Jung S., Moon B.-R. A hybrid genetic algorithm for the vehicle routing problem with time windows. Proc. Genetic Evolutionary Comput. Conf. (2002) (Morgan Kaufmann, San Francisco) 1309–1316Google Scholar
• Kilby P., Prosser P., Shaw P., Voss S., Martello S., Osman I. H., Roucairol C. Guided local search for the vehicle routing problem with time windows. META-HEURISTICS Advanced Trends Local Search Paradigms for Optimization (1999) (Kluwer Academic Publishers, Boston, MA) 473–486Crossref, Google Scholar
• Kirkpatrick S., Gelatt C. D., Vecchi P. M. Optimization by simulated annealing. Science (1983) 220:671–680Crossref, Google Scholar
• Kohonen T.Self-Organization and Associative Memory (1988) (Springer-Verlag, Berlin, Germany) Crossref, Google Scholar
• Kontoravdis G. A., Bard J. F. A GRASP for the vehicle routing problem with time windows. INFORMS J. Comput. (1995) 7:10–23Link, Google Scholar
• Lau H. C., Lim Y. F., Liu Q. Diversification of neighborhood via constraint-based local search and its application to VRPTW. Proc. CP-AI-OR 2001 Workshop (2001) Kent, UKGoogle Scholar
• Lau H. C., Sim M., Teo K. M. Vehicle routing problem with time windows and a limited number of vehicles. Eur. J. Oper. Res. (2003) 148:559–568Crossref, Google Scholar
• Le Bouthillier A., Crainic T. G. A cooperative parallel metaheuristic for vehicle routing with time windows. Comput. Oper. Res. (2005) 32:1685–1708Crossref, Google Scholar
• Li H., Lim A. Large scale time-constrained vehicle routing problems: A general metaheuristic framework with extensive experimental results. (2001) . Working paper, National University of SingaporeGoogle Scholar
• Li H., Lim A., Huang J. Local search with annealing-like restarts to solve the VRPTW. Eur. J. Oper. Res. (2003) 150:115–127Crossref, Google Scholar
• Liu F.-H., Shen S.-Y. A route-neighborhood-based metaheuristic for vehicle routing problem with time windows. Eur. J. Oper. Res. (1999) 118:485–504Crossref, Google Scholar
• Mester D. An evolutionary strategies algorithm for large scale vehicle routing problem with capacitate and time window restrictions. (2002) . Working paper, Institute of Evolution, University of Haifa, IsraelGoogle Scholar
• Metropolis W., Rosenbluth A., Rosenbluth M., Teller A., Teller E. Equation of the state calculations by fast computing machines. J. Chemical Physics (1953) 21:1087–1092Crossref, Google Scholar
• Mladenovic N., Hansen P. Variable neighborhood search. Comput. Oper. Res. (1997) 24:1097–1100Crossref, Google Scholar
• Mühlenbein H., Aarts E., Lenstra J. K. Genetic algorithms. Local Search in Combinatorial Optimization (1997) (John Wiley and Sons, Chichester, UK) 137–172Google Scholar
• Or I. Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. (1976) . Ph.D. thesis, Northwestern University, ILGoogle Scholar
• Pesant G., Gendreau M., Rousseau J. M., Smolka G. GENIUS-CP: A generic vehicle routing algorithm. Principles and Practice of Constraint Programming—CP97, Lecture Notes in Computer Science (1997) (Springer-Verlag, New York) 420–434Crossref, Google Scholar
• Pesant G., Gendreau M., Potvin J.-Y., Rousseau J.-M. An exact constraint logic programming algorithm for the traveling salesman problem with time windows. Transportation Sci. (1998) 32:12–29Link, Google Scholar
• Potvin J.-Y., Bengio S. The vehicle routing problem with time windows, Part II: Genetic search. INFORMS J. Comput. (1996) 8:165–172Link, Google Scholar
• Potvin J.-Y., Robillard C. Clustering for vehicle routing with a competitive neural network. Neurocomputing (1995) 8:125–139Crossref, Google Scholar
• Potvin J.-Y., Rousseau J.-M. A parallel route building algorithm for the vehicle routing and scheduling problem with time windows. Eur. J. Oper. Res. (1993) 66:331–340Crossref, Google Scholar
• Potvin J.-Y., Dubé D., Robillard C. A hybrid approach to vehicle routing using neural networks and genetic algorithms. Appl. Intelligence (1996) 6:241–252Crossref, Google Scholar
• Potvin J.-Y., Kervahut T., Garcia B. L., Rousseau J.-M. The vehicle routing problem with time windows, Part I: Tabu search. INFORMS J. Comput. (1996) 8:157–164Google Scholar
• Rechenberg I.Evolutionsstrategie (1973) (Fromman-Holzboog, Stuttgart) Google Scholar
• Rochat Y., Taillard E. Probabilistic diversification and intensification in local search for vehicle routing. J. Heuristics (1995) 1:147–167Crossref, Google Scholar
• Rousseau L.-M., Gendreau M., Pesant G. Using constraint-based operators to solve the vehicle routing problem with time windows. J. Heuristics (2002) 8:43–58Crossref, Google Scholar
• Russell R. A. Hybrid heuristics for the vehicle routing problem with time windows. Transportation Sci. (1995) 29:156–166Link, Google Scholar
• Schulze J., Fahle T. A parallel algorithm for the vehicle routing problem with time window constraints. Ann. Oper. Res. (1999) 86:585–607Crossref, Google Scholar
• Schwefel H.-P.Numerische Optimierung von Computer-Modellen mittels der Evolutionsstrategie (1977) (Birkhäuser, Basel) Crossref, Google Scholar
• Shaw P., Maher M., Puget J.-F. Using constraint programming and local search methods to solve vehicle routing problems. Principles and Practice of Constraint Programming—CP98, Lecture Notes in Computer Science (1998) (Springer-Verlag, New York) 417–431Crossref, Google Scholar
• Solomon M. M. Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. (1987) 35:254–265Link, Google Scholar
• 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 Sci. (1997) 31:170–186Link, Google Scholar
• Tan K. C., Lee L. H., Zhu K. Q. Heuristic methods for vehicle routing problem with time windows. Proc. 6th Internat. Sympos. Artificial Intelligence Math. (2000) (Ft. Lauderdale, FL) Google Scholar
• Tan K. C., Lee L. H., Ou K. Hybrid genetic algorithms in solving vehicle routing problems with time window constraints. Asia-Pacific J. Oper. Res. (2001a) 18:121–130Google Scholar
• Tan K. C., Lee T. H., Ou K., Lee L. H. A messy genetic algorithm for the vehicle routing problem with time window constraints. Proc. 2001 Congress Evolutionary Comput. (2001b) (IEEE Service Center, Pistacaway, NJ) 679–686Crossref, Google Scholar
• Tan K. C., Lee L. H., Ou K. Artificial intelligence heuristics in solving vehicle routing problems with time window constraints. Engrg. Appl. Artificial Intelligence (2001c) 14:825–837Crossref, Google Scholar
• Thangiah S. R., Chambers L. Vehicle routing with time windows using genetic algorithms. Application Handbook of Genetic Algorithms: New Frontiers (1995a) II(CRC Press, Boca Raton, FL) 253–277Crossref, Google Scholar
• Thangiah S. R., Eshelman L. J. An adaptive clustering method using a geometric shape for vehicle routing problems with time windows. Proc. 6th Internat. Conf. Genetic Algorithms (1995b) (Morgan Kaufmann, San Francisco, CA) 536–543Google Scholar
• Thangiah S. R., Nygard K. E., Juell P. L. GIDEON: A genetic algorithm system for vehicle routing with time windows. Proc. 7th IEEE Conf. Artificial Intelligence Appl. (1991) (IEEE Computer Society Press, Los Alamitos) 322–328Crossref, Google Scholar
• Thangiah S. R., Osman I., Sun T. Hybrid genetic algorithm, simulated annealing and tabu search methods for vehicle routing problems with time windows. (1994) . Working paper UKC/IMS/OR94/4, Institute of Mathematics and Statistics, University of Kent, Canterbury. UKGoogle Scholar
• Thangiah S. R., Osman I. H., Vinayagamoorthy R., Sun T. Algorithms for the vehicle routing problems with time deadlines. Amer. J. Math. Management Sci. (1995) 13:323–355Google Scholar
• Voudouris C. Guided local search for combinatorial problems. (1997) . Ph.D. thesis, Department of Computer Science, University of Essex, Colchester, UKGoogle Scholar
• Voudouris C., Tsang E. Guided local search. Eur. J. Oper. Res. (1998) 113:80–119Google Scholar
• Wee Kit H., Chin J., Lim A. A hybrid search algorithm for the vehicle routing problem with time windows. Internat. J. Artificial Intelligence Tools (2001) 10:431–449Crossref, Google Scholar