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...
| Main Authors: | , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/142233 |
| _version_ | 1811688648329920512 |
|---|---|
| author | Liang, Zhe Xiao, Fan Qian, Xiongwen Zhou, Lei Jin, Xianfei Lu, Xuehua Karichery, Sureshan |
| 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 |
| author_sort | Liang, Zhe |
| collection | NTU |
| 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. |
| first_indexed | 2024-10-01T05:35:33Z |
| format | Journal Article |
| id | ntu-10356/142233 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T05:35:33Z |
| publishDate | 2020 |
| record_format | dspace |
| spelling | ntu-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. |
| 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 |
| title | 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_short | 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 |
| topic | Engineering::Mechanical engineering Aircraft Recovery Problem Disruptions Management |
| url | https://hdl.handle.net/10356/142233 |
| work_keys_str_mv | AT liangzhe acolumngenerationbasedheuristicforaircraftrecoveryproblemwithairportcapacityconstraintsandmaintenanceflexibility AT xiaofan acolumngenerationbasedheuristicforaircraftrecoveryproblemwithairportcapacityconstraintsandmaintenanceflexibility AT qianxiongwen acolumngenerationbasedheuristicforaircraftrecoveryproblemwithairportcapacityconstraintsandmaintenanceflexibility AT zhoulei acolumngenerationbasedheuristicforaircraftrecoveryproblemwithairportcapacityconstraintsandmaintenanceflexibility AT jinxianfei acolumngenerationbasedheuristicforaircraftrecoveryproblemwithairportcapacityconstraintsandmaintenanceflexibility AT luxuehua acolumngenerationbasedheuristicforaircraftrecoveryproblemwithairportcapacityconstraintsandmaintenanceflexibility AT karicherysureshan acolumngenerationbasedheuristicforaircraftrecoveryproblemwithairportcapacityconstraintsandmaintenanceflexibility AT liangzhe columngenerationbasedheuristicforaircraftrecoveryproblemwithairportcapacityconstraintsandmaintenanceflexibility AT xiaofan columngenerationbasedheuristicforaircraftrecoveryproblemwithairportcapacityconstraintsandmaintenanceflexibility AT qianxiongwen columngenerationbasedheuristicforaircraftrecoveryproblemwithairportcapacityconstraintsandmaintenanceflexibility AT zhoulei columngenerationbasedheuristicforaircraftrecoveryproblemwithairportcapacityconstraintsandmaintenanceflexibility AT jinxianfei columngenerationbasedheuristicforaircraftrecoveryproblemwithairportcapacityconstraintsandmaintenanceflexibility AT luxuehua columngenerationbasedheuristicforaircraftrecoveryproblemwithairportcapacityconstraintsandmaintenanceflexibility AT karicherysureshan columngenerationbasedheuristicforaircraftrecoveryproblemwithairportcapacityconstraintsandmaintenanceflexibility |