# American Institute of Mathematical Sciences

July  2021, 17(4): 1809-1823. doi: 10.3934/jimo.2020047

## A note on optimization modelling of piecewise linear delay costing in the airline industry

 College of Science, Nanchang Institute of Technology, Nanchang, Jiangxi 330099, P.R. China

Received  February 2019 Revised  October 2019 Published  March 2020

Fund Project: The author was supported by Grant No. GJJ161113 (2017-2019) from the Education Department of Jiangxi Province, P.R. China

We present a mathematical model in an integer programming (I.P.) framework for non-linear delay costing in the airline industry. We prove the correctness of the model mathematically. Time is discretized into intervals of, for example, 15 minutes. We assume that the cost increases with increase in the number of intervals of delay in a piecewise linear manner. Computational results with data obtained from Sydney airport (Australia) show that the integer programming non-linear cost model runs much slower than the linear cost model; hence fast heuristics need to be developed to implement non-linear costing, which is more accurate than linear costing. We present a greedy heuristic that produces a solution only slightly worse than the ones produced by the I.P. models, but in much shorter time.

Citation: Prabhu Manyem. A note on optimization modelling of piecewise linear delay costing in the airline industry. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1809-1823. doi: 10.3934/jimo.2020047
##### References:
 [1] N. Boland, A. Ernst, C. Goh and A. Mees, Optimal two-commodity flows with non-linear cost functions, Journal of the Operational Research Society, 46 (1995), 1192-1207.   Google Scholar [2] L. Brunetta, G. Guastalla and L. Navazio, Solving the multi airport ground holding problem, Annals of Operations Research, 81 (1998), 271-287.  doi: 10.1023/A:1018909224543.  Google Scholar [3] A. Cook, G. Tanner, V. Williams and G. Meise, Dynamic cost indexing - Managing airline delay costs, Journal of Air Transport Management, 15 (2009), 26-35.  doi: 10.1016/j.jairtraman.2008.07.001.  Google Scholar [4] A. Cook and G. Tanner, European Airline Delay Cost Reference Values, Report from the University of Westminster UK, Eurocontrol, 2015. Google Scholar [5] A. Cook, G. Tanner and S. Anderson, Evaluating the True Cost to Airlines of One Minute of Airborne or Ground Delay: Final Report, Eurocontrol, 2004. Google Scholar [6] A. Cook, G. Tanner and A. Lawes, The Hidden cost of airline unpunctuality, Journal of Transport Economics and Policy, 46 (2012), 157-173.   Google Scholar [7] J. Ferguson, A. Q. Kara, K. Hoffman and L. Sherry, Estimating domestic US airline cost of delay based on European model, Transportation Research Part C: Emerging Technologies, 33 (2013), 311-323.  doi: 10.1016/j.trc.2011.10.003.  Google Scholar [8] J. A. Filar, P. Manyem, D. M. Panton and K. White, A model for adaptive rescheduling of flights in emergencies (MARFE), Journal of Industrial and Management Optimization, 3 (2007), 335-356.  doi: 10.3934/jimo.2007.3.335.  Google Scholar [9] J. A. Filar, P. Manyem, M. S. Visser and K. White, Air traffic management at Sydney with cancellations and curfew penalties, Optimization and Industry: New Frontiers, Appl. Optim., Kluwer Academic Publishers, 78 (2003), 113-140.  doi: 10.1007/978-1-4613-0233-9_5.  Google Scholar [10] W. Gao, X. Xu, L. Diao and H. Ding, Simmod based simulation optimization of flight delay cost for multi-airport system, 2008 International Conference on Intelligent Computation Technology and Automation (ICICTA), 1 (2008), 698-702.   Google Scholar [11] A. Gardi, R. Sabatini and S. Ramasamy, Multi-objective optimisation of aircraft flight trajectories in the atm and avionics context, Progress in Aerospace Sciences, 83 (2016), 1-36.  doi: 10.1016/j.paerosci.2015.11.006.  Google Scholar [12] S. Ketabi, Network optimization with piecewise linear convex costs, Iran. J. Sci. Technol. Trans. A Sci., 30 (2006), 315–323,379.  Google Scholar [13] P. Manyem, Disruption recovery at airports: Integer programming formulations and polynomial time algorithms, Discrete Applied Mathematics, 242 (2018), 102-117.  doi: 10.1016/j.dam.2017.11.010.  Google Scholar [14] A. Mukherjee, Dynamic Stochastic Optimization Models for Air Traffic Flow Management, PhD thesis, University of California at Berkeley, 2004. Google Scholar [15] L. Navazio and G. Romanin-Jacur, The Multiple Connections Multi Airport Ground Holding Problem: Models and Algorithms, Transportation Science, 32 (1998), 268-276.  doi: 10.1287/trsc.32.3.268.  Google Scholar [16] H. Zolfagharinia and M. Haughton, The importance of considering non-linear layover and delay costs for local truckers, Transportation Research Part E: Logistics and Transportation Review, 109 (2018), 331-355.  doi: 10.1016/j.tre.2017.10.007.  Google Scholar

