Capacity Planning
Facility Location · p-Median
A healthcare network must position p facilities among candidate sites to minimize the population-weighted response time across demand zones. Optimal facility placement can reduce emergency response times by 20–40% (Li et al., 2011), and every minute of reduced response for cardiac arrest increases survival by 5–10%. This is the Uncapacitated Facility Location Problem (UFLP), an NP-hard cornerstone of location science.
The Problem
Optimal placement of healthcare facilities to minimize response time
A regional healthcare authority must decide where to place medical facilities to serve a population spread across diverse neighborhoods — from the dense Downtown Core with 45,000 residents to the sparse Highway Corridor with 7,000. Each population zone 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 facility is minimized.
| Healthcare Domain | Mathematical Concept | In This Model |
|---|---|---|
| Facility | Candidate site | 10 candidate locations with fixed costs |
| Population zone | Demand point | 20 zones with weighted populations |
| Population | Demand weight wj | 6K – 45K residents per zone |
| Response time | Distance dji | Euclidean distance (grid units) |
Given m = 10 candidate sites, n = 20 demand zones with population weights wj, and pairwise distances d(j, i), the objective is to select exactly p = 4 facilities to open so as to minimize Σ wj · mini ∈ S d(j, i), where S is the set of opened facilities. This is the p-Median Problem — NP-hard in general. The UFLP variant adds fixed opening costs fi and is also NP-hard with a best known approximation ratio of 1.488 (Li, 2013).
The Model
Uncapacitated Facility Location Problem (UFLP)
subject to
Σi xji = 1 ∀ j // each zone assigned to exactly one facility
xji ≤ yi ∀ j, i // can only assign to open facilities
Σi yi = p // exactly p facilities opened (p-Median variant)
xji, yi ∈ {0, 1} // binary decision variables
Where fi is the fixed cost of opening facility i, wj is the population of demand zone j, dji is the distance from zone j to candidate site i, yi indicates whether facility i is opened, and xji assigns zone j to facility i.
See full Facility Location theoryTry It Yourself
Select a scenario, adjust parameters, then solve with all algorithms
Facility Location Solver
10 Sites · 20 Zones · p = 4| Name | X | Y | Cost ($K) | Type |
|---|
| Name | X | Y | Population (K) |
|---|
The Algorithms
Three approaches for the Facility Location Problem
The UFLP is NP-hard with a best known approximation ratio of 1.488. In practice, constructive heuristics (Greedy Add, Greedy Drop) produce solutions within 5–15% of optimality in milliseconds, while Simulated Annealing can close the gap to 1–3% with more computation time. For networks with 10–50 sites, these heuristics are often sufficient.
Greedy Add Constructive
Builds the solution incrementally by opening one facility at a time.
- Start with no facilities open.
- Evaluate each closed candidate: compute total weighted distance if it were added.
- Open the facility that reduces total cost the most.
- Repeat until p facilities are open.
Complexity: O(p · m · n) — fast but may miss global optimum.
Greedy Drop Destructive
Starts with all facilities open and removes the least useful one at each step.
- Open all m facilities.
- Evaluate each open facility: compute total cost if it were closed.
- Close the facility whose removal increases cost the least.
- Repeat until exactly p facilities remain.
Complexity: O((m−p) · m · n) — complementary perspective to Greedy Add.
Simulated Annealing Metaheuristic
Probabilistic method that escapes local optima by accepting worse solutions with decreasing probability.
- Start with a random set of p open facilities.
- Swap one open facility with one closed facility.
- Accept if cost improves, or probabilistically if it worsens.
- Cool temperature; repeat until frozen.
Complexity: O(iterations · n · m) — converges to near-optimal with tuning.
Why It’s More Complex
Real-world healthcare facility planning goes beyond the p-Median model
Time-Varying Demand
Patient arrival rates shift between day and night, weekdays and weekends, requiring dynamic capacity allocation and repositioning strategies.
Traffic & Geography
Travel times vary by time of day, road conditions, and terrain. Euclidean distance is a poor proxy for actual ambulance response time in urban areas.
Coverage Constraints
Regulations may require every zone to have a facility within a maximum response time, introducing hard Set Covering constraints alongside the p-Median objective.
Capacity Limits
Real facilities have finite bed counts, staffing levels, and equipment. The capacitated variant (CFLP) adds upper bounds on each facility’s assignment volume.
Budget Constraints
Opening costs, staffing budgets, and construction timelines create multi-period capital planning problems that extend beyond single-period UFLP models.
Key References
- (2011). “Covering models and optimization techniques for emergency response facility location.” Mathematical Methods of Operations Research, 74(3), 281–310. DOI: 10.1007/s00186-011-0363-4
- (2003). “Ambulance location and relocation models.” European Journal of Operational Research, 147(3), 451–463. DOI: 10.1016/S0377-2217(02)00364-8
- (2017). “Emergency medical services location problems.” Annals of Operations Research, 253(1), 129–154. DOI: 10.1007/s10479-016-2268-8
Need to Optimize Facility Placement?
Every healthcare 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.