We study disruptions at a major airport. Disruptions could be caused by bad weather, for example. Our study is from the perspective of the airport, the air services provider (such as air traffic control) and the travelling public, rather than from the perspective of a single airline. Disruptions cause flights to be subjected to ground holding, or they cause the flights to violate airport curfew hours. We consider curfew and arrival capacities applicable at a single airport. After proving that the problem is NP-hard, we present a polynomial time approximation algorithm based on the primal–dual schema and show that if the problem is feasible, the algorithm finds a feasible solution that is both within a certain additive bound and within a certain multiplicative factor of the optimal solution. The algorithm returns a solution mix of which flights suffer no delay, which ones to be ground-held and which ones may violate the curfew (and hence pay a curfew penalty). Computational results are positive; our heuristic outperforms the integer programming solver by a wide margin.
Prabhu Manyem
. Disruption Recovery at Airports: Ground Holding, Curfew Restrictions and an Approximation Algorithm[J]. Journal of the Operations Research Society of China, 2021
, 9(4)
: 819
-852
.
DOI: 10.1007/s40305-020-00338-1
[1] Filar, J., Manyem, P., White, K.:How airlines and airports recover from schedule perturbations:a survey. Ann. Oper. Res. 108, 315-333(2001)
[2] Navazio, L., Romanin-Jacur, G.:The multiple connections multi airport ground holding problem:models and algorithms. Transp. Sci. 32(3), 268-276(1998)
[3] Filar, J., Manyem, P., Panton, D., White, K.:A model for adaptive rescheduling of flights in emergencies (MARFE). J. Ind. Manage. Optim. 3(2), 335-356(2007)
[4] Filar, J., Manyem, P., Visser, M., White, K.:Air Traffic Management at Sydney with Cancellations and Curfew Penalties. In:P. Pardalos, V. Korotkich (eds.) Optimization and Industry:New Frontiers, pp. 113-140. Kluwer Academic Publishers, Dordrecht (2003)
[5] M.Ball, Barnhart, C., G.Nemhauser, Odoni, A.:Air Transportation:Irregular Operations and Control. In:C.Barnhart,G.Laporte(eds.)HandbookinOperationsResearchandManagementScience,vol.14, pp. 1-73. Elsevier, Amsterdam (2007)
[6] Clausen, J., Larsen, A., Larsen, J., Rezanova, N.:Disruption management in the airline industry:Concepts, models and methods. Networks 37, 809-821(2010)
[7] Vossen, T.W., Hoffman, R., Mukherjee, A.:Air traffic flow management. In:Quantitative problem solving methods in the airline industry, pp. 385-453. Springer (2012)
[8] Manyem, P.:Disruption recovery at airports:integer programming formulations and polynomial time algorithms. Discrete Appl. Math. 242, 102-117(2018)
[9] Cook, A., Tanner, G., Lawes, A.:The hidden cost of airline unpunctuality. J. Trans. Econ. Policy 46(2), 157-173(2012)
[10] Manyem, P.:A note on optimization modelling of piecewise linear delay costing in the airline industry. J. Ind. Manage. Optim. (2020) https://doi.org/10.3934/jimo.2020047h
[11] Peterson, E.B., Neels, K., Barczi, N., Graham, T.:The economic cost of airline flight delay. J. Transp. Econ. Policy 47(1), 107-121(2013)
[12] Yuan, D.:Ground Holding Optimisation and Air Schedule Recovery. Ph.D. thesis, RMIT University (Australia) (2007)
[13] Gilbo, E., West, M.:Enhanced model for joint optimization of arrival and departure strategies and arrival/departure capacity utilization at congested airports. In:AIAA Modeling and Simulation Technologies (MST) Conference, p. 4599, Boston (2013)
[14] Gilbo,E.P.:Optimizingairportcapacityutilizationinairtrafficflowmanagementsubjecttoconstraints at arrival and departure fixes. IEEE Trans. Control Syst. Technol. 5(5), 490-503(1997)
[15] Ramanujam, V., Balakrishnan, H.:Estimation of arrival-departure capacity tradeoffs in multi-airport systems. In:Proceedings of the 48th IEEE Conference on Decision and Control 2009 held jointly with the 28th Chinese Control Conference. CDC/CCC 2009., pp. 2534-2540. IEEE (2009)
[16] Lenstra, J.K., Kan, A.R., Brucker, P.:Complexity of machine scheduling problems. Ann. Discrete Math. 1, 343-362(1977)
[17] Williamson, D.P., Shmoys, D.B.:The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2010)
[18] Vazirani, V.V.:Approximation Algorithms. Springer, Berlin (2001)
