Günter Rote and Guochuan Zhang:

Optimal logistics for expeditions - the jeep problem with complete refilling

SFB-Bericht Nr. 71, June 1996, 34 pages.


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.

  PostScript file (gzipped)   pdf file (gzipped)
other papers about this subject
Last update: April 4, 2002.