Using deficit functions for aircraft fleet routing

Stern, Helman I.; Gertsbakh, Ilya B. Article Using deficit functions for aircraft fleet routing Operations Research Perspectives Provided in Cooperation with: Elsevier Suggested Citation: Stern, Helman I.; Gertsbakh, Ilya B. (2019) : Using deficit functions for aircraft fleet routing, Operations Research Perspectives, ISSN 2214-7160, Elsevier, Amsterdam, Vol. 6, pp. 1-11, https://doi.org/10.1016/j.orp.2019.100104 This Version is available at: https://hdl.handle.net/10419/246390 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc-nd/4.0 Contents lists available at ScienceDirect Operations Research Perspectives journal homepage: www.elsevier.com/locate/orp Using deficit functions for aircraft fleet routing Helman I. Stern a,⁎ , Ilya B. Gertsbakh b a Department of Industrial Engineering and Management, Ben Gurion University of the Negev, Israel b Department of Mathematics, Ben Gurion University of the Negev, Israel ARTICLE INFO Keywords: Deficit function Flight schedule Aircraft fleet Chain decomposition Aircraft routing ABSTRACT We consider the problem of minimizing the number of airplanes needed to flyafixed daily repeating schedule of flights. We use deficit functions (DF) to decompose an aviation schedule of aircraft flights into aircraft chains (routes) called a chain decomposition. Each chain visits periodically a set of airports and is served by several cockpit crews circulating along the airports of this set. The initial step in our approach is to find the minimal number of aircraft needed to carry out the flight schedule. This is achieved by using the fleet size theorem based on a DF representation of an aircraft flight schedule. A DF is a step function associated with an aircraft terminal which changes by + 1 and −1atflight departure and arrival times, respectively. DF theory was developed in the 1960–70s by Linis and Maksim (1967) and Gertsbakh and Gurevich (1977). Although the initial application of DFs was to the Russian AEROFLOT fleet it has subsequently attracted more attention on bus scheduling than aircraft scheduling. Here we discuss the revival of this method and its crucial use to construct the so-called chain decomposition of the schedule for a single period. We provide a justification for maximizing the number of balanced chains (flight sequences with the same start and end terminals). To do this we propose The Maximal Balanced Chain Problem. These are then converted into a set of infinite periodic flight sequences, each of which can be carried out by a single aircraft. The conversion is carried out by mapping the single period set of chains into an Euler graph. To construct the set of mutiperiod chains that are “balanced”(return to the same terminal at the start) we find all edge disjoint cycle covers of the Euler graph using a modified version of Hierholzer's algorithm. These cycles are converted back into a balanced multiperiod chain solution and modified to conform to any maintenance constraints. To insure maintenance check constraints are satisfied for multiperiod chains, it may be necessary to add deadhead flights. Minimizing the cost of deadhead trips and overnight stays provide the basis for selecting an optimal routing solution. 1. Introduction Because airline scheduling is a very complex problem, it has been tackled by decomposing it into a set of sub problems. The process starts with the design of a flight schedule involving a flight network, based on which markets to serve and their customer demands. Then a set of flights or “flight legs”to meet this demand are determined, each defined by its departure and arrival time. This is followed by the fleet assignment problem which assigns flights to fleets of different aircraft types. Then aircraft routes are determined as the sequence of flight legs flown by individual aircraft. Finally, a crew schedule is determined which consists of a crew pairing followed by crew rostering. In this paper we are interested in the aircraft fleet routing problem. As the aircraft represents the largest cost associated with the operation of an airline, this prompted us to focus on the problem of finding the least number of aircraft required to meet the demand of a passenger flight schedule (FS). When reviewing the literature, we found that most problems start with the assumption that the fleet size and its composition are already fixed. For example, in the aircraft assignment problem it is known at the start that the airline has a fixed number of aircraft of each aircraft type. The solution separates this heterogeneous fleet into homogeneous sub fleets of identical aircraft types assigned to different flight collections. There is no consideration whether the given fleet size is optimal or not. An optimal fleet size is the minimal number of aircraft needed to service all flights assigned to it. If this differs from the original fixed number of aircraft, then there is a need to either rent or buy additional aircraft or dispose of surplus aircraft (both most likely at inflated market prices). Our primary goal then is to find the minimum fleet size for a given fleet type required to service the FS followed by a chain decomposition (CD). A CD is a decomposition of the flights in the FS into chains of sequential flights (or routes) carried out by individual aircraft in the https://doi.org/10.1016/j.orp.2019.100104 Received 5 August 2018; Received in revised form 28 January 2019; Accepted 26 February 2019 ⁎ Corresponding author. E-mail addresses: [email protected] (H.I. Stern), [email protected] (I.B. Gertsbakh). Operations Research Perspectives 6 (2019) 100104 Available online 06 March 2019 2214-7160/ © 2019 Published by Elsevier Ltd. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/BY-NC-ND/4.0/). T fleet. Each flight leg must be included in exactly one chain. A chain/ route must start and end at the same terminal, have feasible flight pair joinings (a flight arriving at a terminal is followed by a flight departing from the same terminal after an acceptable layover time) and satisfy maintenance constraints. This is referred to as the aircraft routing problem. Barnhardt et al. [1] defines a chain (or string) as maintenance feasible, if it satisfies all Federal Aviation Administration and carrier-specified maintenance requirements. The maintenance checks require each aircraft to undergo checks for every 60 h of flying time. However, some airlines may require more severe flying time checks. The maximum time between checks are typically restricted to three to four calendar days. As these checks can be quite long (typically 4–6 h), these checks are performed at night. These checks can be conducted at the aircrafts home base or a designated terminal, where it is assumed the necessary equipment and labor are available. We do not consider the long-term maintenance checks which are typically performed once a year. The aircraft routing problem has been addressed by many researchers in the past, especially as an integer mathematical programming problem. [2–7]. We adopt a simpler approach based on deficit function (DF) theory developed in the 1960–70s by Linis and Maksim [8] and Gertsbakh and Gurevich [9], primarily because of its transparency, visual appeal, and polynomial complexity. Each DF is associated with a terminal and is a step function which has unit changes at flight departure and arrival times. The DF is a discrete multimodal function with regions of maximal values between which are valleys referred to as “hollows”. This admits to building chains by joining flight arrivals to departures. After a chain is completed, its flights are removed and the DFs are redrawn with the remaining flights. Then other chains are extracted until no flights remain. Each chain then becomes a single aircrafts route. It is desirable to obtain a CD in which all its chains are fully balanced, that is one in which each aircraft returns to the terminal from whence it started. If the aircraft does not return in time to undergo required maintenance checks, it is necessary to add costly empty (deadheading) flights to bring the aircraft associated with an unbalanced chain and its crew back to the terminal from which it originated. To avoid this situation, we consider a 2-stage process: First a CD is found containing the maximal number of single period chains; and secondly, we offer a method to convert any unbalanced chains into balanced multiperiod chains (MPCs). A MPC is a concatenation of single period unbalanced chains. It should be noted, that although this investigation addresses the airline schedule problem it has applications to other domains as well, such as ground transportation and even jobmachine scheduling. The paper is organized as follows. Section 2 provides some background on DFs and aircraft routing. Section 3 describes the DF approach and the minimum fleet size theorem. Section 4 describes a method for determining a CD. Flight joining rules are introduced with the aid of hollow analysis. In Section 5 the procedure for finding a balanced aircraft routing that insures a daily repeating schedule of flights. This proceeds in three stages: Stage 1- Find the Maximal Single Period Balanced Chain Decomposition, Stage 2 -Converting all single period unbalanced chains into a Basic Set of balanced MPCs. This stage employs an Euler graph for converting the unbalanced chains in a CD into a ‘basic set’of MPCs, Stage 3 - Expanding the basic set of MPCs in order to create a daily repeated aircraft schedule. In 6 the routing solution for a 30 flight - 4 terminal example in terms of a periodic set of balanced MPCs is displayed. Sections 7 and 8provide a method to ensure that the maintenance constraints are satisfied for each aircraft route, and a means for finding the optimal routing solution among alternatives, respectively. In Section 9 an analysis and comparison of the presented DF model with other approaches such as integer programming formulations is given. The final section provides a conclusion. 2. Background on deficit functions Much of the research on aircraft routing assumes a single fleet for a fixed type of aircraft. Two approaches have been taken. The first is to solve a fleet assignment problem where the numbers of aircraft of different types, owned by the airline, are given constants. The fleets of each aircraft type have different capabilities to service flights according to the number of passengers, range of travel, costs, etc. The solution to the fleet assignment problem decomposes the set of flights in the original flight schedule into separate subsets to be operated by fleets of a single type. Mancel et al. [10] provide a state of the art for the airline fleet assignment problem. Most authors formulate the problem as an integer linear program. For example, Ozdemir et al. [11] solve a fleet assignment problem using Turkish Airlines data and Markus et al. [12] apply it to Lion Air in Indonesia. The second approach is to determine directly the minimum fleet size (of a given type) required to service the FS assigned to the fleet. Once the minimum number of aircraft is determined, the routes, or chain of flights, for each aircraft is found. This in fact partitions the FS into subsets, each being serviced by a single aircraft. The seminal paper of Dilworth [13] on a decomposition theorem of partially ordered sets was the first to address this problem. Methods such as mathematical programming and network flows, were carried out in the 1950s and 70s by Dantzig and Fulkerson [14] Bartlett [15] Salzborn [16]. Then there is the infinite vehicle chain problem approached from a theoretical point of view of periodic scheduling problems and partial orders of flights Serafini and Ukovich [17] Orlin [18] Gertsbakh and Serafini [19]. In parallel, around the decade of the 70s, we see the start of the DF approach for solving minimum fleet size and CD problems. DFs were first introduced by Linis and Maksim [8] Gertsbakh and Gurevich [9] Gertsbakh and Gurevich [20] for airline scheduling. An English translation of Linis and Maksim's 1967 paper [8] is provided in Linis and Maksim [21], along with a discussion of its merit in Gertsbakh et al. [22]. This thread has been continued with a few scattered papers in the 80s, and subsequently by the work of Ceder and colleagues with regard to public transit bus and rail scheduling. Liu and Ceder [23] provide an excellent 50-year retrospective of the use of the DF approach related to public transport. Lui and Ceder [24] incorporate the DF approach to help solve an integrated public transit timetable and vehicle scheduling problem. The insertion of “deadheading trips”to further decrease the fleet size was developed by Ceder and Stern [25], Stern and Ceder [26] in the context of bus transit scheduling. A second method for reducing the fleet size, using possible shifts in departure times within given tolerances, is described in Ceder and Stern [27]. DFs have also been applied to machine job scheduling by Gertsbakh and Stern [28]. In a recent paper, Gertsbakh and Stern [29] describe the use of DFs for crew planning and rostering in aviation. 3. Deficit function and minimum fleet size theorem 3.1. Definitions and notations Let I = {i: i = l, . . ., n} denote a set of required flight legs. The flights are conducted between a set of terminals (airports) K = {k: k = l, . . ., q}. Each flight is to be serviced by a single aircraft and each aircraft is able to service any flight. For a flight ideparting from terminal k i d and arriving at terminal k i a ,let t i d and t i a represent its departure and arrival times, respectively. The arrival time includes an extension of the duration of each flight by a minimum turn-time. A flight leg i is represented as a quadruple (t i d ,t i a ,k i d ,k i a ). A flight schedule FS is a set of all flights {(t i d ,t i a ,k i d ,k i a ): k i d ,k i a ∈K, i ∈I}. Two flights i, j may be serviced sequentially (feasibly joined) by the same aircraft only if the precedence relation R is satisfied. ≺∋ ≤ = R ij t t andk k: iajdiajd(1) H.I. Stern and I.B. Gertsbakh Operations Research Perspectives 6 (2019) 100104 2 Here the arrival time has been prolonged to include the minimum turn time between any two flights. Denote [0, T] as a daily schedule horizon (say 24 h) where flights are excluded from crossing the 24:00 h line. All flights depart and arrive within this time interval, i.e., 0≤<≤tt T. d ia iSuch a daily FS is said to be balanced. Adeficit function, DF(k, t), is a step function defined for each terminal k, whose value at time t is equal to the number of flight departures less the number of arrivals over the interval [0, t]. The function changes by +1 and −1atflight departure and arrival times, respectively. At these times, the DF is right-continuous Theorem 1. Minimum Fleet Size Theorem The minimum number of aircraft required to service a FS equals the sum of the Max values of qDFs. Here mrepresents the minimum fleet size. ∑ =∈ = mMax{DF(k,t)|t[0,T]} k1 q (2) Proof. The proof may be found in Linis and Maksim [8]. Corollary 1. The DFs also provide the starting numbers of ac at each terminal k as: ∈ M ax{DF(k, t)|t [0, T]} 3.2. DF as a function of plateaus and hollows A DF is a discrete step function containing multiple regions or intervals of maximal values (plateaus). Regions between plateaus are denoted as hollows. Let the maximal value of DF(k, t) = DF(k). Let r(k) equal the total number of such maximal regions for DF(k) defined by a tuple of adjacent points M k r =[s k r, e k r ],r=1,…, r(k). Here, rrepresents the rth maximal interval ordered from the left. Note, s k rand e k r represent departure and arrival flights from and to terminal k, respectively (not necessarily the same). The one exception occurs when the DF reaches its maximum value at the end of the horizon in which case M k r(k) has a departure not followed by an arrival, and e k r(k) =T.Define the set of hollow intervals (regions) for each DF(k) as; H k0 = [ 0, s k1 ],H k1 =[e k1 , s k2 ],…,H k r(k) =[e k r(k) , T]. H k0 and H k r(k) may consist of only one point. It is now possible to describe the partition of the schedule horizon of DF (k, t) into a sequence of alternating hollow and maximal intervals, i.e., (H k 0 ,M k1 ,H k1 ,...,M k r ,H k r ,…., M k r(k) ,H k r(k) ). An example of a FS named FS30 is given in the Appendix. The FS and its corresponding set of DFs is displayed in Figs. 1 and 2, respectively. In Fig. 1. we see that all flights are carried out within a daily 24 h schedule. A homogeneous fleet is assumed allowing any aircraft to carry out any flight. For this example, we see from the DF's max values that the minimum fleet size is12. From Corollary 1 we see that the starting number of aircraft at terminals A, B, C, D are 1, 4, 4, 3, respectively. 4. Chain decomposition (aircraft routing) Below we show how to use DFs for a decomposition of the FS into vehicle routes or chains. It should be noted, that aircraft route and chain are used interchangeably. A Chain (C) is an ordered sequence of flights [f 1 ,f 2 ,.., f i, …,f c ] such that, t i a ≤t i+1 d , and k i a =k i+1 d ,∀i=1,…c-1. A set of chains is a CD; if all flights in a chain are serviced by a single aircraft, and each flight i∈Iis included exactly once in a chain. It is convenient at this point to introduce the importance of hollows in the construction of aircraft chains. 4.1. Hollow analysis Hollows are an important region of the DF to look for possible joinings between arrival and departure flights to form chains. In order for a flight jto be joined to a previous flight iit needs to be a feasible joining satisfying (1). In fact, the 2 hollows in DF(C) allow for a single feasible joining. We refer to such hollows as a Vhollow of depth 1.AV- Hollow of depth nis monotone decreasing and increasing and corresponds to a sequence of narrivals followed by ndepartures with the number of possible multi-joinings is n!. Any arrival in a V-Hollow can be joined with any departure. However, there are more complicated hollows which we refer to as U-Hollows. A U-Hollow also has narrivals and ndepartures, but exhibits at least one arrival event which is preceded by one or more departure events. For U-Hollows, with n arrivals and departures, the number of feasible joining pairs is less than n!. This feature implies that the number of CDs is finite and bounded. 4.2. Feasible flight joinings The problem of finding the number of feasible pairs of joinings can be formulated as an assignment problem with inadmissible cells whereby only a feasible solution is sought. The inadmissible cells are determined by identifying the cases in which an arrival event is preceded by one or more departure events. For example, H B3 in Fig. 2. Theorem 2. (Necessary Hollow Joinings) In creating chains, an arriving flight in any hollow must be connected to a departing flight in the same hollow, in order to achieve a chain decomposition equal to the minimal fleet size. Conversely, connecting an arrival flight in a hollow to a departing flight in any other hollow will result in a chain decomposition exceeding the minimal fleet size. Proof. A proof can be found in Gertsbakh and Gurevich [9]. Corollary 2.1. For any feasible CD, it is necessary that the single arrival and departure of all Hollows of depth 1 must be joined. Proof. The theorem states for “any hollow”. A Hollow of depth 1 is the simplest hollow. Corollary 2.2. The two flight legs comprising a hollow of depth 1 may be replaced by a single representative flight. Let t i a and t j d be the arrival and departure times of flights iand j defining a hollow of depth 1 in terminal k. According to Corollary 2.1 flights iand jmust be joined. Hence, they can be replaced by a dummy representative flight = f ttkk( ) ij ijdijaijdija ,, where =t , ijd === t ttkkkk,, , idijajaijdidijaj a . 4.3. Chain decomposition Proposition 1. Given a FS and its associated set of q DFs. Let m equal the minimum fleet size. Then m flight chains C 1 ,C 2 ,…,C m may be constructed. Proof. Gertsbakh and Gurevich [9]. Such a construction is said to be a CD,and may be determined by the following algorithm. Chain Decomposition Algorithm For a FS of nflight legs, q terminals, and a fleet size of m. Initialization: Replace all necessarily joined jobs in hollows of depth 1 by a single job according to Corollary2.2. 1 Starting from the maximal valued DF, say DF(k, t). Select any flight i with its starting point t i d ∈H k 0. Find the arrival time of this flight, t i a , at some terminal k ai . Let k= k ai and join it to a feasible flight departure t j d ∈H k r according to Eq (1). Continuing joining a flight arrival with a departure within each hollow visited, until some flight varrives at some end hollow H k r(k) at time t v a . Here no departure flight is available to feasibly connect a flight v. 2 Remove the chain of flights from the DFs. Recompute the DFs. The value of the total Max DF decreases by one. H.I. Stern and I.B. Gertsbakh Operations Research Perspectives 6 (2019) 100104 3 3 Repeat until all DF(k)s have MaxDF(k)=0 4 This results in a feasible CD. Gertsbakh and Gurevich [9] also prove that the algorithm terminates after a finite number of msteps. Proposition 2. The Chain Decomposition Algorithm is of polynomial complexity O(nq). Proof: Step 1. Find max valued DF ⇒O(q). Find a flight number in the FS array ⇒O(n). Step 2. Sequentially check list for element k > arvtime, and if k< current min ⇒O(2n) Step 3. Update FS and n by removing the flights in the chain C(i), by finding the flight number in a list ⇒O(n). Update DFs and remove flights in FS, Precompute plateaus and hollows. All that is needed is a list of max values of each DF (Find all max values of a list and repeat for each DF⇒O(nq) Repeat all m times: ++ ++ =mOqOnOnOnOnq[()()(2)()()] ++q n nq m O nq ( 4)() . 5. Finding balanced aircraft routes Given a CD comprised of a set of chains Cof cardinality m. If for a given chain C=[f 1 ,f 2 ,.., f i, …,f c ], the start and end terminals are the same, i.e.; k f1 d= k fc a then the chain is said to be a balanced chain. Otherwise it is an unbalanced chain. These chains cover a single period and are referred to as 1T chains.ACcan be partitioned into β and β of balanced and unbalanced chains, respectively. It is rare that a 1T CD is fully comprised of balanced chains. In order to obtain a 1T CD (a set of aircraft routes) that are fully balanced it is necessary to add costly empty (deadheading) flights to bring the aircrafts associated with the unbalanced chains and their crews back to the terminal from which they originated. To avoid this situation a method is proposed to convert the set of unbalanced 1T chains into a family of balanced chains. Such chains are formed by concatenating several 1T unbalanced chains into Balanced MPCs. Also, longer MPCs increase the number of nights and the cost for crew and aircraft to be away from the home base. Finally, the number and length of MPCs subsequently increases the complexity of finding crew pairing solutions. All of this provides a justification for finding a 1T CD that has the minimum number of MPCs, or equivalently a CD that has the maximum number of IT balanced chains. Thus, we propose a Maximal 1T Balanced Chain Decomposition problem (MBCP). As our final goal is to obtain balanced aircraft routings that insure a daily repeating schedule of flights we propose a three-stage process. In Stage 1 we solve the MBCP. In Stage 2 we convert any remaining 1T unbalanced chains into a Basic Set of MPCs. In Stage 3 we expand the Basic set of MPCs in order to create a daily aircraft schedule. 5.1. Stage 1: finding the maximal balanced chain decomposition Here we wish to find the Maximal 1T Balanced Chain Decomposition among all possible CDs. Let  represent the set of all possible CDs associated with a FS where, each CD is a set Cof chains of cardinality m(m= min fleet size). Let C i (k)∈Sbe the ith set of chains partitioned into βand β of balanced and unbalanced such that the cardinality of βis k. Partition  into subsets S(k); k = L(k),..,U(k), where S(k) is the set of all CDs of the form C i (k) and =∅ ∀ 〈 ∀ 〉Sk k Lk and kUk() , () ( ) .Note, that L(k) and U(k) are not know a priori. Then the MBCD problem is defined as find the subset: Fig. 1. The flight schedule FS30 (k=1,2,3,4=A, B, C, D). H.I. Stern and I.B. Gertsbakh Operations Research Perspectives 6 (2019) 100104 4 ∋= = … =SkkMaxkkLk Uk iekUk() {: (), , ()}, . .; () (3) The MBCP can be formulated as a multi commodity network problem which is NP-hard, and therefore we provide a probabilistic heuristic method. For this purpose, we have developed a method for generating random chains and selecting the “best”from this set. To generate a random chain each arrival in a hollow is joined to a randomly chosen (feasible) departure in the same hollow. These arrival - departure pairs are then placed in a “list of flight joinings”. A chain builder procedure then traces through the pairs to extract a chain and the list is updated. The procedure terminates when the list is empty. The formal algorithm follows. 5.1.1. Random Chain generation algorithm 1 Denote each pairwise arrival - departure joining as a tuple (i,j). 2 Combine all tuples into a list of joinings J. 3 Chain Builder (Create a Chain from J) aDefine a flight chain connection rule (FCCR). For any two tuples in J,if(i-j) and (j-k) connect them into a 3-flight chain of the form (i-j-k). b Begin with a Start tuple (0-i)inJ c Using the FCCR find the tuple (i,j) and connect it to (0-i) to obtain (0-i-j). Find the tuple (j,k) connect to (0-i-j) to obtain (0-i-j-k). Continue until an end tuple (v-0) is found. d The resulting chain is C= [0-i-j-k-…..-v-0] e Update J. 4After the chain is found remove the tuples from Jthat formed it. 5IfJis empty STOP, otherwise return to Step 3. 5.1.2. Balanced chains and 100 random CDs For the example FS30 we generated 100 random CDs. Let RS(k) denote the set of randomly generated CDs with k balanced chains. Let the cardinality of RS(k) be r(k). The distribution of r(k) is shown in Fig. 3. This figure helps us understand the underlying structure of the solution space of balanced CDs. In column 3 of Table 1 (Term(s,i) - Term(e,i)) represents the ith chain's start and end terminals. 5.2. Stage 2: converting unbalanced chains into a basic set of balanced MPCs At this stage we describe a method to convert the set of unbalanced 1T chains into a family of balanced chains. We introduce the notion of a chain period equal to the number of unbalanced 1T chains combined to form a MPC. For example, consider two unbalanced 1T chains, represented by their terminal endpoints (A-B) and (B-A). Then joining (B- A) to (A-B) forms a chain [A-B-A] with a chain period of 2T. Note, connecting the last flight, say x, in B-A to the first flight, say y, in A-B is a feasible joining because it occurs at the same terminal A and t y d >t x a is satisfied since y departs the day after x arrives. If the schedule is balanced there always exist a set of balanced MPCs. This conversion can be carried out by constructing an Euler graph, and using a modified version of Hierholzer's algorithm, to extract a set of disjunctive cycles. Each cycle becomes a MPC. As an example, we show, using the CD RS38, how to construct the associated Euler graph, and from it extracting the basic set of balanced MPCs. Also, after how to take a basic MPC and after applying circular shifts generate shifted copies in order to insure all flights in the FS are serviced daily. Definition. AMPC is a balanced chain comprised of nordered unbalanced 1T chains [C 1 ,C 2 ,…,C i, C i+1 ,…,C n ]. Each pair of successive unbalanced chains C i, C i+1 has Term (e, i) = Term (s, i+1). Also, as a multiperiod balanced chain Term(s,1) = Term (e, n). Fig. 2. Deficit functions for flight schedule FS30, k= 1, 2, 3, 4 (A, B, C, D). H.I. Stern and I.B. Gertsbakh Operations Research Perspectives 6 (2019) 100104 5 A MPC does not have any interior balanced sub chains. It is convenient at times to refer to an MPC with nordered 1T chains as a nT MPC. Such a chain is said to have a Chain Period of nT. The following propositions will be useful in designing an algorithm to perform this conversion. Proposition 3. Given a Balanced FS, and its CD with a set of chains C={C 1 ,C 2 ,…,C k ,..,C m }. Let C k have a start flight i departing from Term(s, i), and an end flight j arriving at terminal Term(e, j) Let Cs be the set of chains departing from Term(s, i), and Ce the set of chains ending at Term(e, i) where Cs ⊂C and Ce ⊂C then the total number of chains with Term(e, j) and the total number of chains with Term(e, i) are equal, i.e.; /Cs/ = /Ce/. Proof. This is true since 1T chains must start at some terminal and end at another terminal within a single time period (since the FS is balanced i.e.; all flights start and end within a single time period) Proposition 4. Given a Balanced FS, and a CD, for all chains in β the total number of chains whose starting terminal is Term(s, i) equals the total number of chains whose ending terminal is Term(e, j), where for a given chain in β ¯Term(s, i) ≠Term(e, j). Proof. This follows from Proposition 3 after removing all balanced 1T chains from the CD. For example, in Table 1, the number of unbalanced chains that start with terminal C equals 2 as do those that end with terminal C. This is also true for terminal D. Also, chain 12 starts at Band chain 11 ends at B. 5.2.1. Euler graph and Hierholzer's algorithm Euler's Theorem, first given by Hierholzer in 1873 states: A directed graph has an Eulerian Cycle if the graph is connected and all vertices have even degree Biggs et al. [30].To convert 1T unbalanced chains to balanced MPCs. Define a directed graph G (E, V), where Vis a set of vertices and Eis the set of directed edges (i, j) from vertex ito j. Let each vertex in Gcorrespond to a terminal in V. Let each unbalanced chain iin β ¯, with Dept Term(s,i) ≠Arv Term(e, j), be represented as a directed arc (i, j) in E. Balanced 1T chains are loops at a single node, and after stripping away looped edges corresponding to balanced chains it becomes a directed Euler graph (see Fig. 4.). All vertices are of even degree according to Proposition 4. A cycle in an Euler graph comprised of ndirected edges (1, 2), (2, 3),…,(n,1), corresponds to a nT MPC of the type [ 1-2 2 - 3 ….. n - 1]. Hierholzer's algorithm (1873) finds a set of disjunctive cycles as it traverses a Euler graph. We denote this set of disjunctive cycles as the basic set. 5.2.2. Finding the basic MPC set Theorem 3. Conversion Unbalanced to Balanced Given a balanced FS whose 1T CD chains are partitioned into βand Fig. 3. The distribution of r(k) for example FS30. Table 1 Chain decomposition for RS38 (* = balanced chain). Chain Flights (Start-End) 1 [17-19] (A-A)* 2 [1-15] (B-B)* 3 [16-26-27-28] (B-B)* 4 [14-2] (B-B)* 5 [25-22-18-9] (C-C)* 6 [10-6-11-12] (C-C)* 7 [29-21-30] (D-D)* 8 [13] (C-D)’ 9 [5-24] (D-C) 10 [8] (C-D)” 11 [3-20] (D-B) 12 [7-23-4] (B-C) H.I. Stern and I.B. Gertsbakh Operations Research Perspectives 6 (2019) 100104 6 β ¯. There exists a conversion of β into a set of balanced MPCs (Using a modified Hierholzer's algorithm). We denote this set as the basic set of MPCs. Proof. After constructing an Euler graph from the set of unbalanced single period chains, according to Proposition 4 each terminal type appears the same number of times at the start and end of the chains. This insures that each vertex in G, corresponding to a terminal in V,isof even degree. A cycle in an Euler graph comprised of n directed edges (1, 2), (2, 3),…,(n,1), corresponds to a nT MPC of the type [1-22-3….. n -1]. Each edge represents an unbalanced single period chain between a pair of vertices representing its start and end terminals. Traversing each cycle from any of its vertices and back covers a sequence of edges (unbalanced chains). Starting and ending at the same vertex is tantamount to starting and ending at the same terminal, and hence the cycle represents a balanced multiperiod chain. Corollary 3.1. The conversion of a set of unbalanced chains from a feasible CD results in a basic set of MPCs such that each 1T unbalanced chain appears exactly once in some MPC and the set of MPCs contains all 1T unbalanced chains. Proof. This follows from the fact that a complete cover of the Euler graph provides a set of disjunctive cycles. The CD chains for example RS38 are shown in Table 1. Note, since chains 8 and 10 have different flight sequences, we denote them by C-D’ and C-D”, respectively. Balanced chains are indicated by an asterisk. In the CD, there are 7 balanced 1T chains, the remaining are unbalanced β ¯= {(B-C), (C-D)’, (C-D)”, (D-B), (D-C)}. However, according to Proposition 4 for each terminal type that appears at the start of an unbalanced chain it also appears end of some other unbalanced chain. The corresponding Euler graph is shown in Fig. 4. where the loops represent the 1T balanced chains. After stripping the loops, we are left with a 3 vertex directed connected Euler graph. Referring to the Euler graph in Fig. 4 start from an arbitrary node B and traverse the unvisited edges (B, C), (C, D)’, (D, B). Remove this cycle from the graph, but retain nodes C and D in the reduced graph as they have unvisited arcs attached to them. Select any one of the retained nodes, say C, and traverse the arcs until a second cycle (C, D)”, (D, C) is obtained. We denote this set of disjunctive cycles as a basic set: [(C-D)”(D-C)], [(B-C) (C-D)’(D-B)]. Here we have one 2T MPC and one 3T MPC. Note, because of the two arc traversal options from vertices C to D, there exists a second basic set from the set of disjunctive cycles [(C-D)’(D-C)], [(B-C) (C-D)”(D-B)]. The conversion takes O(E) time, using Hierholzer's algorithm for an Euler graph G(E,V), since each arc is traversed exactly once. 5.3. Stage 3: Expanding the basic set of MPCs Because the basic set of MPCs has “collected”the unbalanced 1T chains to cover a span of several periods, it is no longer the case that all flight legs are serviced on a daily basis. Thus, it is necessary that all interior 1T chains of the MPCs be clockwise circular shifted in order to ensure that all flight legs in the FS appear in a daily schedule. The number of disjunctive cycles and hence the number of basic MPCs is less than the number of unbalanced 1T chains. This is true because a cycle is comprised of at least 2 1T unbalanced chains. It follows that the number of basic MPCs plus the number of 1T balanced chains is less than m. Because the unbalanced chains have been collapsed into the basic chains, we need to resurrect the total chain count to m. This can be done by expanding each MPC in the basic MPC set into additional MPCs, in order to restore the total number of MPCs (including the 1T balanced chains) to mchains. This is necessary because after the concatenation, the 1T chains in the basic MPC appear in successive periods. In order expand the basic MPCs, to ensure that all flights in the FS are flown each day, we need to apply several Clockwise Circular Shifts (CSS)s to each basic MPC. This will insure the construction of an aircraft routing that includes a daily repeating schedule of flights. Corollary 3.2. Clockwise Circular Shifts: Given a MPC of nordered 1T chains (a chain period of nT), where MPC= [C 1 ,C 2 ,..,C i ;C i+1 ,..C n ]. The chain can be split at any interior point into two parts (say, between C i and C i+1 ) and a CCS operation applied. The new MPC* = [C i+1 ,…,C n ; C 1 ,…,C i ]. After n-1 CCS operations the MPC provides n-1 offspring MPC*s. When added to the original MPC a set of ndifferent nT MPCs is obtained. The CCS operation preserves the balanced aspect of the MPC. Proof. After applying the CCS operation to all possible interior points, n-1 offspring MPC*s are obtained. These n-1 MPCs each of period nT, plus the original nT MPC results in ndifferent nT MPCs. Also, after the CCS the new MPC is balanced. Let the shift point for the MPC be between C i and C i+1 . Recall for a feasible MPC each pair of successive unbalanced chains C i, C i+1 has Term (e, i) = Term (s, i + 1). After the CCS, the first 1T chain becomes C i+1 as with starting terminal Term (s, i+1)and the last 1T chain becomes C i with ending terminal Term (e, i). For a basic set of MPCs, each nT MPC may be expanded in O(n) operations because the CCS operation finds n-1 shift points and for each step it takes one operation to rearrange the two parts. As an example, let a basic MPC with a chain period of 3T be [8] [3- 20] [7-23-4]. Here we have 3 1T unbalanced chains. The flights in periods 1, 2 and 3 are 8, 3,20 and 7,23,4, respectively. After providing 2 CCSs we obtain the following 3 MPCs: [8] [3-20] [7-23-4], [3-20] [7- 23-4] [8][7-23-4], [8] [3-20]. It can now be seen that in each period all flights 8, 3, 20, 7, 23, and 4 are serviced daily. Continuing with example RS38 we create the set of all m balanced MPCs. Here the elements of each balanced MPC in the basic set are CCSed to obtain additional balanced MPCs. For the 2T basic MPC we obtain [(C-D)”(D-C)] and [(D- C) (C-D)”]. For the 3T basic MPC we obtain [(B-C) (C-D)’(D-B)] and [(C-D)’(D-B) (B-C)] and [(D-B) (B-C) (C-D)’]. This results in five MPCs (2 of length 2T, and 3 of length 3T) as shown in Table 2. 6. Aircraft routes for a daily repeating schedule of flights Each 1T chain is repeated periodically and represents the trajectory of a single aircraft. All 2T chains in the basic set are repeated twice after being clockwise circular shifted. This represents the trajectory of two aircraft doing in fact the same sequence of flights with a shift by one T. In general, each nT MPC in the basic set is CCSed n times to represent the trajectories of n aircraft repeating periodically the same sequence of flights with shifts of 1T to (n-1)T. As an example, the complete set of aircraft trajectories for RS38 is shown in Table 2. The terminals visited (shown in the 5th column) are those for the start-end terminals of the aircraft flight sequences. The last column shows the aircraft home base, and the MPC lengths in column 3 indicate the number of days to return home after leaving the home base. At each 24 h time period all of the 12 original chains whose flights constitute the entire number of flights in the FS are serviced by the 12 aircraft fleet as shown in Fig. 5. The figure shows three 24 h time periods, because C B D (C-D)’ (C - D) ” A A Fig. 4. Euler Graph for Example RS38. H.I. Stern and I.B. Gertsbakh Operations Research Perspectives 6 (2019) 100104 7 the longest MPC is of length 3T. This is repeated every 3 days in order to obtain a periodic set of aircraft routings. 7. Checking the maintenance constraints The schedule must now be checked to ensure that the maintenance constraints are satisfied. If it is necessary to return to the aircrafts home base after 2 days in order to perform maintenance, then it is necessary to introduce deadheading trips [B-C], [C-D] and [D-B] at the end of the second period in the 3T aircraft trajectories of chains 10,11 and 12, respectively. All 1T and 2T trajectories automatically satisfy this requirement. After the deadheading trips are added feasible flight joinings are preserved by switching the last period of the 3T MPCs. To see this more clearly, consider chain 10 in Fig. 5 which starts at terminal C. After inserting a deadheading trip [B-C] at the end of period 2, the aircraft has returned to its base at terminal C for overnight maintenance. However, now at the start of period 3 the aircraft it must continue from terminal B. It appears that to resolve this situation a second reverse deadheading trip [C-B] must be added. However, this is easily avoided by continuing with the flights in period 3 of MPC 11. Then MPC 11 continues with the 3rd period of MPC 12 and MPC 12 continues with MPC 10 s 3rd period. The same principle applies if a maintenance constraint on the total air time of an aircraft is exceeded. In our case even a more severe check of every 40 h of total air flight time is satisfied, as it occurs after the 2-day return constraint. If the maintenance constraint requires each aircraft to return to its home base after every 3 days, then the current schedule need not be changed. 8. Finding the optimal routing solution Many consider the aircraft routing problem one of finding a feasible solution. However, we have shown that there are many alternative Table 2 Multiperiod Aircraft Trajectories for RS38. Aircraft Trajectory Original Chain Sequence MPC Length Aircraft Flight Sequence Start-End Terminals Home Base 1 1 1T [17-19] A-A A 2 2 1T [1-15] B-B B 3 3 1T [16-26-27-28] B-B B 4 4 1T [14-2] B-B B 5 5 1T [25-22-18-9] C-C C 6 6 1T [10–6-11-12] C-C C 7 7 1T [29-21–30] D-D D 8 8,9 2T [13] [5-24] C-D-C C 9 9,8 2T [5-24] [13] D-C-D D 10 10,11,12 3T [8] [3-20] [7–23-4] C-D-B-C C 11 11,12,10 3T [3-20] [7-23-4] [8] D-B-C-D D 12 12,10,11 3T [7-23-4] [8] [3-20] B-C-D-B B 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 6869707172 Time (Hrs) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 Chains MultiPeriod Chain Decomposition for RS38 1T 2T 3T 1T 1T 1T 1T 1T 1T 1T 2T 2T 3T 3T 3T Term TermFlt 1217 2119 2414215 2116 1226 2327 3228 2414 422 3225 2122 1218 239 3210 2363211 2312 4129 1221 2430 1217 2119 2414215 2116 1226 2327 3228 2414 422 3225 2122 1218 239 3210 2363211 2312 4129 1221 2430 1217 2119 2414215 2116 1226 2327 3228 2414 422 3225 2122 1218 239 3210 2363211 2312 4129 1221 2430 3413 4252324 348 4131220 2171223 234 4252324 3413 3413 4252324 4131220 2171223 234 348 2171223 234 348 4131220 Fig. 5. Aircraft Trajectories for RS38 over a Chain Period of 3T. H.I. Stern and I.B. Gertsbakh Operations Research Perspectives 6 (2019) 100104 8