A polyhedral approach to simplified crew scheduling and vehicle schedulingproblems

Crew and vehicle scheduling are fundamental issues in public transit manage ment. Informally, they can be described as the problem of determining the o ptimal duties for a set of crews (e.g., bus drivers) or vehicles (e.g., bus es) so as to cover a given set of timetabled trips, satisfying a number of constraints laid down by the union contract and company regulations. We con sider the simplified but still NP-hard case in which several depots are spe cified, and limits on both the total time between the start and the end of any duty (spread time) and the total duty operational time (working time) a re imposed. We give a 0-1 linear programming formulation based on binary va riables associated with trip transitions, which applies to both crew and ve hicle scheduling. The model is enhanced by means of new families of valid i nequalities, for which exact and heuristic separation procedures are propos ed. These techniques are embedded into an exact branch-and-cut algorithm, w hich also incorporates heuristic procedures. The performance of two impleme ntations of the method (for vehicle scheduling and crew scheduling, respect ively) are evaluated through computational testing on both random and real- world test problems from the literature.