How do I set up a solution to this?
Peter is the baker’s son in a rural town which produces bonbons as its local specialty. He and his friends plan to earn some money on Sunday by selling bonbons, supplied by Peter’s father, in the streets of the neighbouring towns. The coordinates in miles of those towns, relative to Peter’s hometown, are as follows: Aliceville (15, 18), Brownvale (35, 6), Carlstown (−14, 19), Damsonvale (−11, −23), Ellistown (25, −5), Farville (−20, −4), Greenvale (−38, 26) and Heinsberg (32, −24). Any two of these cities are linked by a direct road and the speed limit on all roads is 50 mph.
The expected hourly profit in dollars for selling bonbons is 22/h in Aliceville, 26/h in Brownsville, 21/h in Carlstown, 23/h in Damsonvale, 22/h in Ellistown, 19/h in Farville, 27/h in Greenvale and 23/h in Heinsberg. Peter and four of his friends plan to depart on Sunday at 8am. Peter, the only one who can drive, will drop them off to sell bonbons, each in a different town, head to a fifth town to sell bonbons himself. Once done, he will pick them up again and bring everyone home where they will share their collected earnings. Given that they must all return home by 4pm, how should they plan their trip in order to maximise their profit?
Any advice on how to set this up would be greatly appreciated! Thank you
Best Answer
By using mixed integer linear programming, I obtained an optimal solution with a total profit of $618.56, achieved by the following schedule, where time is measured in hours starting from 0 and ending at 8:
The formulation uses two nodes $(i,1)$ and $(i,2)$ for each town $i$, for dropoff and pickup, respectively. Let $p_i$ denote the hourly profit rate for town $i$, and let $t_{i,j}$ denote the travel time (in hours) from town $i$ to town $j$. Let binary decision variable $x_i$ indicate whether town $i$ is visited. Let binary decision variable $y_{i,k_i,j,k_j}$ indicate whether node $(i,k_i)$ is visited immediately before node $(j,k_j)$. Let $\overline{a}_i = t_{i,\text{Hometown}}$, and let decision variable $a_{i,k} \in [0,\overline{a}_i]$ be the arrival time at node $(i,k)$. The problem is to minimize $$\sum_i p_i (a_{i,2}-a_{i,1})$$ subject to \begin{align} x_{\text{Hometown}} &= 1 \\ \sum_i x_{i} &= 6 \\ \sum_{j,k_j} y_{i,k_i,j,k_j} &= x_{i} &&\text{for $i,k_i$} \\ \sum_{j,k_j} y_{j,k_j,i,k_i} &= x_{i} &&\text{for $i,k_i$} \\ \sum_{i,j} y_{i,1,j,2} &= 1 \\ a_{i,k} &\le \overline{a}_i x_i &&\text{for $i,k$}\\ a_{i,k_i} + t_{i,j} - a_{j,k_j} &\le (\overline{a}_i + t_{i,j}) (1 - y_{i,k_i,j,k_j}) && \text{for $i,k_i,j,k_j$ with $j \not=$ Hometown} \end{align} Constraints 3 and 4 are flow balance constraints. Constraint 5 forces exactly one transition from dropoff to pickup, which happens at Greenvale in the optimal solution. The final "MTZ" constraints prevent subtours and enforce $a_{i,k_i} + t_{i,j} \le a_{j,k_j}$ if $y_{i,k_i,j,k_j}=1$.