Aircraft Routing with Maintenance Triggers: An Analysis of Maintenance Timing
International Journal of Industrial and Operations Research
(ISSN: 2633-8947 )
Volume 7, Issue 2
Research Article
DOI: 10.35840/2633-8947/6521
Aircraft Routing with Maintenance Triggers: An Analysis of Maintenance Timing
Robert M Saltzman and Helman I Stern
Table of Content
Figures
Figure 1: Standard deviation in...
Standard deviation in the number of flights taken by aircraft for each DTM scenario.
Tables
Table 1: Days to maintenance for five initial condition test cases.
Table 2: Trigger types used in published research papers.
Table 3a: Maintenance schedule results from initial condition case A.
Table 3b: Maintenance schedule results from initial condition case B.
Table 3c: Maintenance schedule results from initial condition case C.
Table 3d: Maintenance schedule results from initial condition case D.
Table 3e: Maintenance schedule results from initial condition case E.
Table 4: Summary of results for FX102x9 problem for DTM experiments.
Table 5: Summary of results for FX102x9 problem for FTMATM experiments.
Table 6: Summary of results for FX102x9 Problem for all five DTM initial condition cases.
References
- Haouari M, Shao S, Sherali HD (2012) A lifted compact formulation for the daily aircraft maintenance routing problem. Transportation Science 47: 508-525.
- Stern HI, Saltzman RM (2023) Aircraft maintenance facility location planning. EURO Journal on Transportation and Logistics 12: 100116.
- Mirjafari M, Komijan AR, Shoja A (2023) Aircraft routing problem considering various maintenance operation factors: A literature review. Journal of Industrial Engineering International 19.
- Deng Q, Santos B (2021) Look ahead approximate dynamic programming for stochastic aircraft maintenance check scheduling optimization. European Journal of Operational Research 299: 814-833.
- Kabbani NM, Patty BW (1992) Aircraft routing at American airlines. Proceedings of the 32 ^{ nd } Annual Symposium of AGIFORS. Budapest.
- Yurek EE (2024) Combinatorial Benders decomposition for the operational aircraft maintenance routing problem. Computers & Operations Research 164: 106545.
- Sarac A, Batta R, Rump CM (2006) Branch and price approach for operational aircraft maintenance routing. European Journal of Operational Research 175: 1850-1869.
- Cui R, Dong X, Lin Y (2019) Models for aircraft maintenance routing problem with consideration for remaining time and robustness. Computers and Industrial Engineering 137: 106045.
- Esmaeilzadeh H, Komijan AR, Kazemipoor H, Fallah M, Tavakkoli-Moghaddam R (2022) A bi-objective aircraft maintenance routing problem based on flying hours to efficient use of available fleet. Journal of Facilities Management 22: 325-344.
- Orhan I, Kapanoglu M, Karakoc TH (2011) Concurrent aircraft routing and maintenance scheduling. Journal of Aeronautics and Space Technologies 5: 73-79.
- Deng Q, Santos BF, Curran R (2020) A practical dynamic programming-based methodology for aircraft maintenance check scheduling optimization. European Journal of Operational Research 281: 256-273.
- Van der Weide T, Deng Q, Santos B (2021) Robust long-term aircraft heavy maintenance check scheduling optimization under uncertainty. Computers and Operations Research 141: 105667.
- Shabanpour A, Bashiri M, Tavakkoli-Moghaddam R, Samghabadi AS (2023) Integrated linear integer model of a fleet allocation and aircraft routing problem with operational constraints. International Journal of Engineering, Transactions A: Basics 36: 669-681.
- Verhagen W, Santos B, Freeman F, Kessel P, Zarouchas D, et al. (2023) Condition-based maintenance in aviation: Challenges and opportunities. Aerospace 10: 762.
- Tseremoglou I, van Kessel PJ, Santos BF (2023) A comparative study of optimization models for condition-based maintenance scheduling of an aircraft fleet. Aerospace 10: 120.
- Gerdes M, Scholtz D, Galar D (2016) Effects of condition-based maintenance on costs caused by unscheduled maintenance of aircraft. J Quality Maint Eng 22: 394-417.
- IBM (2024) IBM ILOG CPLEX Optimization Studio.
- Kabbani NM, Patty BW (1993) Aircraft routing model. TIM/ORSA. Chicago, IL, USA.
- Afsar HM, Espinouse M-L, Penz B (2006) A two-step heuristic to build flight and maintenance planning in a rolling-horizon. In 2006 International Conference on Service Systems and Service Management, IEEE, Troyes, France.
- Liang Z, Chaovalitwongse WA (2009) The aircraft maintenance routing problem. Optimization and Logistics Challenges in the Enterprise 30: 327-348.
- Basdere M, Bilge U (2014) Operational aircraft maintenance routing problem with remaining time consideration. European Journal of Operational Research 235: 315-328.
- Al-Thani NA, Ahmed MB, Haouri M (2016) A model and optimization-based heuristic for the operational aircraft maintenance routing problem. Transportation Research Part C: Emerging Technologies 72: 29-44.
- Eltoukhy AEE, Chan FTS, Chung SH (2017) Airline schedule planning: A review and future directions. Industrial Management & Data Systems 117: 1201-1243.
- Eltoukhy AEE, Chan FTS, Chung SH, Niu B, Wang XP (2017) Heuristic approaches for operational aircraft maintenance routing problem with maximum flying hours and manpower availability considerations. Industrial Management & Data Systems 117: 2142-2170.
- Ruan JH, Wang ZX, Chan FTS, Patnaik S, Tiwari MK (2021) A reinforcement learning-based algorithm for the aircraft maintenance routing problem. Expert Systems with Applications 169: 114399.
- Andrade P, Silva C, Ribeiro B, Santos BF (2021) Aircraft maintenance check scheduling using reinforcement learning. Aerospace 8: 113.
Author Details
Robert M Saltzman^{1*} and Helman I Stern^{2}
^{1}Professor, Decision Sciences Department, San Francisco State University, USA
^{2}Professor, Department of Industrial Engineering and Management, Ben Gurion University of the Negev, ISRAEL
Corresponding author
Robert M Saltzman, Professor, Decision Sciences Department, San Francisco State University, USA.
Accepted: July 17, 2024 | Published Online: July 19, 2024
Citation: Saltzman RM, Stern HI (2024) Aircraft Routing with Maintenance Triggers: An Analysis of Maintenance Timing. Int J Ind Operations Res 7:021.
Copyright: © 2024 Saltzman RM, et al. This This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Abstract
This article focuses on the types of events that trigger maintenance visits in the context of aircraft maintenance routing problems (AMRP). That is, given a flight schedule for a homogenous aircraft fleet, we find a sequence of flights for each aircraft that indicates when and where each aircraft should receive maintenance. Using a compact integer linear program, we examine three events that trigger maintenance: The number of days, the total flying time between, and the total number of takeoffs between type A maintenance checks. Our model’s objective function is a weighted sum of 1-day and 2-day cyclic routes, subject to all three types of trigger constraints and many other requirements of the AMRP. We use the model to perform a comparative evaluation of these maintenance triggers using an actual flight schedule. The paper’s main contributions are that it (a) Examines alternative criteria to determine maintenance requests, (b) Provides an extensive literature review, (c) Presents computational experiments for a real-life aircraft flight schedule, and (d) Evaluates interactions among the maintenance triggers.
Keywords
Aircraft, Maintenance routing, Maintenance operation triggers, Multicommodity flow problem, Integer programming
Introduction
The aircraft maintenance routing problem (AMRP) is considered of prime importance to airline planners in terms of cost reduction and passenger safety. In terms of safety, a number of maintenance checks are stipulated. These are termed letter checks. The letter checks B, C, and D are long-term checks, whereas A checks are more immediate. Typically, A checks are performed in a hanger overnight and can take in the order of ten hours. Several criteria are adopted for type A maintenance to determine when the next maintenance will be undertaken. We denote these as maintenance triggers and consider three types: (i) After some number of aircraft flight landings or f lights t o m aintenance (FTM); (ii) After a fixed number of flight hours or airtime to m aintenance (ATM); and (iii) The number of d ays t o m aintenance (DTM) since the last maintenance check. Others consider all three maintenance triggers simultaneously and pick the maintenance date according to which comes first. It is also possible to perform maintenance before the trigger dates if it is advantageous. The values of FTM and ATM depend on the type of aircraft. For type A checks, Haouari, Shao, and Sherali [1] used FTM = 6 flight takeoffs for international flights (and no limit for domestic flights), ATM = 45-75 hours, and DTM = 4 days. The values used for our FS are FTM = 12, 14, 16, 18 and ATM = 40, 45, 50 hours.
We formulate an integer linear program (ILP) to perform a comparative evaluation of maintenance triggers. The objective function of the ILP is to minimize the number of non-cyclic routes flown. The motivation for this approach is to reduce the cost and displacement of crew and aircraft being away from their home airport. Tests are conducted using an actual flight schedule from Florida Express Airlines.
Regarding the DTM case it is often assumed that all aircraft have just received maintenance at some time t and have x days to the next maintenance check. (See cases A and E in Table 1). This approach is problematic because it results in a simultaneous clustering of maintenance demands for all aircraft on the maintenance facility at time t + x. This is the assumption made by Stern and Saltzman [2]. To avoid this, it is preferable to stagger the days to the next required maintenance. Thus, it is assumed that each aircraft in the fleet has a specified number of days left until it needs maintenance (DTM). For a fleet of size F, allowing 1, 2, or 3 days to maintenance for each aircraft, the number of possibilities is exponential at 3 ^{ F } . This number is vast; for our example, with a fleet of 28 aircraft, it is 22.8 × 10^{12}. As such, we defined five exemplary cases containing a mix of DTM values for testing (see Table 1).
The rest of the paper is organized as follows. A literature review appears in the next section. After that, we introduce the concept of a maintenance trigger and a list of research papers regarding maintenance inspection policies used by various authors. This is followed by our formulation of a maintenance trigger evaluator. The subsequent section provides computational results. These results and a conclusion are discussed in the last sections of the paper.
Literature Review
Several research papers have dealt with aircraft maintenance facility planning. Haouari, et al. [1] consider an aircraft routing problem (ARP) represented by a daily repeated flight schedule with maintenance constraints similar to our maintenance triggers. Most closely related to our depiction of maintenance triggers appears in the recent review of Mirjafari, et al. [3]. Also, Deng and Santos [4] refer to three usage parameters that mirror the description of our three maintenance triggers. Kabbani and Patty [5] consider a three-day to maintenance constraint for American Airlines. Yurek [6] contains a detailed review and mentions the use of all three maintenance triggers. Sarac, et al. [7] consider an operational maintenance routing problem with maintenance facility availability. They solve the problem by a modified branch and price algorithm. Cui, et al. [8] consider an integer linear program for solving the aircraft maintenance routing problem with a remaining time to maintenance constraint. Also, Esmaeilzadeh, et al. [9] include the remaining time to maintenance constraint in a bi-objective mixed-integer programming model. Haouari, et al. [1] solve the aircraft routing problem with constraints on total flying time, the number of flights, and days between maintenance checks. Orhan, et al. [10] provide an integer linear problem for the aircraft routing problem, which considers different maintenance types, remaining flight hours, and remaining flight days. An investigation similar to ours of the longer interval B, C, and D letter checks appears in Deng, et al. [11]. Sarac, et al. [7] developed a formulation for an aircraft maintenance routing problem with stochastic events such as the effects of weather, equipment failures, and scheduling flight delay disruptions. Deng, et al. [11] use dynamic programming to solve the long-term maintenance schedule problem where several letter checks are merged. Deng and Santos [4] present a stochastic simulation of unplanned events that provides letter check update decisions as a function of aircraft utilization. Van der Weide, et al. [12] also studied the stochastic aircraft maintenance check scheduling problem. Shabanpour, et al. [13] integrate fleet allocation and aircraft routing models with operational constraints that include all three maintenance triggers. Condition-based maintenance based on the health of the aircraft to determine the nature and timing of required maintenance operations is discussed in Verhagen, et al. [14], Tseremoglou, et al. [15], and Gerdes, et al. [16].
Maintenance Triggers
A perusal of research papers regarding maintenance inspection policies was made, and it was found that most contain the ATM trigger, and several describe the use of all three triggers. The details appear in Table 2 below.
Formulation of Maintenance Trigger Evaluator
We set up an experimental design to compare the impact of the three types of maintenance triggers: DTM, ATM, and FTM. We formulated an integer linear program to evaluate the worth of a trigger. The testing uses flight data from Florida Express Airlines, consisting of 102 flights and 9 airport terminals, which we designate as the FX102x9 test problem. Appendix B of Stern and Saltzman [2] shows the complete flight schedule.
Notation
We use the following notation in our AMRP formulation. Sets are denoted by capital letters.
I = { i : i = l, …, n }, the set off light leg indices.
K = { k : k = l,…, q }, the set of indices for airports or commodities.
${t}_{d}^{i},{t}_{a}^{i}$ = flight i's departure and arrival times, respectively.
${k}_{d}^{i},{k}_{a}^{i}$ = flight i's departure and arrival airports, respectively (not necessarily the same aircraft).
(${t}_{d}^{i},{t}_{a}^{i}$,${k}_{d}^{i},{k}_{a}^{i}$ ) = a flight leg i ( ${k}_{d}^{i}\ne {k}_{a}^{i}$ ) .
f ^{ i } = airtime of flight leg i in minutes = ${t}_{a}^{i}-{t}_{d}^{i}$
FS = { i ∈ I}, a flight schedule for flight leg indices i.
M = the set of airports that can perform aircraft maintenance, M ⊂ K.
c _{ kd } = maintenance capacity of airport k ∈ K on day d ∈ D.
C _{ d } = [c _{ 1 d } , c _{ 2d } , …., c _{ kd } , …, c _{ qd } ] = maintenance capacity vector, by airport, for day d ∈ D.
C = [C _{ 1 } , C _{ 2 } , C _{ 3 } ] = a complete 3-day maintenance configuration.
m = Total number of aircraft in the fleet (determined a prior i as the minimum number needed to service a FS).
s ^{ k } = origin node for airport k .
t ^{ k } = destination node for airport k .
S = {s ^{ k } | k ∈ K}, |S| = q . The set of supply (origin) nodes.
T = {t ^{ k } | k ∈ K}, |T| = q . The set of demand (destination) nodes.
N = I ∪ S ∪ T.
G = [N, A] is a directed acyclic graph based on an FS connection network, where N and A are the node and arc sets, respectively.
G is a complete connection graph or a hollow graph). A predecessor/successor of node i is a node j connected to i by a directed arc ( j, i )/( i, j ) ∋ ( j, i )/( i, j ) ∈A.
B( i ) = the set of predecessor nodes of node i.
A( i ) = the set of successor nodes of node i.
R = {( ijk )} ∋ commodity k ∈ K may flow on arc ( i, j ), where i ∈ N and j ∈ A( i ).
S ^{ k } = supply of commodity k at node s ^{ k } .
T ^{ k } = demand of commodity k at node t ^{ k } .
D = {1, 2, 3}.The set of days.
AM1 = the set of aircraft tail numbers that must get maintenance within 1 day from the last time.
AM2 = the set of aircraft tail numbers that must get maintenance within 2 days from the last time.
AM3 = the set of aircraft tail numbers that must get maintenance within 3 days from the last time,
i.e., on day 1, day 2, or day 3.
AC = {A01, A02, …, A m } = ${\text{U}}_{i=1}^{i=3}\mathrm{AM}i.$ The set of all aircraft tail numbers.
DTM = Days to maintenance since the last maintenance check.
ATM = Airtime to maintenance (total flight time in minutes).
FTM = Total number of flights to maintenance (flight landings).
DTM _{ max } _{ . } = Maximum number of days to maintenance since last maintenance.
ATM _{ max } = Maximum time an aircraft may fly between maintenances (in minutes).
FTM _{ max } = Maximum number of flights an aircraft may fly between maintenances.
Formulating AMRP as a binary integer multi-commodity flow problem
We formulate the AMRP as a large-scale binary integer linear program called the 3-day multi-commodity flow (3DMCF) model. We define R as the set of indices ( kij ) where ( i, j ) is an arc in G and k is an airport index. The set R also includes elements of the form ( kkj ), for all k ∈ K and flights j departing from airport k , which help identify the airport from which each aircraft starts its daily route. Our model uses a binary flow variable for each aircraft and each element of R every day.
$${x}_{ij}^{akd}\in \left\{0,1\right\},\text{}\forall a\in \text{AC,}d\in D,\text{}\left(ijk\right)\in \text{R(1)}$$
In particular, ${x}_{ij}^{akd}$ equals 1 if aircraft a is assigned to fly a route that starts at airport k on day d and includes flights i and j in sequence, and 0 otherwise. A second, smaller set of binary variables indicates the days and airports each aircraft is scheduled to receive maintenance.
$${y}_{akd}\in \left\{0,1\right\},\forall a\in \text{AC},k\in \text{M},d\in \text{D(2)}$$
Here, y _{ akd } is 1 if aircraft a is scheduled to receive maintenance at airport k at the end of day d and is 0 otherwise. Three sets of auxiliary variables keep track of the total number of cyclic 1-day and 2-day routes.
$$\text{B}{1}_{akd}\text{=}\left\{\begin{array}{l}1,\text{}if\text{aircarft}a\text{fliesacyclic1-dayrouteendingataiport}k\text{onday}d\text{;}\\ 0,otherwise.\end{array}\right.\text{}$$
$${\text{B2}}_{ak2}\text{=}\left\{\begin{array}{l}1,\text{}if\text{aircarft}a\text{fliesacyclic2-dayroutendingataiport}k\text{onday}2\text{;}\\ 0,otherwise.\end{array}\right.\text{}$$
$${\text{B2}}_{ak3}\text{=}\left\{\begin{array}{l}1,\text{}if\text{aircarft}a\text{fliesacyclic2-dayroutendingataiport}k\text{onday3;}\\ 0,otherwise.\end{array}\right.\text{}$$
Note that B2 _{ ak2 } counts the number of cyclic 2-day routes over days 1 and 2 that do not consist of two consecutive cyclic 1-day routes on days 1 and 2 ( i.e., it counts routes that only return to their day 1 starting airport at the end of day 2), while B2 _{ ak3 } counts the number of cyclic 2-day routes over days 2 and 3 which do not consist of two consecutive cyclic 1-day routes on days 2 and 3 (see constraints (23) and (24) below).The auxiliary variables allow the objective function Z to be defined as a weighted sum of each type of cyclic route.
$$\text{Z=}{w}_{1}{\displaystyle \sum _{a\in AC}{\displaystyle \sum _{k\in \text{M}}{\displaystyle \sum _{d\in \text{D}}\text{B}}}}{1}_{akd}+{w}_{2}{\displaystyle \sum _{a\in AC}{\displaystyle \sum _{k\in \text{M}}\left(\text{B}{2}_{ak2}+\text{B}{2}_{ak3}\right)}}\text{(6)}$$
While the weights w _{ 1 } and w _{ 2 } may be set as desired, we have used w _{ 1 } = 1 and w _{ 2 } = 0 to maximize the number of cyclic routes within a day. Our rationale is that maximizing the number of aircraft that return to their home airport at the end of each day will save the airline the expense of housing airline crews away from their home bases and simplify crew scheduling, especially during disruptions. The model’s constraints follow.
$$\sum _{a\in AC}{\displaystyle \sum _{j\in \text{A}\left({s}^{k}\right)}{x}_{{s}^{k}j}^{akd}}}{\text{=S}}^{k},\text{}\forall k\in K,\text{}d\in D\text{(7)$$
$\sum _{a\in AC}{\displaystyle \sum _{j\in \text{B}\left({t}^{k}\right)}{x}_{i{t}^{k}}^{akd}}}{\text{=T}}^{k},\text{}\forall k\in K,\text{}d\in D$ (8)
$$\sum _{a\in \text{AC}}{\displaystyle \sum _{k\in K}{\displaystyle \sum _{i\in \text{B}\left(j\right)}{x}_{ij}^{akd}}}}\text{=1},\text{}\forall j\in \text{I},\text{}d\in D\text{(9)$$
$$\sum _{a\in \text{AC}}{\displaystyle \sum _{\text{k}\in \text{K}}{\displaystyle \sum _{j\in \text{A}\left(i\right)}{x}_{ij}^{akd}}}}\text{=1},\text{}\forall j\in \text{I},\text{}d\in D\text{(10)$$
$$\sum _{i\in \text{B}\left(j\right)}{x}_{ij}^{akd}}\text{=}{\displaystyle \sum _{i\in A\left(j\right)}{x}_{ji}^{akd}},\text{}\forall j\in \text{I},\text{a}\in \text{AC,}k\in \text{K,}d\in D\text{(11)$$
$$\sum _{i\in \text{B}\left({t}^{k}\right)}{x}_{ij}^{ak1}}\text{=}{\displaystyle \sum _{j\in \text{A}\left({s}^{k}\right)}{x}_{{s}^{k}j}^{ak2}},\text{}\forall a\in \text{AC,}k\in \text{K(12)$$
$$\sum _{i\in B\left({t}^{k}\right)}{x}_{ij}^{ak2}}\text{=}{\displaystyle \sum _{j\in A\left({s}^{k}\right)}{x}_{{s}^{k}j}^{ak3}},\text{}\forall a\in \text{AC,}k\in \text{K(13)$$
$$\sum _{i\in B\left({t}^{k}\right)}{x}_{ij}^{ak3}}\text{=}{\displaystyle \sum _{j\in A\left({s}^{k}\right)}{x}_{{s}^{k}j}^{ak1}},\text{}\forall a\in \text{AC,}k\in \text{K(14)$$
$${y}_{akd}\le {\displaystyle \sum _{i\in \text{B}\left({t}^{k}\right)}{x}_{ij}^{akd}},\text{}\forall a\in \text{AC,}k\in \text{M,}d\in \text{D(15)}$$
$$\sum _{k\in \text{M}}{\displaystyle \sum _{d\in \text{D}}{y}_{akd}}}\text{=1,}\forall a\in \text{AC(16)$$
$$\sum _{a\in \text{AC}}{y}_{akd}}\le {\text{C}}_{kd},\text{}\forall k\in \text{M,}d\in \text{D(17)$$
$${y}_{ak2}\text{=0,}\forall a\in \text{AM1,}k\in \text{M(18)}$$
$${y}_{ak3}\text{=0,}\forall a\in \left(\text{AM1}\cup \text{AM2}\right)\text{,}k\in \text{M(19)}$$
$$\sum _{\left(ijk\right)\in \text{R}}{\displaystyle \sum _{d\in \text{D}}{x}_{ij}^{akd}}}-3\le {\text{FTM}}_{max},\text{}\forall a\in \text{AC(20)$$
$$\sum _{\left(ijk\right)\in \text{R}}{\displaystyle \sum _{d\in \text{D}}{f}^{i}{x}_{ij}^{akd}}}\le {\text{ATM}}_{max},\text{}\forall a\in \text{AC(21)$$
$${\text{B1}}_{akd}\text{=}\left({\displaystyle \sum _{\left(ijk\right)\in \text{R:}j\in \text{A}\left({s}^{k}\right)}{x}_{ij}^{akd}+{\displaystyle \sum _{\left(ijk\right)\in \text{R:}i\in B\left({t}^{k}\right)}{x}_{ij}^{akd}\text{=2}}}\right),\text{}\forall a\in \text{AC},\text{}k\in \text{K,d}\in \text{D(22)}$$
$${\text{B1}}_{ak2}\text{=}\left({\displaystyle \sum _{\left(ijk\right)\in \text{R:}j\in \text{A}\left({s}^{k}\right)}{x}_{ij}^{ak1}+{\displaystyle \sum _{\left(ijk\right)\in \text{R:}i\in B\left({t}^{k}\right)}{x}_{ij}^{ak2}\text{=2}}}\right)\text{-}\left(\text{B}{1}_{ak1}+\text{B}{1}_{ak2}\text{=2}\right)\text{,}\forall a\in \text{AC},\text{}k\in \text{K(23)}$$
$${\text{B2}}_{ak3}\text{=}\left({\displaystyle \sum _{\left(ijk\right)\in \text{R:}j\in \text{A}\left({s}^{k}\right)}{x}_{ij}^{ak2}+{\displaystyle \sum _{\left(ijk\right)\in \text{R:}i\in B\left({t}^{k}\right)}{x}_{ij}^{ak3}\text{=2}}}\right)\text{-}\left(\text{B}{1}_{ak2}+\text{B}{1}_{ak3}\text{=2}\right)\text{,}\forall a\in \text{AC},\text{}k\in \text{K(24)}$$
$${x}_{ij}^{akd}\in \left\{0,1\right\},\text{}\forall a\in \text{AC},\text{d}\in \text{D},\text{}\left(ijk\right)\in \text{R(25)}$$
$${y}_{akd}\in \left\{0,1\right\},\text{}\forall a\in \text{AC},\text{}k\in \text{M,d}\in \text{D(26)}$$
Constraints (7) and (8) are commodity supply and demand constraints, respectively. Constraints (9) and (10) require that the flow into and out of each flight node is one, ensuring that each flight lies on just one route. Conservation of flow at each flight node is achieved by constraints (11). Constraint sets (12) and (13) are continuity conditions that ensure an aircraft's ending airport on days 1 and 2 are the same as its starting airport on days 2 and 3, respectively. Similarly, constraint (14) requires each aircraft's route to be cyclic, returning to its day 1 starting airport at the end of day 3.
Constraint sets (15)-(21) impose all desired maintenance conditions. Specifically, constraint (15) allows maintenance to be performed on an aircraft only if its last flight ends at a maintenance airport, while (16) requires each aircraft to be scheduled for maintenance once every three days. Constraint (17) prevents the number of aircraft getting maintenance at airport k on day d from exceeding the input maintenance capacity C _{ kd } . Constraints (18)-(19) are the days-to-maintenance constraints, while (20) imposes the set of lights-to-maintenance constraints. To accurately count the number of flights taken by each aircraft, we must subtract three from the left-hand side of (20) because the first arc of each day for each aircraft simply indicates the aircraft's start-of-day airport; over three days, three extra flights per aircraft would otherwise be counted. Airtime-to-maintenance constraints are expressed in (21), where f ^{ i } is the airtime of flight i in minutes. FTM _{ max } and ATM _{ max } in constraints (20) and (21) are runtime parameters that can be set as desired. Experiments with these parameters are described below.
Constraints (22)-(24) use logical expressions in parentheses to compute the aforementioned objective function variables that indicate whether or not each aircraft flies a cyclic 1-day or 2-day route starting and ending at airport k . Finally, we restate the binary decision variable declarations in (25) and (26) for completeness.
Heuristic solution procedure
Because our formulation of the 3DMCF model involves many variables and constraints, it can take a long time to solve exactly to optimality. Consequently, we developed a heuristic procedure that yields high-quality (and frequently optimal) solutions quickly compared to solving 3DMCF exactly. Our heuristic begins by initializing the 3DMCF model with a partial solution generated by a simpler one-day version of this formulation (1DMCF), which does not include a day index for any binary flow variable. Thus, 1DMCF omits the continuity constraints (12-14), maintenance constraints (15-21), and constraints that determine whether or not an aircraft flies cyclic 2-day routes (23-24) of the 3DMCF model. The 1DMCF model maximizes the number of cyclic 1-day routes flown by all aircraft subject to constraints similar to (7-11) but without a day index. Once 1DMCF has been solved to optimality, the values of its flow variables are written to a text file. These values are then read in at the start of the 3DMCF model run and assigned to the day 1 flow variables (${x}_{ij}^{ak1}$ ), causing them to be treated as fixed during execution. The 3DMCF model is then run to determine day 2 and day 3 flow variables, as well as when and where maintenance of each aircraft should occur ( y _{ akd } ). Solution times for 1DMCF were relatively fast, and this heuristic approach dramatically lowers the time to (approximately) solve the 3DMCF model.
Computational Tests and Results
We implemented our model with the widely used mathematical programming software package ILOG CPLEX Optimization Studio, Version 12.6.3 (IBM) [17]. All instances of the test problem described in this section were solved on a Dell Precision 5540 laptop with 32 GB of RAM and an i7-9850H processor running at 2.60 GHz. A typical problem instance took less than two minutes to solve, and almost all runs finished in less than four minutes. In just one case out of the 65 reported below, the run time reached a 15-minute imposed computational time limit. Run times increased significantly only in the case where FTM _{ max } = 12 flights, the most highly constrained of the four FTM _{ max } cases.
Description of tests
The model was tested with the FX102x9 flight schedule, the details of which appear in Stern and Saltzman [2]. Tests were made for the five exemplary DTM initial condition cases using various input maintenance capacity vectors. These cases appear in Table 1 and are labeled A, B, C, D, and E. For each case and each of the 28 aircraft in the flight schedule, a DTM value is associated. The DTM values in the table decrease from 3 to 1 from the upper right to the lower left, providing plausible configurations.
Computational test results focused on DTM
Our first set of runs with the model focuses on the impact of DTM conditions while omitting the FTM and ATM constraints (by setting the parameters FTM _{ max } and ATM _{ max } so high as to make constraints (20) and (21) inactive). The right-most column of each table below gives the (near) minimum input maintenance capacity required to achieve Z* = 84. In each case, the total maintenance demand over the three days is M(1) + M(2) + M(3) = 28. Input maintenance capacity (MCap) may vary by day and is shown in the last column of each table. The following Tables 3a, 3b, 3c, 3d and 3e display the Aircraft Maintenance Schedule by Airport for various DTM initial conditions. Each table contains the set of aircraft numbers = {A01,…, A28}, DTM = Number of Days to Maintenance = 1, 2, 3, and M(DTM) = Total Maintenance demand for day DTM from the last maintenance check.
Interestingly, the Case E solution collapses the Case D solution from two days into one. Here, the total maintenance capacity is just 28 since no maintenance is performed on either day 2 or day 3, and day 1 capacities at each airport simply match the aircraft supply. Although it is reassuring that all aircraft can get maintenance in one day (provided adequate capacity), this is probably the least applicable case since it leads to a very unbalanced schedule for personnel performing the maintenance work.
As the DTM initial conditions become weighted more heavily toward one and two days, constraints (18) and (19) restrict more of the model's scheduling variables, making it harder to solve. At the same time, there is a corresponding shift in the scheduled maintenance toward the first two days, as seen in Table 4. In all but initial condition Case E, maintenance on some aircraft is scheduled a little earlier than required, e.g., in case D, 19 aircraft receive maintenance on day 1, five more than the 14 needed to get maintenance on day 1. In Case E, maintenance on all 28 aircraft must be done on day 1. All runs reported above had Z ^{ * } = 84 cyclic 1-day routes. In most cases, somewhat less maintenance capacity could be used to obtain a feasible solution, but doing so causes Z ^{ * } to fall below 84.
Computational test results focused on DTM
Our second, larger set of runs with the model focused on the impact of the FTM and ATM conditions while keeping the DTM conditions fixed. Here, we focus our analysis on DTM case C because it is the most realistic of the five initial condition test cases. At any point in time, it seems likely that there will be a wide variety among the aircraft in the number of days left for them each to get maintenance. In a system that performs maintenance on each aircraft every three days on average, about one-third of the aircraft would each need maintenance within 1, 2, or 3 days. While working with DTM case C, the input parameter FTM _{ max } was varied systematically in increments of two from 12 to 18 flights (landings), and the input parameter ATM _{ max } was varied from 2400 to 2700 to 3000 minutes ( i.e., 40 to 45 to 50 hours) of airtime between maintenances. Detailed results from these dozen runs are given below in Table 5. For each of the four test values of FTM _{ max } , the table shows a group of three ATM _{ max } runs. For each combination of the two input parameters, the table's main body indicates the number of flights taken and total airtime by each aircraft tail number between scheduled maintenances. The bottom rows of the table provide a few summary measures, including average maximum, the percentage of aircraft flying, maximum allowed number of flights, and standard deviation across the 28 aircraft in this test flight schedule.
First, all twelve scenarios yield the same average number of flights per aircraft, namely, 102 flights/day × 3 days/28 aircraft = 10.9 flights, and the same average amount of time flown, namely, 1954 minutes. This makes sense because all feasible schedules must service the same flight schedule regardless of parameters. Looking at the row of maximum values across the flights, the limitation on the number of flights is not binding when FTM _{ max } = 18 (as the maximum number of flights for each value of ATM _{ max } is only 17), but that this limitation does impact each of the other three cases. As FTM _{ max } decreases from 18 to 16 to 14 to 12, the percentage of aircraft flying the maximum number of flights permitted between maintenances increases, and there is greater consistency across the set of aircraft in terms of the total number of flights taken between maintenances. This can be quantified more precisely by examining the standard deviation in the number of flights each aircraft takes in the second to last row of Table 5. These values are shown graphically for all twelve scenarios in Figure 1 below. Overall, for this test problem, the FTM limitation substantially impacts the resulting flight schedule more than the ATM limitation. This test problem appeared infeasible when FTM _{ max } was set to 10, or ATM _{ max } was set to 2100 minutes (35 hours).
We also ran the model for the other four DTM initial condition cases under the same twelve scenarios. The results are summarized (without individual aircraft details) in Table 6. We can see that in all five DTM cases, the same Ave(NFlts) and Ave(Time) values were found (as expected), in addition to reaching the same Z ^{ * } values for the various FTM _{ max } values. All cases also yielded the same Max(NFlts) value for each FTM _{ max } case except when FTM _{ max } = 18 (which was binding in only a few scenarios). The five DTM cases have similar, but not identical, % at Max values over the various FTM _{ max } scenarios. As FTM _{ max } decreases in each DTM case, the StdDev(NFlts) decreases fairly consistently since the FTM constraints require more conformity among the aircraft. However, StdDev(Time) does not change in a consistent manner as FTM _{ max } increases.
Discussion
It is interesting to look critically at the potential for aircraft parts or structural failures in designing maintenance policies. Most aircraft stress, wear, and tear occur during takeoffs and landings. During takeoffs, this happens when the engine accelerates as the aircraft picks up speed on the runway and ascends to cruising altitude. On landings, the reversal of the engine puts stress on parts and structure. At touchdown, especially at the time of the landing bump, tires, and landing gear are affected. All of these factors are captured over time by the number of flights . However, using the number of flight hours does not correlate with the number of flights because a given number of flight hours can be comprised of various flights depending on the aircraft route. Likewise, flight days or days to maintenance criteria may mask the number of flights and the number of flight hours. Flight days can be a good or bad approximation and have no relation to flight hours or the number off lights, which are better indicators of the requirements for a maintenance check.
All of these factors may lead a maintenance manager to ponder what criteria to select as a trigger for a maintenance check. Scientific advice leads to an experimental design using real-time data on time to failure or flights to failure. However, while useful for small parts reliability tests, this is impractical from a cost and especially a safety perspective for large-body aircraft. Simulation is another analytical option, but it depends on the assumptions of what factors to use. Also, artificial intelligence, especially using machine learning techniques, is impractical without a large database training set of cases containing factors of aircraft flights or flight hours vs. actual parts or aircraft failures. Nevertheless, criteria are required to design a maintenance policy. As is the practice for automobile maintenance, a first come policy such as "10,000 miles or six months" is preferable. In our perusal of research papers, the only paper discussing this option explicitly is that of Yurek [7], who mentions using three triggers simultaneously. For all the others, we shall understand that this criterion is implicit.
Conclusion
The analysis here has been limited to the shortest A check schedule. A detailed investigation similar to ours of the longer interval B, C, and D letter checks is suggested for future work. In our review of research papers regarding maintenance inspection policies, only one paper by Deng, et al. [12] was discovered for the non-A letter checks. Three alternative methods for requesting aircraft maintenance checks were undertaken. We denoted each method as a "trigger type" that signals when an aircraft maintenance operation is to commence. The three trigger types are (i) Days since the last maintenance check, (ii) Total flying time, and (iii) Total number of aircraft takeoffs since the last maintenance check. To perform a comparative evaluation of these maintenance triggers, we formulated an integer linear program to minimize the cost of cyclic routes. A cyclic route within one day is preferred to one that involves several days with crew displacement and aircraft being away from their home terminal. Tests were conducted using an actual flight schedule from Florida Express Airlines.
The paper's main contributions are that it (a) Examined alternative criteria to determine maintenance requests, (b) Provided an extensive literature review, (c) Presented computational experiments for a real-life aircraft flight schedule, and (d) Evaluated interactions among the maintenance triggers.
Funding
This research did not receive grants from funding agencies in the public, commercial, or not-for-profit sectors.