Cache and Ferry (How far can a truck go in a desert?) A pick-up truck in the desert gets 10 miles per...

If the truck can siphon gas out of its tank and leave it in the cache,
the answer is:

        rem = (50 n) mod 60

        m = (50 n - rem) / 60

        d = (1 + 1/3 + 1/5 + ... + 1/(2*m-1)) * 600 + 10 rem/(2*m+1)

A much harder problem occurs when the truck can siphon gas, but if it
does, it must siphon the gas into one of the initial barrels.

Here is a table with the amounts of gas that pass the depot sites, the
optimal locations of the depot sites, and the amounts of gas to have in
the tank as one leaves the depot sites on the outbound trip, for the
50-gallon drum, 10 MPG, 10-gallon tank, for the limited cache problem.
An optimal solution is obtained by working from the finish, back, and
using multiple trucks as detailed below. The algorithm which produced
the table is also provided.

The table is read diagonally from bottom to top beginning with the row
with the proper gas amount. Start with the trip 1 column, and fill the
tank to the designated amount, proceed to the location in the distance
column for one row up, and leave a full drum. Continue with the trip 2
column for the beginning row, fill the truck to the designated amount,
proceed up one row and over one column to the trip 1 column, fill the
tank to the designated amount, proceed to the location in the distance
column for another row up, and leave a full drum. For trips 3 to n
start in the appropriate column and move up and over until you reach
the distance column and leave the drum. If a truck arrives at a depot
site with more gas than the table amount, then no gas is added. Gas is
never removed. On return trips, the tank is only filled with enough gas
to reach the next depot site.

Since the drum and tank capacities and mileage are rational numbers,
all the table entries could be expressed precisely as rational numbers,
e.g., Row 3 is

 420-10/11, 600*(1+1/3+1/5+1/7+1/9+1/11)+(600-100/11)/13, 100/11, 10, ...

The solutions all result in 6 full drums a distance 1076.9264 from the
end, and a truck with 5 Gallons in the tank. The rest of the solution
is the same as the unlimited cache solution. The distances obtained for
419 1/11 Gallons or less are the same as the unlimited cache problem
solutions. Once the depot sites are over 1/2 of a tank apart the
limited and unlimited solutions converge. The key to finding
cache-limited solutions is to realize that gas stored in the tank
beyond what is necessary for the return trip is only useful if the
truck continues on past the previously established depot sites.

                          minimum gas in tank on trip out leaving depot site
    Gas     Distance   Trip 1    Trip 2    Trip 3    Trip 4    Trip 5   Trip 6^
 305.00000 1076.9264 Begin unlimited cache solution.
 360.00000 1126.9264 10.000000 10.000000 10.000000 10.000000 10.000000 10.00( 1)
 419.09091 1172.3810  9.090909 10.000000 10.000000 10.000000 10.000000 10.00( 2)
 477.83217 1211.5418  7.832168 10.000000 10.000000 10.000000 10.000000 10.00( 3)
 536.95571 1246.3203  6.955711 10.000000 10.000000 10.000000 10.000000 10.00( 4)
 596.24050 1277.5229  6.240505 10.000000 10.000000 10.000000 10.000000 10.00( 5)
 655.65889 1305.8173  5.658894 10.000000 10.000000 10.000000 10.000000 10.00( 6)
 715.17534 1331.6941  5.175343 10.000000 10.000000 10.000000 10.000000 10.00( 7)
 774.69915 1355.5036  4.761905  9.937248 10.000000 10.000000 10.000000 10.00( 8)
 833.46847 1377.2700  4.353283  9.115188 10.000000 10.000000 10.000000 10.00( 9)
 892.49485 1397.6239  4.070785  8.424068 10.000000 10.000000 10.000000 10.00(10)
 951.71166 1416.7261  3.820439  7.891224 10.000000 10.000000 10.000000 10.00(11)
