<figure><img src="image_1.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# An ant colony optimization with turn-around-time reduction mechanism for the robust aircraft maintenance routing problem

Abdelrahman E. E. Eltoukhy[0000-0001-5714-3641]

Department of Industrial and Systems Engineering, The Hong Kong Polytechnic University, Hung Hum, Hong Kong
abdelrahman.eltoukhy@polyu.edu.hk

Noha Mostafa[0000-0002-6410-3848]

Mechanical Engineering Department, Faculty of Engineering, The British University in Egypt,
11837, Shorouk, Egypt
noha.mostafa@bue.edu.eg

Industrial Engineering Department, Faculty of Engineering, Zagazig University, 44519, Zagazig, Egypt
namostafa@eng.zu.edu.eg

**Abstract.** The robust aircraft maintenance routing problem (RAMRP) is adopted by airlines to determine aircraft routes with better withstanding for possible disruptions. This can be achieved using a common approach called the buffer time insertion approach (BT). From the literature, it was observed that this approach has a pitfall of reducing the fleet productivity while inserting long buffer times. Besides, it cannot accommodate flight delays while inserting short buffer times. These disadvantages were the motivation to conduct this study to propose a RAMRP solution that incorporates a novel robustness approach, called turn-around-time reduction (TR), in which all the previous drawbacks are avoided. An ant colony-based algorithm (AC) was developed to solve the proposed RAMRP. To demonstrate the viability and effectiveness of the proposed approach, experiments are conducted based on real data obtained from a major airline company located in the Middle East. The results show that the proposed TR outperforms the existing BT in terms of fleet productivity and delay accommodation.

**Keywords:** Aircraft Maintenance Routing Problem, Airline Operations, Robustness, Ant Colony Optimization

## 1 Introduction

The aircraft maintenance routing problem (AMRP) is essential for airlines because it constructs the aircraft routes and schedules the aircraft maintenance visits. The AMRP has been addressed in the literature through three different variants: tactical (TAMRP) [1, 2], operational (OAMRP) [3-7], and robust (RAMRP) [8-11]. The focus of this
research is the RAMRP, which adopts the robustness idea to create flexible routes that can withstand unpredictable events [8-11]. In RAMRP, the flight delays are considered besides the operational maintenance requirements. Usually, the robustness can be achieved using an approach, called the buffer time insertion approach (BT). This ap- proach is used to insert buffer or slack time between flight legs to deal with the expected flight delays. Indeed, the BT approach was widely adopted in the literature [12, 13]. However, there are significant drawbacks of the BT approach. On the one hand, impos- ing a large buffer time among flight legs reduces the number of flight legs covered by each aircraft, henceforth reducing fleet productivity, mainly when covering many flight legs. On the other hand, inserting a short buffer time may not be enough to absorb the expected delays. The recent survey in [14] provides further details about the AMRP.

This study makes the following contributions; first, in contrast to the BT robustness approach, we propose a novel robustness approach, called the TR. Before proposing this approach, it is essential to define the turn-around time (TRT) as the time required by the airlines, or other service companies, to help the aircraft complete the operations related to the last covered flight legs and to finalize the operations associated with the next flight legs. These operations are called ground handling operations and include unloading the luggage of the previously covered flight leg, loading the luggage for the next flight leg, moving the aircraft between gates, and fueling the aircraft. The main idea of the TR is to speed up or to reduce the normal TRT by allocating more ground resources (i.e., workforce and facilities) while observing any delay. Consequently, the accumulated propagated delay can be mitigated, avoiding the delay propagation for the downstream flight legs, leading to significant recovery cost savings for the airlines company. Before designing the TR, several interviews were made with experts in a major Middle Eastern airlines company, they mentioned that allocating more ground resources can contribute to speeding up some ground operations, resulting in a 30-50% reduction in the normal TRT. Based on this remark, three types of TRT were addressed: the normal TRT, the reduced TRT (i.e., 30% reduction of the normal TRT), and the extra-reduced TRT (i.e., 50% reduction of the normal TRT). The first TRT is applied when the accumulated propagated delay does not appear, whereas the rest of the TRTs are used when the delay appears.

