A Unified Modeling and Solution Framework for Vehicle Routing and Local Search-Based Metaheuristics

References

• Aarts E., Lenstra J. K.Local Search in Combinatorial Optimization (1997) (Wiley, Chichester, UK) Google Scholar
• Ascheuer N. Hamiltonian path problems in the on-line optimization of flexible manufacturing systems. (1995) . PhD thesis, Technische Universität Berlin, BerlinGoogle Scholar
• Bräysy O., Gendreau M. Vehicle routing with time windows, Part I: Route construction and local search algorithms. Transportation Sci. (2005a) 39:104–118Link, Google Scholar
• Bräysy O., Gendreau M. Vehicle routing with time windows, Part II: Metaheuristics. Transportation Sci. (2005b) 39:119–139Link, Google Scholar
• Christofides N., Eilon S. An algorithm for the vehicle-dispatching problem. Oper. Res. Quart. (1969) 20:309–318Crossref, Google Scholar
• Christofides N., Eilon S. Algorithms for large-scale travelling salesman problems. Oper. Res. Quart. (1972) 23:511–518Crossref, Google Scholar
• Cordeau J.-F., Desaulniers G., Desrosiers J., Solomon M. M., Soumis F. VRP with time windows. The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications (2002) (SIAM, Philadelphia) 155–194Chapter 7Crossref, Google Scholar
• Desaulniers G., Desrosiers J., Solomon M. M. Accelerating strategies in column generation for vehicle routing and crew scheduling problems. Essays and Surveys in Metaheuristics. Operations Research/Computer Science Interface Series (2002) (Kluwer, Boston) 309–324Chapter 14Crossref, Google Scholar
• Desaulniers G., Desrosiers J., Solomon M. M.Column Generation (2005) (Springer, New York) Crossref, Google Scholar
• Desaulniers G., Lessard F., Hadjar A. Tabu search, generalized k-path inequalities, and partial elementarity for the vehicle routing problem with time windows. (2006) . Les Cahiers du GERAD G-2006-45, HEC Montréal, MontréalGoogle Scholar
• Desaulniers G., Desrosiers J., Ioachim I., Solomon M. M., Soumis F., Villeneuve D., Crainic T. G., Laporte G. A unified framework for deterministic time constrained vehicle routing and crew scheduling problems. Fleet Management and Logistics (1998) (Kluwer Academic Publishers, Boston) 57–93Chapter 3Crossref, Google Scholar
• Desrochers M., Desrosiers J., Solomon M. A new optimization algorithm for the vehicle routing problem with time windows. Oper. Res. (1992) 40:342–354Link, Google Scholar
• Desrochers M., Lenstra J. K., Savelsbergh M. W. P. A classification scheme for vehicle routing and scheduling problems. Eur. J. Oper. Res. (1990) 46:322–332Crossref, Google Scholar
• Desrosiers J., Dumas Y., Solomon M. M., Soumis F., Ball M. O., Magnanti T. L., Monma C. L., Nemhauser G. L. Time constrained routing and scheduling. Network Routing. Handbooks in Operations Research and Management Science (1995) 8(Elsevier, Amsterdam) 35–139Google Scholar
• Fukasawa R., Lysgaard J., Poggi de Aragão M., Uchoa E., Reis M., Werneck R. F. Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming Ser. A. (2006) 106:491–511Crossref, Google Scholar
• Funke B. Effiziente lokale suche für vehicle routing und scheduling probleme mit ressourcenbeschränkungen. (2003) . PhD thesis, Rheinisch-Westfälische Technische Hochschule Aachen University, Aachen, GermanyGoogle Scholar
• Funke B., Grünert T., Irnich S. Local search for vehicle routing and scheduling problems: Review and conceptual integration. J. Heuristics (2005a) 11:267–306Crossref, Google Scholar
• Funke B., Grünert T., Irnich S. A note on single alternating cycle neighborhoods for the TSP. J. Heuristics (2005b) 11:135–146Crossref, Google Scholar
• Glover F. Ejection chains, reference structures and alternating path structures for traveling salesman problems. Discrete Appl. Math. (1996) 65:223–253Crossref, Google Scholar
• Glover F., Laguna M.Tabu Search (1997) (Kluwer, Dordrecht, the Netherlands) Crossref, Google Scholar
• Hansen P., Mladenović N. Variable neighborhood search: Principles and applications. Eur. J. Oper. Res. (2001) 130:449–467Crossref, Google Scholar
• Hansen P., Mladenović N. Developments of variable neighborhood search. Essays and Surveys in Metaheuristics. Operations Research/Computer Science Interface Series (2002) (Kluwer, Boston) 415–439Chapter 19Crossref, Google Scholar
• Hasle G., Løk ketangen A., Martello S. Rich models in discrete optimization: Formulation and resolution (ECCO XVI). Eur. J. Oper. Res. (2006) 175:1752–1753Crossref, Google Scholar
• Hempsch C., Irnich S. Vehicle-routing problems with inter-tour resource constraints. (2007) . Technical report 2007-01, Deutsche Post Endowed Chair of Optimization of Distribution Networks, Rheinisch-Westfälische Technische Hochschule Aachen University, Aachen, Germany. http://www.dpor.rwth-aachen.deGoogle 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
• Hoos H. H., Stützle T.Stochastic Local Search Foundations and Applications (2005) (Morgan Kaufmann Publishers, Elsevier, San Francisco) Google Scholar
• Irnich S. Resource extension functions: Properties, inversion, and generalization to segments. OR Spectrum (2008) 30(1):113–148Crossref, Google Scholar
• Irnich S., Desaulniers G. Shortest path problems with resource constraints. Column Generation (2005) (Springer, New York) 33–65Chapter 2Crossref, Google Scholar
• Irnich S., Funke B., Grünert T. Sequential search and its application to vehicle-routing problems. Comput. Oper. Res. (2006) 33:2405–2429Crossref, Google Scholar
• Janssens G. K., Hartl R., Hasle G. Special issue on rich vehicle routing problems. Central Eur. J. Oper. Res. (2006) 14:103–104Crossref, Google Scholar
• Jepsen M., Spoorendonk S., Petersen B., Pisinger D. A non-robust branch-and-cut-and-price algorithm for the vehicle routing problem with time windows. (2006) . DIKU Technical Report 06/03, Department of Computer Science, University of Copenhagen, CopenhagenGoogle Scholar
• Kallehauge B., Larsen J., Madsen O. B. G., Solomon M. M. Vehicle routing problem with time windows. Column Generation (2005) (Springer, New York) 67–98Chapter 3Crossref, Google Scholar
• Kernighan B. W., Lin S. An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. (1970) 49:291–307Crossref, Google Scholar
• Kilby P., Prosser P., Shaw P. A comparison of traditional and constraint-based heuristic methods on vehicle routing problems with side constraints. Constraints (2000) 5:389–414Crossref, Google Scholar
• Kindervater G. A. P., Savelsbergh M. W. P. Vehicle routing: Handling edge exchanges. Local Search in Combinatorial Optimization (1997) (Wiley, Chichester, UK) 337–360Chapter 10Google Scholar
• Laporte G. The vehicle routing problem: An overview of exact and approximate algorithms. Eur. J. Oper. Res. (1992) 59:345–358Crossref, Google Scholar
• Laporte G., Dell'Amico M., Maffioli F., Martello S. Vehicle routing. Annotated Bibliographics in Combinatorial Optimization (1997) (Wiley, Chichester, UK) 223–240Google Scholar
• Lin S., Kernighan B. W. An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. (1973) 21:498–516Link, Google Scholar
• Lübbecke M., Desrosiers J. Selected topics in column generation. Oper. Res. (2005) 53:1007–1023Link, Google Scholar
• Martin O., Otto S. W., Felten E. W. Large-step Markov chains for the TSP incorporating local search heuristics. Oper. Res. Lett. (1992) 11:219–224Crossref, Google Scholar
• Ribeiro C. C., Hansen P.Essays and Surveys in Metaheuristics (2002) (Kluwer, Boston) Operations Research/Computer Science Interfaces SeriesCrossref, Google Scholar
• Røpke S., Pisinger D. A unified heuristic for a large class of vehicle routing problems with backhauls. Eur. J. Oper. Res. (2006) 171:750–775Crossref, Google Scholar
• Shaw P. Using constraint programming and local search methods to solve vehicle routing problems. (1998) . Technical report, Department of Computer Science, University of Strathclyde, Glasgow, ScotlandGoogle Scholar
• Solomon M. M. Algorithms for the vehicle routing and scheduling problem with time window constraints. Oper. Res. (1987) 35:254–265Link, Google Scholar
• Toth P., Vigo D.The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications (2002) (SIAM, Philadelphia) Crossref, Google Scholar
• Toth P., Vigo D. The granular tabu search and its application to the vehicle-routing problem. INFORMS J. Comput. (2003) 15:333–346Link, Google Scholar
• Voß S., Woodruff D.Optimization Software Class Libraries (2002) (Kluwer Academic Publishers, Boston) Crossref, Google Scholar