Jeep problem


The jeep problem, desert crossing problem or exploration problem is a mathematics problem in which a jeep must maximize the distance it can travel into a desert with a given quantity of fuel. The jeep can only carry a fixed and limited amount of fuel, but it can leave fuel and collect fuel at fuel dumps anywhere in the desert.
The problem first appeared in the 9th-century collection Propositiones ad Acuendos Juvenes, attributed to Alcuin. The De viribus quantitatis of Luca Pacioli also discusses the problem. A modern treatment was given by N. J. Fine in 1947.
The jeep problem is related to several other optimization problems:
There are n units of fuel stored at a fixed base. The jeep can carry at most 1 unit of fuel at any time, and can travel 1 unit of distance on 1 unit of fuel. At any point in a trip the jeep may leave any amount of fuel that it is carrying at a fuel dump, or may collect any amount of fuel that was left at a fuel dump on a previous trip, as long as its fuel load never exceeds 1 unit. There are two variants of the problem:
In either case the objective is to maximize the distance traveled by the jeep on its final trip. Alternatively, the objective may be to find the least amount of fuel required to produce a final trip of a given distance.
In the classic problem the fuel in the jeep and at fuel dumps is treated as a continuous quantity. More complex variations on the problem have been proposed in which the fuel can only be left or collected in discrete amounts.
In the camel and bananas problem, the merchant has n units of bananas. The camel can carry at most 1 unit of bananas at any time, and can travel 1 unit of distance on 1 unit of bananas. The market is at m units of distance away. At any point in a trip the camel may leave any amount of bananas that it is carrying at a camp post, or may collect any amount of bananas that was left at a camp post on a previous trip, as long as its banana load never exceeds 1 unit. The problem asks for the maximum units of bananas that can be transported to the market.
In the travelers across the desert problem, the starting base has unlimited units of supplies. Each traveler can carry at most 1 unit of supplies at any time, and can travel 1 unit of distance on 1 unit of supplies. The other base is at m units of distance away. Contrary to the previous two problems, the travelers can't leave supplies in the desert; However, at any point in a trip, accompanying travelers can transfer supplies among themselves, as long as each traveler never carries more than 1 unit of supplies. Each returning traveler must have enough supplies on the way back. The problem asks for the minimum number of accompanying travelers needed to reach the other base. A variant of this problem gives the total number of travelers available, and asks for the maximum distance that can be reached.
In the cars across the desert problem, the starting base has unlimited units of fuel. Each car can carry at most 1 unit of supplies at any time, and can travel 1 unit of distance on 1 unit of fuel. The other base is at m units of distance away. The cars can't leave fuel in the desert; However, at any point in a trip, accompanying cars can transfer fuel among themselves, as long as each car never carries more than 1 unit of fuel. Empty cars with no fuel are abandoned in the desert. The problem asks for the minimum number of accompanying cars needed to reach the other base. A variant of this problem gives the total number of cars available, and asks for the maximum distance that can be reached.

Solution

