IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v113y2018icp34-53.html
   My bibliography  Save this article

Multiple depot vehicle scheduling with controlled trip shifting

Author

Listed:
  • Desfontaines, Lucie
  • Desaulniers, Guy

Abstract

The multiple depot vehicle scheduling problem (MDVSP) has been widely studied in the context of public transit systems. Given a timetable of bus trips, it consists of finding a set of bus schedules that covers every trip exactly once while satisfying vehicle availability at each depot and minimizing the operating costs. This work considers a generalization of the MDVSP that allows slight modifications of the trip scheduled start times. By shifting some trips, one can indeed expect to cover all trips with fewer vehicles or less expensive deadheads (vehicle moves without passengers). However, reducing the operational costs in this way should not be too detrimental to the overall quality of the timetable and, therefore, the following criteria should be controlled: the number of shifted trips, the headways between the consecutive trips of a line, and the quality of some passenger connections. To solve this generalized problem, we develop a two-phase matheuristic: the first phase computes vehicle schedules with a column-generation heuristic; the second relies on a mixed integer program to find the best possible timetable considering the computed vehicle schedules. Penalties are introduced in the first phase to increase the chances of finding a better-quality timetable in the second phase. Computational tests on real-life datasets from a bus company show that the proposed matheuristic can solve the problem efficiently, yielding solutions with a significant reduction in the number of vehicles used compared to the solutions of the classical MDVSP and a limited alteration of the timetable.

Suggested Citation

  • Desfontaines, Lucie & Desaulniers, Guy, 2018. "Multiple depot vehicle scheduling with controlled trip shifting," Transportation Research Part B: Methodological, Elsevier, vol. 113(C), pages 34-53.
  • Handle: RePEc:eee:transb:v:113:y:2018:i:c:p:34-53
    DOI: 10.1016/j.trb.2018.05.011
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261517310652
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.trb.2018.05.011?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Enzi, Miriam & Parragh, Sophie N. & Pisinger, David & Prandtstetter, Matthias, 2021. "Modeling and solving the multimodal car- and ride-sharing problem," European Journal of Operational Research, Elsevier, vol. 293(1), pages 290-303.
    2. Wu, Weitiao & Lin, Yue & Liu, Ronghui & Jin, Wenzhou, 2022. "The multi-depot electric vehicle scheduling problem with power grid characteristics," Transportation Research Part B: Methodological, Elsevier, vol. 155(C), pages 322-347.
    3. van Lieshout, R.N., 2019. "Integrated Periodic Timetabling and Vehicle Circulation Scheduling," Econometric Institute Research Papers EI2019-27, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    4. Kulkarni, Sarang & Krishnamoorthy, Mohan & Ranade, Abhiram & Ernst, Andreas T. & Patil, Rahul, 2018. "A new formulation and a column generation-based heuristic for the multiple depot vehicle scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 118(C), pages 457-487.
    5. Johann Hartleb & Markus Friedrich & Emely Richter, 2022. "Vehicle scheduling for on-demand vehicle fleets in macroscopic travel demand models," Transportation, Springer, vol. 49(4), pages 1133-1155, August.
    6. Perumal, Shyam S.G. & Lusby, Richard M. & Larsen, Jesper, 2022. "Electric bus planning & scheduling: A review of related problems and methodologies," European Journal of Operational Research, Elsevier, vol. 301(2), pages 395-413.
    7. Rolf N. Van Lieshout, 2021. "Integrated Periodic Timetabling and Vehicle Circulation Scheduling," Transportation Science, INFORMS, vol. 55(3), pages 768-790, May.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transb:v:113:y:2018:i:c:p:34-53. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.