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

Anantaram Balakrishnan (), Prakash Mirchandani () and Sifeng Lin ()
Additional contact information
Anantaram Balakrishnan: McCombs School of Business, The University of Texas at Austin, Austin, Texas 78712
Prakash Mirchandani: Katz Graduate School of Business, University of Pittsburgh, Pittsburgh, Pennsylvania 15260
Sifeng Lin: Cockrell School of Engineering, The University of Texas at Austin, Austin, Texas 78712

Operations Research, 2022, vol. 70, issue 2, 690-714

Abstract: 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.

Keywords: Transportation; urban transit; crew assignment; integer programming; strong formulations (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2155 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:2:p:690-714

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().