The Bicycle Problem

OR 389 Student Seminar

"On the Bicycle Problem"

V. Chvátal, Disc. Appl. Math. 5 (1983): 165-173

Given one single-seat bicycle, n people with known walking and biking speeds, and a track of length d miles, devise a schedule that minimizes the arrival time of the last person at the finish line. Note that an optimal schedule might require biking backwards.

Overheads in postscript format

The following four animations illustrate some possible schedules for n = 3 and d = 10, where the first two people have walking speed 2 miles/hour and biking speed 12 miles/hour, and the third person has walking speed 4 miles/hour and biking speed 16 miles/hour.

Sample Schedule

Optimal Schedule

For the two ε-optimal schedules, we must add the time necessary to get from the starting line to the initial positions and from the final positions to the finish line. The point is that, with enough stages, we can make this additional time less than any given ε > 0.

ε-Optimal Schedule Using Lemma 2 (ε = 8, One Stage)

ε-Optimal Schedule Using Lemma 2 (ε = 4, Two Stages)

Links to this page.

Return to my home page.