School Location Planning
p-Median · ReVelle-Swain (1970) · Teitz-Bart interchange
Canonical method: p-MedianWhere should a district build (or close) schools so the total distance students travel is minimised? The question reduces to the classical p-median problem — open p facilities to minimise weighted distance from a set of demand points. Hakimi (1964) introduced the absolute p-center / p-median on graphs; ReVelle & Swain (1970) gave the first LP-based formulation; Teitz & Bart (1968) contributed the interchange heuristic that remains the practical workhorse. Distinct from school-choice-mechanism: this is about where schools exist; that is about who gets assigned.
Problem context
Where a school exists shapes who can attend it
A school district (or a state, or a nonprofit charter network) has a budget to open p schools from a set of candidate locations. Each residential block has an expected student population; each candidate location carries opening costs, capacity bounds, and proximity characteristics. The operational question is which p locations minimise the total (weighted) distance students travel. In most practical studies this is also constrained by maximum travel time (a busing budget), school capacity, and a requirement that every student be assigned to exactly one school.
The p-median formulation traces to Hakimi (1964) and ReVelle & Swain (1970); Kariv & Hakimi (1979) proved it NP-hard for general p. The Teitz & Bart (1968) vertex-interchange heuristic — repeatedly swap one open facility with a closed candidate if the swap improves the objective — is the practical baseline; modern practitioners add Lagrangian relaxation, MILP with valid inequalities, or tabu-search.
For public-school siting specifically, the formulation carries equity constraints that generic p-median does not. Districts often require that no neighbourhood's travel distance exceed a maximum threshold (a p-center-like constraint), that school capacity reflect enrollment forecasts rather than physical building size, and that proposed closures trigger different decision politics than proposed new sites. The mathematical tool is stable; the policy wrapping is where the action is.
Multi-stakeholder framing
Mathematical formulation
p-Median, capacitated, and equity-constrained variants
| Symbol | Definition | Domain |
|---|---|---|
| I | Set of demand points (blocks with students) | |I| = n |
| J | Set of candidate school sites | |J| = m |
| wi | Number of students at demand point i | ℕ⁺ |
| dij | Distance (or travel time) from i to j | ℝ⁺ |
| qj | Capacity of candidate site j | ℕ⁺ |
| p | Number of schools to open | ℕ⁺ |
| xj | Binary: 1 if school opened at j | {0, 1} |
| yij | Binary (or fractional): 1 if demand i assigned to j | {0, 1} |
s.t. Σj yij = 1 ∀ i // each demand point assigned to exactly one school
yij ≤ xj ∀ i, j // must assign to open site
Σj xj = p // open exactly p schools
xj, yij ∈ {0, 1}
Capacitated p-Median (CPMP) Add: Σi wi yij ≤ qj ∀ j // capacity constraint per school
Allow fractional yij for multi-assignment (e.g., grade-band splits)
Equity-constrained (max-distance cap) Add: dij yij ≤ Dmax ∀ i, j // nobody assigned farther than D_max
Complexity Uncapacitated p-median NP-hard (Kariv-Hakimi 1979); exact MILP practical for n,m ≲ 500 via modern solvers. Heuristics: Teitz-Bart vertex interchange (O(nmp)), greedy add / drop, Lagrangian, GRASP, tabu search.
Interactive solver
Greedy + Teitz-Bart interchange on a synthetic district map
p-Median School Siting Solver
Solution interpretation
Reading the map — and what it hides
Teitz-Bart typically beats greedy on the same instance — greedy is myopic and can trap itself in a poor configuration that a single swap would improve. On small scenarios the two often match; on larger ones the interchange advantage grows.
Adding the capacity constraint generally increases total weighted distance (the feasible set is smaller). Students from populous neighbourhoods may now be assigned to a farther school when their nearest one is full. This is a policy-relevant effect: uncapped p-median underestimates the real-world distance students travel in districts with actual capacity constraints.
The map's aggregate metric (total weighted distance) can hide large variance. A few isolated neighbourhoods may have 2–3x the average travel distance. Districts often respond by adding a maximum-distance (p-center-like) constraint — reducing aggregate efficiency to bound the worst case. The equity constraint is the policy knob that makes this model acceptable.
Limitations & Critique
Why “minimise average distance” is not the whole story
School closures track historical disinvestment
When districts close schools, the closures have disproportionately affected communities of colour and low-income neighbourhoods — documented in Chicago, Philadelphia, Detroit, and elsewhere. A p-median solution that closes the “highest-cost” school may be mathematically right and socially catastrophic. The efficiency objective cannot adjudicate this; it must be a policy decision with community input.
Enrollment forecasts drive everything and are often wrong
Demand wi is a forecast (typically 5–10 years out). Births, migration, gentrification, charter-school growth, and policy changes all shift it. Districts routinely close schools because projected enrollment fell, then scramble to re-open or bus in when projections were wrong. Robust and scenario-based p-median address this but are rarely used in practice.
Distance is a coarse accessibility proxy
Travel distance ignores transit access, pedestrian safety, crossing dangerous arterials, school start-time alignment with parent work schedules, and the specific-needs geography of special education. A 2-km walk past a highway is functionally different from a 2-km walk in a residential neighbourhood.
Legacy schools are capital-sunk
New schools cost $10M–$100M. Closures forfeit those capital investments. A p-median model that recommends closing 20-year-old schools to open greenfield sites conflates total-cost with future-marginal-cost. Conditional / relocation p-median that treats existing schools as low-cost- to-keep is more realistic.
Segregation persists across siting choices
Because residential patterns are themselves segregated, p-median solutions tend to concentrate neighbourhood students in nearest-school attendance zones — replicating residential segregation. Fighting this requires controlled-choice assignment (see school-choice-mechanism), which is a different problem, or intentional zone-boundary design, which has its own political costs.
Capacity means different things in different eras
A building's physical capacity and its instructional capacity diverge. Class-size regulations, special-education requirements, programme needs (music, science labs), and post-COVID ventilation standards all shift usable capacity. The qj parameter cannot be a single static number and be taken seriously.
Extensions & variants
Capacity, equity, dynamics, robustness
Capacitated p-median (CPMP)
Add capacity constraint qj per site; more realistic for school planning. Lorena & Senne (2004) column generation.
Equity-constrained p-median
Cap maximum assigned distance per student. Blends p-median efficiency with p-center equity.
Dynamic / multi-period p-median
Enrollment changes over 5–10 years; open / close schools across a planning horizon. Current-ReVelle-Cohon (1990).
Robust p-median
Snyder & Daskin (2006). Uncertainty-set over demand or distance; conservative siting under forecast error.
Conditional / relocation p-median
Existing schools are cheap to keep; closures have political cost. Marginal-gain formulation more realistic than greenfield.
Multi-objective
ε-constraint over {total distance, max distance, closure count, equity Gini}. Surfaces the tradeoff.
Network-based distance
Use street network travel times / walking-safe routes, not Euclidean distance. Changes optimal maps in cities with highways or rivers.
Joint location-routing for bus fleet
If the district buses students, the siting problem interacts with a VRP. Laporte, Nickel, Saldanha-da-Gama (2019) handbook.
Key references
Cited above · DOIs where available
Related applications
The siting / assignment siblings