5
$\begingroup$

Five friends Alice, Bob, Carole, Dylan and Emma are heading to a common destination 100 unit distance away. They start together. Grandma Alice walks at a speed of 1. Bob and Carole walk at speeds 4 and 5, respectively. Dylan uses a skateboard and is able to travel at speed 7. The roller skating Emma travels at speed 9. It's kind of late, so they want to arrive at the destination as quickly as possible. Just as they're worrying about the lack of transportations, two friendly motorcyclists pass by and are willing to help out. The motorcycles are able to travel at speeds 10 and 15 respectively. One motorcyclist can carry only one passenger at a time, but of course, the passenger can get off any time so another person can get on board when needed.

We assume getting on and off the motorcycles take no time at all, and ignore the deceleration when dropping off and picking up a person. The motorcyclists don't mind going back and forth many times. The road is wide so there's no problem for one vehicle to overtake or pass by another vehicle or person.

What's your plan to minimize the amount of time it takes for all of the five friends to arrive at the destination?

$\endgroup$
7
$\begingroup$

Here's a schedule that takes 12.2828 time units.

Motorcycle 1 takes Alice for 9.7464 time units, deadheads back 1.1414 time units to pick up Bob, and takes Bob 1.3950 time units to the finish line.

Motorcycle 2 takes Bob for 3.8635 time units, deadheads back 1.9318 time units to pick up Carole, takes Carole 3.8586 time units, deadheads back 0.8763 time units to pick up Dylan, and takes Dylan 1.7526 time units to the finish line.

Emma skates the whole way, arrives at time 11.1111, and waits for everybody else (including both motorcyclists) to arrive at time 12.2828.

Here's an animation: enter image description here


I obtained this solution via linear programming as follows, inspired by Chvatal, "On the Bicycle Problem" (1983).

For person $p$, let $us_p$ be the unassisted speed $(1,4,5,7,9)$. For motorcycle $m$, let $rs_m$ be the riding speed ($rs_1=10$ and $rs_2=15$).

For person $p$, let $u_p^+ \ge 0$ and $u_p^- \ge 0$ be the unassisted time spent moving forward or backward, respectively. For motorcycle $m$, let $d_m^+ \ge 0$ and $d_m^- \ge 0$ be the time spent deadheading (no passengers) forward or backward, respectively. For person $p$ and motorcycle $m$, let $r_{p,m}^+ \ge 0$ and $r_{p,m}^- \ge 0$ be the time spent riding forward or backward, respectively. Let $t$ be the overall finish time. The problem is to minimize $t$ subject to \begin{align} u_p^+ + u_p^- + \sum_m (r_{p,m}^+ + r_{p,m}^-) &\le t &&\text {for all $p$} \\ d_m^+ + d_m^- + \sum_p (r_{p,m}^+ + r_{p,m}^-) &\le t &&\text {for all $m$} \\ us_p (u_p^+ - u_p^-) + \sum_m rs_m (r_{p,m}^+ - r_{p,m}^-) &= 100 &&\text {for all $p$} \\ rs_m \left(d_m^+ - d_m^- + \sum_p (r_{p,m}^+ - r_{p,m}^-)\right) &\le 100 &&\text {for all $m$} \\ \end{align}

$\endgroup$
4
  • $\begingroup$ +1. That's a clever scheme. Do you have any reason to suspect whether it may or may not be a best scheme? $\endgroup$
    – Eric
    Aug 15 at 1:07
  • $\begingroup$ Yes, it can be shown optimal via linear programming. Does your comment mean that you had a different schedule in mind when you posed the question? $\endgroup$
    – RobPratt
    Aug 15 at 1:13
  • $\begingroup$ I do have some other candidates in mind, which would take some effort to describe. What're the constraints you use in LP? $\endgroup$
    – Eric
    Aug 15 at 1:29
  • $\begingroup$ It looks like the optimum solution to me, but given they arrive at different times I wonder if there is room for optimisation - got the +1 from me and I cannot see a better solution $\endgroup$
    – tom
    Aug 15 at 13:00
3
$\begingroup$

The goal: average speed s 7<s<9
The plan: The longer the slow people are helped the better, so the speed 10 motorcycle M10 should prioritize A over B, B over C etc.
The M15 + C + D are faster than speed 10 + A + B so speed 15 will have time to help B a bit too

formulae for the fraction of time available for forward movement i.e.carrying
M10 : (speed+10)/20
M15 : (speed+15)/30
formulae for the fraction of time being carried
A carried (by M10) (speed-1)/9
D carried (by M15) (speed-7)/8
C carried (by M15) (speed-5)/10
The optimal solution should have B use all the remaining M10+M15 time (assuming E does not need assistance), and with it reach the same speed, thus:
speed = 4 + (10-4) * ((speed+10)/20-(speed-1)/9) + (15-4) * ((speed+15)/30 - (speed-7)/8 - (speed-5)/10 )
solving this give speed=8.141486, indeed between 7 and 9. (or time = 12.2828, like the earlier answer)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.