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 relie s on a set partitioning formulation for the driver scheduling problem that incorporates side constraints for the bus itineraries. The proposed solutio n approach consists of a column generation process (only for the crew sched ules) integrated into a branch-and-bound scheme. The side constraints on bu ses guarantee that an optimal vehicle assignment can be derived afterwards in polynomial time. A computational study shows that this approach out-perf orms the previous methods found in the literature for a set of randomly gen erated instances. A heuristic version of the solution approach is also prop osed and tested on larger instances.