Using deficit functions for aircraft fleet routing

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.