Bicycle Route Optimization Puzzle

Question

I tried to make some expressions about where each person stops the bike, but I couldn't solve it :( There are three people who would like to cross the road.

It takes $a$ minutes for the first person to cross the road by walking.

It takes $b$ minutes for the second person to do so.

It takes $c$ minutes for the third person to do so.

They also have one bike - all three of them can cross the road in $k$ minutes - where $k<a,b,c$.

However, only one person at a time can ride the bike.

Now they want to cross the road as fast as possible. What is the shortest time possible for all three of them to arrive at the end of the road?

Please note, that these people cannot go outside the road.

The below solutions have some cases where people go outside the road - also possibly implying negative time.

Answer 1

Here is an example: suppose $k=26, a=52, b=65, c=78$ minutes (a wide road).

Then I suspect an optimal choice is for the third person to ride for $14$ minutes, getting $\frac{14}{26}$ of the way across, leaves the bike there, and walks the rest of the time, taking $\frac{26-14}{26}\times 78 = 36$ extra minutes, making a total of $14+36=50$ minutes.

At the same starting time, the first person walks to where the bicycle will be left by the third, taking $\frac{14}{26}\times 52 = 28$ minutes to get there, then rides the bike for $2$ minutes, so is now $\frac{14}{26} + \frac{2}{26} = \frac{16}{26}$ of the way across, leaves the bike, and finally walks across the rest of the road, taking $\frac{26-16}{26}\times 52 = 20$ extra minutes, making a total of $28+2+20 = 50$ minutes again.

At the same starting time, the second person walks to where the bicycle will be left by the first, taking $\frac{16}{26}\times 65 = 40$ minutes to get there, then rides the bike for $10$ minutes, so is now $\frac{16}{26} + \frac{10}{26}=1$ i.e. the whole way across, making a total of $40+10 = 50$ minutes again.

So in this example it is possible for all three people and the bike to cross in less time than the fastest person walking, and faster than the bike going there and back.

---

Generalising this, but with the same bike order of slowest, then fastest, then middle-speed riding, I suspect that the fastest time comes from:

• first person riding for $k\frac{ {{k}^{2}}-2 a k-b c+a c+a b }{3 {{k}^{2}}-2 c k-2 b k-2 a k+b c+a c+a b}$ minutes and walking for $a\frac{2k^2-2ck-2bk+2bc}{3 {{k}^{2}}-2 c k-2 b k-2 a k+b c+a c+a b}$ minutes

• second person riding for $k\frac{ {{k}^{2}}-2 b k-c a+b a+bc }{3 {{k}^{2}}-2 a k-2 c k-2 b k+ca+ba+bc}$ minutes and walking for $b\frac{2k^2-2ak-2ck+2ca}{3 {{k}^{2}}-2 a k-2 c k-2 b k+ca+ba+bc}$ minutes

• third person riding for $k\frac{ {{k}^{2}}-2 c k-ab+cb+ca }{3 {{k}^{2}}-2 b k-2 a k-2 c k+ab+cb+ca}$ minutes and walking for $c\frac{2k^2-2bk-2ak+2ab}{3 {{k}^{2}}-2 b k-2 a k-2 c k+ab+cb+ca}$ minutes

so with total crossing time of $\dfrac{k^3-bck-ack-abk+2abc}{3 {{k}^{2}}-2 c k-2 b k-2 a k+b c+a c+a b}$ for each person.

This does not work when it gives a negative riding time for the fastest walker, suggesting riding in the opposite direction, as that individual still needs a non-negative riding time.

Answer 2

First, it will be useful to notice two principles

1. All walkers, no matter how many they are, have to get to the end of the road at the same time, always. If some walker got before another, it could have given some of her "bicycle time" to the walker that arrived the last to decrease the total time.
2. It doesn't make sense for any walker at any time to go backwards to give the bicycle to other walker. Going back is less efficient than just letting the bicycle in the road and keep walking.

The total crossing time is determined by the proportion of walking to riding time, that should be adjusted so that all walkers get to the end of the road at the same moment.