show all references

##### References:
 [1] N. Boland, A. Ernst, C. Goh and A. Mees, Optimal two-commodity flows with non-linear cost functions, Journal of the Operational Research Society, 46 (1995), 1192-1207.   Google Scholar [2] L. Brunetta, G. Guastalla and L. Navazio, Solving the multi airport ground holding problem, Annals of Operations Research, 81 (1998), 271-287.  doi: 10.1023/A:1018909224543.  Google Scholar [3] A. Cook, G. Tanner, V. Williams and G. Meise, Dynamic cost indexing - Managing airline delay costs, Journal of Air Transport Management, 15 (2009), 26-35.  doi: 10.1016/j.jairtraman.2008.07.001.  Google Scholar [4] A. Cook and G. Tanner, European Airline Delay Cost Reference Values, Report from the University of Westminster UK, Eurocontrol, 2015. Google Scholar [5] A. Cook, G. Tanner and S. Anderson, Evaluating the True Cost to Airlines of One Minute of Airborne or Ground Delay: Final Report, Eurocontrol, 2004. Google Scholar [6] A. Cook, G. Tanner and A. Lawes, The Hidden cost of airline unpunctuality, Journal of Transport Economics and Policy, 46 (2012), 157-173.   Google Scholar [7] J. Ferguson, A. Q. Kara, K. Hoffman and L. Sherry, Estimating domestic US airline cost of delay based on European model, Transportation Research Part C: Emerging Technologies, 33 (2013), 311-323.  doi: 10.1016/j.trc.2011.10.003.  Google Scholar [8] J. A. Filar, P. Manyem, D. M. Panton and K. White, A model for adaptive rescheduling of flights in emergencies (MARFE), Journal of Industrial and Management Optimization, 3 (2007), 335-356.  doi: 10.3934/jimo.2007.3.335.  Google Scholar [9] J. A. Filar, P. Manyem, M. S. Visser and K. White, Air traffic management at Sydney with cancellations and curfew penalties, Optimization and Industry: New Frontiers, Appl. Optim., Kluwer Academic Publishers, 78 (2003), 113-140.  doi: 10.1007/978-1-4613-0233-9_5.  Google Scholar [10] W. Gao, X. Xu, L. Diao and H. Ding, Simmod based simulation optimization of flight delay cost for multi-airport system, 2008 International Conference on Intelligent Computation Technology and Automation (ICICTA), 1 (2008), 698-702.   Google Scholar [11] A. Gardi, R. Sabatini and S. Ramasamy, Multi-objective optimisation of aircraft flight trajectories in the atm and avionics context, Progress in Aerospace Sciences, 83 (2016), 1-36.  doi: 10.1016/j.paerosci.2015.11.006.  Google Scholar [12] S. Ketabi, Network optimization with piecewise linear convex costs, Iran. J. Sci. Technol. Trans. A Sci., 30 (2006), 315–323,379.  Google Scholar [13] P. Manyem, Disruption recovery at airports: Integer programming formulations and polynomial time algorithms, Discrete Applied Mathematics, 242 (2018), 102-117.  doi: 10.1016/j.dam.2017.11.010.  Google Scholar [14] A. Mukherjee, Dynamic Stochastic Optimization Models for Air Traffic Flow Management, PhD thesis, University of California at Berkeley, 2004. Google Scholar [15] L. Navazio and G. Romanin-Jacur, The Multiple Connections Multi Airport Ground Holding Problem: Models and Algorithms, Transportation Science, 32 (1998), 268-276.  doi: 10.1287/trsc.32.3.268.  Google Scholar [16] H. Zolfagharinia and M. Haughton, The importance of considering non-linear layover and delay costs for local truckers, Transportation Research Part E: Logistics and Transportation Review, 109 (2018), 331-355.  doi: 10.1016/j.tre.2017.10.007.  Google Scholar
