An iterative graph expansion approach for the scheduling and routing of airplanes

摘要

A tourism company that offers fly-in safaris is faced with the challenge to route and schedule its fleet of airplanes in an optimal way. Over the course of a given time horizon several groups of tourists have to be picked up at airports and flown to their destinations within a certain time-window. Furthermore, the number of available seats, the consumption of fuel, the maximal takeoff weight, and restrictions on the detour of the individual groups have to be taken into account. The task of optimally scheduling the airplanes and tour groups belongs to the class of vehicle routing problems with pickup and delivery and time-windows. A flow-over-flow formulation on the time expanded graph of the airports was used in the literature in order to model this problem as a mixed integer linear program. Most of the benchmark problems, however, could not be solved within a time limit of three hours, which was overcome by what they call the time-free approach (TFA). In the TFA they formulate the problem for a simplified (time-free) graph and use an incumbent callback to check for feasibility in the original graph. While this approach led to very good results for instances, where few time-free solutions were infeasible for the original problem, some instances remained unsolved. In order to overcome this problem, we derive two new exact formulations that include time as variables. Although these formulations by themselves are not always better than the approach from the literature, they allow for an effective construction of graphs which can be interpreted as intermediate graphs between the graph of airports and the expanded graph with vertices for each visit. Using similar relaxation techniques to the TFA and constructing these graphs based on solutions of the relaxations guarantees that only critical airports are expanded. A computational study was performed in order to compare the new formulations to the methods from the literature. Within a time limit of 3 hours, the new approach was able to find proven optimal solutions for all previously unsolved benchmark instances. Furthermore, the average computation time of all benchmark instances was reduced by 90 percent. (C) 2019 The Authors. Published by Elsevier Ltd.