# 25 analysis/bicycle.p

A boy, a girl and a dog go for a 10 mile walk. The boy and girl can
walk at 2 mph and the dog can trot at 4 mph. They also have a bicycle
which only one of them (including the dog!) can use at a time. When
riding, the boy and girl can travel at 12 mph while the dog can pedal
at 16 mph. What is the shortest time in which all three can complete
the trip?

analysis/bicycle.s

First note that there's no apparent way to benefit from letting either the
boy or girl ride the bike longer than the other. Any solution which gets the
boy there faster, must involve him using the bike (forward) more; similarly
for the girl. Thus the bike must go backwards more for it to remain within
the 10-mile route. Thus the dog won't make it there in time. So the solution
assumes they ride the bike for the same amount of time.

Also note that there's no apparent way to benefit from letting any of the three
arrive at the finish ahead of the others. If they do, they can probably take
time out to help the others. So the solution assumes they all finish at the
same time.

The boy starts off on the bike, and travels 5.4 miles. At this
point, he drops the bike and completes the rest of the trip on foot. The
dog eventually reaches the bike, and takes it *backward* .8 miles (so the
girl gets to it sooner) and then returns to trotting. Finally, the girl makes
it to the bike and rides it to the end. The answer is 2.75 hours.

The puzzle is in Vasek Chvatal, Linear Programming, W. H. Freeman & Co.
The generalized problem (n people, 1 bike, different walking and riding speeds)
is known as "The Bicycle Problem". A couple references are

Masuda, S. (1970). "The bicycle problem," University of California, Berkeley:
Operations Research Center Technical Report ORC 70-35.

Chvatal, V. (1983). "On the bicycle problem," Discrete Applied Mathematics 5:
pp. 165 - 173.

As for the linear program which gives the lower bound of 2.75 hours, let
t[person, mode, direction] by the amount of time "person" (boy, girl or dog)
is travelling by "mode" (walk or bike) in "direction" (forward or backwards).
Define Time[person] to be the total time spent by person doing each of these
four activities. The objective is to minimize the maximum of T[person], for
person = boy, girl, dog, e.g.

minimize T
subject to T >= T[boy], T >= T[girl], T >= T[dog].

Now just think of all the other linear constraints on the variables t[x,y,z],
such as everyone has to travel 10 miles, etc. In all, there are 8 contraints
in 18 variables (including slack variables). Solving this program yields the
lower bound.

Continue to: