Logistics Depot Location
Capacitated Facility Location (CFLP) — Lagrangian Relaxation
A logistics company must decide which of 5 candidate depot sites to open and what capacity to provision. Each depot costs €1–3M to establish. Transport from depot to customer zones adds €0.5–2.0 per parcel-km. Wrong locations lock in 10-year excess delivery costs.
Where This Decision Fits
Logistics planning chain — the highlighted step is what this page optimizes
The Problem
Minimize total fixed plus transport cost across candidate depots
A logistics company evaluates 5 candidate depot locations to serve 10 demand zones. Each depot has a fixed opening cost (ranging from €1M to €3M), a maximum parcel-handling capacity, and a geographic position. Each demand zone requires a specific daily parcel volume, and the cost to transport parcels from depot i to zone j depends on distance and a per-parcel-km rate.
The objective is to select which depots to open and assign each zone’s demand to opened depots without exceeding capacity, minimizing total fixed cost plus transport cost. This is the classical Capacitated Facility Location Problem (CFLP), proven NP-hard.
subject to
Σi xij = dj ∀ j // each zone's demand fully met
Σj xij ≤ Qi · yi ∀ i // depot capacity if opened
yi ∈ {0, 1} // open or not
xij ≥ 0 // parcels from depot i to zone j
Where fi is the fixed cost of depot i, yi is the binary open/close decision, Qi is the capacity of depot i, cij is the per-parcel transport cost from depot i to zone j, dj is the demand of zone j, and xij is the parcel flow variable.
See Integer Programming theoryTry It Yourself
Select depots and assign demand zones to minimize total cost
Depot Location Optimizer
5 Depots · 10 Zones| Depot | Capacity (parcels/day) | Fixed Cost (€M) |
|---|
| Zone | Demand (parcels/day) |
|---|
Ready. Click “Solve & Compare All Algorithms” to run.
| Algorithm | Total (€M) | Depots Open | Capacity % | Fixed (€M) | Transport (€M) | Time |
|---|---|---|---|---|---|---|
| Click Solve & Compare All Algorithms | ||||||
The Algorithms
Three approaches to capacitated facility location
Greedy (Cheapest per Demand)
O(n²m) | No approximation guaranteeStart with no depots open. At each step, evaluate the marginal cost-per-parcel of opening each closed depot: its fixed cost amortized over the demand it would capture, plus the transport savings from reassigning zones. Open the depot with the best ratio. Continue until all demand is covered or no improvement remains. Fast and intuitive but can miss globally optimal configurations.
Lagrangian Relaxation (5 iterations)
O(K · n · m) | Provides lower boundRelax the demand-satisfaction constraints into the objective using Lagrange multipliers λj. The relaxed problem decomposes into independent per-depot subproblems: open depot i if its reduced fixed cost minus the sum of profitable adjusted transport margins is negative. Update multipliers via subgradient ascent over 5 iterations. The best primal-feasible solution encountered gives an upper bound; the Lagrangian value gives a lower bound.
Local Search
O(n · m · I) | No guaranteeStart from the Greedy solution. At each iteration, consider three neighborhood moves: (1) swap — close one depot and open another; (2) add — open an additional depot; (3) drop — close an existing depot if capacity allows. Accept the best improving move. Repeat until no single move improves the objective. Typically refines the greedy solution by 5–15%.
Real-World Complexity
Why practical depot location goes beyond the basic CFLP model
Beyond Capacitated Location
- Multi-echelon networks — Hub-and-spoke designs with regional hubs, local depots, and last-mile micro-hubs add nested location decisions
- Time-window constraints — Same-day and next-day delivery promises impose maximum distance or travel-time limits on depot-to-zone assignments
- Demand uncertainty — Seasonal peaks (holiday surges) and stochastic daily volumes require robust or chance-constrained formulations
- Multi-period expansion — Leases span 5–10 years; phased rollout must balance upfront investment with demand growth trajectories
- Labor market access — Depot viability depends on local wage levels, driver availability, and workforce commuting patterns
- Zoning and permits — Industrial zoning, noise restrictions, and truck-route limitations constrain feasible locations
- Returns and reverse logistics — Depots that also handle returns have asymmetric flow, requiring additional capacity and sorting infrastructure
Key References
Foundational works in capacitated 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 logistics network?
From depot location to fleet planning and last-mile routing, mathematical modeling can transform supply chain investment decisions. Let’s discuss how Operations Research can work for you.