1011.0079  1434.6947  3.593709  7.414148 10.000000 10.000000 10.000000 10.00(12)
1070.3790  1451.6578  3.392636  6.986344 10.000000 10.000000 10.000000 10.00(13)
1129.8185  1467.7226  3.212949  6.605584 10.000000 10.000000 10.000000 10.00(14)
1188.9094  1482.8741  3.030303  6.243252  9.635887 10.000000 10.000000 10.00(15)
1247.9074  1497.2638  2.877949  5.908252  9.121201 10.000000 10.000000 10.00(16)
1307.0368  1511.0149  2.750205  5.628155  8.658458 10.000000 10.000000 10.00(17)
1366.2771  1524.1794  2.632900  5.383105  8.261054 10.000000 10.000000 10.00(18)
1425.5876  1536.7986  2.523851  5.156751  7.906956 10.000000 10.000000 10.00(19)
1484.9494  1548.9133  2.422932  4.946783  7.579683 10.000000 10.000000 10.00(20)
1544.2517  1560.5412  2.325581  4.748514  7.272365  9.905264 10.000000 10.00(21)
1603.2522  1571.6734  2.226433  4.552014  6.974946  9.498797 10.000000 10.00(22)
1662.3493  1582.4183  2.148987  4.375420  6.701001  9.123934 10.000000 10.00(23)
1721.5317  1592.8012  2.076574  4.225561  6.451994  8.777576 10.000000 10.00(24)
1780.7890  1602.8448  2.008723  4.085297  6.234284  8.460717 10.000000 10.00(25)
1840.1078  1612.5692  1.944879  3.953601  6.030175  8.179163 10.000000 10.00(26)
1899.4662  1621.9911  1.884394  3.829273  5.837995  7.914569 10.000000 10.00(27)
1958.5571  1631.0820  1.818182  3.702576  5.647455  7.656177  9.732751 10.00(28)
2017.6432  1639.9009  1.763763  3.581945  5.466339  7.411218  9.419940 10.00(29)

Here are some examples of how to use the table to construct solutions:

Given 26 full barrels and one partially full barrel with 7.0368 Gallons
in it (for a total of 1307.0368 Gallons), one sees that the optimal
distance is 1511.0149 Miles. There will be 19 (17+1+1) trips starting
with full gas tanks, and 3 trips with partially full tanks. A total of
22 drums will be moved from the start, using 21 round trips and one
one-way trip.

Trip 1 will take a total of 2.750205 Gallons from drums 23-27, and take
drum 22 13.7511 miles and return.

        13.7511=1511.0149-1497.2638,   2.7502=2*13.751/10

Trip 3 will take a total of 8.658458 Gallons from drums 23-27, and take
drum 20 43.2923 miles and return.

        43.2923=1511.0149-1467.7226,   8.6584=2*43.292/10

Notice that this trip does not use any gas from drums 21 or 22.

Trip 6 will take a total of 10 Gallons from drums 23-27, 2.750205
Gallons from drum 22, 2.877949 Gallons from drum 21, 3.030303 Gallons
from drum 20, and 0.199293 [=3.212949-(10-6.986344)] from drum 19, no
gas from drum 18 and take drum 17 a total of 94.2888 miles and return.

94.2888=1511.0149-1416.7261, 10+2.7502+2.8779+3.0303+.1993=18.8577=2*94.2888/10

Trip 21 will fill up at every depot site on the way up, leave drum 2 at
1076.9624, and take just enough gas from each site to return to the
next one.

Trip 22 will empty all the drums as it passes and end up at 1076.9264
with 6 full drums and 5 Gallons of gas in the tank.

Check on gas use at a depot site:

The total gas taken from drum 19 is 0.199293+(15+0.5)*3.212949=50
Gallons.

If only 1306.038 Gallons were available, then the optimal distance
decreases by 10*1/(21*2+1), and the starting gas amounts would decrease
by 2/(21*2+1) for the first 21 trips and by 1/(21*1+1) for the last
trip. No other rows need to be changed.

The gas amounts in the Trip 1 column are always the amounts to go to
the next depot site and back.

The optimal distances can be obtained with other fueling schedules than
those presented here. In particular, there is considerable flexibility
in how to allot the gas at the start and at the first depot site.

Since the question is often posed in terms of optimal distance for a
number of drums, the following table is provided.

# of Drums     8         9        10        11        12        13
Distance   1157.6965 1192.9870 1224.5817 1253.1858 1279.3131 1303.1226
# of Drums    14        15        16        17        18        19
Distance   1325.0961 1345.6239 1364.8743 1382.9705 1400.0449 1416.1740
# of Drums    20        21        22        23        24        25
Distance   1431.3589 1445.8353 1459.6635 1472.8973 1485.5791 1497.7505
# of Drums    26        27        28        29        30        31
Distance   1509.3784 1520.5622 1531.3545 1541.7808 1551.8644 1561.6258
# of Drums    40        50        60        70        80       100
Distance   1637.2676 1703.4762 1757.5352 1803.2453 1842.8159 1908.9429

