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.

Strategic

Staff Planning

Patient Flow

Supply Chain

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 w_j	6K – 45K residents per zone
Response time	Distance d_ji	Euclidean distance (grid units)

Given m = 10 candidate sites, n = 20 demand zones with population weights w_j, and pairwise distances d(j, i), the objective is to select exactly p = 4 facilities to open so as to minimize Σ w_j · min_{i ∈ 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 f_i and is also NP-hard with a best known approximation ratio of 1.488 (Li, 2013).

Educational Demonstration

Data shown is illustrative. Populations and distances are approximate. Locations represent a fictional regional healthcare network; coordinates and population figures are simplified for educational purposes.

The Model

Uncapacitated Facility Location Problem (UFLP)

UFLP Formulation minimize Σ_i f_i · y_i + Σ_j Σ_i w_j · d_ji · x_ji // fixed cost + weighted distance
subject to
  Σ_i x_ji = 1 ∀ j // each zone assigned to exactly one facility
  x_ji ≤ y_i ∀ j, i // can only assign to open facilities
  Σ_i y_i = p // exactly p facilities opened (p-Median variant)
  x_ji, y_i ∈ {0, 1} // binary decision variables

Where f_i is the fixed cost of opening facility i, 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 facility i is opened, and x_ji assigns zone j to facility i.

See full Facility Location theory

Try It Yourself

Select a scenario, adjust parameters, then solve with all algorithms

Facility Location Solver

10 Sites · 20 Zones · p = 4

Scenario

Facilities (p): 4

Candidate Sites

Name	X	Y	Cost ($K)	Type

Population Zones

Name	X	Y	Population (K)

Candidate Site (closed) Open Facility Population Zone

Select a scenario and click Solve & Compare All Algorithms.

The Algorithms

Three approaches for the Facility Location Problem

Key Insight

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.

Beyond p-Median / UFLP

The solver on this page uses the classical p-Median and UFLP formulations (Hakimi 1964; Balinski 1965). The healthcare facility-location literature (Ahmadi-Javid, Seyedi & Syam, 2017) documents a much broader model bestiary:

Capacitated FLP (CFLP) — facilities have finite capacity $q_i$, so demand allocation becomes constrained: $\sum_j w_j x_{ji} \leq q_i y_i$. The standard generalization when hospitals have bed or throughput caps.
Maximal Covering Location Problem (MCLP) — maximize population covered within a response-time threshold, rather than minimize total distance. Used by regulators that set target-coverage mandates.
Hierarchical facility location — primary + secondary + tertiary care coordinated simultaneously. Critical for regional health-network design.
Stochastic / robust variants — demand uncertainty, disaster resilience, and budget-at-risk.

This page sits at Inpatient × Strategic in the Hulshof (2012) taxonomy but has strong cross-cutting character with Ambulatory (outpatient clinic networks) and Emergency (the ambulance station placement page uses the same model family).

Key References

Hakimi, S. L. (1964). Seminal “Optimum locations of switching centers and the absolute centers and medians of a graph.” Operations Research, 12(3), 450–459. doi:10.1287/opre.12.3.450 — defines the p-Median problem.
Balinski, M. L. (1965). Seminal “Integer programming: Methods, uses, computation.” Management Science, 12(3), 253–313. doi:10.1287/mnsc.12.3.253 — introduces the UFLP formulation.
ReVelle, C. S., & Swain, R. W. (1970). Seminal “Central facilities location.” Geographical Analysis, 2(1), 30–42. doi:10.1111/j.1538-4632.1970.tb00142.x
Daskin, M. S. (2013). Textbook Network and Discrete Location: Models, Algorithms, and Applications (2nd ed.). Wiley. doi:10.1002/9781118537015 — canonical textbook covering p-Median, UFLP, CFLP, MCLP with healthcare case studies.
Li, X., Zhao, Z., Zhu, X., & Wyatt, T. (2011). Survey “Covering models and optimization techniques for emergency response facility location and planning: A review.” Mathematical Methods of Operations Research, 74(3), 281–310. doi:10.1007/s00186-011-0363-4
Brotcorne, L., Laporte, G., & Semet, F. (2003). Survey “Ambulance location and relocation models.” European Journal of Operational Research, 147(3), 451–463. doi:10.1016/S0377-2217(02)00364-8
Aringhieri, R., Bruni, M. E., Khodaparasti, S., & van Essen, J. T. (2017). Survey “Emergency medical services and beyond: Addressing new challenges through a wide literature review.” Computers & Operations Research, 78, 349–368. doi:10.1016/j.cor.2016.09.016
Ahmadi-Javid, A., Seyedi, P., & Syam, S. S. (2017). Survey “A survey of healthcare facility location.” Computers & Operations Research, 79, 223–263. doi:10.1016/j.cor.2016.05.018 — the most comprehensive recent review of discrete, continuous, and network models for healthcare facility location.
Hulshof, P. J. H., Kortbeek, N., Boucherie, R. J., Hans, E. W., & Bakker, P. J. M. (2012). Taxonomy “Taxonomic classification of planning decisions in health care: A structured review of the state of the art in OR/MS.” Health Systems, 1(2), 129–175. doi:10.1057/hs.2012.18 — positions this page at Inpatient × Strategic (with strong cross-cutting character into Ambulatory).

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.