The airplane refueling problem can be stated as follows. We are given n airplanes which can refuel one another during the flight. Each airplane has a reservoir volume wj (liters) and a consumption rate pj (liters per kilometer). As soon as one airplane runs out of fuel, it is dropping out of the flight. The problem asks for finding a refueling scheme such that the last plane in the air reach a maximal distance. An equivalent version is the n-vehicle exploration problem. The computational complexity of
this non-linear combinatorial optimization problem is open so far. This paper employs the neighborhood exchange method of single-machine scheduling to study the precedence relations of jobs, so as to improve the necessary and sufficiency conditions of optimal solutions, and establish an efficient heuristic algorithm which is a generalization of several existing special algorithms.
