Ambulance Station Placement

P-Median Problem

Healthcare · Emergency · Strategic Canonical method: p-Median

A city must position p ambulance stations among candidate sites to minimize the population-weighted distance to the nearest station. Every second counts in emergency response — optimal placement can mean the difference between life and death. This is the p-Median Problem, a cornerstone of facility location theory.

The Problem

Minimizing emergency response times across Quebec City

Quebec City’s emergency medical services must decide where to place ambulance stations to serve a population spread across diverse neighborhoods — from the dense historic core of Vieux-Québec to the sprawling suburbs of Charlesbourg and Cap-Rouge. Each neighborhood has a population that generates emergency calls proportional to its size, and the goal is to ensure that the total population-weighted distance from every demand zone to its nearest station is minimized.

Given m candidate sites, n demand zones with population weights w_j, and pairwise distances d(j, i), the objective is to select exactly p stations to open so as to minimize Σ w_j · min_{i ∈ S} d(j, i), where S is the set of opened stations. This is the p-Median Problem — NP-hard for general p (Kariv & Hakimi, 1979).

With 8 demand zones and 5 candidate sites choosing p = 3, there are C(5,3) = 10 possible configurations. But real cities have hundreds of zones and dozens of candidate sites, making exhaustive enumeration infeasible and heuristic methods essential.

Educational Demonstration

Data shown is illustrative. Populations and distances are approximate. Locations represent real Quebec City neighborhoods, but coordinates and population figures are simplified for educational purposes.

The Model

Mathematical formulation of the p-Median Problem

p-Median Formulation minimize Σ_j Σ_i w_j · d_ji · x_ji // total weighted distance
subject to
  Σ_i x_ji = 1 ∀ j // each demand zone assigned to exactly one station
  x_ji ≤ y_i ∀ j, i // can only assign to open stations
  Σ_i y_i = p // exactly p stations opened
  x_ji, y_i ∈ {0, 1} // binary decision variables

Where w_j is the population of demand zone j, d_ji is the distance from zone j to candidate site i, y_i indicates whether station i is opened, and x_ji assigns zone j to station i.

See full p-Median theory and all algorithms

Try It Yourself

Edit demand zones and candidate sites, then solve with all algorithms

Station Placement Solver

8 Zones · 5 Candidates · p = 3

Stations (p): 3

Demand Zones

Name	Lat	Lng	Population

Candidate Station Sites

Name	Lat	Lng

Edit data above and click Solve & Compare All Algorithms.

The Algorithms

Two heuristic approaches for the p-Median Problem

Greedy Add Heuristic

A constructive heuristic that builds the solution incrementally.

Start with no facilities open.
Evaluate each closed candidate: compute the total weighted distance if it were added to the current set.
Open the facility that reduces total weighted distance the most.
Repeat until p facilities are open.

Complexity: O(p · m · n) — fast but may miss global optimum.

Teitz-Bart Interchange Heuristic

An improvement heuristic that refines the greedy solution by swapping facilities.

Start with the greedy solution (p open facilities).
For each open facility, try swapping it with each closed facility.
Accept the swap if total weighted distance improves.
Repeat until no improving swap exists.

Complexity: O(iterations · p · (m−p) · n) — converges to local optimum.

Why It’s More Complex

Real-world ambulance placement goes beyond the p-Median model

Real-World Considerations

Time-varying demand — call volumes shift between day and night, weekdays and weekends, requiring dynamic repositioning strategies.
Traffic congestion — travel times vary by time of day and route; Euclidean distance is a poor proxy for actual response time in urban areas.
Coverage constraints — regulations may require that every zone has a station within a maximum response time (the Set Covering variant).
Multiple vehicle types — basic life support vs. advanced life support units have different capabilities and deployment considerations.
Relocation during calls — when an ambulance is dispatched, remaining units must be repositioned to maintain coverage across the city.
Backup coverage — ensuring that zones have access to a second-nearest station in case the primary unit is unavailable.