Entries can be calculated from the first table. For example, for 19 drums,

   1416.1740 = 1416.7261 - 10*(951.71166 - 950)/(15*2 + 1)


Optimal Limited Cache Solutions for the General Case.

Cache and Ferry. (How far can a truck go in a desert?) A pick-up truck
is in the desert beside N gas drums. Each drum is full and contains K
units of gas.  The truck's gas tank is empty and holds 1 unit of gas
and the gets 1 unit of distance per unit of gas. The truck can carry
one drum, whether full or empty, in its bed. How far away from the
starting point can you drive the truck?

Consider the problem beginning at the end of the trip and try to find the
minimum amount of gas that must pass any point. The backwards multiple-truck
statement of the problem is as follows:
  You are given a truck with an empty gas tank and an empty drum. At
  any time you may acquire another truck and drum. The first truck
  produces one unit of gas for every unit of distance traveled.
  Additional trucks produce two units of gas per unit of distance. The
  gas is created in the truck's gas tank. It may be removed and placed
  into any unfilled drum. No gas may be placed into a truck's gas tank
  and all gas must be placed somewhere. You cannot get rid of a truck
  unless you can place all of the gas in its tank and drum into other
  drums.  Your objective is to have traveled as far as possible when
  the total gas in your caravan is N K.

The optimal strategy is clear:
        Never take gas from a tank until it is full, i.e., you have to.
        Get a new truck and drum only when all current drums are full.
In other words, always drive as far as you possibly can before getting
another truck and drum.

Here is the outline of an algorithm to find the optimal solution.
At each stage of the backwards trip: compute the distances that the
current caravan must travel to have each of the following occur:
        1. D1 distance until the total gas in the caravan is N K.
        2. D2 distance until all the available drums are full.
        3. D3 distance until a partially full gas tank is filled.
We must keep track of:
        1. NV number of vehicles=number of drums
        2. NTPF number of partially full tanks
        3. PD amount in the partially filled drum
        4. PT(1,NTPF) amounts in partially filled tanks
        5. GT total gas in the caravan
        6. DT distance traveled to current stage
Determine the minimum of D1, D2, and D3; increment DT; and adjust the other
variables as need (e.g., add another drum and truck if D2 was the minimum).
Continue until GT = N K. Where we get new drums are depot sites and the PT
amounts are the amounts of gas as we leave the sites.


Here is a program to find the values in the first table (or
for any other drum and tank sizes and mileages).

; A program to compute the optimal limited cache distances
; and depot sites for any combination of drum capacities (cdrum),
; tank capacities (ctank), mileage (munit), and number of drums (ndrum).
cdrum=0.D & ctank=0.D & munit=0.D & ndrum=0
read,'cdrum,ctank,munit,ndrum ',cdrum,ctank,munit,ndrum
; Initialize variables.
ratio=cdrum/ctank  &  factor=ctank*munit
gused=0.D  &  gstart=ndrum*ratio
ntrucks=1  &  ntfill=0  &  ntpart=1  &  ndrums=1
tpart=dblarr(ndrum)
dtot=0.D  &  dpart=0.D
; If we only need 1 truck, solve immediately.
if gstart lt ratio+1. then begin
  print,' Trivial. Distance is ',gstart*factor
  stop
endif
ntrucks=2  &  ntfill=1  &  ntpart=1  &  ndrums=2
gused=ratio+1.  & dtot=ratio+1.
; Work backwards.
while gstart gt gused do begin
; How far until another tank is full?
  dtank=10.^10.D
  if ntpart gt 0 then dtank=(1.-tpart(0))/2.
; How far until all the gas is used?
  dend=(gstart-gused)/(2*ntrucks-1)
; How far until another drum is full?
  dfill=(ratio-dpart)/(2*ntfill-1)
