
-
Previous Article
The viability of switched nonlinear systems with piecewise smooth Lyapunov functions
- JIMO Home
- This Issue
-
Next Article
Network data envelopment analysis with fuzzy non-discretionary factors
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 |
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.
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. |

Range (A) |
(B) |
Cost (C) coefficient |
Delay cost (D) |
1 | |||
2 | |||
3 | + |
||
(A) | Requirements (F) | ||
1 | |||
2 | |||
3 |
Range (A) |
(B) |
Cost (C) coefficient |
Delay cost (D) |
1 | |||
2 | |||
3 | + |
||
(A) | Requirements (F) | ||
1 | |||
2 | |||
3 |
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 | |
Cost coefficients | ( |
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 | |
Cost coefficients | ( |
Model |
Single-range | 3-range A | 3-Range B | 3-Range C |
(1) Solution how far from optimal ( |
1.0 | |||
(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 |
Single-range | 3-range A | 3-Range B | 3-Range C |
(1) Solution how far from optimal ( |
1.0 | |||
(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/Solver |
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 |
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 |
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] |
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
Other articles
by authors
[Back to Top]