A strategy that maximizes the distance traveled on the final trip for the "exploring the desert" variant is as follows:
When the jeep starts its final trip, there are n − 1 fuel dumps. The farthest contains 1/2 of a unit of fuel, the next farthest contain 1/3 of a unit of fuel, and so on, and the nearest fuel dump has just 1/n units of fuel left. Together with 1 unit of fuel with which it starts from base, this means that the jeep can travel a total round trip distance of
units on its final trip. It collects half of the remaining fuel at each dump on the way out, which fills its tank. After leaving the farthest fuel dump it travels 1/2 a unit further into the desert and then returns to the farthest fuel dump. It collects the remaining fuel from each fuel dump on the way back, which is just enough to reach the next fuel dump or, in the final step, to return to base.
The distance travelled on the last trip is the nth harmonic number, Hn. As the harmonic numbers are unbounded, it is possible to exceed any given distance on the final trip, as along as sufficient fuel is available at the base. However, the amount of fuel required and the number of fuel dumps both increase exponentially with the distance to be traveled.
The "crossing the desert" variant can be solved with a similar strategy, except that there is now no requirement to collect fuel on the way back on the final trip. So on trip k the jeep establishes a new kth fuel dump at a distance of 1/ units from the previous fuel dump and leaves / units of fuel there. On each of the next n − k − 1 trips it collects 1/ units of fuel from the kth dump on its way out and another 1/ units of fuel on its way back.
Now when the jeep starts its final trip, there are n − 1 fuel dumps. The farthest contains 1/3 of a unit of fuel, the next farthest contain 1/5 of a unit of fuel, and so on, and the nearest fuel dump has just 1/ units of fuel left. Together with 1 unit of fuel with which it starts from base, this means that the jeep can travel a total distance of
units on its final trip. It collects all of the remaining fuel at each dump on the way out, which fills its tank. After leaving the farthest fuel dump it travels a further distance of 1 unit.
Note that
so it is possible in theory to cross a desert of any size given enough fuel at the base. As before, the amount of fuel required and the number of fuel dumps both increase exponentially with the distance to be traveled.
In the camel and bananas problem, the above solution for "crossing the desert" is optimal if, and the maximum units of bananas that can be transported is, which is between 0 and 1. However, if, then the -th camp post is unnecessary, because its location would be farther than the market itself. Instead, the market itself will be the -th camp post. Therefore, the maximum units of bananas that can be transported is, which is between 1 and 2. Similarly, if, then the -th and -th camp post are both unnecessary, and the maximum units of bananas that can be transported is, which is between 2 and 3. And so on.
In the travelers across the desert problem, assume that n travelers set out from the starting base with n units of supplies. After 1/ units of distance, they would have already consumed n/ units of supplies; At this point, one of the travelers should return with 1/ units of supplies, leaving the group exactly units of supplies so that each remaining traveler carries exactly one unit of supplies. The group then travels another 1/ units of distance, consuming / units of supplies; At this point, one of the remaining travelers should return with 2/ units of supplies to safely get back to the starting base, leaving the group exactly units of supplies. The group keeps moving 1/ units of distance and reducing one traveler, until there is only one traveler left carrying exactly one unit of supplies. Finally, this traveler can travel one unit of distance to reach the farthest point. In total, the longest distance n travelers can reach is /+1=2-2/; Equating this to m, one may solve for the minimum number of travelers needed to travel m units of distance. Note that solutions only exist for m<2.
In the cars across the desert problem, assume that n cars set out from the starting base with n units of fuel. After 1/n units of distance, the group would have already consumed exactly one unit of fuel; At this point, they should transfer fuel between them, leave an empty car behind, and carry units of fuel among cars. After another 1/ units of distance, the group would have consumed another one unit of fuel; Again, they should transfer fuel, leave an empty car behind, and carry units of fuel among cars. The group keeps moving and reducing one car, until there is only one car left carrying exactly one unit of fuel. Finally, this car can travel one unit of distance to reach the farthest point. In total, the longest distance n cars can reach is the nth harmonic number, Hn; Equating this to m, one may solve for the minimum number of cars needed to travel m units of distance.

Order independence

Note that the order of the jeep trips is not fixed. For example in the "exploring the desert" version of the problem, the jeep could make round-trips between the base and the first fuel dump, leaving units of fuel at the fuel dump each time and then make an -th trip one-way to the first fuel dump, thus arriving there with a total of units of fuel available. The units are saved for the return trip to base at the very end and the other units of fuel are used to move fuel between the first and second fuel dump, using round-trips and then an -th trip one-way to the second fuel dump. And so on.

Continuous amount of fuel

The number of fuel units available at the base need not be an integer. In the general case, the maximum distance achievable for the "explore the desert" problem with units of fuel is
and maximum distance achievable for the "cross the desert" problem with units of fuel is

Practical applications

The problem can have a practical application in wartime situations, especially with respect to fuel efficiency. In the context of the bombing of Japan in World War II by B-29s, Robert McNamara says in the film The Fog of War that understanding the fuel efficiency issue caused by having to transport the fuel to forward bases was the main reason why the strategy of launching bombing raids from mainland China was abandoned in favor of the island hopping strategy:
See also Operation Black Buck for an application of these ideas. In these missions, conducted during the Falklands War, the Royal Air Force used air to air refueling by staging tankers to enable the Vulcan bombers based on Ascension Island to bomb targets in the Falkland Islands.
The problem is also a theme in Terry Pratchett's book Small Gods, where the Omnian Army propagates a stash of water to cross a vast desert.