; Do you fill a tank first?
  if dtank lt dend and dtank le dfill then begin
    gused=gused+dtank*(2*ntrucks-1)
    dtot=dtot+dtank
    dpart=dpart+dtank*(2*ntfill-1.)
    ntfill=ntfill+1
    ntpart=ntpart-1
    if ntpart gt 0 then for i=0,ntpart-1 do tpart(i)=tpart(i+1)+dtank*2
    tpart(ntpart)=0.
; print, '1. full tank',ntfill,'  gas used',gused*ctank,' Distance',dtot*factor
  endif
; Do you reach the solution first?
  if dend le dtank and dend le dfill then begin
    gused=gused+dend*(2*ntrucks-1)
    dtot=dtot+dend
    dpart=dpart+dend*(2*ntfill-1)
    if ntpart gt 0 then for i=0,ntpart-1 do tpart(i)=tpart(i)+dend*2 
    print, '2. Solution gas used',gused*ctank,' Distance',dtot*factor
  endif
; Do you fill a drum first?
  if dfill lt dend and dfill lt dtank then begin
    gused=gused+dfill*(2*ntrucks-1)
    dtot=dtot+dfill
    if ntpart gt 0 then for i=0,ntpart-1 do tpart(i)=tpart(i)+dfill*2
    ntpart=ntpart+1
    tpart(ntpart-1)=0.0
    dpart=0.
    ndrums=ndrums+1
    ntrucks=ntrucks+1
    print, '3. full drum',ndrums-1,' Gas used',gused*ctank,$
         ' Distance',dtot*factor
    ff='('+str(ntpart)+'f10.6,a24)'
    if tpart(0) gt 0.0 then print, reverse(tpart(0:ntpart-2)*ctank),$
      ctank,' in the next '+string(ntfill,format='(i4)')+' trucks',format=ff
    if tpart(0) eq 0.0 then print, ctank,' in the next '+str(ntfill)+' trucks'
  endif
endwhile
end

;SAMPLE RUN
;cdrum,ctank,munit,ndrum 50. 10. 10. 19
;3. full drum       2 Gas used       120.00000 Distance       800.00000
;       10.000000 in the next 2 trucks
;3. full drum       3 Gas used       180.00000 Distance       920.00000
;       10.000000 in the next 3 trucks
;3. full drum       4 Gas used       240.00000 Distance       1005.7143
;       10.000000 in the next 4 trucks
;3. full drum       5 Gas used       300.00000 Distance       1072.3810
;       10.000000 in the next 5 trucks
;3. full drum       6 Gas used       360.00000 Distance       1126.9264
;       10.000000 in the next 6 trucks
;3. full drum       7 Gas used       419.09091 Distance       1172.3810
;  9.090909 10.000000 in the next    6 trucks
;3. full drum       8 Gas used       477.83217 Distance       1211.5418
;  7.832168 10.000000 in the next    7 trucks
;3. full drum       9 Gas used       536.95571 Distance       1246.3203
;  6.955711 10.000000 in the next    8 trucks
;3. full drum      10 Gas used       596.24050 Distance       1277.5229
;  6.240505 10.000000 in the next    9 trucks
;3. full drum      11 Gas used       655.65889 Distance       1305.8173
;  5.658894 10.000000 in the next   10 trucks
;3. full drum      12 Gas used       715.17534 Distance       1331.6941
;  5.175343 10.000000 in the next   11 trucks
;3. full drum      13 Gas used       774.69915 Distance       1355.5036
;  4.761905  9.937248 10.000000 in the next   11 trucks
;3. full drum      14 Gas used       833.46847 Distance       1377.2700
;  4.353283  9.115188 10.000000 in the next   12 trucks
;3. full drum      15 Gas used       892.49485 Distance       1397.6239
;  4.070785  8.424068 10.000000 in the next   13 trucks
;2. Solution gas used       950.00000 Distance       1416.1740

-- flynn@ozone.stx.com (Lawrence E. Flynn)

References:

C.G. Phipps, The jeep problem : a more general solution, American
Mathematical Monthly, 54, pp 458-62, (1947).
Unlimited cache problem and solution.

G.G. Alway, Crossing the desert, Mathematical Gazette, 41(209),
Note #2707 (1957).
Half way across in one one load problem and solution.

The limited cache problem is the same as the "Desert Fox" problem
described, but not solved, by A. K. Dewdney, July 1987, "Scientific
American."

Dewdney's October 1987 Scientific American article gives for N=2, the
optimal distance of 733.33 miles.

