Check-In Desk Scheduling Optimisation at CDG International Airport

Thibault Falque, Gilles Audemard, Christophe Lecoutre, Bertrand MazureAAAI 2024 · DOI

Abstract

This paper presents a Constraint Programming (CP) framework designed to automate and optimize the Airport Check-In Desk Assignment Problem (ACIDAP) at Paris’s Charles de Gaulle (CDG) and Orly airports. By transitioning from legacy commercial software to an open-source toolchain utilizing PyCSP3 and the ACE solver, the proposed system achieves a significant reduction in computation time while enhancing scheduling quality. Real-world deployment at Paris airports demonstrates the practical efficacy of this approach.

Introduction

Managing a major international hub like CDG involves solving the complex Airport Check-In Desk Assignment Problem (ACIDAP). With over 1,400 daily flight movements, operators must assign flights to physical desk banks while adhering to stringent operational constraints. These include physical requirements (consecutive desks in specific zones), temporal overlaps (shared desks for specific airline groups), and maintenance availability. The primary objective is to maximize airline preferences (rewards) while ensuring all flights are serviced within operational rules.

Methodology

The researchers employed Constraint Programming (CP) to model the ACIDAP, leveraging its suitability for complex, heterogeneous rules.

System Architecture and Toolchain

The system utilizes a Python-based modeling library, PyCSP3, to describe the problem mathematically. These models are compiled into the XCSP3 format and solved using the ACE solver. The integration of these components allows for a flexible and customizable scheduling engine.

System architecture and task execution sequence diagram showing the interaction between PyCSP3 and the ACE solver.

Technical Innovations

  • Fictive Bank Modeling: To handle gaps in schedules or unassigned tasks, a "fictive bank" ($f$) with zero reward was introduced. This allows the use of standard consecutive constraints across non-contiguous physical zones.
  • Specialized Propagators: The implementation of the AllDifferentExcept constraint significantly reduced the complexity of the model by optimizing how the solver handles unique desk assignments versus the fictive bank.
  • Decomposition Strategies: To manage large-scale weekly schedules, the problem was decomposed into smaller sub-problems (e.g., by terminal or by day). This approach allowed the solver to explore search spaces more effectively within a 30-second timeout.

Datasets and Experimental Setup

The study utilized real-world operational data provided by Aéroports de Paris (ADP). The instances vary in scale and complexity, ranging from terminal-specific tasks to massive airport-wide schedules.

Summary of airport instances used for testing, including task counts and strategy rules for ORLY and CDG.

Testing involved three scenario variants: $\Phi_1$ (no overlaps), $\Phi_2$ (overlaps allowed), and $\Phi_3$ (overlaps with a limited number of tasks).

Results and Discussion

The transition to an open-source CP toolchain yielded several key insights:

  • Performance Gains: Optimizing the communication pipeline between Python and the solver reduced total resolution time by 17% to 21%.
  • Quality through Decomposition: Breaking the global problem into daily or terminal-specific sub-problems improved solution quality. Smaller search spaces allowed for deeper exploration, resulting in higher rewards and fewer unassigned flights compared to global solving.
  • Operational Viability: The system has been validated through over a year of parallel operation with legacy systems in a pre-production environment at Paris Airport.

Conclusion

The proposed CP framework offers a robust, cost-effective alternative to proprietary scheduling software. While the current bottleneck remains the compilation overhead between PyCSP3 and the ACE solver, future work will focus on developing more direct APIs to further reduce latency. The successful deployment at CDG and Orly demonstrates the power of specialized CP propagators and decomposition strategies in solving large-scale industrial scheduling problems.

Summary updated

BibTeX
@inproceedings{falque2024check,
  author = {Thibault Falque and Gilles Audemard and Christophe Lecoutre and Bertrand Mazure},
  title = {{Check-In Desk Scheduling Optimisation at CDG International Airport}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i21.30308},
}
Figure