The remainder of this paper is organized as follows. In Section 2, the model formu-
lation is presented. The solution method for the RAMRP and the computational exper-
iments are provided in Section 3. Finally, Section 4 gives the conclusions of the study.

2 Model formulation

The RAMRP is formulated based on the connection network [3]. The node sets of the network include the flight legs set (I) and the maintenance stations set (MT), whereas the arc sets of the network include the normal TRT coverage arc set (COVN), the reduced TRT coverage arc set (COVR), the extra-reduced TRT coverage set (COVE), the visiting maintenance arc set (VMA), and the leaving maintenance arc set (LMA). The normal TRT coverage arc $covn(i, j) \in COVN$ is used to link two consecutive flight legs, such that the TRT is normal, i.e. when there is no accumulated
propagated delay. On the other hand, when the accumulated propagated delay appears, $covr(i, j) \in COVR$ and $cove(i, j) \in COVE$, are used, depending on the severity of the accumulated propagated delay. The visiting maintenance arc $vma(i, m) \in VMA$ is designed to prepare maintenance visits for the aircraft, whereas the leaving maintenance arc $lma(m, j) \in LMA$ is incorporated in the network to let the aircraft leave the maintenance stations and resume covering the subsequent flight legs.

Notations used throughout the model are given as follows:

Sets and indices:

<table><tr><td>A</td><td>Set of airports, indexed by a.</td></tr><tr><td>MT</td><td>Set of maintenance stations, indexed by m.</td></tr><tr><td>I</td><td>Set of flight legs, indexed by i or j.</td></tr><tr><td>K</td><td>Set of aircraft, indexed by k.</td></tr><tr><td>t &isin; T</td><td>Turn-around time (TRT) types {n, r, e}, such that n, r, and e represent the normal TRT, the reduced TRT, and the extra-reduced TRT, respectively.</td></tr><tr><td>v &isin; {1, 2, ..., &Psi;}</td><td>The average number of maintenance checks that each aircraft should receive during the planning horizon.</td></tr><tr><td>{o, s}</td><td>Starting and ending node of the modified connection network.</td></tr></table>

Parameters:

<table><tr><td>DT<sub>i</sub></td><td>Flight leg i departure time.</td></tr><tr><td>O<sub>ia</sub></td><td>Binary integer. It takes a value of 1 if the origin airport of flight leg i is airport a and 0 otherwise.</td></tr><tr><td>AT<sub>i</sub></td><td>Flight leg i arrival time.</td></tr><tr><td>D<sub>ia</sub></td><td>Binary integer. It takes a value of 1 if the destination airport of flight leg i is airport a and 0 otherwise.</td></tr><tr><td>FT<sub>i</sub></td><td>Duration of flight leg i.</td></tr><tr><td>TRT<sup>t</sup></td><td>Turn-around time of type t. It is noteworthy that TRT is the time consumed in unloading and loading the luggage, and fueling the aircraft</td></tr><tr><td>E(NPD<sub>i</sub>)</td><td>The expected value of the non-propagated delay of flight leg i.</td></tr><tr><td>Mb<sub>ma</sub></td><td>Binary indicator. It takes a value of 1 if maintenance station m is located at airport a and 0 otherwise.</td></tr><tr><td>MAT</td><td>Time required to complete Type A maintenance check.</td></tr><tr><td>FS</td><td>Fleet size</td></tr><tr><td>&Psi;</td><td>The maximum average number of maintenance checks should be received by each aircraft. The value of &Psi; can be achieved through &Psi; = &Sigma;<sub>i&isin;NF</sub> FT<sub>i</sub>/(T<sub>max</sub> FS).</td></tr><tr><td>M</td><td>A big number.</td></tr><tr><td>PD<sub>ijkv</sub><sup>t</sup></td><td>The propagated delay value appears when flight leg i and j are consecutively flown by aircraft k, while using turn-around time of type t, before receiving the maintenance check number v.</td></tr></table>
$PD_{ikv}$ The accumulated propagated delay value appears before covering flight leg *i* by aircraft *k*, before receiving the maintenance check number *v*.

