Fire Station Siting
MCLP · Church-ReVelle (1974) · RAND NYC deployment study
Related canonical: p-Median (MCLP cousin)Where should a city put its fire stations so the greatest population can be reached within a 4–6 minute response window? Church & ReVelle's Maximal Covering Location Problem (1974) answers this with a clean integer program that became the template for emergency-service-facility planning worldwide. The RAND Corporation's Walker, Chaiken & Ignall (1974) deployment study for New York City demonstrated that relocating a handful of companies materially reduced response-time disparities across boroughs — the founding case study of public-services OR. Larson (1974)'s hypercube queuing extension added occupancy dynamics that made the coverage numbers honest.
Problem context
Response-time coverage, 1970s NYC onwards
Fire suppression and EMS response share a binary success criterion: you either arrived in time or you did not. The National Fire Protection Association (NFPA 1710) recommends a 4-minute travel time for first-arriving engine company and 8 minutes for full first-alarm assignment. The urban-OR question reduces to a covering problem: given candidate station sites, a fleet size p, and a service radius R, which p sites cover the largest population?
Toregas, Swain, ReVelle & Bergman (1971) introduced the Location Set Covering Problem (LSCP): minimise the number of stations needed to cover every demand point within R. Church & ReVelle (1974) reversed the framing into the Maximal Covering Location Problem (MCLP): given a budget of p stations, maximise the population covered. In practice MCLP is the more useful formulation because LSCP often requires more stations than budgets allow.
Walker, Chaiken & Ignall's 1974 RAND report (R-1566-NYC) used a blend of these tools for New York City in the aftermath of the 1970s fire crisis. The study showed that closing some overlapping stations and relocating companies to under-served areas materially reduced response-time disparities across boroughs. This was the first large-scale OR deployment in public services and is still the canonical worked example.
Larson's 1974 hypercube queuing model addressed an important deficiency of pure MCLP: stations are not always available. A station busy on one call cannot respond to another, so nominal coverage overstates real coverage. The hypercube treats each unit's busy/idle state as a bit in a 2N-dimensional state space and produces time-averaged response metrics that account for realistic busy probabilities.
Multi-stakeholder framing
Mathematical formulation
MCLP, LSCP, and the p-center equity alternative
| Symbol | Definition | Domain |
|---|---|---|
| I | Set of demand points (neighbourhoods, census blocks) | |I| = n |
| J | Set of candidate station sites | |J| = m |
| wi | Demand weight (population, expected calls) | ℝ⁺ |
| dij | Travel distance / time from j to i | ℝ⁺ |
| R | Coverage radius (e.g., 4-min travel time) | ℝ⁺ |
| Ni | Coverage neighbourhood = {j : dij ≤ R} | Ni ⊆ J |
| p | Budget (number of stations to open) | ℕ⁺ |
| xj | Binary: 1 if station opened at j | {0, 1} |
| yi | Binary: 1 if demand point i is covered | {0, 1} |
s.t. yi ≤ Σj ∈ Ni xj ∀ i // covered only if an open station is within R
Σj xj = p // budget: open exactly p stations
xj, yi ∈ {0, 1}
Location Set Covering Problem (LSCP, Toregas et al. 1971) min Σj xj // minimise stations needed
s.t. Σj ∈ Ni xj ≥ 1 ∀ i // every demand point must be covered
p-Center — worst-case equity alternative min L // minimise the MAXIMUM response distance
s.t. Σj dij yij ≤ L ∀ i // worst demand point no farther than L
Σj yij = 1 ∀ i // each demand assigned to one station
yij ≤ xj ∀ i, j // must assign to open station
Σj xj = p
MCLP vs p-center is the efficiency vs equity tradeoff. MCLP maximises total covered demand (an efficiency objective) and is indifferent to the worst-served demand point. The p-center minimises the maximum travel distance (a max-min equity objective) but may cover less total population. These produce different maps on the same instance. A p-median formulation — which minimises total weighted distance — sits between them. No mechanism-free answer picks among the three; the choice is a policy statement.
MEXCLP (Daskin 1983) extends MCLP with busy probabilities. Each candidate station has a probability q of being busy when a call arrives; MEXCLP maximises expected covered demand subject to this degradation. This closes the gap toward Larson's hypercube without the full 2N-state space. MALP (Maximal Availability Location Problem, ReVelle-Hogan 1989) adds backup coverage.
All covering formulations are NP-hard. Practical instances solve via MILP (CPLEX, Gurobi) for small-to-medium problems and Lagrangian relaxation or tabu search for larger ones. Recent work includes robust variants under demand uncertainty (Snyder & Daskin 2006) and multi-objective MCLP for equity-coverage tradeoffs.
Interactive solver
Compare MCLP, LSCP, and p-center on the same candidate map
Fire-Station Siting Solver
Solution interpretation
Three objectives, three maps
MCLP places stations to cover as many people as possible within R, even if a minority of the population sits outside the coverage altogether. The worst-served neighbourhoods may be very far from any station. This is the efficiency-dominant solution.
p-Center sacrifices some total coverage to bound the worst response distance. Every neighbourhood is within L of its nearest station; L is as small as possible for the given p. This is the equity-dominant solution, directly relevant in rural or low-density contexts where a small number of isolated households can skew the utilitarian calculus.
p-Median minimises total weighted distance — a middle ground between the two. Most municipal-siting studies use p-median for generic facility placement but MCLP for time-critical emergency response, where the hard cutoff (covered / not covered at R) matters more than smooth distance minimisation.
Swapping R surfaces the equity tension. A small R (tight response-time standard) leaves more demand uncovered but bounds response time for those who are covered. A large R covers more people but treats 2-minute and 5-minute responses as equivalent — which for a structure fire they are decidedly not.
Limitations & Critique
What MCLP does not see
Uniform coverage radius is a fiction
R is a single number, but real travel times vary by time of day (traffic), weather, station busy state, and incident type. MCLP with a single R over-covers at night and under-covers at rush hour. Time-varying formulations exist but are rarely used in municipal practice.
Availability — busy stations cannot respond
Pure MCLP assumes every open station is always available. Larson (1974)'s hypercube and Daskin (1983)'s MEXCLP correct for this; without them, nominal coverage substantially overstates realised response performance, particularly in high-call-volume areas.
Efficiency vs. equity is a real choice
MCLP's utilitarian “most people covered” objective explicitly accepts leaving isolated or low-density areas uncovered. p-center flips the priority. A municipality's choice between them encodes a political judgment about whose response time matters.
Legacy stations are sunk costs
Real siting problems rarely start from a clean slate. Existing stations are expensive to close and politically contested to relocate. The MCLP “greenfield” formulation ignores path-dependence; practitioners use conditional MCLP / relocation models that evaluate the marginal gain from each closure.
Demand weights embed assumptions
Using residential population as wi ignores commuter flux, commercial occupancy, and event-driven concentrations (stadiums, conferences). Calls-per-capita varies by demographics in ways that overlap with legacy disparities. The honest choice is to report results under multiple weightings, not to claim a single “neutral” weight.
Political feasibility is not in the model
Closures trigger community opposition disproportionate to the utility loss; new stations face siting NIMBYism. OR-optimal maps routinely ignore the political-transaction costs that dominate implementation. A “best” technical solution that cannot pass council is less useful than a somewhat-inferior one that can.
Extensions & variants
From static MCLP to busy-aware, multi-objective, robust variants
MEXCLP & MALP
MCLP with busy probabilities (Daskin 1983) and backup coverage (ReVelle-Hogan 1989). Standard in EMS deployment studies.
Larson hypercube queuing
Full state-space of unit busy-idle combinations (1974). Exact response-time distribution; exponential in N so practical for N ≲ 15.
Multi-objective MCLP
ε-constraint and weighted-sum over {total coverage, worst-case distance, equity Gini}. Surfaces the tradeoff explicitly.
Robust MCLP
Snyder & Daskin (2006). Coverage guarantees under demand or distance uncertainty; box / ellipsoidal uncertainty sets.
Conditional / relocation MCLP
Given current stations, which closures / additions maximise marginal coverage gain? More useful in practice than greenfield MCLP.
Dynamic MCLP
Temporal demand patterns (rush hour, seasons); mobile / relocatable units; continuous-time coverage. Important for EMS more than fire.
Joint fire + EMS + hazmat
Stations typically host multiple unit types with different demand and response standards. Multi-commodity MCLP.
Network-based distances
Replace Euclidean dij with actual street-network travel times (OpenStreetMap, HERE). Changes the optimal map materially in grid-broken cities.
Key references
Cited above · DOIs where available
Related applications
Sibling location & coverage problems