# American Institute of Mathematical Sciences

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, doi: 10.3934/jimo.2020047
##### References:

show all references

##### References:
$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] Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102 [2] Denis Serre. Non-linear electromagnetism and special relativity. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 435-454. doi: 10.3934/dcds.2009.23.435 [3] Noufel Frikha, Valentin Konakov, Stéphane Menozzi. Well-posedness of some non-linear stable driven SDEs. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 849-898. doi: 10.3934/dcds.2020302 [4] Ahmad El Hajj, Hassan Ibrahim, Vivian Rizik. $BV$ solution for a non-linear Hamilton-Jacobi system. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020405 [5] David W. K. Yeung, Yingxuan Zhang, Hongtao Bai, Sardar M. N. Islam. Collaborative environmental management for transboundary air pollution problems: A differential levies game. Journal of Industrial & Management Optimization, 2021, 17 (2) : 517-531. doi: 10.3934/jimo.2019121 [6] Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2021001 [7] Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021013 [8] Guihong Fan, Gail S. K. Wolkowicz. Chaotic dynamics in a simple predator-prey model with discrete delay. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 191-216. doi: 10.3934/dcdsb.2020263 [9] Ting Liu, Guo-Bao Zhang. Global stability of traveling waves for a spatially discrete diffusion system with time delay. Electronic Research Archive, , () : -. doi: 10.3934/era.2021003 [10] Ali Mahmoodirad, Harish Garg, Sadegh Niroomand. Solving fuzzy linear fractional set covering problem by a goal programming based solution approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020162 [11] Sabine Hittmeir, Laura Kanzler, Angelika Manhart, Christian Schmeiser. Kinetic modelling of colonies of myxobacteria. Kinetic & Related Models, 2021, 14 (1) : 1-24. doi: 10.3934/krm.2020046 [12] Thazin Aye, Guanyu Shang, Ying Su. On a stage-structured population model in discrete periodic habitat: III. unimodal growth and delay effect. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2021005 [13] Zhongbao Zhou, Yanfei Bai, Helu Xiao, Xu Chen. A non-zero-sum reinsurance-investment game with delay and asymmetric information. Journal of Industrial & Management Optimization, 2021, 17 (2) : 909-936. doi: 10.3934/jimo.2020004 [14] Qiang Long, Xue Wu, Changzhi Wu. Non-dominated sorting methods for multi-objective optimization: Review and numerical comparison. Journal of Industrial & Management Optimization, 2021, 17 (2) : 1001-1023. doi: 10.3934/jimo.2020009 [15] Xiaoxiao Li, Yingjing Shi, Rui Li, Shida Cao. Energy management method for an unpowered landing. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020180 [16] Jian-Xin Guo, Xing-Long Qu. Robust control in green production management. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021011 [17] Shipra Singh, Aviv Gibali, Xiaolong Qin. Cooperation in traffic network problems via evolutionary split variational inequalities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020170 [18] Caterina Balzotti, Simone Göttlich. A two-dimensional multi-class traffic flow model. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020034 [19] 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  doi: 10.3934/nhm.2021004 [20] Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251

2019 Impact Factor: 1.366

## Tools

Article outline

Figures and Tables