Feeder Routing for Air-to-Air Refueling Operations

We consider the problem of routing a fleet of feeders for civil air-to-air refueling operations. In the air-to-air refueling problem, a fixed set of cruisers requires refueling by a fleet of feeders at fixed locations and fixed points in time. A typical objective function is to minimize the fuel consumption or the total number of required feeders. We formulate a discrete optimization problem based on an ODE model for the fuel consumption of the feeders. The fuel consumption of a feeder depends on its weight. The weight changes over time and depends significantly on the fuel mass stored in the feeder. The fuel mass stored depends on the length of the route and the fuel mass for the requests served. We prove NP-hardness of the problem and develop a column generation approach. We prove several structural properties of the model that allow us to improve the solution method. The resulting method is applicable in practice, which we demonstrate by conducting computational experiments on instances for both random generated demands and demands based on real-world air-traffic. We compare the optimized routes to state-of-the-art solutions. It turns out that mathematical optimization techniques on average reduce the fuel consumption of the feeder fleet by more than half.



View Feeder Routing for Air-to-Air Refueling Operations