TY - JOUR
T1 - Metaheuristics for efficient aircraft scheduling and re-routing at busy terminal control areas
AU - Samà, Marcella
AU - D'Ariano, Andrea
AU - Corman, Francesco
AU - Pacciarelli, Dario
PY - 2017
Y1 - 2017
N2 - Intelligent decision support systems for the real-time management of landing and take-off operations can be very effective in helping air traffic controllers to limit airport congestion at busy terminal control areas. The key optimization problem to be solved regards the assignment of airport resources to take-off and landing aircraft and the aircraft sequencing on them. The problem can be formulated as a mixed integer linear program. However, since this problem is strongly NP-hard, heuristic algorithms are typically adopted in practice to compute good quality solutions in a short computation time. This paper presents a number of algorithmic improvements implemented in the AGLIBRARY solver (a state-of-the-art optimization solver to deal with complex routing and scheduling problems) in order to improve the possibility of finding good quality solutions quickly. The proposed framework starts from a good initial solution for the aircraft scheduling problem with fixed routes (given the resources to be traversed by each aircraft), computed via a truncated branch-and-bound algorithm. A metaheuristic is then applied to improve the solution by re-routing some aircraft in the terminal control area. New metaheuristics, based on variable neighbourhood search, tabu search and hybrid schemes, are introduced. Computational experiments are performed on an Italian terminal control area under various types of disturbances, including multiple aircraft delays and a temporarily disrupted runway. The metaheuristics achieve solutions of remarkable quality, within a small computation time, compared with a commercial solver and with the previous versions of AGLIBRARY.
AB - Intelligent decision support systems for the real-time management of landing and take-off operations can be very effective in helping air traffic controllers to limit airport congestion at busy terminal control areas. The key optimization problem to be solved regards the assignment of airport resources to take-off and landing aircraft and the aircraft sequencing on them. The problem can be formulated as a mixed integer linear program. However, since this problem is strongly NP-hard, heuristic algorithms are typically adopted in practice to compute good quality solutions in a short computation time. This paper presents a number of algorithmic improvements implemented in the AGLIBRARY solver (a state-of-the-art optimization solver to deal with complex routing and scheduling problems) in order to improve the possibility of finding good quality solutions quickly. The proposed framework starts from a good initial solution for the aircraft scheduling problem with fixed routes (given the resources to be traversed by each aircraft), computed via a truncated branch-and-bound algorithm. A metaheuristic is then applied to improve the solution by re-routing some aircraft in the terminal control area. New metaheuristics, based on variable neighbourhood search, tabu search and hybrid schemes, are introduced. Computational experiments are performed on an Italian terminal control area under various types of disturbances, including multiple aircraft delays and a temporarily disrupted runway. The metaheuristics achieve solutions of remarkable quality, within a small computation time, compared with a commercial solver and with the previous versions of AGLIBRARY.
KW - Disjunctive programming
KW - Disruption management
KW - Hybrid algorithms
KW - Landing and take-off operations
KW - Optimal air traffic control
KW - Tabu search
KW - Variable neighbourhood search
UR - http://www.scopus.com/inward/record.url?scp=84988523511&partnerID=8YFLogxK
U2 - 10.1016/j.trc.2016.08.012
DO - 10.1016/j.trc.2016.08.012
M3 - Article
AN - SCOPUS:84988523511
SN - 0968-090X
VL - 80
SP - 485
EP - 511
JO - Transportation Research. Part C: Emerging Technologies
JF - Transportation Research. Part C: Emerging Technologies
ER -