Günter Rote and Guochuan Zhang:
Optimal logistics for expeditions - the jeep problem with complete refilling
SFB-Bericht Nr. 71, June 1996, 34 pages.
Abstract
We consider a variant of the classical "jeep problem", whose origins date
back more than 1000 years. We have n cans of fuel on the edge of
a desert and a jeep whose tank can hold the contents of one can. The jeep
can carry one can in addition the fuel in its tank, and therefore it can
establish depots in the desert for later use. When a can is opened, the
fuel must immediately be filled into the jeep's tank. The goal is to find
the farthest point in the desert which the jeep can reach.
We give a simple algorithm for the jeep which improves previous solutions
of Derick Wood (1984) and Ute and Wilfried Brauer (1989), and we use a
linear programming formulation to derive an upper bound which shows that
our solution is optimal.
Last update: April 4, 2002.