$SEV$ Severity threshold for the accumulated propagated delay such that going beyond it causes several delays for the downstream flights.

$C_{pD}$ Expected cost incurred by the airline for each minute of propagated delay.

Decision variables:

$x_{ijkv}^t \in \{0,1\}$ It takes a value of 1 if aircraft *k* covers two consecutive flight legs *i* and *j* using turn-around time of type *t*, before receiving the maintenance check number *v*, and 0 otherwise.

$y_{imkv} \in \{0,1\}$ It takes a value of 1 if flight leg *i* is covered by aircraft *k*, then the aircraft proceeds to maintenance station *m* to receive the maintenance check number *v*, and 0 otherwise.

$z_{mjkv} \in \{0,1\}$ It takes a value of 1 if aircraft *k* leaves maintenance station *m* to cover flight leg *j*, after receiving the maintenance check number *v*, and 0 otherwise.

$RT_{kvm} > 0$ The ready time when aircraft *k* completes receiving the maintenance check number *v* at maintenance station *m*, and can fly the next scheduled flight legs.

Based on the previous defined notations, the formulation of the RAMRP can be represented as follows:

$$ \text{Min} \sum_{v=1,...,\psi} C_{pD} \left( \sum_{k \in K} \sum_{i \in I} \sum_{j \in I} \sum_{t \in T} PD_{ijkv}^t x_{ijkv}^t \right) \quad (1) $$

Subject to

$$ PD_{ijkv}^t = (PD_{ikv} + E(NPD_i) - (DT_j - AT_i - TRT^t))^+ \quad \forall i, j \in I, \forall t \in T, \forall k \in K, \forall v = 1, \dots, \psi \quad (2) $$

$$ \sum_{k \in K} \left( \sum_{j \in I \cup \{s\}} \sum_{t \in T} \sum_{v \in \psi} x_{ijkv}^t + \sum_{m \in MT} \sum_{v \in \psi} y_{imkv} \right) = 1 \quad \forall i \in I \quad (3) $$

$$ \sum_{j \in I \cup \{o\}} \sum_{t \in T} x_{ijkv}^t + \sum_{m \in MT} z_{mikv} = \sum_{j \in I \cup \{s\}} \sum_{t \in T} x_{ijkv}^t + \sum_{m \in MT} y_{imkv} \quad \forall i \in I, \forall k \in K, \forall v = 1, \dots, \psi \quad (4) $$

$$ \sum_{j \in I} \sum_{v=1,...,\psi} y_{jmkv} = \sum_{j \in I \cup \{t\}} \sum_{v=1,...,\psi} z_{mjkv} \quad \forall m \in MT, \forall k \in K \quad (5) $$

$$ AT_i + TRT^t - DT_j \le M(1 - x_{ijkv}^t) \quad \forall i, j \in I, \forall t \in T, \forall k \in K, \forall v = 1, \dots, \psi \quad (6) $$

$$ \sum_{k \in K} x_{ijkv}^t \le \sum_{a \in A} D_{ia} O_{ja} \quad \forall i, j \in I, \forall v = 1, \dots, \psi \quad (7) $$

$$ x_{ijkv}^n + x_{ijkv}^r + x_{ijkv}^e \le 1 \quad \forall i, j \in I, \forall k \in K, \forall v = 1, \dots, \psi \quad (8) $$

$$ 1 - PD_{ikv} \le M(1 - x_{ijkv}^n) \quad \forall i, j \in I, \forall k \in K, \forall v = 1, \dots, \psi \quad (9) $$

$$ PD_{ikv} - SEV \le M(1 - x_{ijkv}^r) \quad \forall i, j \in I, \forall k \in K, \forall v = 1, \dots, \psi \quad (10) $$
$$SEV - PD_{ikv} \leq M(1 - x_{ijkv}^e) \quad \forall i, j \in I, \forall k \in K, \forall v = 1, \dots, \Psi \quad (11)$$

