Primal dual algorithms for the vehicle refueling problem

George Steiner, Dan Wang and Yufei Yuan

Naval Research Logistics (NRL), 1992, vol. 39, issue 7, 905-918

Abstract: 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 we present algorithms for the general case, where vehicles have different capacities and consumption rates. Our 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, we 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. We also show that a small number of the best vehicles can always reach almost the same range as a large fleet. © 1992 John Wiley & Sons, Inc.

Date: 1992
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199212)39:73.0.CO;2-T

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:39:y:1992:i:7:p:905-918

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().