New State-Space Relaxations for Solving the Traveling Salesman Problem with Time Windows

References

• Ascheuer N., Fischetti M., Grötschel M. A polyhedral study of the asymmetric traveling salesman problem with time windows. Networks (2000) 36(2):69–79Crossref, Google Scholar
• Ascheuer N., Fischetti M., Grötschel M. Solving the asymmetric travelling salesman problem with time windows by branch-and-cut. Math. Programming Ser. A (2001) 90(3):475–506Crossref, Google Scholar
• Baker E. K. An exact algorithm for the time-constrained traveling salesman problem. Oper. Res. (1983) 31(5):938–945Link, Google Scholar
• Balas E., Simonetti N. Linear time dynamic-programming algorithms for new classes of restricted TSPs: A computational study. INFORMS J. Comput. (2001) 13(1):56–75Link, Google Scholar
• Baldacci R., Mingozzi A., Roberti R. New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. (2011) . ForthcomingLink, Google Scholar
• Baldacci R., Bartolini E., Mingozzi A., Roberti R. An exact solution framework for a broad class of vehicle routing problems. Comput. Management Sci. (2010) 7(3):229–268Crossref, Google Scholar
• Christofides N., Mingozzi A., Toth P. An algorithm for the time constrained travelling salesman problem. (1981a) . Technical Report IC OR 8125, Imperial College, LondonGoogle Scholar
• Christofides N., Mingozzi A., Toth P. State-space relaxation procedures for the computation of bounds to routing problems. Networks (1981b) 11(2):145–164Crossref, Google Scholar
• Dash S., Günlük O., Lodi A., Tramontani A. A time bucket formulation for the traveling salesman problem with time windows. INFORMS J. Comput. (2012) 24(1):132–147Link, Google Scholar
• Desaulniers G., Lessard F., Hadjar A. Tabu search, partial elementarity, and generalized k-path inequalities for the vehicle routing problem with time windows. Transportation Sci. (2008) 42(3):387–404Link, Google Scholar
• Dumas Y., Desrosiers J., Gélinas E., Solomon M. M. An optimal algorithm for the traveling salesman problem with time windows. Oper. Res. (1995) 43(2):367–371Link, Google Scholar
• Focacci F., Lodi A., Milano M. A hybrid exact algorithm for the TSPTW. INFORMS J. Comput. (2002) 14(4):403–417Link, 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(3):330–335Link, Google Scholar
• Jepsen M., Petersen B., Spoorendonk S., Pisinger D. Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. (2008) 56(2):497–511Link, Google Scholar
• Langevin A., Desrochers M., Desrosiers J., Gélinas S., Soumis F. A two-commodity flow formulation for the traveling salesman and the makespan problems with time windows. Networks (1993) 23(7):631–640Crossref, Google Scholar
• Li J. Q. A computational study of bi-directional dynamic programming for the traveling salesman problem with time windows. (2009) . Working paper, University of California, Berkeley, BerkeleyGoogle Scholar
• López-Ibáñez M., Blum C. Beam-ACO for the travelling salesman problem with time windows. Comput. Oper. Res. (2010) 37(9):1570–1583Crossref, Google Scholar
• Mingozzi A., Bianco L., Ricciardelli S. Dynamic programming strategies for the traveling salesman problem with time window and precedence constraints. Oper. Res. (1997) 45(3):365–377Link, Google Scholar
• Ohlmann J. W., Thomas B. W. A compressed-annealing heuristic for the traveling salesman problem with time windows. INFORMS J. Comput. (2007) 19(1):80–90Link, Google Scholar
• Ohlmann J., Thomas B. (2010) . Private communication. (April 7)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(1):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(2):165–172Link, Google Scholar
• Righini G., Salani M. Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optim. (2006) 3(3):255–273Crossref, Google Scholar
• Wolfler Calvo R. A new heuristic for the traveling salesman problem with time windows. Transportation Sci. (2000) 34(1):113–124Link, Google Scholar