Research map / Learning theory and algorithms / Combinatorial and search optimization
Check-In Desk Scheduling Optimisation at CDG International Airport
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a constraint programming model (with table constraints and a custom GatherAllDifferentExcept global) for assigning check-in desks to flights at CDG/Orly, deployed in preprod at Paris Airport.
Problem
Airport Check-in Desk Assignment Problem: assign consecutive, zone-compatible check-in desks to airline registrations under overlap rules, pre-assignments, exclusions, and reward maximization.
Approach
Models the check-in desk assignment as a constraint optimization problem using table constraints, AllDifferentExcept over overlapping registrations, and a single pragmatic GatherAllDifferentExcept global with a limited-filtering propagator, plus problem decomposition, solved by ACE via PyCSP3/XCSP3.
Key results
- Second version reduced total resolution time by 17% (best case) and 21% (worst case) over the first version on ORLY 1234 instances.
- Decomposition on ORLY 1234 yields a total bound of 45255160 with 262 unassigned flights, versus no decomposition giving 9+253 unassigned comparisons and a lower bound 43924300 with 298 unassigned flights.
- Static value ordering gave the best bounds in the no-decomposition setting (43,674,100 with 274 unassigned flights).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Gather AllDifferentExcept constraints (ablation) | CP check-in scheduling model · ORLY 124, 7 days | unassigned registrations: 281 -> 253 | Helped |
| Gather AllDifferentExcept constraints (ablation) | CP check-in scheduling model · ORLY 3, 7 days | unassigned registrations: 12 -> 9 | Helped |
| Use Static value ordering instead of Bivs + Static (ablation) | CP check-in scheduling model · ORLY 124, 7 days | unassigned registrations: 253 -> 243 | Helped |
| Use Static value ordering instead of Bivs + Static (ablation) | CP check-in scheduling model · ORLY 3, 7 days | unassigned registrations: 9 -> 3 | Helped |
| Use Static value ordering instead of Bivs + Static (ablation) | CP check-in scheduling model · ORLY 1234, no decomposition | unassigned registrations: 298 -> 274 | Helped |
| Use Bivs value ordering instead of Bivs + Static (ablation) | CP check-in scheduling model · ORLY 124, 7 days | objective reward: 23,795,100 -> 23,819,100 | No clear effect |
| Use Bivs value ordering instead of Bivs + Static (ablation) | CP check-in scheduling model · ORLY 3, 7 days | unassigned registrations: 9 -> 9 | No clear effect |
| Solve the instance by decomposition | CP check-in scheduling model · ORLY 1234 | unassigned registrations: 298 -> 262 | Helped |
| Solve the instance by decomposition | CP check-in scheduling model · ORLY 1234 | objective reward: 43,927,600 -> 45,255,160 | Helped |
Surprising findings
- Adding the GatherAllDifferentExcept global with limited filtering was necessary: the plain binary formulation was too slow to find acceptable bounds.
- Without decomposition, some configurations timed out, suggesting decomposition improves both bound and number of unassigned flights.
Limitations
- Python/PyCSP3 compilation time can become a bottleneck
- Direct comparison with the legacy tool is constrained by differing objective scales
- Only the ORLY instance results are reported in detail due to space
Experimental setup
Datasets: ADP Paris Airport real planning data (ORLY and CDG instances)
Benchmarks: ORLY 1234 real instance from Paris Airport
Metrics: solver resolution time objective bound (reward) number of unassigned registrations
Baselines: legacy commercial planning tool
Builds on: XCSP3 PyCSP3 AllDifferentExcept
Closest papers by meaning
- What Are the Rules? Discovering Constraints from Data (AAAI 2024 · similarity 0.78)
- Differentiable Combinatorial Scheduling at Scale (ICML 2024 · similarity 0.77)
- Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degrees (NeurIPS 2025 · similarity 0.77)
- Proactive and Reactive Constraint Programming for Stochastic Project Scheduling with Maximal Time-Lags (AAAI 2025 · similarity 0.77)
- Learning-Augmented Algorithms for the Bahncard Problem (NeurIPS 2024 · similarity 0.76)
- BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization (ICML 2025 · similarity 0.76)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.