Skip to main content
5 of 5
added 105 characters in body
RobPratt
  • 15.7k
  • 1
  • 35
  • 61

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}

RobPratt
  • 15.7k
  • 1
  • 35
  • 61