Distribution Center Location
Uncapacitated Facility Location (UFLP) — NP-Hard
An e-commerce company must decide which of 5 candidate DC sites to open, minimizing fixed costs ($500K–$2M) plus shipping to 8 customer zones. Each day of added transit costs $3–$5 per parcel in customer satisfaction loss.
Where This Decision Fits
Supply chain planning chain — the highlighted step is what this page optimizes
The Problem
Minimize total fixed plus shipping cost across candidate DC sites
An e-commerce logistics team evaluates 5 candidate distribution center sites to serve 8 customer zones. Each DC has a fixed annual lease and setup cost (ranging from $500K for a small regional facility to $2M for a major hub), and a geographic position that determines per-parcel shipping cost to each zone. Each customer zone generates a known daily parcel volume, and the cost to ship from DC i to zone j depends on distance and parcel weight.
The objective is to select which DCs to open and assign each customer zone to exactly one open DC, minimizing total fixed costs plus shipping costs. This is the classical Uncapacitated Facility Location Problem (UFLP), proven NP-hard by reduction from Set Cover.
subject to
Σi xij = 1 ∀ j // each zone served by exactly one DC
xij ≤ yi ∀ i,j // can only assign to open DCs
yi ∈ {0, 1} // open or not
xij ≥ 0 // assignment fraction
Where fi is the fixed cost of opening DC i, yi is the binary open/close decision, cij is the shipping cost from DC i to zone j, and xij is the assignment variable.
See Integer Programming theoryTry It Yourself
Select DCs and assign customer zones to minimize total cost
DC Location Optimizer
5 DCs · 8 Zones| DC Site | Fixed Cost ($K) | Region |
|---|
| Zone | Daily Parcels | Population (K) |
|---|
Ready. Click “Solve & Compare All Algorithms” to run.
| Algorithm | Total Cost ($K) | DCs Open | Time |
|---|---|---|---|
| Click Solve & Compare All Algorithms | |||
The Algorithms
Three approaches to facility location
Greedy (Cheapest)
O(n²m) | 1.61-approximationStart with no DCs open. At each step, evaluate the total cost if each remaining closed DC were to be opened (its fixed cost plus the shipping savings from reassigning zones). Open the DC that yields the lowest total cost. Repeat until no further improvement is possible. This simple constructive heuristic greedily picks the cheapest marginal addition at every iteration.
Greedy (Best Saving)
O(n²m) | 1.61-approximationAlso constructive, but instead of picking the DC that produces the lowest absolute cost, this variant picks the DC whose opening yields the largest net saving (shipping reduction minus fixed cost). It continues adding DCs as long as the net saving is positive. The two greedy variants often find different local optima.
Local Search
O(k · n · m) | 3-approximationBegin from the Greedy (Cheapest) solution. Explore three neighborhood moves: add a closed DC, drop an open DC, or swap (close one, open another). Accept the best improving move at each iteration. Repeat until no single add, drop, or swap improves the objective. This hill-climbing approach refines the greedy solution and often closes the gap to optimality.
Real-World Complexity
Why practical DC siting goes beyond the basic UFLP model
Beyond Uncapacitated Location
- Capacity constraints — Each DC has a max throughput; large zones may require multiple sources (capacitated FLP)
- Multi-echelon networks — Regional hubs feed local sort centres; the problem becomes a multi-level facility location
- Demand uncertainty — Seasonal spikes (Black Friday, holiday) require stochastic or robust formulations
- Service-level agreements — Same-day or next-day delivery constraints impose maximum distance/time limits per zone
- Labour market access — Warehouse staffing availability and wage differentials vary across geographies
- Lease flexibility — Multi-year lease terms, expansion options, and shared-space models affect the true fixed cost
- Returns logistics — Reverse flow from customers back to DCs adds another dimension to the network design
Key References
Foundational works in facility location
- (1977). “Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms.” Management Science, 23(8), 789–810.
- (2013). “A 1.488-Approximation Algorithm for the Uncapacitated Facility Location Problem.” Information and Computation, 222, 45–57.
Need to optimize your distribution network?
From DC location to inventory positioning and last-mile routing, mathematical modeling can transform supply chain investment decisions. Let’s discuss how Operations Research can work for you.