The Facility Location Problem: Where to Place Resources for Maximum Coverage

Why the Obvious Greedy Picks Fail

A natural first instinct is to rank every candidate site by how much nearby demand it could serve, then simply take the top p sites. This fails because it ignores competition between facilities for the same demand points. If two of the best-ranked sites both sit near the same dense cluster of demand, picking both wastes a facility on redundant coverage while some other, sparser region of the map is left completely unserved. In reality, once a facility is opened, nearby demand points are assigned to it, and any other facility competing for that same demand no longer needs to be there. This means the value of adding a facility at a particular site is not a fixed number you can compute in isolation; it depends on which other facilities have already been chosen. Two mediocre sites that together cover complementary regions can beat two locally excellent sites that overlap. This interdependence between choices is exactly what makes facility location a genuine combinatorial optimization problem rather than a simple sorting exercise, and it is why the field needs formal objective functions and dedicated algorithms rather than a one-pass ranking.

The p-Median Objective: Minimizing Average Travel

The most widely used formulation is the p-median problem. Given a set of demand points, each with a weight w_i representing how much demand originates there (a population count, an order volume, a number of vehicles), and a candidate set of facility locations, the goal is to choose exactly p of those locations to open so that total weighted travel distance is as small as possible. Formally, if we let d(i, nearest open facility) denote the distance from demand point i to whichever open facility is closest to it, the objective is: minimize the sum over all demand points i of w_i times d(i, nearest open facility). Every demand point is served by its single nearest open facility, and the p-median objective adds up all of those weighted distances and tries to make the total as small as possible. This is fundamentally an average-case, efficiency-oriented objective: it is the natural choice when you care about minimizing total cost or total travel time across an entire system, such as a distribution network where every mile driven costs money, or a retail chain trying to minimize aggregate customer travel. A useful mental model is that p-median facilities gravitate toward the centers of mass of dense demand clusters, since serving a lot of weighted demand with a short average distance does more to shrink the total sum than serving a few far-flung, lightly weighted points well.

The p-Center Objective: Minimizing the Worst Case

A very different, equally important formulation is the p-center problem. Instead of minimizing the total or average distance, it minimizes the maximum distance that any single demand point has to travel to reach its nearest open facility. Formally: minimize the maximum, over all demand points i, of d(i, nearest open facility). Where p-median asks a system-wide question (how much total travel does this network require), p-center asks a worst-case question (what is the longest anyone will ever have to wait or travel, in the least convenient case). This distinction matters enormously in practice. For a warehouse network optimizing shipping costs, average cost is what matters, so p-median is the right tool. But for siting fire stations or ambulance depots, nobody wants to be the one household that is, on average, well served by the system but happens to sit an unacceptably long response time from any facility; an emergency planner cares about the worst-case response time, not the citywide average, which is exactly what p-center directly controls. This makes p-center the natural framework whenever the objective is equity or guaranteed service levels rather than aggregate efficiency, and the two formulations can genuinely disagree on where to place facilities: an optimal p-median solution can leave one remote demand point badly underserved even while achieving an excellent system-wide average, precisely the outcome a p-center solution is designed to prevent.

NP-Hardness and Practical Heuristics

Both p-median and p-center are NP-hard in general: the number of ways to choose p facilities out of n candidate sites grows combinatorially (n choose p), and there is no known algorithm that finds the guaranteed optimal solution in time that scales reasonably as the problem grows. Even modest instances with a few hundred candidate sites and a dozen facilities to place can have more possible combinations than there are atoms worth counting by brute force. This is why real-world facility location relies on heuristics that find very good, though not certified-optimal, solutions quickly. A common approach is greedy construction with local search: start by adding facilities one at a time, each time picking whichever remaining candidate site most reduces the objective given the facilities already placed, then refine the result with swap moves that try replacing one open facility with a closed candidate and keep the swap if it improves the objective, repeating until no beneficial swap remains. Another family of heuristics borrows the spirit of Lloyd's algorithm from k-means clustering: alternate between assigning every demand point to its nearest currently-open facility, and then relocating each facility to the point (or candidate site) that best serves the demand points currently assigned to it, repeating this relabel-and-relocate cycle until the assignment stabilizes. Neither approach guarantees the true optimum, and both can get stuck in a locally good but globally suboptimal arrangement, so practitioners often run them from multiple random starting configurations and keep the best result found, trading a proof of optimality for a solution that is good enough, fast enough, and robust in practice.

Real-World Applications

Facility location shows up wherever a limited number of physical resources must serve a spread-out population. EV charging network planning uses p-median-style models to decide where to place a fixed number of charging stations along highways or across a city so that total driver detour distance is minimized, while some planners layer in p-center-style constraints to guarantee that no driver in a rural region is ever stranded far from the nearest charger. Warehouse and distribution center siting is a textbook p-median application: retailers and logistics companies choose a handful of warehouse locations out of many candidate sites to minimize total weighted shipping distance to all their customers or stores, directly translating into lower fuel costs and faster average delivery times. Emergency service placement, including fire stations, ambulance depots, and disaster-relief supply caches, leans heavily on p-center thinking, since regulators and planners typically care about guaranteeing a maximum response time to every neighborhood rather than only minimizing the citywide average. Many real deployments actually blend both ideas, first using a p-center-style constraint to guarantee every point falls within some maximum acceptable distance of a facility, then using a p-median-style objective to pick the specific configuration, among all those meeting that guarantee, that minimizes total cost.

Frequently asked questions

Try it live

Everything above runs in your browser — open The Facility Location Problem: Where to Place Resources for Maximum Coverage and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.