Dynamic Discretization Discovery for the Multidepot Vehicle Scheduling Problem with Trip Shifting

References

• Amberg B, Amberg B, Kliewer N (2019) Robust efficiency in urban public transportation: Minimizing delay propagation in cost-efficient bus and driver schedules. Transportation Sci. 53(1):89–112.Link, Google Scholar
• Bertossi AA, Carraresi P, Gallo G (1987) On some matching problems arising in vehicle scheduling models. Networks 17(3):271–281.Crossref, Google Scholar
• Boland N, Savelsbergh MW (2019) Perspectives on integer programming for time-dependent models. TOP 27(2):147–173.Crossref, Google Scholar
• Boland N, Hewitt M, Marshall L, Savelsbergh M (2017) The continuous-time service network design problem. Oper. Res. 65(5):1303–1321.Link, Google Scholar
• Borndörfer R, Löbel A, Löbel F, Weider S (2024) Solving the electric bus scheduling problem by an integrated flow and set partitioning approach. 24th Sympos. Algorithmic Approaches Transportation Model. Optim. Systems, vol. 123 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 11:1–11:16.Google Scholar
• Bunte S, Kliewer N (2009) An overview on vehicle scheduling models. Public Transport 1(4):299–317.Crossref, Google Scholar
• Carpaneto G, Dell’Amico M, Fischetti M, Toth P (1989) A branch and bound algorithm for the multiple depot vehicle scheduling problem. Networks 19(5):531–548.Crossref, Google Scholar
• Castro MP, Bodur M, Shalaby A (2024) Incorporating service reliability in multi-depot vehicle scheduling. Preprint, submitted June 30, https://arxiv.org/abs/2407.00836.Google Scholar
• Desaulniers G, Lavigne J, Soumis F (1998) Multi-depot vehicle scheduling problems with time windows and waiting costs. Eur. J. Oper. Res. 111(3):479–494.Crossref, Google Scholar
• Desfontaines L, Desaulniers G (2018) Multiple depot vehicle scheduling with controlled trip shifting. Transportation Res. Part B Methodological 113:34–53.Crossref, Google Scholar
• Desrosiers J, Lübbecke M, Desaulniers G, Gauthier JB (2024) Branch-and-Price (GERAD, HÉC, Montréal).Google Scholar
• Fonseca JP, van der Hurk E, Roberti R, Larsen A (2018) A matheuristic for transfer synchronization through integrated timetabling and vehicle scheduling. Transportation Res. Part B Methodological 109:128–149.Crossref, Google Scholar
• Forbes M, Holt J, Watts A (1994) An exact algorithm for multiple depot bus scheduling. Eur. J. Oper. Res. 72(1):115–124.Crossref, Google Scholar
• Hadjar A, Soumis F (2009) Dynamic window reduction for the multiple depot vehicle scheduling problem with time windows. Comput. Oper. Res. 36(7):2160–2172.Crossref, Google Scholar
• Hadjar A, Marcotte O, Soumis F (2006) A branch-and-cut algorithm for the multiple depot vehicle scheduling problem. Oper. Res. 54(1):130–149.Link, Google Scholar
• Haghani A, Banihashemi M (2002) Heuristic approaches for solving large-scale bus transit vehicle scheduling problem with route time constraints. Transportation Res. Part A Policy Practice 36(4):309–333.Crossref, Google Scholar
• He EY, Boland N, Nemhauser G, Savelsbergh M (2022) Dynamic discretization discovery algorithms for time-dependent shortest path problems. INFORMS J. Comput. 34(2):1086–1114.Link, Google Scholar
• Hewitt M (2019) Enhanced dynamic discretization discovery for the continuous time load plan design problem. Transportation Sci. 53(6):1731–1750.Link, Google Scholar
• Huisman D, Freling R, Wagelmans AP (2005) Multiple-depot integrated vehicle and crew scheduling. Transportation Sci. 39(4):491–502.Link, Google Scholar
• Kliewer N, Amberg B, Amberg B (2012) Multiple depot vehicle and crew scheduling with time windows for scheduled trips. Public Transport 3(3):213–244.Crossref, Google Scholar
• Kliewer N, Bunte S, Suhl L (2006a) Time windows for scheduled trips in multiple depot vehicle scheduling. Proc. EWGT2006 Joint Conf., 340–346.Google Scholar
• Kliewer N, Mellouli T, Suhl L (2006b) A time–space network based exact optimization model for multi-depot bus scheduling. Eur. J. Oper. Res. 175(3):1616–1627.Crossref, Google Scholar
• Kroon LG, Peeters LW, Wagenaar JC, Zuidwijk RA (2014) Flexible connections in PESP models for cyclic passenger railway timetabling. Transportation Sci. 48(1):136–154.Link, Google Scholar
• Kulkarni S, Krishnamoorthy M, Ranade A, Ernst AT, Patil R (2018) A new formulation and a column generation-based heuristic for the multiple depot vehicle scheduling problem. Transportation Res. Part B Methodological 118:457–487.Crossref, Google Scholar
• Lagos F, Boland N, Savelsbergh M (2022) Dynamic discretization discovery for solving the continuous time inventory routing problem with out-and-back routes. Comput. Oper. Res. 141:105686.Crossref, Google Scholar
• Laporte G, Ortega FA, Pozo MA, Puerto J (2017) Multi-objective integration of timetables, vehicle schedules and user routings in a transit network. Transportation Res. Part B Methodological 98:94–112.Crossref, Google Scholar
• Liu T, Ceder AA (2017) Integrated public transport timetable synchronization and vehicle scheduling with demand assignment: A bi-objective bi-level model using deficit function approach. Transportation Res. Procedia 23:341–361.Crossref, Google Scholar
• Marshall L, Boland N, Savelsbergh M, Hewitt M (2021) Interval-based dynamic discretization discovery for solving the continuous-time service network design problem. Transportation Sci. 55(1):29–51.Link, Google Scholar
• Mesquita M, Paixão J (1992) Multiple depot vehicle scheduling problem: A new heuristic based on quasi-assignment algorithms. Computer-Aided Transit Scheduling (Springer, Berlin, Heidelberg), 167–180.Crossref, Google Scholar
• Mingozzi A, Bianco L, Ricciardelli S (1995) An exact algorithm for combining vehicle trips. Computer-Aided Transit Scheduling (Springer, Berlin, Heidelberg), 145–172.Crossref, Google Scholar
• Pepin AS, Desaulniers G, Hertz A, Huisman D (2009) A comparison of five heuristics for the multiple depot vehicle scheduling problem. J. Scheduling 12(1):17–30.Crossref, Google Scholar
• Petersen HL, Larsen A, Madsen OB, Petersen B, Ropke S (2013) The simultaneous vehicle scheduling and passenger service problem. Transportation Sci. 47(4):603–616.Link, Google Scholar
• Ribeiro CC, Soumis F (1994) A column generation approach to the multiple-depot vehicle scheduling problem. Oper. Res. 42(1):41–52.Link, Google Scholar
• Scherr YO, Hewitt M, Saavedra BAN, Mattfeld DC (2020) Dynamic discretization discovery for the service network design problem with mixed autonomous fleets. Transportation Res. Part B Methodological 141:164–195.Crossref, Google Scholar
• Schmid V, Ehmke JF (2015) Integrated timetabling and vehicle scheduling with balanced departure times. OR Spectrum 37(4):903–928.Crossref, Google Scholar
• Steinzen I, Gintner V, Suhl L, Kliewer N (2010) A time-space network approach for the integrated vehicle-and crew-scheduling problem with multiple depots. Transportation Sci. 44(3):367–382.Link, Google Scholar
• van der Schaft T (2022) Dynamic discretization discovery for the multi-depot vehicle scheduling problem with trip shifting. Unpublished master’s thesis, Erasmus School of Economics, Erasmus University Rotterdam, Netherlands.Google Scholar
• van Lieshout RN (2021) Integrated periodic timetabling and vehicle circulation scheduling. Transportation Sci. 55(3):768–790.Link, Google Scholar
• van Lieshout RN, van der Schaft T (2025) Dynamic discretization discovery for the multi-depot vehicle scheduling problem with trip shifting. https://doi.org/10.1287/ijoc.2024.0698.cd, https://github.com/INFORMSJoC/2024.0698.Google Scholar
• Vu DM, Hewitt M, Vu DD (2022) Solving the time dependent minimum tour duration and delivery man problems with dynamic discretization discovery. Eur. J. Oper. Res. 302(3):831–846.Crossref, 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