Power Plant Siting
Facility Location · NP-Hard
A poorly sited power plant incurs €10–€50M in excess transmission infrastructure costs over its 30-year lifetime, with fuel transport adding 8–15% to generation costs. Every 5 years, a utility planning commission must decide where to build new generation capacity to serve growing demand regions. This is the Facility Location Problem — NP-hard with a 1.488-approximation — where construction cost, transmission distance, and environmental constraints must be jointly optimized.
Where This Decision Fits
Energy systems planning chain — the highlighted step is what this page optimizes
The Problem
Minimize total build and transmission cost across candidate sites
A utility planning commission evaluates 6 candidate generation sites to serve 8 demand districts. Each site has a fixed construction cost (ranging from €50M for a gas peaker to €800M for a nuclear facility), a fuel type, and a maximum generation capacity. Each demand district requires a specific MW allocation, and the cost to transmit power from site i to district j depends on distance and terrain.
The objective is to select which sites to build and assign each district to exactly one built site, minimizing total construction plus transmission cost. This is the classical Uncapacitated Facility Location Problem (UFLP), proven NP-hard by reduction from Set Cover.
subject to
Σi xij = 1 ∀ j // each district served by exactly one site
xij ≤ yi ∀ i,j // can only assign to built sites
yi ∈ {0, 1} // build or not
xij ≥ 0 // assignment fraction
Where fi is the fixed build cost of site i, yi is the binary open/close decision, cij is the transmission cost from site i to district j, and xij is the assignment variable.
See Integer Programming theoryTry It Yourself
Select sites and assign demand districts to minimize total cost
Plant Siting Optimizer
6 Sites · 8 Districts| Site | Type | Capacity (MW) | Build Cost (€M) |
|---|
| District | Demand (MW) | 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 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 (build cost minus the transmission savings from reassigning districts). 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 (transmission cost increase minus the saved build cost). Close the site whose removal causes the least cost increase, as long as the total cost decreases. Repeat until no further closures are beneficial. 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. 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 siting goes beyond the basic UFLP model
Beyond Uncapacitated Location
- Capacity constraints — Each plant has a maximum MW output; large districts may require multiple sources (capacitated FLP)
- Multi-period expansion — Demand grows over decades; sites must be phased in over multiple planning horizons
- Environmental impact assessment — Zoning laws, protected areas, water access, and air quality regulations restrict candidate locations
- Fuel supply logistics — Coal and gas plants need pipeline or rail access; transport cost varies by geography
- Grid interconnection — Transmission line routing, right-of-way acquisition, and substation capacity affect true connection cost
- Reliability requirements — N-1 contingency standards require backup capacity; single-point-of-failure avoidance
- Political and social factors — Community opposition (NIMBY), job creation incentives, and cross-jurisdictional agreements
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 infrastructure siting?
From power plant location to transmission network design and grid planning, mathematical modeling can transform infrastructure investment decisions. Let’s discuss how Operations Research can work for you.