A New Compact Formulation for the Daily Crew Pairing Problem

Mohamed Haouari (), Farah Zeghal Mansour () and Hanif D. Sherali ()
Additional contact information
Mohamed Haouari: Department of Mechanical and Industrial Engineering, College of Engineering, Qatar University, Doha, State of Qatar
Farah Zeghal Mansour: Optimisation et Analyse des Systèmes Industriels et de Service, Ecole Nationale d‘Ingénieurs de Tunis, Université de Tunis El Manar, 1002 Tunis, Tunisia
Hanif D. Sherali: Grado Department of Industrial and Systems Engineering, Virginia Tech, Blacksburg, Virginia 24061

Transportation Science, 2019, vol. 53, issue 3, 811-828

Abstract: The daily crew pairing problem (DCPP) seeks to generate a set of minimal-cost pairings that covers all the planned daily flights while complying with a variety of labor regulations, safety rules, and policies of the airline. The DCPP is a highly complex and large-scale optimization problem that is often modeled using a set-partitioning formulation and then solved via advanced optimization techniques (i.e., specialized column generation or branch-and-price algorithms). To complement this approach, we present a novel compact polynomial-sized nonlinear formulation for the DCPP, which is then linearized and lifted using the reformulation-linearization technique (RLT). Moreover, we propose two enhancement strategies to further improve the computational performance of the proposed formulation. The experimental results show that the compact formulation can be solved efficiently by commercial software without complicated algorithmic implementations, thus facilitating its use in the airline industry.

Keywords: crew pairing; compact formulation; reformulation linearization technique (RLT) (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
https://doi.org/10.1287/trsc.2018.0860 (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:ortrsc:v:53:y:2019:i:3:p:811-828

Access Statistics for this article

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