Dynamic Programming for the Time-Dependent Traveling Salesman Problem with Time Windows

References

• Adamo T, Ghiani G, Guerriero E (2020) An enhanced lower bound for the time-dependent traveling salesman problem. Comput. Oper. Res. 113(January):104795.Crossref, Google Scholar
• Applegate DL, Bixby RE, Chvatal V, Cook WJ (2007) The Traveling Salesman Problem: A Computational Study (Princeton University Press, Princeton, NJ).Google Scholar
• Arigliano A, Calogiuri T, Ghiani G, Guerriero E (2018a) A branch-and-bound algorithm for the time-dependent travelling salesman problem. Networks 72(3):382–392.Crossref, Google Scholar
• Arigliano A, Ghiani G, Grieco A, Guerriero E, Plana I (2018b) Time-dependent asymmetric traveling salesman problem with time windows: Properties and an exact algorithm. Discrete Appl. Math. 261(May):28–39.Google Scholar
• Ascheuer N, Fischetti M, Grötschel M (2000) A polyhedral study of the asymmetric traveling salesman problem with time windows. Networks 36(2):69–79.Crossref, Google Scholar
• Ascheuer N, Fischetti M, Grötschel M (2001) Solving the asymmetric travelling salesman problem with time windows by branch-and-cut. Math. Programming 90(3):475–506.Crossref, Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283.Link, Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2012) New state-space relaxations for solving the traveling salesman problem with time windows. INFORMS J. Comput. 24(3):356–371.Link, Google Scholar
• Christofides N, Mingozzi A, Toth P (1981) State-space relaxation procedures for the computation of bounds to routing problems. Networks 11(2):145–164.Crossref, Google Scholar
• Cordeau JF, Ghiani G, Guerriero E (2014) Analysis and branch-and-cut algorithm for the time-dependent travelling salesman problem. Transportation Sci. 48(1):46–58.Link, Google Scholar
• Dash S, Günlük O, Lodi A, Tramontani A (2012) A time bucket formulation for the traveling salesman problem with time windows. INFORMS J. Comput. 24(1):132–147.Link, Google Scholar
• Dumas Y, Desrosiers J, Gelinas E, Solomon MM (1995) an optimal algorithm for the traveling salesman problem with time windows. Oper. Res. 43(2):367–371.Link, Google Scholar
• Gendreau M, Ghiani G, Guerriero E (2015) Time-dependent routing problems: A review. Comput. Oper. Res. 64:189–197.Crossref, Google Scholar
• Gendreau M, Hertz A, Laporte G, Stan M (1998) A generalized insertion heuristic for the traveling salesman problem with time windows. Oper. Res. 46(3):330–335.Link, Google Scholar
• Ichoua S, Gendreau M, Potvin JY (2003) Vehicle dispatching with time-dependent travel times. Eur. J. Oper. Res. 144(2):379–396.Crossref, Google Scholar
• Joerss M, Schröder J, Neuhaus F, Klink C, Mann F (2016) Parcel delivery: The future of last mile. Technical report, McKinsey & Company, New York.Google Scholar
• Lera-Romero G, Miranda-Bront JJ (2018) Integer programming formulations for the time-dependent elementary shortest path problem with resource constraints. Electronic Notes Discrete Math. 69(August):53–60.Crossref, Google Scholar
• Lera-Romero G, Miranda-Bront JJ (2021) A branch and cut algorithm for the time-dependent profitable tour problem with resource constraints. Eur. J. Oper. Res. 289(3):879–896.Crossref, Google Scholar
• Lera-Romero G, Miranda-Bront JJ, Soulignac FJ (2020) Linear edge costs and labeling algorithms: The case of the time-dependent vehicle routing problem with time windows. Networks 76(1):24–53.Crossref, Google Scholar
• Mingozzi A, Bianco L, Ricciardelli S (1997) Dynamic programming strategies for the traveling salesman problem with time window and precedence constraints. Oper. Res. 45(3):365–377.Link, Google Scholar
• Montero A, Méndez-Díaz I, Miranda-Bront JJ (2017) An integer programming approach for the time-dependent traveling salesman problem with time windows. Comput. Oper. Res. 88(December):280–289.Crossref, Google Scholar
• Ohlmann JW, Thomas BW (2007) A compressed-annealing heuristic for the traveling salesman problem with time windows. INFORMS J. Comput. 19(1):80–90.Link, Google Scholar
• Potvin JY, Bengio S (1996) The vehicle routing problem with time windows part II: Genetic search. INFORMS J. Comput. 8(2):165–172.Link, Google Scholar
• Savelsbergh MWP (1992) The vehicle routing problem with time windows: Minimizing route duration. ORSA J. Comput. 4(2):146–154.Link, Google Scholar
• Savelsbergh MWP, Van Woensel T (2016) 50th anniversary invited article—City logistics: Challenges and opportunities. Transportation Sci. 50(2):579–590.Link, Google Scholar
• Sun P, Veelenturf LP, Dabia S, Van Woensel T (2018) The time-dependent capacitated profitable tour problem with time windows and precedence constraints. Eur. J. Oper. Res. 264(3):1058–1073.Crossref, Google Scholar
• Tilk C, Irnich S (2017) Dynamic programming for the minimum tour duration problem. Transportation Sci. 51(2):549–565.Link, Google Scholar
• Vu DM, Hewitt M, Boland N, Savelsbergh M (2020) Dynamic discretization discovery for solving the time-dependent traveling salesman problem with time windows. Transportation Sci. 54(3):703–720.Link, Google Scholar