$$\sum_{k \in K} y_{imkv} \leq \sum_{a \in A} D_{ia} M b_{ma} \quad \forall i \in I, \forall m \in MT, \forall v = 1, \dots, \Psi \quad (12)$$

$$\sum_{k \in K} z_{mjkv} \leq \sum_{a \in A} M b_{ma} O_{ja} \quad \forall m \in MT, \forall j \in I, \forall v = 1, \dots, \Psi \quad (13)$$

$$RT_{kvm} - DT_j \leq M(1 - z_{mjkv}) \quad \forall m \in MT, \forall j \in I, \forall k \in K, \forall v = 1, \dots, \Psi \quad (14)$$

$$RT_{kvm} \geq \sum_{i \in I \cup \{0\}} \sum_{j \in I \cup \{t\}} \sum_{m \in MT} (AT_i + MAT)z_{mjkv} \quad \forall k \in K, \forall v = 1, \dots, \Psi, \forall m \in MT \quad (15)$$

The objective function stated in (1) is to minimize the expected propagated delay cost over the planning horizon. Constraints (2) express the propagated delay calculations. Constraints (3) are cast to cover all the flight legs, which indicates covering each flight leg strictly by one aircraft. Balance constraints (4) and (5) are formulated to keep the aircraft's circulation throughout the network. To connect two flight legs by using the same aircraft, that connection should be feasible in terms of time and space considerations, as described by constraints (6) and (7). As mentioned earlier, one of the distinctive features of the proposed model is using the TR as a robustness approach. This approach is indicated in constraints (8) – (11). To prepare a maintenance visit for the aircraft, constraints (12) are formulated to consider the locations of the maintenance stations. After finishing the maintenance operation, the aircraft should resume covering its route. For this purpose, constraints (13) - (15) are developed.

## 3 Solution method and Computational experiments

Since the RAMRP is modeled as a network-based problem, the ACO has been selected as it has been successfully applied in solving large and complex network-based problems [15-18]. The ACO based-algorithm proposed by Eltoukhy, et al. [5] was used to solve the RAMRP model. In addition, this algorithm employs a neural network algorithm for flight delay prediction [19]. The adopted ACO algorithm has two main parts; route construction with the help of an ant that simulates an aircraft moving throughout the network, and updating the pheromone trail to improve the solution quality through several iterations.

To demonstrate the effectiveness of the proposed TR approach, computational experiments were conducted based on real data obtained from a major Middle Eastern airline. A summary of the data is given in Table 1.

<table><caption>**Table 1.** Features of the collected test cases</caption><thead><tr><td>Test cases</td><td>Number of flight legs</td><td>Fleet size</td><td>Maximum number of take-offs</td><td>Number of airports</td><td>Maintenance Stations</td></tr></thead><tbody><tr><td>Case 1</td><td>400</td><td>65</td><td>15</td><td>28</td><td>18</td></tr><tr><td>Case 2</td><td>2040</td><td>332</td><td>15</td><td>35</td><td>24</td></tr><tr><td>Case 3</td><td>4080</td><td>664</td><td>15</td><td>35</td><td>24</td></tr></tbody></table>
## 3.1 Performance analysis

To test the superiority of the proposed TR over the BT approach, our experiments are conducted to compare the performance of the TR with the BT approach proposed by Liang, et al. [12]. The performance of the robustness approaches is shown in Table 2.

<table><caption>**Table 2.** Performance characteristics of the two robustness approaches</caption><thead><tr><th rowspan="2">Test case</th><th rowspan="2">No. of flight legs</th><th colspan="2">BT approach</th><th colspan="2">TR approach</th><th rowspan="2">%(<span style="text-decoration: overline;">Z</span>)<sub>BT</sub></th><th rowspan="2">%(<span style="text-decoration: overline;">FP</span>)<sub>BT</sub></th></tr><tr><th><span style="text-decoration: overline;">Z</span></th><th><span style="text-decoration: overline;">FP</span></th><th><span style="text-decoration: overline;">Z</span></th><th><span style="text-decoration: overline;">FP</span></th></tr></thead><tbody><tr><td>Case 1</td><td>400</td><td>6849</td><td>365</td><td>6,325</td><td>400</td><td>7.65</td><td>8.75</td></tr><tr><td>Case 2</td><td>2040</td><td>53,308</td><td>1802</td><td>47,754</td><td>2040</td><td>10.42</td><td>11.67</td></tr><tr><td>Case 3</td><td>4080</td><td>154,501</td><td>3526</td><td>135,652</td><td>4080</td><td>12.20</td><td>13.58</td></tr></tbody></table>

