Skip to main content
SpringerLink
Log in

Multiple depot vehicle and crew scheduling with time windows for scheduled trips

  • Original Paper
  • Published:
Public Transport Aims and scope Submit manuscript

Abstract

This paper examines time windows for scheduled trips in multiple depot vehicle and crew scheduling problems that arise in public bus transportation. In practice, the two planning tasks vehicle scheduling and crew scheduling are traditionally solved sequentially with the implicit understanding that the scheduled time for timetabled trips remains fixed. In order to improve cost efficiency two concepts have been developed over the last years: In order to obtain better flexibility when scheduling crews, vehicle and crew scheduling problems are tackled simultaneously. In order to extend flexibility while scheduling vehicles, variable trip departure and arrival times are considered. Obviously the combination of both concepts promises the largest savings, but probably leads to bursting computational times due to growing problem complexity.

In this paper we combine both concepts by extending the integrated vehicle and crew scheduling problem with the possibility to shift scheduled trips within defined time windows. We examine the tradeoffs between solution quality and computational time for different solution approaches.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

References

  • Bertossi AA, Carraresi P, Gallo G (1987) On some matching problems arising in vehicle scheduling models. Networks 17:271–281

    Article  Google Scholar 

  • Bokinge U, Hasselstroem D (1980) Improved vehicle scheduling in public transport through systematic changes in the timetable. Eur J Oper Res 5(6):388–395

    Article  Google Scholar 

  • Borndoerfer R, Loebel A, Weider S (2008) A bundle method for integrated multi-depot vehicle and duty scheduling in public transit. In: Computer-aided systems in public transport. Lecture notes in economics and mathematical systems, Part I, vol 600. Springer, Berlin, pp 3–24

    Chapter  Google Scholar 

  • Bunte S, Kliewer N (2009) An overview on vehicle scheduling models. Public Transp 1(4):299–317

    Article  Google Scholar 

  • Desaulniers G, Hickman D (2007) Public transit. In: Transportation. Handbooks in operations research and management science, vol 14. Holland North, The Netherlands, pp 69–127, Chap 2

    Chapter  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

    Article  Google Scholar 

  • Desrochers M, Soumis F (1989) A column generation approach to the urban transit crew scheduling problem. Transp Sci 23(1):1–13

    Article  Google Scholar 

  • Desrosiers J, Dumas Y, Solomon MM, Soumis F (1995) Time constrained routing and scheduling. Handbooks in operations research and management science, vol 8. Elsevier, Amsterdam, pp 35–139, Chap 2

    Google Scholar 

  • Fischetti M, Lodi A, Martello S, Toth P (1987) The fixed job schedule problem with spread-time constraints. Oper Res 35(6):849–858

    Article  Google Scholar 

  • Fischetti M, Lodi A, Toth P (1989) The fixed job schedule problem with working-time constraints. Oper Res 37(3):395–403

    Article  Google Scholar 

  • Fischetti M, Lodi A, Toth P (1999) A branch-and-cut algorithm for the multiple depot vehicle scheduling problem. Technical report, DEIS, Universit di Bologna, Italy

  • Forbes M, Holt J, Watts A (1994) An exact algorithm for multiple depot bus scheduling. Eur J Oper Res 72(1):115–124

    Article  Google Scholar 

  • Freling R (1997) Models and techniques for integrating vehicle and crew scheduling. PhD thesis, Erasmus University of Rotterdam, The Netherlands

  • Gintner V, Steinzen I, Suhl L (2006) A time-space network based approach for integrated vehicle and crew scheduling in public transport. In: Proceedings of the EURO working group on transportation (EWGT) joint conferences 2006, pp 371–377

    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

    Article  Google Scholar 

  • Huisman D (2004) Integrated and dynamic vehicle and crew scheduling. PhD thesis, Erasmus University of Rotterdam, The Netherlands

  • Huisman D, Freling R, Wagelmans AP (2005) Multiple-depot integrated vehicle and crew scheduling. Transp Sci 39(4):491–502

    Article  Google Scholar 

  • Keri A, Haase K (2008) Simultaneous vehicle and crew scheduling with trip shifting. In: Operations research proceedings 2007. Springer, Berlin, pp 467–472

    Chapter  Google Scholar 

  • Kliewer N, Mellouli T, Suhl L (2002) A new solution model for multi-depot multi-vehicle type vehicle scheduling in (sub)urban public transport. In: Proceedings of the 13th Mini-EURO conference and the 9th meeting of the EURO working group on transportation (EWGT). Politecnico of Bari, Bari

    Google Scholar 

  • Kliewer N, Mellouli T, Suhl L (2006a) A time-space network based exact optimization model for multiple-depot bus scheduling. Eur J Oper Res 175(3):1616–1627

    Article  Google Scholar 

  • Kliewer N, Bunte S, Suhl L (2006b) Time windows for scheduled trips in multiple depot vehicle scheduling. In: Proceedings of the EURO working group on transportation (EWGT) joint conferences 2006, pp 340–346

    Google Scholar 

  • Kliewer N, Gintner V, Suhl L (2008) Line change considerations within a time-space network based multi-depot bus scheduling model. In: Proceedings of 9th international conference on computer-aided scheduling of public transport (CASPT), pp 57–70

    Google Scholar 

  • Loebel A (1999) Solving large-scale multiple-depot vehicle scheduling problems. In: Lecture notes in economics and mathematical systems (LNEMS). Computer-aided transit scheduling, vol 471. Springer, Berlin, pp 193–220

    Google Scholar 

  • Mesquita M, Paias A (2008) Set partitioning/covering-based approaches for the integrated vehicle and crew scheduling problem. Comput Oper Res 35(5):1562–1575

    Article  Google Scholar 

  • Mesquita M, Paias A, Respicio A (2009) Branching approaches for integrated vehicle and crew scheduling. Public Transp 1(1):21–37

    Article  Google Scholar 

  • Mingozzi A, Bianco L, Ricciardelli S (1995) An exact algorithm for combining vehicle trips. In: Proceedings of the 6th international workshop on computer aided scheduling of public transport (CASPT), pp 145–172

    Google Scholar 

  • Pepin A-S, Desaulniers G, Hertz A, Huisman D (2009) A comparison of five heuristics for the multiple depot vehicle scheduling problem. J Sched 12(1):17–30

    Article  Google Scholar 

  • Portugal R, Lourenço HR, Paixao JP (2009) Driver scheduling problem modelling. Public Transp 1(2):103–120

    Article  Google Scholar 

  • Ribeiro C, Soumis F (1994) A column generation approach to the multiple-depot vehicle scheduling problem. Oper Res 42(1):41–52

    Article  Google Scholar 

  • Steinzen I (2007) Topics in integrated vehicle and crew scheduling in public transit. PhD thesis, University of Paderborn, Germany

  • 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. Transp Sci 44(3):367–382

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Chair of Information Systems, Freie Universität Berlin, Garystr. 21, 14195, Berlin, Germany

    Natalia Kliewer & Bastian Amberg

  2. Decision Support & OR Lab and International Graduate School of Dynamic Intelligent Systems, University of Paderborn, Warburger Str. 100, 33098, Paderborn, Germany

    Boris Amberg

Authors
  1. Natalia Kliewer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bastian Amberg
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Boris Amberg
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bastian Amberg.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kliewer, N., Amberg, B. & Amberg, B. Multiple depot vehicle and crew scheduling with time windows for scheduled trips. Public Transp 3, 213–244 (2012). https://doi.org/10.1007/s12469-011-0049-6

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12469-011-0049-6

Keywords

Search

Navigation