Simultaneous Vehicle and Crew Scheduling in Urban Mass Transit Systems

This paper presents an exact approach for solving the simultaneous vehicle and crew scheduling problem in urban mass transit systems. We consider the single depot case with a homogeneous fleet of vehicles. This approach relies on a set partitioning formulation for the driver scheduling problem that incorporates side constraints for the bus itineraries. The proposed solution approach consists of a column generation process (only for the crew schedules) integrated into a branch-and-cut scheme. The side constraints on buses guarantee that an optimal vehicle assignment can be derived afterwards in polynomial time. A computational study shows that this approach outperforms the previous methods found in the literature for a set of randomly generated instances. A heuristic version of the solution approach is also proposed and tested on larger instances.