Crew Assignment with Duty Time Limits for Transport Services: Tight Multicommodity Models

Crew costs account for a significant portion of the operating expenses for transportation service providers, and so utilizing crews effectively is an important priority for these organizations. This paper addresses the core problem of assigning crews to urban transit and other scheduled transportation services at minimum total cost for crew usage, assignment, and transfers, taking into account crew work rules that limit their duty and working times. We propose a new multicommodity flow model with polynomial number of variables and constraints that is well suited to capture these work rules. This model can also readily incorporate additional desired features of crew assignments, such as balancing task assignments across crew members. It is more compact than previous flow-based and set partitioning models that have exponential constraints or variables. When work rules impose only duty time restrictions, our model is at least as tight as these previous models and can be strictly tighter than single-commodity models. We develop several classes of valid inequalities to further strengthen our model and discuss how to exploit any limits on working time to reduce model size and tighten the constraints. The model is easy to implement and apply, without requiring specialized decomposition procedures. To accelerate computational performance for large problems, we propose an effective optimization-based approach that entails first solving a restricted problem and then applying an optimality test to eliminate variables. We demonstrate the effectiveness of our modeling approach by applying it to several large-scale problem instances from the literature, solving most problems within a few minutes using a standard solver.