American Institute of Mathematical Sciences

Advanced
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

Prabhu Manyem

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

Received  February 2019 Revised  October 2019 Published  July 2021 Early access  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.

Keywords: Air traffic management, Non-linear delay costing, Mathematical modelling, Discrete (Combinatorial) optimization, Integer programming.
Mathematics Subject Classification: Primary: 90C10; Secondary: 90B06.
Citation: Prabhu Manyem. A note on optimization modelling of piecewise linear delay costing in the airline industry. Journal of Industrial and 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. 

[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.

[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.

[4]

A. Cook and G. Tanner, European Airline Delay Cost Reference Values, Report from the University of Westminster UK, Eurocontrol, 2015.

[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.

[6]

A. Cook, G. Tanner and A. Lawes, The Hidden cost of airline unpunctuality, Journal of Transport Economics and Policy, 46 (2012), 157-173. 

[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.

[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.

[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.

[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. 

[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.

[12]

S. Ketabi, Network optimization with piecewise linear convex costs, Iran. J. Sci. Technol. Trans. A Sci., 30 (2006), 315–323,379.

[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.

[14]

A. Mukherjee, Dynamic Stochastic Optimization Models for Air Traffic Flow Management, PhD thesis, University of California at Berkeley, 2004.

[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.

[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.

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. 

[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.

[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.

[4]

A. Cook and G. Tanner, European Airline Delay Cost Reference Values, Report from the University of Westminster UK, Eurocontrol, 2015.

[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.

[6]

A. Cook, G. Tanner and A. Lawes, The Hidden cost of airline unpunctuality, Journal of Transport Economics and Policy, 46 (2012), 157-173. 

[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.

[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.

[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.

[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. 

[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.

[12]

S. Ketabi, Network optimization with piecewise linear convex costs, Iran. J. Sci. Technol. Trans. A Sci., 30 (2006), 315–323,379.

[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.

[14]

A. Mukherjee, Dynamic Stochastic Optimization Models for Air Traffic Flow Management, PhD thesis, University of California at Berkeley, 2004.

[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.

[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.

Figure 1.  $ S $-shaped piecewise linear curve for Cost vs Delay; the curve is convex first and concave later
Figure Options

Download full-size image

Download as PowerPoint slide

Table 2.  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})$
Table Options

Download as excel

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})$
Table 3.  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)
Table Options

Download as excel

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)
Table 4.  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
Table Options

Download as excel

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
Table 5.  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
Table Options

Download as excel

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
Table 6.  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
Table Options

Download as excel

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]

A. Marigo, Benedetto Piccoli. Cooperative controls for air traffic management. Communications on Pure and Applied Analysis, 2003, 2 (3) : 355-369. doi: 10.3934/cpaa.2003.2.355
[2]

José M. Amigó, Isabelle Catto, Ángel Giménez, José Valero. Attractors for a non-linear parabolic equation modelling suspension flows. Discrete and Continuous Dynamical Systems - B, 2009, 11 (2) : 205-231. doi: 10.3934/dcdsb.2009.11.205
[3]

Edward S. Canepa, Alexandre M. Bayen, Christian G. Claudel. Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming. Networks and Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783
[4]

Dengfeng Sun, Issam S. Strub, Alexandre M. Bayen. Comparison of the performance of four Eulerian network flow models for strategic air traffic management. Networks and Heterogeneous Media, 2007, 2 (4) : 569-595. doi: 10.3934/nhm.2007.2.569
[5]

Simone Göttlich, Oliver Kolb, Sebastian Kühn. Optimization for a special class of traffic flow models: Combinatorial and continuous approaches. Networks and Heterogeneous Media, 2014, 9 (2) : 315-334. doi: 10.3934/nhm.2014.9.315
[6]

Michael Herty, S. Moutari, M. Rascle. Optimization criteria for modelling intersections of vehicular traffic flow. Networks and Heterogeneous Media, 2006, 1 (2) : 275-294. doi: 10.3934/nhm.2006.1.275
[7]

Niclas Bernhoff. On half-space problems for the weakly non-linear discrete Boltzmann equation. Kinetic and Related Models, 2010, 3 (2) : 195-222. doi: 10.3934/krm.2010.3.195
[8]

Byungik Kahng, Miguel Mendes. The characterization of maximal invariant sets of non-linear discrete-time control dynamical systems. Conference Publications, 2013, 2013 (special) : 393-406. doi: 10.3934/proc.2013.2013.393
[9]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[10]

Akhlad Iqbal, Praveen Kumar. Geodesic $ \mathcal{E} $-prequasi-invex function and its applications to non-linear programming problems. Numerical Algebra, Control and Optimization, 2021  doi: 10.3934/naco.2021040
[11]

Kurt Falk, Marc Kesseböhmer, Tobias Henrik Oertel-Jäger, Jens D. M. Rademacher, Tony Samuel. Preface: Diffusion on fractals and non-linear dynamics. Discrete and Continuous Dynamical Systems - S, 2017, 10 (2) : i-iv. doi: 10.3934/dcdss.201702i
[12]

Dmitry Dolgopyat. Bouncing balls in non-linear potentials. Discrete and Continuous Dynamical Systems, 2008, 22 (1&2) : 165-182. doi: 10.3934/dcds.2008.22.165
[13]

Dorin Ervin Dutkay and Palle E. T. Jorgensen. Wavelet constructions in non-linear dynamics. Electronic Research Announcements, 2005, 11: 21-33.

[14]

Armin Lechleiter. Explicit characterization of the support of non-linear inclusions. Inverse Problems and Imaging, 2011, 5 (3) : 675-694. doi: 10.3934/ipi.2011.5.675
[15]

Denis Serre. Non-linear electromagnetism and special relativity. Discrete and Continuous Dynamical Systems, 2009, 23 (1&2) : 435-454. doi: 10.3934/dcds.2009.23.435
[16]

Feng-Yu Wang. Exponential convergence of non-linear monotone SPDEs. Discrete and Continuous Dynamical Systems, 2015, 35 (11) : 5239-5253. doi: 10.3934/dcds.2015.35.5239
[17]

Anugu Sumith Reddy, Amit Apte. Stability of non-linear filter for deterministic dynamics. Foundations of Data Science, 2021, 3 (3) : 647-675. doi: 10.3934/fods.2021025
[18]

Ahmad El Hajj, Aya Oussaily. Continuous solution for a non-linear eikonal system. Communications on Pure and Applied Analysis, 2021, 20 (11) : 3795-3823. doi: 10.3934/cpaa.2021131
[19]

Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557
[20]

Tommi Brander, Joonas Ilmavirta, Manas Kar. Superconductive and insulating inclusions for linear and non-linear conductivity equations. Inverse Problems and Imaging, 2018, 12 (1) : 91-123. doi: 10.3934/ipi.2018004

2021 Impact Factor: 1.411

Tools

Metrics

  • PDF downloads (310)
  • HTML views (749)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy