Refueling strategies to maximize the operational range of a nonidentical vehicle fleet

Recently Mehrez et al., Mehrez and Stern and Melkman et al. studied a vehicle fleet refueling problem that arises in military applications and is aimed at maximizing the operational range of the fleet. More specifically, they investigated the problem of maximizing the range of the last vehicle from a fleet of n vehicles by employing a pure refueling chain strategy. However, the problem is solved only for the vehicles with the same fuel consumption rate or the same fuel capacity. This paper is aimed at solving the problem of a more general case where vehicles may have different fuel consumption rates and different fuel capacities. Based on the analysis of fuel demand and supply curve, a recursive procedure which requires only O(n) calculations is developed to solve the linear programming problem of maximizing the operational range for a given refueling chain. A pairwise interchange rule is also provided to improve the maximum operation range by switching the adjacent vehicles in a refueling chain. Finally, a heuristic approach is suggested for finding an optimal refueling chain. Computer simulations show that for n = 6, by using the heuristic approach, the chance of finding an optimal solution is 72% and the average operational range is 97.8% of the optimal. Furthermore, employing an O(n) recursive formula, the solution of a multiple-transfer refueling chain is derived. An illustrative example is demonstrated for a military assessment of the trade-offs between the maximum operational range and the number of fuel transferring operations under the pure and the multiple-transfer chains.