Plant Location & Capacity Design
Capacitated Facility Location Problem (CFLP) · NP-Hard
A manufacturer planning network expansion must decide which candidate sites to open as production plants and what capacity to install at each, minimizing the sum of fixed opening costs and variable transportation costs. Site selection errors can lock in 15–20% excess logistics costs over a 10-year planning horizon. This is the Capacitated Facility Location Problem — NP-hard with a best-known 1.488-approximation.
Where This Decision Fits
Manufacturing planning chain — the highlighted step is what this page optimizes
The Problem
Minimize total fixed opening costs and variable transportation costs under capacity limits
A manufacturing firm evaluates 6 candidate plant sites across Canada — Oakville ON, Calgary AB, Montréal QC, Winnipeg MB, Vancouver BC, and Halifax NS — to serve 8 demand regions. Each site has a fixed build cost (ranging from $2M to $8M), a maximum production capacity in tonnes, and variable transportation costs proportional to distance. Each demand region requires a specific tonnage allocation.
The objective is to select which sites to open, determine capacity allocation, and assign each demand region to open sites, minimizing total fixed plus transportation cost subject to capacity constraints. This is the classical Capacitated Facility Location Problem (CFLP), proven NP-hard by reduction from Set Cover.
subject to
Σi xij = dj ∀ j // each region's demand fully met
Σj xij ≤ Qi · yi ∀ i // capacity limit at open sites
yi ∈ {0, 1} // open or not
xij ≥ 0 // tonnes shipped from i to j
Where fi is the fixed opening cost of site i, yi is the binary open/close decision, Qi is the capacity limit at site i, cij is the per-tonne transport cost from site i to region j, dj is the demand of region j, and xij is the tonnage shipped.
See Integer Programming theoryTry It Yourself
Select plant sites and assign demand regions to minimize total cost
Plant Location Optimizer
6 Sites · 8 Regions| Site | Province | Capacity (t) | Build Cost ($M) |
|---|
| Region | Demand (t) | Population (k) |
|---|
Ready. Click “Solve & Compare All Algorithms” to run.
| Algorithm | Total Cost ($M) | Sites Open | Time |
|---|---|---|---|
| Click Solve & Compare All Algorithms | |||
The Algorithms
Three approaches to capacitated facility location
Greedy Add
O(n²m) | 1.61-approximationStart with no sites open. At each step, evaluate the marginal cost reduction of opening each closed site (fixed cost minus the transportation savings from reassigning demand regions, respecting capacity limits). Open the site with the greatest net benefit. Repeat until no further improvement is possible. This constructive heuristic builds the solution incrementally and tends to find good solutions quickly.
Greedy Drop
O(n²m) | No guaranteeStart with all sites open. At each step, evaluate the cost increase of closing each open site (transportation cost increase minus the saved fixed cost), checking that remaining capacity can still serve all demand. Close the site whose removal causes the least cost increase, as long as the total cost decreases and feasibility is maintained. This destructive approach often finds different local optima than Greedy Add.
Simulated Annealing
O(T · n · m) | Asymptotically optimalBegin from the Greedy Add solution and explore the neighborhood by randomly toggling sites open/closed (rejecting moves that violate capacity feasibility). Accept improving moves always; accept worsening moves with probability exp(−Δ/T) where T is the temperature, which decreases geometrically. This allows escaping local optima and typically finds near-optimal solutions for moderate-size instances.
Real-World Complexity
Why practical plant location goes beyond the basic CFLP model
Beyond Basic Capacitated Location
- Economies of scale — Build costs are often concave functions of capacity; larger plants have lower per-unit fixed costs
- Multi-period phased investment — Demand grows over decades; plants must be phased in across multiple planning horizons with option to expand
- Product mix constraints — Different plants may specialize in different product lines, adding assignment compatibility constraints
- Labor market availability — Skilled workforce availability varies by region and affects operating costs and feasibility
- Supply chain integration — Raw material sourcing, supplier proximity, and inbound logistics affect total landed cost
- Regulatory and tax environment — Provincial incentives, environmental regulations, and trade agreements shift effective costs
- Risk and resilience — Geographic diversification protects against natural disasters, strikes, and single-point-of-failure scenarios
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.
- (1983). “The Simple Plant Location Problem: Survey and Synthesis.” European Journal of Operational Research, 12(1), 36–81.
Need to optimize your facility network?
From plant location to capacity planning and supply chain design, mathematical modeling can transform infrastructure investment decisions. Let’s discuss how Operations Research can work for you.