Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/246390 
Year of Publication: 
2019
Citation: 
[Journal:] Operations Research Perspectives [ISSN:] 2214-7160 [Volume:] 6 [Publisher:] Elsevier [Place:] Amsterdam [Year:] 2019 [Pages:] 1-11
Publisher: 
Elsevier, Amsterdam
Abstract: 
We consider the problem of minimizing the number of airplanes needed to fly a fixed 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 -1 at flight 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.
Subjects: 
Deficit function
Flight schedule
Aircraft fleet
Chain decomposition
Aircraft routing
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by-nc-nd Logo
Document Type: 
Article

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.