An exact algorithm for the simplified multiple depot crew scheduling problem

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.