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.
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
AllDifferentExceptconstraint 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.
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