Ambulance Station Placement

P-Median Problem

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.

Key References

Hakimi, S. L. (1964). "Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph." Operations Research, 12(3), 450–459.
ReVelle, C. S. & Eiselt, H. A. (2005). "Location Analysis: A Synthesis and Survey." European Journal of Operational Research, 165(1), 1–19.
Kariv, O. & Hakimi, S. L. (1979). "An Algorithmic Approach to Network Location Problems." SIAM Journal on Applied Mathematics, 37(3), 539–560.
Teitz, M. B. & Bart, P. (1968). "Heuristic Methods for Estimating the Generalized Vertex Median of a Weighted Graph." Operations Research, 16(5), 955–961.
Application context and algorithm implementations from this repository’s p-Median module.

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.