Retail Store Location
p-Median · MCLP · Huff gravity
Choose which of \(m\) candidate sites to open as retail stores so the chain reaches its customers best. The classical formulations are p-Median (minimise weighted distance / drive-time) and Maximal Covering (MCLP; maximise demand within a threshold). The retail-specific layer is Huff's gravity model of store attraction, which turns distance into a share of each customer's spend, and the cannibalisation question of how a new store eats into the chain's existing market. Foundational papers: Hakimi (1964); Church & ReVelle (1974); Huff (1964).
Why it matters
Location drives lifetime revenue; once opened, a store stays
Where the decision sits
Chain network strategy · 5-20 year horizon · irreversible
Retail store location is a strategic decision: it fixes the chain's physical footprint for years and drives every downstream operation (assortment, labour, replenishment). The retail framing differs from generic facility location in three ways: (i) trade area — catchment defined by drive time, competitors, and demographics, not pure Euclidean distance; (ii) Huff attraction — demand at a customer is split across stores in proportion to a gravity score, not allocated entirely to the nearest; (iii) cannibalisation — a new store steals from the chain itself, so incremental revenue matters more than total. Pure warehouse / DC siting lives under logistics facility location; the generic p-Median family sits under Location & Covering.
Problem & formulation
Three closely-related MIPs — pick the objective that matches the retailer’s economics
Sets and parameters
| Symbol | Meaning | Unit |
|---|---|---|
| \(i \in \mathcal{J}\) | Candidate site (\(|\mathcal{J}| = m\)) | finite |
| \(j \in \mathcal{I}\) | Demand zone / customer cluster (\(|\mathcal{I}| = n\)) | finite |
| \(w_j\) | Demand weight at zone \(j\) (population × per-capita spend) | $ / yr |
| \(d_{ij}\) | Drive-time distance from site \(i\) to zone \(j\) | min or km |
| \(D\) | Coverage threshold | min or km |
| \(p\) | Number of stores to open | integer |
Decision variables
| Symbol | Meaning | Domain |
|---|---|---|
| \(y_i\) | 1 if site \(i\) opened as a store | binary |
| \(x_{ij}\) | 1 if zone \(j\) assigned to store \(i\) | binary |
p-Median: minimise weighted drive-time
Each zone is assigned to one open store; exactly \(p\) stores are opened. Hakimi (1964) proved optima lie at vertices on a graph; Kariv & Hakimi (1979) proved NP-hardness.
Maximal Covering (MCLP): maximise covered demand
\(z_j = 1\) iff zone \(j\) is within threshold \(D\) of at least one open store. MCLP maximises reach rather than travel cost — natural when the retailer cares about coverage. Church & ReVelle (1974).
Huff gravity attraction
Huff (1964) shifts from “nearest-store wins” to probabilistic share: zone \(j\)'s probability of shopping at store \(i\) depends on store attractiveness \(A_i\) (size, brand, parking) and distance:
\(\gamma\) is the distance-decay parameter (typically 1-3). Expected sales at store \(i\) is \(\sum_j w_j P_{ij}\). Cannibalisation emerges endogenously: opening a new store near an existing one steals share in proportion to its own attractiveness. Joint optimisation over \(y\) is nonlinear; practice approximates with p-Median and audits cannibalisation afterwards.
Real-world → OR mapping
| On the real-estate committee | In the model |
|---|---|
| Candidate property (retail park, mall, high-street, greenfield) | \(i \in \mathcal{J}\) |
| Population cluster / census tract with demographic profile | \(j \in \mathcal{I}\) |
| Trade-area demand (households × spend / week) | \(w_j\) |
| Drive-time from routing engine | \(d_{ij}\) |
| “5-minute rule” coverage threshold | \(D\) |
| Capex budget in stores | \(p\) |
| Open / don’t open this site | \(y_i\) |
| Store size / brand / fascia | \(A_i\) |
| Forecast store sales | \(\sum_j w_j P_{ij}\) |
Interactive solver
p-Median via greedy-add + 1-opt swap local search
Under the hood
The scenario generator places \(n\) demand zones (weights drawn from a skewed Pareto-like distribution) and \(m\) candidate sites on a 100×100 grid using a scenario-specific clustering structure. Drive-times \(d_{ij}\) are Euclidean distances (a proxy; real practice plugs in an OSRM or Google-Maps response). The solver runs greedy-add: start with no stores, at each step open the site whose marginal reduction in \(\sum_j w_j \min_i d_{ij}\) is largest, stop when \(p\) stores are open. Then 1-opt swap: for each open-site / closed-site pair, check if swapping reduces the objective; repeat until no improving swap exists. Complexity \(\mathcal{O}(p \cdot m \cdot n + p (m - p) n)\). Optimality gap vs. MIP is typically under 2% on generated scenarios.
Reading the solution
Three patterns to watch for
- Store clustering around dense zones. As \(p\) grows, stores go into the highest-weight clusters first, then spread outward. The greedy trajectory is itself useful: it tells you which site is the best first store and which is the best next, informing expansion sequencing.
- Coverage vs. distance trade-off. p-Median minimises average distance; MCLP maximises covered demand. On highly skewed geographies they can give different answers — always solve both and compare.
- The Huff post-audit. Once sites are chosen, run Huff with projected store attractiveness and check: how much does the new store cannibalise existing stores? What is the incremental revenue, not the absolute?
Sensitivity questions the model answers
- What if we can only open 3 stores (capex constraint)? — lower \(p\); marginal sites drop off.
- What if an online competitor shifts demand from physical? — scale down \(w_j\) and rerun.
- What if drive-time threshold is 8 min (suburban) instead of 5 min (urban)? — run MCLP with \(D = 8\); covered fraction changes sharply.
Model extensions
Huff gravity + cannibalisation
Replace nearest-store assignment with probabilistic share. Objective becomes nonlinear; solved via greedy + local search on store attractiveness and distance.
Capacitated p-Median
Each store has a capacity \(C_i\). Demand assignment respects capacity; solved via MIP.
Competitive location
Competitor stores are exogenous points; demand split between own and competitor via Huff. Objective: capture share.
Multi-format chain
Open a mix of large and small-format stores (e.g., Express vs. Full). Different cost, capacity, attractiveness per format.
Dynamic network planning
Open/close decisions over a multi-year horizon. Stores “age in” over years; closures trigger severance and brand cost.
Generic facility location
Warehouse / DC siting uses the generic formulation without retail-specific Huff or cannibalisation.
Depot / DC location →Healthcare facility analogue
Ambulance / clinic placement uses MCLP with life-years as the covered-demand metric.
Ambulance placement →OR family reference
Dig into exact MIP formulations and Lagrangian relaxation for p-Median.
Location & covering family →Key references
Back to the retail domain
Retail store location sits in the Place × Strategic cell of the 4P decision matrix — the multi-year decision every downstream operation rests on.
Open Retail Landing