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.

Boschetti, M., Mingozzi, A., Ricciardelli, S. (2004). An exact algorithm for the simplified multiple depot crew scheduling problem. ANNALS OF OPERATIONS RESEARCH, 127, 177-201 [10.1023/B:ANOR.0000019089.86834.91].

An exact algorithm for the simplified multiple depot crew scheduling problem

RICCIARDELLI, SALVATORE
2004-01-01

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.
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore MAT/09 - Ricerca Operativa
English
Con Impact Factor ISI
dual heuristics; set partitioning; personal scheduling
Boschetti, M., Mingozzi, A., Ricciardelli, S. (2004). An exact algorithm for the simplified multiple depot crew scheduling problem. ANNALS OF OPERATIONS RESEARCH, 127, 177-201 [10.1023/B:ANOR.0000019089.86834.91].
Boschetti, M; Mingozzi, A; Ricciardelli, S
Articolo su rivista
File in questo prodotto:
Non ci sono file associati a questo prodotto.

Questo articolo è pubblicato sotto una Licenza Licenza Creative Commons Creative Commons

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/35727
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 14
social impact