Dynamic Discretization Discovery for Solving the Time-Dependent Traveling Salesman Problem with Time Windows

References

• Abeledo HG, Fukasawa R, Pessoa AA, Uchoa E (2013) The time dependent traveling salesman problem: Polyhedra and algorithm. Math. Programming Comput. 5(1):27–55.Crossref, Google Scholar
• Albiach J, Sanchis JM, Soler D (2008) An asymmetric TSP with time windows and with time-dependent travel times and costs: An exact solution through a graph transformation. Eur. J. Oper. Res. 189(3):789–802.Crossref, Google Scholar
• Arigliano A, Ghiani G, Grieco A, Guerriero E, Plana I (2018) Time-dependent asymmetric traveling salesman problem with time windows: Properties and an exact algorithm. Working paper, Università del Salento, Lecce, Italy.Google Scholar
• Baker EK (1983) Technical note—an exact algorithm for the time-constrained traveling salesman problem. Oper. Res. 31(5):938–945.Link, 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
• Boland N, Hewitt M, Marshall L, Savelsbergh M (2017a) The continuous-time service network design problem. Oper. Res. 65(5):1303–1321.Link, Google Scholar
• Boland N, Hewitt M, Vu DM, Savelsbergh M (2017b) Solving the traveling salesman problem with time windows through dynamically generated time-expanded networks. Salvagnin D, Lombardi M, eds. Integration of AI and OR Techniques in Constraint Programming, Theoretical Computer Science and General Issues, vol. 10335 (Springer International Publishing, Cham, Switzerland), 254–262.Google Scholar
• Bront JM, Méndez-Díaz I, Zabala P (2014) Facets and valid inequalities for the time-dependent travelling salesman problem. Eur. J. Oper. Res. 236(3):891–902.Crossref, 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 J-F, 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
• Desrochers M, Desrosiers J, Solomon M (1992) A new optimization algorithm for the vehicle routing problem with time windows. Oper. Res. 40(2):342–354.Link, Google Scholar
• Desrosiers J, Dumas Y, Solomon MM, Soumis F (1995) Time constrained routing and scheduling. Ball MO, Magnanti TL, Monma CL, Nemhauser GI, eds. Network Routing, Handbooks in Operations Research and Management Science, vol. 8 (Elsevier, Amsterdam), 35–139.Google Scholar
• Figliozzi MA (2012) The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics. Transportation Res. Part E: Logist. Trans. Rev. 48(3):616–636.Crossref, Google Scholar
• Fischetti M, Laporte G, Martello S (1993) The delivery man problem and cumulative matroids. Oper. Res. 41(6):1055–1064.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
• Ghiani G, Guerriero E (2014) A note on the Ichoua, Gendreau, and Potvin (2003) travel time model. Transportation Sci. 48(3):458–462.Link, Google Scholar
• Gouveia L, Voz S (1995) A classification of formulations for the (time-dependent) traveling salesman problem. Eur. J. Oper. Res. 83(1):69–82.Crossref, Google Scholar
• Ichoua S, Gendreau M, Potvin J-Y (2003) Vehicle dispatching with time-dependent travel times. Eur. J. Oper. Res. 144(2):379–396.Crossref, Google Scholar
• Kara I, Derya T (2015) Formulations for minimizing tour duration of the traveling salesman problem with time windows. Procedia Econom. Finance 26:1026–1034.Crossref, Google Scholar
• Kara I, Koc ON, Altparmak F, Dengiz B (2013) New integer linear programming formulation for the traveling salesman problem with time windows: Minimizing tour duration with waiting times. Optimization 62(10):1309–1319.Crossref, Google Scholar
• Langevin A, Desrochers M, Desrosiers J, Gélinas S, Soumis F (1993) A two-commodity flow formulation for the traveling salesman and the makespan problems with time windows. Networks 23(7):631–640.Crossref, Google Scholar
• Lucena A (1990) Time-dependent traveling salesman problem-the deliveryman case. Networks 20(6):753–763.Crossref, Google Scholar
• Mahmoudi M, Zhou X (2016) Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state–space–time network representations. Transportation Res. Part B: Methodological 89:19–42.Crossref, Google Scholar
• Melgarejo PA, Laborie P, Solnon C (2015) A time-dependent no-overlap constraint: Application to urban delivery problems. Michel L, ed. Integration of AI and OR Techniques in Constraint Programming, Lecture Notes in Computer Science, vol. 9075 (Springer, Cham, Switzerland), 1–17.Google Scholar
• Méndez-Díaz I, Juan JMB, Toth P, Zabala P (2011) Infeasible path formulations for the time-dependent TSP with time windows. Adacher L, Flamini M, Leo G, Nicosia G, Pacifici A, Piccialli V, eds. Proc. 10th Cologne-Twente Workshop Graphs Combinatorial Optim., Frascati, Itality, 198–202.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:280–289.Crossref, Google Scholar
• Picard J-C, Queyranne M (1978) The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling. Oper. Res. 26(1):86–110.Link, Google Scholar
• Savelsbergh M (1985) Local search in routing problems with time windows. Ann. Oper. Res. 4(1):285–305.Crossref, Google Scholar
• Stecco G, Cordeau J-F, Moretti E (2008) A branch-and-cut algorithm for a production scheduling problem with sequence-dependent and time-dependent setup times. Comput. Oper. Res. 35(8):2635–2655.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
• UN (2014) Our urbanizing world. Technical report, United Nations Department of Economic and Social Affairs, New York.Google Scholar