School Location Planning
p-Median Problem — NP-Hard
A municipal education authority must decide which candidate sites to open as new schools to minimize the average distance children travel. Each mislocated school affects 500–2,000 students for a 30-year lifespan, with annual busing costs of $200–$800 per student for those beyond walking distance.
Where This Decision Fits
Public education planning — the highlighted step is what this page optimizes
The Problem
Select p sites from candidates to minimize total weighted student travel distance
A municipal district evaluates 6 candidate school sites to serve 10 residential demand zones with student populations ranging from 200 to 1,200 children. The authority must open exactly p schools (determined by budget constraints) such that the total population-weighted travel distance is minimized.
This is the classical p-Median Problem, proven NP-hard by reduction from Set Cover (Kariv & Hakimi, 1979). Unlike the uncapacitated facility location problem, here the number of open facilities is fixed at p rather than being a cost-driven decision.
subject to
Σi xij = 1 ∀ j // each zone assigned to exactly one school
xij ≤ yi ∀ i,j // assign only to open schools
Σi yi = p // open exactly p schools
yi ∈ {0, 1} // open or not
xij ≥ 0 // assignment fraction
Where wj is the student population of zone j, dij is the distance from candidate site i to zone j, yi is the binary open/close decision, and xij is the assignment variable.
See Integer Programming theoryTry It Yourself
Choose p and an algorithm to find the best school locations
School Location Optimizer
6 Sites · 10 Zones| Site | Location | Build Cost ($M) |
|---|
| Zone | Students | Households (k) |
|---|
Ready. Click “Solve & Compare All Algorithms” to run.
| Algorithm | Total Wt. Dist. | Schools Open | Time |
|---|---|---|---|
| Click Solve & Compare All Algorithms | |||
The Algorithms
Three approaches to the p-Median problem
Greedy Add
O(p · n · m) | No guarantee for p-MedianStart with no schools open. At each step, evaluate the reduction in total weighted distance from opening each remaining candidate. Open the site with the greatest improvement. Repeat until exactly p schools are open. This constructive heuristic is fast and often produces good initial solutions, though it may miss the global optimum because early greedy choices cannot be undone.
Greedy Swap (Teitz-Bart)
O(iter · p · (n−p) · m) | Local optimumBegin from the Greedy Add solution with p open schools. At each iteration, try every possible swap: close one open school, open one closed site. Accept the swap that yields the largest cost reduction. Repeat until no improving swap exists. This is the classical Teitz & Bart (1968) vertex substitution method, which often reaches a strong local optimum and is the basis for many practical p-Median solvers.
Random
O(k · m) | No guaranteeRandomly select p candidate sites and evaluate the resulting total weighted distance. Repeat for a fixed number of random trials and return the best solution found. This stochastic approach serves as a baseline to compare against the intelligent heuristics, illustrating how much structure the greedy and swap methods exploit.
Real-World Complexity
Why practical school siting goes beyond the basic p-Median model
Beyond the p-Median
- Capacity constraints — Each school has a maximum enrollment; the uncapacitated model may overload popular sites
- Walking distance thresholds — Students within 1–2 km walk; beyond that threshold busing is required, creating a step-function cost
- Equity requirements — Regulations may mandate that no child travels more than a maximum distance, adding covering constraints
- Demographic forecasting — Birth-rate trends, housing developments, and migration shift student populations over the 30-year school lifespan
- Multi-level schooling — Elementary, middle, and high schools serve different age groups with different catchment radii
- Safe routes — Network distance along safe walking routes differs from Euclidean distance; highway crossings and crime zones affect feasibility
- Existing infrastructure — Renovation of existing schools vs. greenfield construction creates asymmetric cost structures
Key References
Foundational works in facility location and the p-Median problem
- (1964). “Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph.” Operations Research, 12(3), 450–459.
- (1968). “Heuristic Methods for Estimating the Generalized Vertex Median of a Weighted Graph.” Operations Research, 16(5), 955–961.
- (1979). “An Algorithmic Approach to Network Location Problems. Part II: The p-Medians.” SIAM Journal on Applied Mathematics, 37(3), 539–560.
Need to optimize your school network?
From school siting to bus routing and staff allocation, mathematical modeling can transform public infrastructure decisions. Let’s discuss how Operations Research can work for you.