An Exact Algorithm for the Simplified Multiple Depot Crew Scheduling Problem

M.A. Boschetti, A. Mingozzi and S. Ricciardelli

Annals of Operations Research, 2004, vol. 127, issue 1, 177-201

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

Keywords: dual heuristics; set partitioning; personal scheduling (search for similar items in EconPapers)
Date: 2004
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://hdl.handle.net/10.1023/B:ANOR.0000019089.86834.91 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:127:y:2004:i:1:p:177-201:10.1023/b:anor.0000019089.86834.91

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/B:ANOR.0000019089.86834.91

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().