Fire Station Siting
Maximum Coverage Location Problem (MCLP) · NP-Hard
A city fire department must locate p stations to maximize population covered within a 4–8 minute response radius. Each uncovered zone of 10,000 residents faces a 40% higher fire fatality risk. The MCLP trades off coverage breadth against station construction cost.
Where This Decision Fits
Public safety operations — the highlighted step is what this page optimizes
The Problem
Select p station sites to maximize population covered within response radius r
A metropolitan fire department evaluates 7 candidate station sites to serve 12 demand nodes (census blocks) with populations ranging from 500 to 5,000 residents. The department must open exactly p stations (constrained by budget) such that the total population within the coverage radius r of at least one open station is maximized.
This is the classical Maximum Coverage Location Problem (MCLP), introduced by Church & ReVelle (1974) and proven NP-hard by reduction from Set Cover. Unlike the p-Median problem which minimizes average distance, the MCLP maximizes the number of demand nodes (weighted by population) that fall within a critical service distance threshold.
subject to
Σj∈Ni yj ≥ zi ∀ i // node i covered only if a station in Ni is open
Σj yj ≤ p // open at most p stations
yj ∈ {0, 1} // station open or not
zi ∈ {0, 1} // node i covered or not
Where di is the population (demand) at node i, Ni is the set of candidate sites within coverage radius r of node i, yj is the binary open/close decision for station j, and zi indicates whether node i is covered.
See Integer Programming theoryTry It Yourself
Choose p, coverage radius, and an algorithm to find the best station locations
Fire Station Siting Optimizer
7 Sites · 12 Nodes| Site | Location | Cost ($M) |
|---|
| Block | Population | Risk Zone |
|---|
Ready. Click “Solve & Compare All Algorithms” to run.
| Algorithm | Pop. Covered | % Covered | Uncovered | Time |
|---|---|---|---|---|
| Click Solve & Compare All Algorithms | ||||
The Algorithms
Three approaches to the Maximum Coverage Location Problem
Greedy (Max New Coverage)
O(p · n · m) | (1 − 1/e) approximationStart with no stations open. At each step, evaluate the additional population newly covered by opening each remaining candidate site. Open the site with the greatest marginal coverage gain. Repeat until exactly p stations are open. This greedy approach has a provable (1 − 1/e) ≈ 63% approximation guarantee for submodular maximization under a cardinality constraint.
Greedy + Swap
O(iter · p · (n−p) · m) | Local optimumBegin from the greedy solution with p open stations. At each iteration, try every possible swap: close one open station, open one closed station. Accept the swap that yields the largest increase in covered population. Repeat until no improving swap exists. This local search often improves beyond the greedy baseline and can escape suboptimal early choices.
Random Selection
O(m) | No guaranteeRandomly select p stations from the candidate set. This serves as a baseline to demonstrate the value of optimization. Repeated 50 times, keeping the best random solution found. While occasionally competitive on small instances, random selection typically performs significantly worse than even the simplest greedy heuristic.
Real-World Complexity
Why practical fire station siting goes beyond the basic MCLP model
Beyond the MCLP
- Travel time variability — Road networks, traffic congestion, and time of day create non-Euclidean response times that differ from straight-line distance
- Backup coverage — When a unit is dispatched, remaining stations must still provide adequate coverage to the rest of the city
- Multiple apparatus types — Engine companies, ladder trucks, and rescue squads have different coverage requirements and response standards
- Call frequency variation — Certain census blocks generate far more emergency calls per capita than others due to building density and demographics
- Mutual aid agreements — Neighboring jurisdictions provide reciprocal coverage, changing effective station placement needs at borders
- Land use constraints — Zoning restrictions, property availability, and environmental regulations limit feasible station sites
- Equity mandates — Political requirements may demand minimum service levels in all districts, not just maximum total coverage
Key References
Foundational works in coverage location and emergency service optimization
- (1974). “The Maximal Covering Location Problem.” Papers in Regional Science, 32(1), 101–118.
- (1971). “The Location of Emergency Service Facilities.” Operations Research, 19(6), 1363–1373.
- (1995). “Network and Discrete Location: Models, Algorithms, and Applications.” John Wiley & Sons.
Need to optimize your emergency service network?
From fire station siting to ambulance deployment and emergency dispatch, mathematical modeling can transform public safety infrastructure decisions. Let’s discuss how Operations Research can work for you.