A new compact formulation for the daily crew pairing problem

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.