Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

Solving the Time-Discrete Winter Runway Scheduling Problem: A Column Generation and Constraint Programming Approach

Abstract : We address the runway scheduling problem under consideration of winter operations. During snowfall, runways have to be temporarily closed in order to clear them from snow, ice and slush. We propose an integrated optimization model to simultaneously plan snow removal for multiple runways and to assign runways and takeoff and landing times to aircraft. For this winter runway scheduling problem, we present a time-discrete binary model formulation using clique inequalities and an equivalent constraint programming model. To solve the winter runway scheduling problem optimally, we propose an exact solution methodology. Our start heuristic based on constraint programming generates a feasible initial start solution. We use a column generation scheme, which we initialize with a heuristic solution, to identify all variables of the binary program which are required to solve it optimally. Finally, we apply a branch-and-bound procedure to our resulting binary program. Additionally, we present an enhanced time discretization method to balance model size and solution quality. We apply our algorithm to realistic instances from a large international airport. An analysis of resulting model sizes proves the ability of our approach to significantly reduce the number of required variables and constraints of the time-discrete binary program. We also show that our method computes optimal schedules in a short amount of time and often outperforms a time-continuous formulation as well as a pure constraint programming approach.
Document type :
Journal articles
Complete list of metadata

https://hal.laas.fr/hal-03344421
Contributor : Christian Artigues Connect in order to contact the contributor
Submitted on : Wednesday, September 15, 2021 - 8:51:29 AM
Last modification on : Monday, July 4, 2022 - 8:42:16 AM
Long-term archiving on: : Thursday, December 16, 2021 - 6:12:24 PM

File

RSP_Winter_Time_Discrete_v53.p...
Files produced by the author(s)

Identifiers

Citation

Maximilian Pohl, Christian Artigues, Rainer Kolisch. Solving the Time-Discrete Winter Runway Scheduling Problem: A Column Generation and Constraint Programming Approach. European Journal of Operational Research, Elsevier, 2022, 299 (2), pp.674-689. ⟨10.1016/j.ejor.2021.08.028⟩. ⟨hal-03344421⟩

Share

Metrics

Record views

33

Files downloads

2