Store Location Selection
p-Median / Facility Location · NP-Hard
A retail chain expanding to a new market must choose which of 6 candidate sites to open as stores, maximizing coverage of 10 demand zones. Each mislocated store costs €2–5M in lost foot traffic over its 10-year lease. The p-Median Problem selects p locations minimizing total weighted customer travel.
Where This Decision Fits
Retail supply chain — the highlighted step is what this page optimizes
The Problem
Select p sites from candidates to minimize total weighted customer distance
A retail chain evaluates 6 candidate store sites to serve 10 demand zones in a new metropolitan market. Each demand zone has a known population weight representing expected weekly customer visits. The chain must open exactly p stores (chosen by budget and strategy) such that the total demand-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 store
xij ≤ yi ∀ i,j // assign only to open stores
Σi yi = p // open exactly p stores
yi ∈ {0, 1} // open or not
xij ≥ 0 // assignment fraction
Where wj is the demand weight 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 store locations
Store Location Optimizer
6 Sites · 10 Zones| Site | Location | Rent (€k/yr) |
|---|
| Zone | Demand Weight | Population (k) |
|---|
Ready. Click “Solve & Compare All Algorithms” to run.
| Algorithm | Total Wt. Dist. | Stores 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 stores 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 stores 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
O(iter · p · (n−p) · m) | Local optimumBegin from the Greedy Add solution with p open stores. At each iteration, try every possible swap: close one open store, open one closed store. Accept the swap that yields the largest cost reduction. Repeat until no improving swap exists. This neighborhood search often reaches a strong local optimum and is the basis for many practical p-Median solvers.
Exhaustive Enumeration (p≤2)
O(C(n,p) · m) | OptimalEnumerate all C(n, p) combinations of candidate sites and evaluate each. Return the combination with minimum total weighted distance. This guarantees the global optimum but is only practical for small p: with n=6 and p=2 there are just 15 combinations. For larger p, the number of combinations grows combinatorially and the algorithm becomes intractable.
Real-World Complexity
Why practical store location goes beyond the basic p-Median model
Beyond the p-Median
- Competitor proximity — Existing rival stores cannibalize demand; gravity models capture market-share splitting
- Cannibalization — Opening stores too close together splits the chain’s own customer base rather than growing it
- Multi-format stores — Flagship, convenience, and warehouse formats serve different customer segments with different catchments
- Real-estate constraints — Lease availability, zoning, parking requirements, and landlord negotiations restrict true candidate set
- Time-varying demand — Weekday commuter traffic vs. weekend residential demand shifts optimal locations
- Demographic forecasting — Population growth, gentrification, and transit expansions alter 10-year demand projections
- Supply chain integration — Store locations must align with distribution center networks and delivery route efficiency
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.
- (1977). “Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms.” Management Science, 23(8), 789–810.
- (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 retail network?
From store location selection to inventory allocation and last-mile delivery, mathematical modeling can transform retail investment decisions. Let’s discuss how Operations Research can work for you.