A New Compact Formulation for the Daily Crew Pairing Problem

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, the authors present a novel compact polynomial-sized nonlinear formulation for the DCPP, which is then linearized and lifted using the reformulation-linearization technique (RLT). Moreover, the authors 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.

  • Record URL:
  • Availability:
  • Supplemental Notes:
    • Abstracts reprinted with permission of INFORMS (Institute for Operations Research and the Management Sciences, http://www.informs.org).
  • Authors:
    • Haouari, Mohamed
    • Mansour, Farah Zeghal
    • Sherali, Hanif D
  • Publication Date: 2019-5


  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01714943
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Jun 17 2019 3:36PM