Primal dual algorithms for the vehicle refueling problem

Mehrez, Stern, and Ronen have defined a vehicle refueling problem in which a fleet of vehicles travels on a round-trip, self-contained mission from a common origin, with the objective of maximizing the operational range of the fleet. They have defined a ‘pure refueling chain’ strategy for transferring fuel between vehicles in the fleet, and have solved the problem in the special cases when all vehicles have the same fuel capacity or consumption rate. In this article the authors present algorithms for the general case, where vehicles have different capacities and consumption rates. The present approach is based on a new primal dual formulation of the problem. The exact algorithm was effective to find the optimal solution for a fleet size n•13. For larger fleets, the authors present an approximation version of it, which very quickly found a solution within 1% of the maximum possible range for arbitrarily large (up to n=200) fleets. They also show that a small number of the best vehicles can always reach almost the same range as a large fleet.