A column generation-based heuristic for aircraft recovery problem with airport capacity constraints and maintenance flexibility

We consider the aircraft recovery problem (ARP) with airport capacity constraints and maintenance flexibility. The problem is to re-schedule flights and re-assign aircraft in real time with minimized recovery cost for airlines after disruptions occur. In most published studies, airport capacity and...

Full description

Saved in:
Bibliographic Details
Main Authors: Liang, Zhe, Xiao, Fan, Qian, Xiongwen, Zhou, Lei, Jin, Xianfei, Lu, Xuehua, Karichery, Sureshan
Other Authors: School of Mechanical and Aerospace Engineering
Format: Article
Language:English
Published: 2020
Subjects:
Online Access:https://hdl.handle.net/10356/142233
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-142233
record_format dspace
spelling sg-ntu-dr.10356-1422332020-06-17T08:29:54Z A column generation-based heuristic for aircraft recovery problem with airport capacity constraints and maintenance flexibility Liang, Zhe Xiao, Fan Qian, Xiongwen Zhou, Lei Jin, Xianfei Lu, Xuehua Karichery, Sureshan School of Mechanical and Aerospace Engineering Engineering::Mechanical engineering Aircraft Recovery Problem Disruptions Management We consider the aircraft recovery problem (ARP) with airport capacity constraints and maintenance flexibility. The problem is to re-schedule flights and re-assign aircraft in real time with minimized recovery cost for airlines after disruptions occur. In most published studies, airport capacity and flexible maintenance are not considered simultaneously via an optimization approach. To bridge this gap, we propose a column generation heuristic to solve the problem. The framework consists of a master problem for selecting routes for aircraft and subproblems for generating routes. Airport capacity is explicitly considered in the master problem and swappable planned maintenances can be incorporated in the subproblem. Instead of discrete delay models which are widely adopted in much of the existing literature, in this work flight delays are continuous and optimized accurately in the subproblems. The continuous-delay model can improve the accuracy of the optimized recovery cost by up to 37.74%. The computational study based on real-world problems shows that the master problem gives very tight linear relaxation with small, often zero, optimality gaps. Large-scale problems can be solved within 6 min and the run time can be further shortened by parallelizing subproblems on more powerful hardware. In addition, from a managerial point of view, computational experiments reveal that swapping planned maintenances may bring a considerable reduction in recovery cost by about 20% and 60%, depending on specific problem instances. Furthermore, the decreasing marginal value of airport slot quota is found by computational experiments. 2020-06-17T08:29:54Z 2020-06-17T08:29:54Z 2018 Journal Article Liang, Z., Xiao, F., Qian, X., Zhou, L., Jin, X., Lu, X., & Karichery, S. (2018). A column generation-based heuristic for aircraft recovery problem with airport capacity constraints and maintenance flexibility. Transportation Research Part B: Methodological, 113, 70-90. doi:10.1016/j.trb.2018.05.007 0191-2615 https://hdl.handle.net/10356/142233 10.1016/j.trb.2018.05.007 2-s2.0-85047617312 113 70 90 en Transportation Research Part B: Methodological © 2018 Elsevier Ltd. All rights reserved.
institution Nanyang Technological University
building NTU Library
country Singapore
collection DR-NTU
language English
topic Engineering::Mechanical engineering
Aircraft Recovery Problem
Disruptions Management
spellingShingle Engineering::Mechanical engineering
Aircraft Recovery Problem
Disruptions Management
Liang, Zhe
Xiao, Fan
Qian, Xiongwen
Zhou, Lei
Jin, Xianfei
Lu, Xuehua
Karichery, Sureshan
A column generation-based heuristic for aircraft recovery problem with airport capacity constraints and maintenance flexibility
description We consider the aircraft recovery problem (ARP) with airport capacity constraints and maintenance flexibility. The problem is to re-schedule flights and re-assign aircraft in real time with minimized recovery cost for airlines after disruptions occur. In most published studies, airport capacity and flexible maintenance are not considered simultaneously via an optimization approach. To bridge this gap, we propose a column generation heuristic to solve the problem. The framework consists of a master problem for selecting routes for aircraft and subproblems for generating routes. Airport capacity is explicitly considered in the master problem and swappable planned maintenances can be incorporated in the subproblem. Instead of discrete delay models which are widely adopted in much of the existing literature, in this work flight delays are continuous and optimized accurately in the subproblems. The continuous-delay model can improve the accuracy of the optimized recovery cost by up to 37.74%. The computational study based on real-world problems shows that the master problem gives very tight linear relaxation with small, often zero, optimality gaps. Large-scale problems can be solved within 6 min and the run time can be further shortened by parallelizing subproblems on more powerful hardware. In addition, from a managerial point of view, computational experiments reveal that swapping planned maintenances may bring a considerable reduction in recovery cost by about 20% and 60%, depending on specific problem instances. Furthermore, the decreasing marginal value of airport slot quota is found by computational experiments.
author2 School of Mechanical and Aerospace Engineering
author_facet School of Mechanical and Aerospace Engineering
Liang, Zhe
Xiao, Fan
Qian, Xiongwen
Zhou, Lei
Jin, Xianfei
Lu, Xuehua
Karichery, Sureshan
format Article
author Liang, Zhe
Xiao, Fan
Qian, Xiongwen
Zhou, Lei
Jin, Xianfei
Lu, Xuehua
Karichery, Sureshan
author_sort Liang, Zhe
title A column generation-based heuristic for aircraft recovery problem with airport capacity constraints and maintenance flexibility
title_short A column generation-based heuristic for aircraft recovery problem with airport capacity constraints and maintenance flexibility
title_full A column generation-based heuristic for aircraft recovery problem with airport capacity constraints and maintenance flexibility
title_fullStr A column generation-based heuristic for aircraft recovery problem with airport capacity constraints and maintenance flexibility
title_full_unstemmed A column generation-based heuristic for aircraft recovery problem with airport capacity constraints and maintenance flexibility
title_sort column generation-based heuristic for aircraft recovery problem with airport capacity constraints and maintenance flexibility
publishDate 2020
url https://hdl.handle.net/10356/142233
_version_ 1681057911352066048