IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v127y2004i1p177-20110.1023-banor.0000019089.86834.91.html
   My bibliography  Save this article

An Exact Algorithm for the Simplified Multiple Depot Crew Scheduling Problem

Author

Listed:
  • M.A. Boschetti
  • A. Mingozzi
  • S. Ricciardelli

Abstract

The Multiple Depot Crew Scheduling Problem (MD-CSP) appears in public transit systems (e.g., airline, bus and railway industry) and consists of determining the optimal duties for a set of crews (or vehicles) split among several depots in order to cover a set of timetabled trips satisfying a number of constraints. We consider the case in which every crew must return to the starting depot and limits are imposed on both the elapsed time and the working time of any duty. The MD-CSP is an extension of both the Multiple Depot Vehicle Scheduling Problem (MD-VSP) and the single depot Crew Scheduling Problem (CSP). The MD-CSP is formulated as a set partitioning problem with side constraints (SP), where each column corresponds to a feasible duty. In this paper we extend to the MD-CSP the exact method used by Bianco, Mingozzi and Ricciardelli (1994) for MD-VSP and that used by Mingozzi et al. (1999) for the CSP. We also introduce a new bounding procedure based on Lagrangian relaxation and column generation which can deal with the MD-CSP constraints. The computational results for both random and real-world test problems from the literature show that the new exact procedure outperforms, on the test problems used, other exact methods proposed in the literature for the MD-VSP and the CSP. Copyright Kluwer Academic Publishers 2004

Suggested Citation

  • M.A. Boschetti & A. Mingozzi & S. Ricciardelli, 2004. "An Exact Algorithm for the Simplified Multiple Depot Crew Scheduling Problem," Annals of Operations Research, Springer, vol. 127(1), pages 177-201, March.
    • Handle: RePEc:spr:annopr:v:127:y:2004:i:1:p:177-201:10.1023/b:anor.0000019089.86834.91
    DOI: 10.1023/B:ANOR.0000019089.86834.91
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1023/B:ANOR.0000019089.86834.91
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1023/B:ANOR.0000019089.86834.91?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. Tristan Becker & Maximilian Schiffer & Grit Walther, 2022. "A General Branch-and-Cut Framework for Rotating Workforce Scheduling," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1548-1564, May.
    2. Heil, Julia & Hoffmann, Kirsten & Buscher, Udo, 2020. "Railway crew scheduling: Models, methods and applications," European Journal of Operational Research, Elsevier, vol. 283(2), pages 405-425.
    3. Boschetti, Marco A. & Golfarelli, Matteo & Graziani, Simone, 2020. "An exact method for shrinking pivot tables," Omega, Elsevier, vol. 93(C).
    4. Ibarra-Rojas, O.J. & Delgado, F. & Giesen, R. & Muñoz, J.C., 2015. "Planning, operation, and control of bus transport systems: A literature review," Transportation Research Part B: Methodological, Elsevier, vol. 77(C), pages 38-75.
    5. Marco Antonio Boschetti & Vittorio Maniezzo, 2022. "Matheuristics: using mathematics for heuristic design," 4OR, Springer, vol. 20(2), pages 173-208, June.

    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:spr:annopr:v:127:y:2004:i:1:p:177-201:10.1023/b:anor.0000019089.86834.91. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.