$S$-shaped piecewise linear curve for Cost vs Delay; the curve is convex first and concave later
Delay ranges and corresponding costs. (The letters (A) to (F) identify the various columns.)
 Range(A) $\Delta_f$ range(B) Cost (C)coefficient Delay cost(D) 1 $0 \le \Delta_f \le d_{1,f}$ $c_{1,f}$ $c_{1,f}\Delta_f$ 2 $d_{1,f}< \Delta_f \le d_{2,f}$ $c_{2,f}$ $c_{1,f}d_{1,f} + c_{2,f}(\Delta_f - d_{1,f})$ 3 $\Delta_f> d_{2,f}$ $c_{3,f}$ $c_{1,f}d_{1,f} + c_{2,f}(d_{2,f} - d_{1,f})$+ $c_{3,f}(\Delta_f - d_{2,f})$ (A) $\delta$ values (E) Requirements (F) 1 $\delta_{1,f} = 1$ and $\delta_{2,f} = \delta_{3,f}$ = 0 $\mu_{2,f} = \mu_{3,f} = 0$ 2 $\delta_{1,f} = \delta_{2,f} = 1$ and $\delta_{3,f}$ = 0 $\mu_{2,f} = (\Delta_f - d_{1,f})$ and $\mu_{3,f} = 0$ 3 $\delta_{1,f} = \delta_{2,f} = \delta_{3,f}$ = 1 $\mu_{2,f} = (\Delta_f - d_{1,f})$ and $\mu_{3,f} = (\Delta_f - d_{2,f})$
 Range(A) $\Delta_f$ range(B) Cost (C)coefficient Delay cost(D) 1 $0 \le \Delta_f \le d_{1,f}$ $c_{1,f}$ $c_{1,f}\Delta_f$ 2 $d_{1,f}< \Delta_f \le d_{2,f}$ $c_{2,f}$ $c_{1,f}d_{1,f} + c_{2,f}(\Delta_f - d_{1,f})$ 3 $\Delta_f> d_{2,f}$ $c_{3,f}$ $c_{1,f}d_{1,f} + c_{2,f}(d_{2,f} - d_{1,f})$+ $c_{3,f}(\Delta_f - d_{2,f})$ (A) $\delta$ values (E) Requirements (F) 1 $\delta_{1,f} = 1$ and $\delta_{2,f} = \delta_{3,f}$ = 0 $\mu_{2,f} = \mu_{3,f} = 0$ 2 $\delta_{1,f} = \delta_{2,f} = 1$ and $\delta_{3,f}$ = 0 $\mu_{2,f} = (\Delta_f - d_{1,f})$ and $\mu_{3,f} = 0$ 3 $\delta_{1,f} = \delta_{2,f} = \delta_{3,f}$ = 1 $\mu_{2,f} = (\Delta_f - d_{1,f})$ and $\mu_{3,f} = (\Delta_f - d_{2,f})$