Regarding the TR and the BT, Table 2 shows that the structure of the TR enables it to outperform the BT by about 7.65 – 12.20% and 8.75 – 13.58% while handling the propagated delay costs and fleet productivity, respectively. The proposed approach was able to reduce the TRT times by allocating more ground resources when the propagated delay appears. This results in accommodating the propagated delay, leading to significant savings in the propagated delay costs. In contrast to the TR, the BT sometimes inserts short buffer times, which may not be enough to absorb the propagated delays, increasing the propagated delay costs. Moving to the reason for the outperformance in terms of fleet productivity. Indeed, the BT sometimes imposes a long buffer time between the flight legs, which reduces the number of flight legs that should be covered by each aircraft. Consequently, the BT suffers from reduced fleet productivity, mainly when covering many flight legs. Opposite to the BT, the TR does not include those large-time slots, so the fleet productivity reduction can be easily avoided.

## 4 Conclusions

This study investigates the RAMRP and sought to propose a novel robust approach, called the TR. The effectiveness of the proposed TR approach is demonstrated through computational experiments using real data acquired from a major Middle Eastern airline. In our computational experiments, we demonstrate the importance of the TR, which is included in the RAMRP, by making a comparison with the BT approach. The results reveal an outperformance of the TR over the BT by about 7.65 – 12.20% and 8.75 – 13.58% while handling the propagated delay costs and fleet productivity, respectively. The results of this study indicate that the novel TR has excellent potential for implementation in the airline industry. Since the airlines have high uncertainty levels, it could be fruitful to develop an AMRP model while considering stochastic parameters such as arrival and departure times [20-22]. For future research, it is recommended to carry out further tests to assess the superiority of the new approach over the existing ones, particularly in different real-life scenarios. Besides, the sensitivity of the obtained results against changes in external parameters might be another avenue for future research.
**Acknowledgments.** The study presented in this article was mainly supported by a grant from the Research Committee of The Hong Kong Polytechnic University under project code P0036181 and RGC (Hong Kong).

**References**

1. R. Gopalan and K. T. Talluri, "The Aircraft Maintenance Routing Problem," *Operations Research*, vol. 46, no. 2, pp. 260-271, 1998.

2. Z. Liang, W. A. Chaovalitwongse, H. C. Huang, and E. L. Johnson, "On a New Rotation Tour Network Model for Aircraft Maintenance Routing Problem," *Transportation Science*, vol. 45, no. 1, pp. 109-120, 2011.

3. A. E. E. Eltoukhy, F. T. S. Chan, S. H. Chung, and B. Niu, "A model with a solution algorithm for the operational aircraft maintenance routing problem," *Computers & Industrial Engineering*, vol. 120, pp. 346-359, 2018.

4. A. E. E. Eltoukhy, F. T. S. Chan, S. H. Chung, B. Niu, and X. P. Wang, "Heuristic approaches for operational aircraft maintenance routing problem with maximum flying hours and man-power availability considerations," *Industrial Management & Data Systems*, vol. 117, no. 10, pp. 2142-2170, 2017.

5. A. E. E. Eltoukhy, Z. X. Wang, F. T. S. Chan, and S. H. Chung, "Joint optimization using a leader-follower Stackelberg game for coordinated configuration of stochastic operational aircraft maintenance routing and maintenance staffing," *Computers & Industrial Engineering*, vol. 125, pp. 46-68, 2018.

6. A. E. E. Eltoukhy, Z. X. Wang, F. T. S. Chan, and X. Fu, "Data analytics in managing aircraft routing and maintenance staffing with price competition by a Stackelberg-Nash game model," *Transportation Research Part E: Logistics and Transportation Review*, vol. 122, pp. 143-168, 2019.

