Skip to main content
added 105 characters in body
Source Link
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}

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.

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}

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}

added 1096 characters in body
Source Link
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.

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}

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

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.

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}

deleted 2 characters in body
Source Link
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.

Here's an animation: enter image description here

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

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.

Here's an animation: enter image description here

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 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

added 87 characters in body
Source Link
RobPratt
  • 15.7k
  • 1
  • 35
  • 61
Loading
Source Link
RobPratt
  • 15.7k
  • 1
  • 35
  • 61
Loading