In the November issue, Dewdney lists the optimal distance of 860 miles
for N=3, and gives a better, but not optimal, general distance
formula.

Westbrook, in Vol 74, #467, pp 49-50, March 1990 "Mathematical Gazette",
gives an even better formula, for which he incorrectly claims optimality:

  For N = 2,3,4,5,6:
     Dist = (600/1 + 600/3 + ... + 600/(2N-3))  +  (600-100N)/(2N-1)
  For N > 6:
     Dist = (600/1 + 600/3 + ... + 600/9)  +  (500/11 + ... + 500/(2N-3))

The following shows that Westbrook's formula is not optimal for N=8:

   Ferry  7 drums forward   33.3333 miles   (356.6667 gallons remain)
   Ferry  6 drums forward   51.5151 miles   (300.0000 gallons remain)
   Ferry  5 drums forward   66.6667 miles   (240.0000 gallons remain)
   Ferry  4 drums forward   85.7143 miles   (180.0000 gallons remain)
   Ferry  3 drums forward  120.0000 miles   (120.0000 gallons remain)
   Ferry  2 drums forward  200.0000 miles   ( 60.0000 gallons remain)
   Ferry  1 drums forward  600.0000 miles
                          ---------------
         Total distance = 1157.2294 miles
   (Westbrook's formula = 1156.2970 miles)

       ["Ferrying n drums forward x miles" involves (2*n-1) trips,
         each of distance x.]

[ Editor: from mail to the archive, March 1994. ]

Somebody said there's been a recent article in THE MATH INTELLIGENCER
on this topic, and another person sent me a LaTeX file from which I
enclose a few excerpts:

-- Charles Blair <ceblair@ux1.cso.uiuc.edu>

Here's someone's LaTeX paper that I got off the net a while ago.

-- Timothy Y. Chow <tycchow@BOURBAKI.MIT.EDU>

    The Desert Fox Problem

    Marc E. Posner
    The Ohio State University
    Department of Industrial and Systems Engineering

    Abstract

    The objective of this problem is to maximize the distance from the
    origin that a truck can reach given a finite quantity of gasoline.
    At the origin, there are drums filled with gasoline and a truck.
    The truck has a gas tank and has cargo space to carry a specified
    number of drums at one time.  Drums may be stored anywhere along
    the route, and gasoline may be siphoned as needed.

    We develop properties of an optimal solution, and find an optimal
    procedure for a wide range of problems.  The basic approach is to
    model the gasoline requirements as an infinite variable, mixed 0-1
    program.  We find an optimal solution to this problem, which
    provides an upper bound on the optimal solution for the Desert Fox
    problem.  We then develop conditions under which a solution to the
    Desert Fox problem can achieve this upper bound.

[ Editor: from mail to the archive, May 1995. ]

I believe this is a general solution to the "analysis/cache" puzzle.  I
sent it to Myron Souris, who wrote the solution currently in the
archives for rec.puzzles, and he said he believes it is an improved
solution.  He suggested I send it to you.  The solution is for the case
in which there are no spare containers at the next cache, i.e., the
truck's gas tank cannot be used to ferry fuel.

The method uses the fact that the maximum mileage, s, as a function of
initial gallons, g, (not necessarily an integral number of barrels) is
continuous, increasing and piecewise linear.  The breakpoints are
initially assumed to be at the natural magic numbers 10+50k gallons and
60k gallons, k=1, 2, ... .  When the slope, ds/dg, at the beginning and
the end of a region is found to be different, in violation of the
piecewise linear requirement, one or more interpolated breakpoints are
inserted.

The process starts with the region 0<=g<=60 where s(g) is known to be
s(g)=10*g.  In the next region, 60<=g<=110, only one optimal option to
reach the first region exists, namely, to move the two drums a distance
x=10*(g-60)/3 miles, so s(g) is determined for this region.  In each
succeeding region, all optimal paths to preceding regions are
evaluated, and the one giving continuous s at the startpoint and
maximum s at the endpoint is chosen.  Since s(g) must be linear in each
region, it is uniquely determined.

For a given g, the distances, x, (and therefore the paths) to be
evaluated are in two sets, one set from each of the relations:

10+50*D+2*D*x/10=g, 0<x<=50, 0<D,
where D, an integer, is the number of drums being moved

and

60*m+(2*D-1)*x/10=g, 0<m, 0<D, 0<x,
where m is an integer, m>int(g/60)-(2*D-1)*5/60

When x and the number of drums moved are known, the remaining fuel,
g', is known; this value can be used to look up the previously
determined maximum mileage, s(g'), to which x is added to determine the
new s(g).

The number, n, of options to be evaluated increases linearly with g.
For g=1000, n=6; for g=7500, n=45.

To determine the breakpoints up to g=7500 gallons, and to find the
maximum mileage, s, at each breakpoint took 119 seconds on a Macintosh
Centris 650 computer without floating point hardware, using a compiled
Microsoft QuickBasic program.  The program actually allows arbitrary
values to be input for the drum size, the truck's gas tank size, and
the truck's miles-per-gallon.

Selected results are given below.  Note that although the numbers
g=10+50*k appear in the analysis of the problem, they turn out not to
be breakpoints, with a few exceptions.  On the other hand, every number
g=60*k so far tried is a breakpoint.  The 60 arises as the sum of the
drum size and the gas tank size.

breakpoint, maximum
gallons mileage
0 0
60 600
120 800
180 920
240 1005.71429
300 1072.38095
360 1126.92641
420 1172.38095
433.53982 1180.34555
480 1211.01732
506.6212 1225.02848
540 1244.51299
578.23864 1262.72186
600 1274.17521
626.3427 1285.62856
660 1301.65584
696.71705 1316.2261
720 1326.34912
736.99602 1332.20982
780 1349.27489
813.56891 1360.10357
840 1369.82738
866.32332 1377.80415
900 1389.35426
937.15278 1399.96934
960 1407.33941
993.56571 1416.36245
1020 1424.37284
1037.52776 1428.6479
1080 1440.78283
1112.6913 1448.38546
1140 1455.7265
1176.71362 1463.88509
1200 1469.82738
1225.21809 1475.19293
1260 1483.63997
1294.03451 1490.5583
1320 1496.59678
1345.94514 1501.49209
1380 1509.05984
1410.19865 1514.5505
1440 1520.89121
1463.7813 1525.06337
1500 1532.42569
1540.15135 1539.231
1560 1543.10841
1595.98938 1548.98946
1620 1553.50428
1648.88889 1557.94873
1680 1563.60529
1703.25064 1567.07554
1740 1573.52279
1757.06327 1575.99573
1800 1583.27314
1841.92758 1589.17844
1860 1592.13167
1903.59632 1598.08776
1920 1600.68377
1955.19599 1605.25468
1980 1609.05984

(data omitted)

7020 1958.29223
7044.18464 1959.15289
7080 1960.67608
7096.50793 1961.2594
7098.92245 1961.35707
7140 1963.08925
7153.12096 1963.54963
7157.01475 1963.70715
7200 1965.5057
7208.82328 1965.81313
7260 1967.93489
7270.33755 1968.29235
7320 1970.33441
7323.66773 1970.45958
7380 1972.75703
7384.45205 1972.90795
7440 1975.1551
7458.18163 1975.76727
7500 1977.44673

        maximum
gallons mileage
50 500
100 733.33333
150 860
200 948.5714
250 1016.8254
300 1072.38095
350 1117.8355
400 1157.22944
450 1191.21212
500 1221.54363
550 1249.27489
600 1274.17521
650 1296.89394
700 1317.65347
750 1337.37013
800 1355.7265
850 1372.85769
900 1389.35426
950 1404.1136
1000 1418.31223
1050 1432.2114
1100 1445.43399
1150 1457.94873
1200 1469.82738
1250 1481.2114
1300 1491.94562
1350 1502.39317
1400 1512.6962
1450 1522.6456
1500 1532.42569
1550 1541.15492
1600 1549.7436
1650 1558.15075
1700 1566.59037
1750 1574.97207
1800 1583.27314
1850 1590.49756
1900 1597.59644
1950 1604.57987

data omitted

7000 1957.43458
7050 1959.40021
7100 1961.40251
7150 1963.44012
7200 1965.5057
7250 1967.5203
7300 1969.51203
7350 1971.53352
7400 1973.53693
7450 1975.4918
7500 1977.44673

[ Editor: the "data omitted" lines are in the original mail. ]

-- George W. Anderson Jr. <georgea400@aol.com>