800. Enhancing Regularity in the Crew Pairing Problem
Invited abstract in session MD-23: OR for a Better Africa - OR@Africa 2, stream OR for Societal Development.
Monday, 14:30-16:00Room: Esther Simpson 3.01
Authors (first author is the speaker)
| 1. | Mohamed Faouzi Benammour
|
| GERAD, Polytechnique Montreal | |
| 2. | Frédéric Quesnel
|
| GERAD | |
| 3. | Francois Soumis
|
| GERAD |
Abstract
The Crew Pairing Problem (CPP) involves constructing feasible sequences of flights, connections, and rest periods for airline crew while minimizing operational costs and ensuring full flight coverage. However, beyond cost minimization, regularity has become a crucial objective for many airlines, as it enhances operational stability and reduces indirect costs associated with hotel accommodations, transportation logistics, and crew training. Traditional CPP optimization methods primarily focus on cost reduction but often fail to effectively incorporate regularity, as they lack a structured mechanism to balance both objectives.
This study proposes several approaches to enhance regularity in the CPP. The first is a bonus-based approach that identifies pairings with high repetition potential in the initial solution. The CPP is then re-solved using a branch-and-price algorithm to encourage the selection of these repeatable pairings. The second approach reoptimizes the initial solution by solving a MIP model that explicitly maximizes regularity. Finally, both approaches are applied sequentially to further enhance regularity while maintaining cost efficiency, forming a hybrid method.
Computational experiments conducted on datasets from a major Asian airline demonstrate the effectiveness of the proposed methods. The results show that they generate highly regular solutions with minimal cost deviations, ensuring practical applicability in airline crew pairing optimization.
Keywords
- Large Scale Optimization
- Column Generation
- Airline Applications
Status: accepted
Back to the list of papers