Parameters used in the testing of the non-linear cost model
 Number of flights 261 arrivals, 256 departures Max. delay allowed Eight periods (four hours) Perfect capacities 20 arrivals, 20 departures (per 30-minute interval) Time intervals 30 minutes each Cost break points $d_1$ = 2 units of delay, $d_2$ = 6 units of delay Cost coefficients $c_{1,f} = c_f$, $c_{2,f} = (1.5)c_f$ and $c_{3,f} = 0.5c_f$.($c_f$ is the coefficient in the single-range model)
 Number of flights 261 arrivals, 256 departures Max. delay allowed Eight periods (four hours) Perfect capacities 20 arrivals, 20 departures (per 30-minute interval) Time intervals 30 minutes each Cost break points $d_1$ = 2 units of delay, $d_2$ = 6 units of delay Cost coefficients $c_{1,f} = c_f$, $c_{2,f} = (1.5)c_f$ and $c_{3,f} = 0.5c_f$.($c_f$ is the coefficient in the single-range model)
Results of comparing single-range versus three-range cost model (Note. The "＄" used in Rows 7 and 8 refers to a generic monetary unit, not actual amount in US dollars or Australian dollars or any other currency.)
 Model $\to$ Single-range 3-range A 3-Range B 3-Range C (1) Solution how far from optimal ($A_{\rm{S}}$ value) 1.0 $\le$ 1.36 $\le$ 1.33 $\le$ 1.32 (2) Number of delayed flights 85 117 122 122 (3) Time taken to find solution 0.18 seconds 97 mins 6.5 hours 38 hours (4) Sum of the delays of all flights (periods) 518 518 518 518 (5) Average delay (periods) over all flights 1.002 1.002 1.002 1.002 (6) Average delay (periods) only over delayed flights 6.094 4.427 4.2459 4.2459 (7) Objective function value (＄) 32960 38975 37830 37830 (8) Optimal value of the Linear Programming relaxation (＄) 32960 7762
 Model $\to$ Single-range 3-range A 3-Range B 3-Range C (1) Solution how far from optimal ($A_{\rm{S}}$ value) 1.0 $\le$ 1.36 $\le$ 1.33 $\le$ 1.32 (2) Number of delayed flights 85 117 122 122 (3) Time taken to find solution 0.18 seconds 97 mins 6.5 hours 38 hours (4) Sum of the delays of all flights (periods) 518 518 518 518 (5) Average delay (periods) over all flights 1.002 1.002 1.002 1.002 (6) Average delay (periods) only over delayed flights 6.094 4.427 4.2459 4.2459 (7) Objective function value (＄) 32960 38975 37830 37830 (8) Optimal value of the Linear Programming relaxation (＄) 32960 7762
Results of comparing the Integer Programming solution and the Heuristic solution
 Model/Solver $\to$ 3-range C (from Table 4) Algorithm 1 (Pages 10-11) Number of delayed flights 122 121 Time taken to find solution 38 hours 60 seconds Sum of the delays of all flights (periods) 518 518 Ave. delay (periods) over all flights 1.002 1.002 Ave. delay (periods) only over delayed flights 4.246 4.281 Objective function value (＄) 37830 39660
 Model/Solver $\to$ 3-range C (from Table 4) Algorithm 1 (Pages 10-11) Number of delayed flights 122 121 Time taken to find solution 38 hours 60 seconds Sum of the delays of all flights (periods) 518 518 Ave. delay (periods) over all flights 1.002 1.002 Ave. delay (periods) only over delayed flights 4.246 4.281 Objective function value (＄) 37830 39660
