A new compact formulation for the daily crew pairing problem
| Autor: | Mohamed Haouari, Farah Zeghal Mansour, Hanif D. Sherali |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
050210 logistics & transportation
021103 operations research Operations research Computer science business.industry 05 social sciences 0211 other engineering and technologies Transportation 02 engineering and technology Variety (cybernetics) Set (abstract data type) Software compact formulation 0502 economics and business reformulation linearization technique (RLT) crew pairing Crew pairing business Civil and Structural Engineering |
| Popis: | 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. Scopus |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|