Description
Problem 1 — Vehicle Routing
A local bakeshop wants determine the minimum cost plan for picking up its daily supply of milk, butter, and eggs from the four farms that supply the bakeshop. The distance (in miles) between the bakeshop (B) and each farm, and also between each pair of farms, is given in the table below. The table also gives the volume of milk, butter, and eggs (total, in ft33) to be collected from each farm each day. (The distance between locations is the same in both directions, so for each pair of locations the distance is only reported once.)
| B | F1 | F2 | F3 | F4 | |
|---|---|---|---|---|---|
| B | – | 5 | 12 | 7 | 15 |
| F1 | – | – | 4 | 10 | 7 |
| F2 | – | – | – | 14 | 20 |
| F3 | – | – | – | – | 8 |
| F1 | F2 | F3 | F4 | ||
| Supply (ft33) | 7 | 2 | 6 | 3 |
The bakeshop has one truck that can carry at most 10 ft33 of supplies at a time. Because of the size limit, the truck will need to make multiple trips each day to collect the supplies from all the farms. Each trip may pick up supplies from one or more farms, provided the total collected in the trip does not exceed the truck limit.
Formulate an integer program to help the bakeshop assign farms to the trips so that the total number of trips required every day is minimized (Hint: model the problem as a set covering problem. The first step will be to list all possible routes a truck can take.)
Problem 2 — The Magical Baked Goods Machine
Suppose you are in charge of a magical baked goods machine that creates delicious baked goods of many varieties. Every day, the machine creates batches of 5 different baked goods. To produce a batch of a baked good, you must first clean the machine to remove the remnants of the previous batch of bakery treats (e.g., the workflow could be, “clean, make bread, clean, make donuts,…”). The durations of baking each of the 5 items (donuts, scones, cookies, bread, and coffee cake) are 40, 32, 50, 28, and 47 minutes respectively. The cleaning times depend on the item that was previously made in the machine. For example, a long cleaning period is required if bread is made after scones, since the scones leave a sticky residue from the dried fruit they contain that can ruin the bread. The times are given in minutes in the following table. Each pair (i,j)(𝑖,𝑗) is the cleaning time required if batch j𝑗 is baked after batch i𝑖.
| Baked good | Donut | Scone | Cookie | Bread | Coffee Cake |
|---|---|---|---|---|---|
| Donut | 0 | 10 | 6 | 15 | 9 |
| Scone | 4 | 0 | 6 | 17 | 8 |
| Cookie | 10 | 11 | 0 | 20 | 14 |
| Bread | 7 | 15 | 6 | 0 | 2 |
| Coffee Cake | 5 | 8 | 7 | 7 | 0 |
We’d obviously like to spend as little time as possible baking and cleaning. What order should we produce the 5 bakery items in? How long do we spend baking and cleaning each day? The order is the same every day, so the cleaning time between the last batch of one week and the first of the following week needs to be accounted for in the total duration of cleaning.
Solve this problem as a TSP. You may use either MTZ reformulation or subtour elimination (or both, for fun!).