Results of the Heuristic solution with 791 flights and flight connections
 Solver → Algorithm 1 (Pages 10-11) 1 Number of delayed flights 130 2 Time taken to find solution 35 seconds 3 Sum of the delays of all flights (periods) 690 4 Ave. delay (periods) over all flights 0.872 5 Ave. delay (periods) only over delayed flights 5.308
 Solver → Algorithm 1 (Pages 10-11) 1 Number of delayed flights 130 2 Time taken to find solution 35 seconds 3 Sum of the delays of all flights (periods) 690 4 Ave. delay (periods) over all flights 0.872 5 Ave. delay (periods) only over delayed flights 5.308
 [1] Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 [2] Ahmad El Hajj, Hassan Ibrahim, Vivian Rizik. $BV$ solution for a non-linear Hamilton-Jacobi system. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3273-3293. doi: 10.3934/dcds.2020405 [3] Ritu Agarwal, Kritika, Sunil Dutt Purohit, Devendra Kumar. Mathematical modelling of cytosolic calcium concentration distribution using non-local fractional operator. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021017 [4] Luigi Barletti, Giovanni Nastasi, Claudia Negulescu, Vittorio Romano. Mathematical modelling of charge transport in graphene heterojunctions. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2021010 [5] José Antonio Carrillo, Martin Parisot, Zuzanna Szymańska. Mathematical modelling of collagen fibres rearrangement during the tendon healing process. Kinetic & Related Models, 2021, 14 (2) : 283-301. doi: 10.3934/krm.2021005 [6] Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023 [7] Vladimir Gaitsgory, Ilya Shvartsman. Linear programming estimates for Cesàro and Abel limits of optimal values in optimal control problems. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021102 [8] Qing Liu, Bingo Wing-Kuen Ling, Qingyun Dai, Qing Miao, Caixia Liu. Optimal maximally decimated M-channel mirrored paraunitary linear phase FIR filter bank design via norm relaxed sequential quadratic programming. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1993-2011. doi: 10.3934/jimo.2020055 [9] Tadeusz Kaczorek, Andrzej Ruszewski. Analysis of the fractional descriptor discrete-time linear systems by the use of the shuffle algorithm. Journal of Computational Dynamics, 2021  doi: 10.3934/jcd.2021007 [10] Elimhan N. Mahmudov. Second order discrete time-varying and time-invariant linear continuous systems and Kalman type conditions. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021010 [11] Emma D'Aniello, Saber Elaydi. The structure of $\omega$-limit sets of asymptotically non-autonomous discrete dynamical systems. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 903-915. doi: 10.3934/dcdsb.2019195 [12] Fumihiko Nakamura. Asymptotic behavior of non-expanding piecewise linear maps in the presence of random noise. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2457-2473. doi: 10.3934/dcdsb.2018055 [13] Feng Luo. A combinatorial curvature flow for compact 3-manifolds with boundary. Electronic Research Announcements, 2005, 11: 12-20. [14] Yu-Hsien Liao. Solutions and characterizations under multicriteria management systems. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021041 [15] Andrea Tosin, Mattia Zanella. Uncertainty damping in kinetic traffic models by driver-assist controls. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021018 [16] Raimund Bürger, Christophe Chalons, Rafael Ordoñez, Luis Miguel Villada. A multiclass Lighthill-Whitham-Richards traffic model with a discontinuous velocity function. Networks & Heterogeneous Media, 2021, 16 (2) : 187-219. doi: 10.3934/nhm.2021004 [17] Mohammed Abdelghany, Amr B. Eltawil, Zakaria Yahia, Kazuhide Nakata. A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2051-2072. doi: 10.3934/jimo.2020058 [18] Baba Issa Camara, Houda Mokrani, Evans K. Afenya. Mathematical modeling of glioma therapy using oncolytic viruses. Mathematical Biosciences & Engineering, 2013, 10 (3) : 565-578. doi: 10.3934/mbe.2013.10.565 [19] Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Applications of mathematical analysis to problems in theoretical physics. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : i-i. doi: 10.3934/dcdss.2020446 [20] Hideaki Takagi. Extension of Littlewood's rule to the multi-period static revenue management model with standby customers. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2181-2202. doi: 10.3934/jimo.2020064

2019 Impact Factor: 1.366