Beyond the p-Median formulation

The p-Median model on this page minimizes population-weighted distance. Two richer families dominate real ambulance-location literature:

Maximal Covering Location Problem (MCLP) — Church & ReVelle (1974). Instead of minimizing distance, maximize demand covered within a response-time threshold $\tau$ (e.g., the NFPA 8-minute target): $\max \sum_j w_j z_j$ s.t. $z_j \leq \sum_{i \in N_j(\tau)} y_i$. More realistic when regulators mandate coverage targets rather than average response.
Double Standard Model (DSM) — Gendreau, Laporte & Semet (1997). A two-tier coverage requirement (every zone within a long threshold; a fraction within a short one) and minimum backup coverage. Adopted in practice by several European EMS providers.
Probabilistic / dynamic variants — Brotcorne, Laporte & Semet (2003) survey the progression from static siting to real-time relocation as ambulances become busy. Aringhieri et al. (2017) extends the lens to the full emergency-care pathway.

The repository positions this page at Emergency × Strategic in the Hulshof (2012) taxonomy — see the landing-page framework for the full decision grid.

Key References

Hakimi, S. L. (1964). Seminal “Optimum locations of switching centers and the absolute centers and medians of a graph.” Operations Research, 12(3), 450–459. doi:10.1287/opre.12.3.450
Toregas, C., Swain, R., ReVelle, C., & Bergman, L. (1971). Seminal “The location of emergency service facilities.” Operations Research, 19(6), 1363–1373. doi:10.1287/opre.19.6.1363 — the Set Covering Location Problem (LSCP) that defines ambulance-coverage formulations.
Church, R., & ReVelle, C. (1974). Seminal “The maximal covering location problem.” Papers of the Regional Science Association, 32(1), 101–118. doi:10.1007/BF01942293 — MCLP, the coverage-maximization counterpart to p-Median and the most-cited model for ambulance location.
Kariv, O., & Hakimi, S. L. (1979). Complexity “An algorithmic approach to network location problems. II: The p-medians.” SIAM Journal on Applied Mathematics, 37(3), 539–560. doi:10.1137/0137041
Teitz, M. B., & Bart, P. (1968). Applied “Heuristic methods for estimating the generalized vertex median of a weighted graph.” Operations Research, 16(5), 955–961. doi:10.1287/opre.16.5.955 — the vertex-interchange heuristic still used as a benchmark.
ReVelle, C. S., & Eiselt, H. A. (2005). Survey “Location analysis: A synthesis and survey.” European Journal of Operational Research, 165(1), 1–19. doi:10.1016/j.ejor.2003.11.032
Brotcorne, L., Laporte, G., & Semet, F. (2003). Survey “Ambulance location and relocation models.” European Journal of Operational Research, 147(3), 451–463. doi:10.1016/S0377-2217(02)00364-8 — canonical survey spanning static, probabilistic, dynamic, and multi-period ambulance location.
Aringhieri, R., Bruni, M. E., Khodaparasti, S., & van Essen, J. T. (2017). Survey “Emergency medical services and beyond: Addressing new challenges through a wide literature review.” Computers & Operations Research, 78, 349–368. doi:10.1016/j.cor.2016.09.016 — reframes EMS planning around the emergency care pathway (dispatch, relocation, transport).
Hulshof, P. J. H., Kortbeek, N., Boucherie, R. J., Hans, E. W., & Bakker, P. J. M. (2012). Taxonomy “Taxonomic classification of planning decisions in health care: A structured review of the state of the art in OR/MS.” Health Systems, 1(2), 129–175. doi:10.1057/hs.2012.18 — positions this page at Emergency × Strategic in the healthcare planning taxonomy.
Algorithm implementations from this repository’s p-Median module and the canonical problem reference for location & covering.

Need to Optimize Facility Placement?

Every emergency services system has unique constraints — terrain, traffic patterns, population density, regulatory requirements. This demo shows the fundamentals, but real-world solutions require tailored modeling and implementation.