Location-Allocation (P-Median)

The location-allocation problem answers the question: given N potential sites, where should I place P facilities to minimize total customer travel? It’s the mathematical core of network planning for retail chains, hospitals, fire stations, and any service with physical locations.

The P-Median Problem

Minimize Z = Σᵢ Σⱼ (wᵢ × dᵢⱼ × xᵢⱼ)

Subject to:

• Each demand point i is assigned to exactly one facility j
• Exactly P facilities are open
• A demand point can only be assigned to an open facility

Where:

• wᵢ = demand (population, spending power) at point i
• dᵢⱼ = distance/travel time from demand point i to facility j
• xᵢⱼ = 1 if point i is served by facility j, 0 otherwise
• P = number of facilities to locate

“Facility location problems involve flows… the p-median problem minimizes total weighted distance.” — de Smith, Goodchild & Longley, Geospatial Analysis, §7.4

Variants

Model	Objective	Use Case
P-median	Minimize average distance	Retail chains, post offices
P-centre	Minimize maximum distance	Emergency services, hospitals
Coverage	Maximize population within threshold distance	Ambulance stations, cell towers
Maximal coverage	Cover max demand with budget constraint	Any service with fixed budget

How It Works

1. Define demand points — census blocks, residential areas, each with a population weight
2. Define candidate sites — all possible locations you’d consider opening
3. Calculate distance matrix — travel time or distance from every demand point to every candidate
4. Run optimization — find the P sites that minimize total weighted distance
5. Assign customers — each demand point goes to its nearest open facility

Caution

P-median is NP-hard for large problems. For real networks with 10,000+ demand points and 100+ candidates, exact solutions are impractical. Heuristic methods (greedy addition, interchange, Lagrangian relaxation) are used instead.

Heuristic Solutions

de Smith et al. describe three practical approaches:

1. Greedy Addition

Start with no facilities. Add the one that reduces total distance the most. Repeat P times. Fast but can get stuck in local optima.

2. Interchange (Teitz-Bart)

Start with P random facilities. Try swapping each one with a non-selected candidate. Accept swaps that reduce total distance. Repeat until no improvement. Better solutions, slower convergence.

3. Lagrangian Relaxation

Relax the assignment constraint, solve a simpler problem, then iteratively tighten. Provides bounds on how close your solution is to optimal.

Applied to Hong Kong

For a restaurant chain evaluating 14 Wa In Fong East among multiple candidates:

Input	HK Open Data Source	Notes
Demand points	Census TPUs (Tertiary Planning Units)	~450 units across HK Island
Population weights	Census 2021 population by TPU	Resident + working population
Candidate sites	FEHD-licensed restaurant locations	208 in C&W, 17,154 across HK
Distance matrix	Google/OSM network distance	Walking + MTR time

Example: “Where should we open 3 branches on HK Island?”

The p-median solver would evaluate all possible combinations of 3 sites from hundreds of candidates, selecting the trio that minimizes total weighted travel time for the entire Island population.

~450

Demand Points (TPUs)

17,154

Candidate Locations

Single-Site Relevance

For evaluating one specific site (14 Wa In Fong East), location-allocation isn’t the right tool directly. But it answers a critical question:

“Is this site in the optimal set?”

If you run p-median for P=5 branches in Central & Western, and 14 Wa In Fong East doesn’t appear in any solution, that’s a strong signal. If it consistently appears, that validates the location.

Strengths & Limitations

Strengths:

• Mathematically rigorous optimization
• Considers the entire network simultaneously (not just one catchment)
• Answers “where” not just “how good”
• Scales to regional and national planning

Limitations:

• Requires complete distance matrix (expensive to compute)
• NP-hard — heuristics needed for real-world size
• Assumes customers always go to nearest facility (ignores brand preference, quality)
• Static — doesn’t account for time-varying demand

Relationship to Other Models

The p-median model pairs naturally with the Huff Model and Spatial Interaction Model:

1. P-median → identifies where to locate
2. Huff/SIM → predicts how much revenue each location captures
3. Agent simulation → tests what happens when consumers make complex choices

Source

📖 de Smith, M.J., Goodchild, M.F. & Longley, P.A. (2024). Geospatial Analysis: A Comprehensive Guide. §7.4: Facility Location — P-Median and P-Centre Problems.