7. A. E. E. Eltoukhy, Z. X. Wang, I. A. Shaban, and F. T. S. Chan, "Coordinating aircraft maintenance routing and integrated maintenance staffing and rostering: a Stackelberg game theoretical model," *International Journal of Production Research*, pp. 1-25, 2022.

8. H. A. Hashim and A. E. E. Eltoukhy, "Landmark and IMU Data Fusion: Systematic Convergence Geometric Nonlinear Observer for SLAM and Velocity Bias," *IEEE Transactions on Intelligent Transportation Systems*, vol. 23, no. 4, pp. 3292-3301, 2022.

9. H. A. Hashim and A. E. E. Eltoukhy, "Nonlinear Filter for Simultaneous Localization and Mapping on a Matrix Lie Group Using IMU and Feature Measurements," *IEEE Transactions on Systems, Man, and Cybernetics: Systems*, vol. 52, no. 4, pp. 2098-2109, 2022.

10. H. A. Hashim, "Guaranteed Performance Nonlinear Observer for Simultaneous Localization and Mapping," *IEEE Control Systems Letters*, vol. 5, no. 1, pp. 91-96, 2021.

11. H. A. Hashim, M. Abouheaf, and K. G. Vamvoudakis, "Neural-Adaptive Stochastic Attitude Filter on SO(3)," *IEEE Control Systems Letters*, vol. 6, pp. 1549-1554, 2022.

12. Z. Liang, Y. Feng, X. Zhang, T. Wu, and W. A. Chaovalitwongse, "Robust weekly aircraft maintenance routing problem and the extension to the tail assignment problem," *Transportation Research Part B: Methodological*, vol. 78, pp. 238-259, 2015.

13. A. Jamili, "A robust mathematical model and heuristic algorithms for integrated aircraft routing and scheduling, with consideration of fleet assignment problem," *Journal of Air Transport Management*, vol. 58, pp. 21-30, 2017.
14. A. E. E. Eltoukhy, F. T. S. Chan, and S. H. Chung, "Airline schedule planning: a review and future directions," *Industrial Management & Data Systems*, vol. 117, no. 6, pp. 1201-1243, 2017.

15. S.-H. Huang, Y.-H. Huang, C. A. Blazquez, and G. Paredes-Belmar, "Application of the Ant Colony Optimization in the Resolution of the Bridge Inspection Routing Problem," *Applied Soft Computing*, 2018.

16. D. P. Mahato, R. S. Singh, A. K. Tripathi, and A. K. Maurya, "On scheduling transactions in a grid processing system considering load through Ant Colony Optimization," *Applied Soft Computing*, vol. 61, pp. 875-891, 2017.

17. R. Skinderowicz, "An improved Ant Colony System for the Sequential Ordering Problem," *Computers & Operations Research*, vol. 86, pp. 1-17, 2017.

18. S. R. Balseiro, I. Loiseau, and J. Ramonet, "An Ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows," *Computers & Operations Research*, vol. 38, no. 6, pp. 954-966, 2011.

19. A. E. E. Eltoukhy, I. A. Shaban, F. T. S. Chan, and M. A. M. Abdel-Aal, "Data Analytics for Predicting COVID-19 Cases in Top Affected Countries: Observations and Recommendations," *International Journal of Environmental Research and Public Health*, vol. 17, no. 19, p. 7080, 2020.

20. H. A. Hashim, "A geometric nonlinear stochastic filter for simultaneous localization and mapping," *Aerospace Science and Technology*, vol. 111, p. 106569, 2021.

21. H. A. Hashim, "Exponentially stable observer-based controller for VTOL-UAVs without velocity measurements," *International Journal of Control*, pp. 1-15, 2022.

22. H. A. Hashim, M. Abouheaf, and M. A. Abido, "Geometric stochastic filter with guaranteed performance for autonomous navigation based on IMU and feature sensor fusion," *Control Engineering Practice*, vol. 116, p. 104926, 2021.