Sharing a bicycle (part 5)

Over the past four posts, I developed a simulation of a bicycle sharing problem that appeared in Parade Magazine’s Ask Marilyn column a few years ago. For what I hope will be the final post in this series, I’m going to derive some analytical results.

First of all, the graphs of completion time vs. distance ahead showed that in both the simple case (rA = rB and wA = wB) and the general case with all velocities different, there was a distinct minimum completion time. In order to determine that time, begin by defining the following quantities:

s_{wA} = total distance A walks
s_{rA} = total distance A rides the bicycle
s_{wB} = total distance B walks
s_{rB} = total distance B rides the bicycle

and as before,

wA = A’s walking speed
wB = B’s walking speed
rA = A’s speed on the bicycle
rB = B’s speed on the bicycle

The minimum completion time is then given by:

(5.1) \qquad t_{min} = \min \left[ \max \left[ \frac{s_{wA}}{wA} + \frac{s_{rA}}{rA},\frac{s_{wB}}{wB} + \frac{s_{rB}}{rB} \right] \right]

Since s_{wA}+ s_{rA} = s and s_{wB}+ s_{rB} = s the walking distances can be eliminated:

(5.2) \qquad t_{min} = \min \left[ \max \left[ \frac{s-s_{rA}}{wA} + \frac{s_{rA}}{rA},\frac{s - s_{rB}}{wB} + \frac{s_{rB}}{rB} \right] \right]

The identity s_{rA} + s_{rB} = s permits further simplification:

(5.3) \qquad t_{min} = \min \left[ \max \left[ \frac{s-s_{rA}}{wA} + \frac{s_{rA}}{rA},\frac{s_{rA}}{wB} + \frac{s - s_{rA}}{rB} \right] \right]

Gathering terms:

(5.4) \qquad t_{min} = \min \left[ \max \left[ s_{rA} \left( \frac{1}{rA} - \frac{1}{wA} \right) + \frac{s}{wA} ,-s_{rA} \left(\frac{1}{rB} - \frac{1}{wB} \right) + \frac{s}{rB} \right] \right]

The pair within the brackets of Eq. (5.4) are both linear functions of s_{rA} , and with rA > wA and rB > wB, the slopes of the two lines have opposite parity. So if these two lines intersect on the interval 0 \leq s_{rA} \leq d , then the point of intersection defines t_{min} . Setting the two expressions equal and solving for s_{rA} gives:

(5.5) \qquad s_{rA} = \frac{s \cdot rA \cdot wB (rB - wA)}{rA \cdot rB (wA + wB) - wA \cdot wB (rA + rB)}

s_{rA} is the distance that A rides the bicycle. If Eq. (5.5) evaluates to a value less than zero (for example if rB < wA) then the optimal strategy is for A to walk (s_{rA} = 0 ) and B to ride the bicycle for the entire journey. The minimum time is the larger of s/wA and s/rB. If Eq. (5.5) evaluates to a quantity greater than d, then the optimal strategy is for A to ride the bicycle and B to walk the entire journey; the minimum completion time is the larger of s/wB and s/rA. Otherwise, s_{rA} is as given by (5.5), and substituting (5.5) into (5.4) gives:

(5.6) \qquad t_{min} = \frac{s (rA \cdot rB - wA \cdot wB)}{rA \cdot rB (wA + wB) - wA \cdot wB (rA + rB)}

Part 3 of this series presented a graph of completion time vs. distance ahead for the case of wA = 2.9333, wB = 4, rA = 8.8, rB = 12. Substituting into the expression above gives t_{min} = 1015.4 sec. This is quite close to the figure of 1010 seconds that I estimated from the graph.

Unfortunately, this formula doesn’t tell us what values of h (and there are obviously many of them) result in the minimum time. However, as shown above, the minimum completion time occurs when A and B complete the journey at the same time. Take another look at the figure from part 4 of this series:

GeneralAnnotate
Figure 5.1: Position of A, B, and C (the bicycle) vs. time.

A and B coincide on the route at three different places as denoted on Figure 5.1:

  1. At about t=285 when A is walking, B is riding for the first time, and B passes A.
  2. At about t=660 when B is walking, A is riding for the second time, and A passes B.
  3. At about t=940 when A is walking, B is riding for the second time, and B passes A.

Clearly A and B can only coincide during Steps 1 and 3, when one of the friends is walking and the other friend is riding the bike.

Finding expressions for h in each case as a function of the other variables is a matter of algebra, and to avoid errors I used Wolfram Mathematica. Omitting the derivation, the longest distance h is given by:

h_1 = \frac{s \cdot wB (rA-wB) (rB-wA)}{\left( rA \cdot rB (wA+wB)-wA \cdot wB (rA+rB) \right)}

With s, rA, wA, rB and wB as above, this gives h = 1883.087. The plot of position vs. time is as follows:

MinTimeShort
Figure 5.2: Longest “distance ahead” that results in minimum completion time.

The next largest value that results in the minimum travel time is:

h_2 = \frac{s \cdot wA \cdot wB(rB - wA)(rA - wB)}{(wA + wB)(rA \cdot rB(wA + wB) - wA \cdot wB(rA + rB))}

With s, rA, wA, rB and wB as above, this gives h = 796.685. The plot of position vs. time is as follows:

MinTimePlot
Figure 5.3: Another value of “distance ahead” that results in minimum completion time.

Both have a completion time of 1015.4 seconds, and in both cases A and B arrive at the end at the same time. I will leave the third distance as an exercise for interested readers.

That’s all for the bike sharing problem (unless I think of something else)!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s