Projects / Where to build fire stations so every region is within 12 minutes
Where to build fire stations so every region is within 12 minutes
Course project, Michigan Ross MBA. Set-covering integer program in Excel Solver, checked by full enumeration in Python. Not client or employer work.
| Situation | A city must give each of its six regions fire cover. It has six candidate sites for stations, each with a different cost. |
|---|---|
| Complication | A station is useful to a region only if it gets there within 12 minutes, and three siting rules limit which sites can open together. To open all six sites costs $1.8M. |
| Question | Which sites must the city open to cover every region at the lowest cost? |
| Answer | Two of six candidate sites are enough, for $700,000. One minute faster costs 64% more. |
The cost depends on which sites open; the 12-minute limit decides how few are enough
- Total cost of the stations$700,000 in the answer
- Stations opened
- Which sites openThe lever: six yes/no choices
Can two stations cover all six regions?
Yes. Sites 1 and 3 reach every region within 12 minutes.
- Response-time limitThe limit: 12 minutes to each region
What does one minute less cost?
$450,000. An 11-minute limit needs three stations.
- Siting rulesThe limit: three rules on which sites go together
Do the rules change the answer?
No. The plan without the rules is the same.
- Cost of each station
- Cost to open a siteFixed: $50,000 to $450,000 by site
- Travel timesFixed: from each site to each region
Lever what the decision changes Limit what the answer must respect Fixed outside the decision
Lowest cost to cover all six regions
$700,000
sites 1 and 3, out of 64 possible plans
Longest response time
12 min
region 5, exactly at the limit
Cost of one minute less
+$450,000
an 11-minute limit needs three stations
Sites 1 and 3 together reach every region within 12 minutes
| Site 1 | Site 2 | Site 3 | Site 4 | Site 5 | Site 6 | |
|---|---|---|---|---|---|---|
| Region 1 | 3 | 15 | 21 | 7 | 15 | 25 |
| Region 2 | 11 | 5 | 13 | 16 | 12 | 21 |
| Region 3 | 21 | 18 | 2 | 19 | 13 | 10 |
| Region 4 | 8 | 21 | 20 | 4 | 8 | 17 |
| Region 5 | 14 | 16 | 12 | 10 | 3 | 9 |
| Region 6 | 22 | 23 | 9 | 18 | 8 | 2 |
| Cost to open | $400,000 | $50,000 | $300,000 | $450,000 | $250,000 | $350,000 |
Site opened 8 the station that serves the region 12 inside the 12-minute limit
The 12-minute limit sits just above a cost step: 11 minutes costs 64% more
No plan covers all regions below 10 minutes. Each bar is the lowest-cost plan for that limit, with the three siting rules applied.
The model
Decision
Open or do not open each of the six candidate sites (six yes/no variables).
Objective
The lowest total cost to open the stations.
Constraints
Each region has at least one open station within the limit. Sites 1 and 6 are not opened together. Site 4 needs site 1. Sites 5 and 6 are opened together or not at all.
- The three siting rules do not change the answer at 12 minutes. The plan without the rules is the same.
- Region 5 is 12 minutes from site 3, so the plan has no spare time there. A limit of 11 minutes adds site 4 and $450,000.
- A limit of 15 minutes lets sites 5 and 6 replace sites 1 and 3 and saves $100,000.