If you let me, I will use speeds rather than times. We'll call the speeds of the walkers $v_1,v_2,v_3$ and the one of the bicycle $V$. Also, lets assume, without loss of generality, that $$v_1<v_2<v_3<V$$ The simplest procedure the walkers could choose to adjust their riding to walking ratio is the following. The slowest walker takes the bicycle up to a distance $d_{c1}$ (the $c$ is for "cut") then leaves it and walks through the end $d$. The middle walker walks until $d_{c1}$ then takes the bicycle up to $d_{c2}$ and walks to the end. Finally, the fastest walker walks to $d_{c2}$ and takes the bicycle to the end. We'll call the total crossing times for the three walkers $t_1,t_2,t_3$. They have the following expressions $$t_1=\frac{d_{c1}}{V}+\frac{d-d_{c1}}{v_1}$$ $$t_2=\frac{d_{c1}}{v_1}+\frac{d_{c2}-d_{c1}}{V}+\frac{d-d_{c2}}{v_2}$$ $$t_3=\frac{d_{c2}}{v_3}+\frac{d-d_{c2}}{v_2}$$ Now, our first principle sets the constraints $t_1=t_2=t_3=t_T$ (total time). With this we have three linear equations to determine three unknowns, $t_T,d_{c1}$ and $d_{c2}$. Actually I just put the equations in Mathematica and obtained

$$t=\frac{d}{V}\frac{2V^3+v_1v_2v_3-V^2(v_1+v_2+v_3)}{3 v_1v_2v_3+V^2(v_1+v_2+v_3)-2V(v_1v_2+v_1v_3+v_2v_3)}$$ $$d_{c1}=d\frac{-2Vv_1v_3+v_1v_2v_3+V^2(-v_1+v_2+v_3)}{3 v_1v_2v_3+V^2(v_1+v_2+v_3)-2V(v_1v_2+v_1v_3+v_2v_3)}$$ $$d_{c2}=2d\frac{(V-v_1)(V-v2)v_3}{3 v_1v_2v_3+V^2(v_1+v_2+v_3)-2V(v_1v_2+v_1v_3+v_2v_3)}$$

The most interesting point is that the total time is symmetric to permutations of $v_1,v_2,v_3$, i.e. we could have made the fastest or the middle walker to take the bicycle first, it doesn't matter, as long as the bicycle times proportions are kept. Besides the grueling algebra, that could be perhaps simplified with some tricks, I think this problem would be easy to generalize for more walkers.

Answer 3

WARNING

The formula given for Case$1$ doesn't necessarily give the optimal time, trial and error can throw up better answers (see comments below the answer), but the formula for Case $2$ should be ok, as all reach the end simultaneously.

---

There are two assumptions I make at start:

(i) the bike is faster than each of the walkers (reasonable !)

(ii) zero time is wasted in switching from bike to walk or vice versa (unreasonable but customary !)

WLOG, I take time to bike entire distance as $1$, and that of the walkers as $a,b,c,\;\; a < b < c$

[ The cases where two or three have the same walking speed are progressively simpler cases ]

First consider the two slowest walkers.

Let (say) the faster one start with the bike, leave it at fraction $f$ of the distance, and walk the rest of the way, whereas the other walker starts by walking, and rides the remaining distance on reaching the bike.

Let $t$ be the time needed for both of them to simultaneously reach the end, then

$f + (1-f)b = (1-f) + f*c = t\;\; \Rightarrow f = \dfrac{b-1}{b+c-2}$

and $\;t = \dfrac{bc-1}{b+c-2}$

Two cases can now arise:

Case $1:\;t > a$

Example:$\; a = 1.5, b = 2, c= 20 \to t= 1.95$

Decision rule: Let $a$ walk the whole distance. Optimal group reach time $= 1.95$

Case $2:\;t \le a$

Example:$\; a = 1.5, b = 1.6, c= 1.7 \to t= 1.323$ (considering only $b$ and $c$)

Decision rule: All three should share the bike for appropriate fractions of the distance and arrive simultaneously.

Appropriate fractions

Let $f_1,f_2,f_3$ be the fractions of full distance the bike is used by $a,b,c$
and the time taken for them to reach simultaneously be $t$

$f_1 + (1-f_1)a = t \to f_1 = \dfrac{a-t}{a-1}$
$f_2 + (1-f_2)b = t \to f_2 = \dfrac{b-t}{b-1}$
$f_3 + (1-f_3)c = t \to f_3 = \dfrac{c-t}{c-1}$

Now $f_1+f_2+f_3 = 1$, which yields:

$t = \dfrac{(2 a b c - a b - a c - b c + 1)}{(a b + a c + b c - 2 a - 2 b - 2 c + 3 )}$

Using the above decision rule brings down the optimal time from $1.5$ (due to laggard $a$ to $\approx 1.3925$