A Reactive Variable Neighborhood Search for the Vehicle-Routing Problem with Time Windows

References

• Antes J., Derigs U. A new parallel tour construction algorithm for the vehicle routing problem with time windows. (1995) . Working Paper, Department of Economics and Computer Science, University of Köln, GermanyGoogle 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
• Baker E. K., Schaffer J. R. Solution improvement heuristics for the vehicle routing and scheduling problem with time window constraints. Amer. J. Math. Management Sci. (1986) 6:261–300Crossref, Google Scholar
• Barnes J. W., Carlton W. B. A tabu search approach to the vehicle routing problem with time windows. (1995) Fall INFORMS ConferenceNew Orleans, LAGoogle Scholar
• Battiti R., Tecchiolli G. The reactive tabu search. ORSA J. Comput. (1994) 6:126–140Link, Google Scholar
• Berger J., Salois M., Begin R. A hybrid genetic algorithm for the vehicle routing problem with time windows. Lecture Notes in Artificial Intelligence (1998) No. 1418:114–127AI'98, Advances in Artificial Intelligence, Vancouver, BC, CanadaCrossref, Google Scholar
• Blanton J. L., Wainwright R. L., Forrest S. Multiple vehicle routing with time and capacity constraints using genetic algorithms. Proc. Fifth Internat. Conf. on Genetic Algorithms. (1993) (Morgan Kaufmann Publishing, San Francisco, CA) 452–459Google Scholar
• Bramel J., Simchi-Levi D. Probabilistic analyses and practical algorithms for the vehicle routing problem with time windows. Oper. Res. (1996) 44:501–509Link, Google Scholar
• Brandão J., Voss S., Martello S., Osman I. H., Roucairol C. Metaheuristic for the vehicle routing problem with time windows. Meta-heuristics—Advances and Trends in Local Search Paradigms for Optimization (1999) (Kluwer Academic Publishers, Boston, MA) 19–36Crossref, Google Scholar
• Bräysy O. A hybrid genetic algorithm for the vehicle routing problem with time windows. (1999a) . Licentiate thesis, Department of Mathematics and Statistics, University of Vaasa, Vaasa, FinlandGoogle Scholar
• Bräysy O. A new algorithm for the vehicle routing problem with time windows based on the hybridization of a genetic algorithm and route construction heuristics. Proc. University of Vaasa, Research papers 227 (1999b) University of Vaasa, Vaasa, FinlandGoogle Scholar
• Bräysy O. Local search and variable neighborhood search algorithms for the vehicle routing problem with time windows. (2001) . Doctoral thesis, Department of Mathematics and Statistics, University of Vaasa, Vaasa, FinlandGoogle Scholar
• Bräysy O., Berger J., Barkaoui M. A new hybrid evolutionary algorithm for the vehicle routing problem with time windows. (2000) . Route 2000-Workshop, Skodsborg, DenmarkGoogle Scholar
• Carlton W. B. A tabu search approach to the general vehicle routing problem. (1995) . Ph.D. thesis, Department of Mechanical Engineering, University of Texas, Austin, TXGoogle Scholar
• Caseau Y., Laburthe F. Heuristics for large constrained vehicle routing problems. J. Heuristics (1999) 5:281–303Crossref, 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
• 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
• Cook W., Rich J. L. A parallel cutting-plane algorithm for the vehicle routing problems with time windows. (1999) . Working Paper, Department of Computational and Applied Mathematics, Rice University, Houston, TXGoogle Scholar
• Cordeau J-F., Desaulniers G., Desrosiers J., Solomon M. M., Soumis F., Toth P., Vigo D. The VRP with time windows. The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications (2001a) (SIAM, Philadelphia, PA) 157–194Google Scholar
• Cordeau J-F., Laporte G., Mercier A. A unified tabu search heuristic for vehicle routing problems with time windows. J. Oper. Res. Soc. (2001b) 52:928–936Crossref, Google Scholar
• Cordone R., Wolfler-Calvo R. A heuristic for the vehicle routing problem with time windows. J. Heuristics (2001) 7:107–129Crossref, Google 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
• Desrochers M., Lenstra J. K., Savelsbergh M. W. P., Soumis F., Golden B., Assad A. Vehicle routing with time windows: optimization and approximation. Vehicle Routing: Methods and Studies (1988) (Elsevier Science Publishers, Amsterdam, The Netherlands) 65–84Google Scholar
• Desrosiers J., Dumas Y., Solomon M. M., Soumis F., Ball M. Time constrained routing and scheduling. Handbooks in Operations Research and Management Science 8: Network Routing (1995) (Elsevier Science Publishers, Amsterdam, The Netherlands) 35–139Google Scholar
• Dongarra J. Performance of various computers using standard linear equations software. (1998) . Report CS-89-85, Department of Computer Science, University of Tennessee, Knoxville, TNGoogle 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—Short Course on Evolutionary Algorithms in Engineering and Comput. Sci., Reports of the Department of Mathematical Information Technology (1999) University of Jyväskylä, Jyväskylä, Finland:57–64Series A. Collections, No. A 2/1999Google 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
• 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
• Golden B. L., Assad A. A. Perspectives on vehicle routing: exciting new developments. Oper. Res. (1986) 34:803–809Link, Google Scholar
• Golden B. L., Assad A. A.Vehicle Routing: Methods and Studies (1988) (Elsevier Science Publishers, Amsterdam, The Netherlands) Google Scholar
• Hansen P., Mladenovic N., Pardalos P. M., Resende M. G. C. Variable neighborhood search. Handbook of Applied Optimization (2002) (Oxford University Press, New York) 221–234Google Scholar
• Homberger J., Gehring H. Two evolutionary meta-heuristics for the vehicle routing problem with time windows. INFOR (1999) 37:297–318Google 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 Advances and Trends in Local Search Paradigms for Optimization (1999) (Kluwer Academic Publishers, Boston, MA) 473–486Crossref, Google Scholar
• Kohl N. Exact methods for time constrained routing and related scheduling problems. (1995) . Ph.D. thesis, Institute of Mathematical Modelling, Technical University of Denmark, Lyngby, DenmarkGoogle Scholar
• Kohl N., Desrosiers J., Madsen O. B. G., Solomon M. M., Soumis F. 2-path cuts for the vehicle routing problem with time windows. Transportation Sci (1999) 33:101–116Link, Google Scholar
• Kontoravdis G. A., Bard J. F. A GRASP for the vehicle routing problem with time windows ORSA. J. Comput. (1995) 7:10–23Abstract, Google Scholar
• Larsen J. Parallelization of the vehicle routing problem with time windows. (1999) . Ph.D. thesis, Institute of Mathematical Modelling, Technical University of Denmark, Lyngby, DenmarkGoogle 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
• Mladenovic N., Hansen P. Variable neighborhood search. Comput. Oper. Res. (1997) 24:1097–1100Crossref, Google Scholar
• Or I. Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. (1976) . Ph.D. thesis, Department of Computer Science, Northwestern University, Evanston, ILGoogle Scholar
• Osman I. H. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problems. Ann. Oper. Res. (1993) 41:421–452Crossref, Google Scholar
• Potvin J-Y., Bengio S. The vehicle routing problem with time windows part II: genetic search. ORSA. J. Comput. (1996) 8:165–172Abstract, Google Scholar
• Potvin J-Y., Kervahut T., Garcia B. L., Rousseau J-M. The vehicle routing problem with time windows part I: Tabu search. ORSA. J. Comput. (1996b) 8:157–164Google Scholar
• Potvin J-Y., Dube D., Robillard C. A hybrid approach to vehicle routing using neural networks and genetic algorithms. Appl. Intelligence (1996a) 6:241–252Crossref, 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., Rousseau J-M. An exchange heuristic for routing problems with time windows. J. Oper. Res. Soc. (1995) 46:1433–1446Crossref, 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. An effective heuristic for the M-tour traveling salesman problem with some side conditions. Oper. Res. (1977) 25:517–524Link, Google Scholar
• Russell R. A. Hybrid heuristics for the vehicle routing problem with time windows. Transportation Sci (1995) 29:156–166Link, Google Scholar
• Savelsbergh M. W. P. The vehicle routing problem with time windows: minimizing route duration. ORSA. J. Comput. (1992) 4:146–154Abstract, 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
• Shaw P. A new local search algorithm providing high quality solutions to vehicle routing problems. (1997) . Working Paper, Department of Computer Science, University of Strathclyde, Glasgow, ScotlandGoogle 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
• Solomon M. M., Baker E. K., Schaffer J. R., Golden B., Assad A. Vehicle routing and scheduling problems with time window constraints: efficient implementations of solution improvement procedures. Vehicle Routing: Methods and Studies (1988) (Elsevier Science Publishers, Amsterdam, The Netherlands) 85–106Google Scholar
• Solomon M. M., Desrosiers J. Time window constrained routing and scheduling problems. Transportation Sci (1988) 22:1–13Link, 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., Ou K. Hybrid genetic algorithms in solving vehicle routing problems with time window constraints. Asia-Pacific J. Oper. Res. (2001) 18:121–130Google Scholar
• Tan K. C., Lee L. H., Zhu K. Q. Heuristic methods for vehicle routing problem with time windows. Proc. 6th Internat. Sympos. on Artificial Intelligence & Mathematics (2000) Ft. Lauderdale, FLGoogle Scholar
• Thangiah S., Chambers L. Vehicle routing with time windows using genetic algorithms. Application Handbook of Genetic Algorithms: New Frontiers, Volume II (1995) (CRC Press, Boca Raton, FL) 253–277Crossref, Google Scholar
• Thangiah S., 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
• Thompson P. M., Psaraftis H. N. Cyclic transfer algorithms for multivehicle routing and scheduling problems. Oper. Res. (1993) 41:935–946Link, Google Scholar
• Van Landeghem H. R. G. A bi-criteria heuristic for the vehicle routing problem with time windows. Eur. J. Oper. Res. (1988) 36:217–226Crossref, Google 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