Site Layout Planning
SLP · QAP · Temporary Facility Placement
Construction · Select & Locate · TacticalA construction site needs a place for the site office, the rebar yard, the formwork stacks, the lay-down area, the tower-crane pad, the concrete batching plant, the materials storage, the worker welfare facilities, and the security gate. Poor placement wastes 15–25% of crew-hours and 10–15% of crane utilisation on avoidable cross-site travel. Tommelein & Zouein (1993) formalised site-layout planning (SLP) as a Quadratic Assignment Problem (QAP) — the classical Koopmans & Beckmann (1957) problem of placing \( n \) facilities in \( n \) locations to minimise weighted inter-facility flow. Sahni & Gonzalez (1976) proved QAP is strongly NP-hard; even approximating it within any constant factor is NP-hard. Real construction SLP solvers rely on heuristics and metaheuristics, and this page uses both.
Where This Decision Fits
Site mobilisation — the highlighted step is what this page optimises
The Problem
Place n facilities in n candidate locations to minimise weighted flow
Let \( \mathcal{F} = \{1, \ldots, n\} \) be the set of temporary facilities (site office, rebar yard, lay-down, crane pad, gate, etc.) and \( \mathcal{L} = \{1, \ldots, n\} \) the set of candidate locations on the site grid. Two input matrices:
- Flow matrix \( f_{ik} \) — the expected material or crew flow (tons/day, trips/day) between facility \( i \) and facility \( k \). Estimated from project schedule and quantity takeoffs.
- Distance matrix \( d_{j\ell} \) — the travel distance (m) between candidate location \( j \) and location \( \ell \). Usually Manhattan or Euclidean, sometimes network distance if site topology is non-trivial.
Binary decision variable \( x_{ij} = 1 \) if facility \( i \) is placed at location \( j \).
The objective is quadratic in \( \mathbf{x} \), which is what makes QAP hard even for small \( n \). At \( n = 10 \) the solution space already has \( 10! \approx 3.6 \times 10^6 \) permutations — still tractable by full enumeration, but by \( n = 15 \) (\( \sim 1.3 \times 10^{12} \)) it is not.
Sahni & Gonzalez (1976)'s strong-NP-hardness result rules out polynomial-time approximation schemes. Practical construction SLP solvers use pairwise-exchange local search (Robins & Robinson's 2-opt applied to assignments), simulated annealing with swap moves, and genetic algorithms with permutation encoding (Elbeltagi, Hegazy & Eldosouky 2004). The page's solver runs both.
Compare to Site Selection — picking which site, not how to lay it outTry It Yourself
Place temporary facilities on the site grid to minimise cross-flow
Site Layout Solver
9 Facilities · 9 LocationsFacility blocks are placed in their chosen locations; line thickness between blocks = flow volume; line colour fades with distance.
Pick a scenario and algorithm, then click Solve.
The Algorithms
From pairwise swap to simulated annealing on QAP
Pairwise-Exchange (2-opt swap)
O(n\u2074) first-improvement / O(n\u00b2) per swap checkStart from a random assignment. Try swapping every pair of facilities; if the swap reduces total flow-distance cost, accept it. Repeat until no improving swap exists (local optimum). The objective change on a swap can be computed in \( O(n) \) if you precompute flow-row sums, making the full neighbourhood scan \( O(n^3) \) per iteration. Fast and effective on construction-sized QAPs (\( n \le 20 \)). The default algorithm on this page.
Simulated Annealing
O(iterations · n\u00b2)Burkard & Rendl (1984) applied SA to QAP with excellent results. Propose a random swap; accept if it improves; otherwise accept with probability \( e^{-\Delta / T} \) where \( T \) decays geometrically. Escapes local optima that pure swap search cannot. Implemented here with \( T_0 = \bar{c}/10 \), cooling \( \alpha = 0.995 \), 5000 iterations.
Elbeltagi GA for Construction SLP
Iterative · permutation encodingElbeltagi, Hegazy & Eldosouky (2004)'s GA uses permutation encoding (chromosome = location assignment per facility), order crossover (OX), and swap mutation. Benchmarked against Tommelein-Zouein's ConsSite and Mawdesley et al's MCMF; competitive on all published real-site cases. Typical runtime 30–90 s for 15-facility instances.
Real-World Complexity
Why real sites go beyond textbook QAP
Beyond Koopmans-Beckmann
- Unequal facility sizes — QAP assumes each facility takes one grid cell. In reality the batching plant is 25 x 25 m, the office trailer is 4 x 12 m. Zouein, Harmanani & Hajar (2002)'s MCLOP handles unequal areas.
- Obstacles & exclusion zones — Existing structures, trees, buried utilities carve no-go areas out of the grid. Distance calculations must route around them (A* or Dijkstra instead of Euclidean).
- Time-varying layouts — Sites reconfigure as the project progresses: excavation yards become foundation zones become structure zones. Elbeltagi & Hegazy (2001)'s dynamic SLP re-optimises per phase.
- Safety separation rules — Fuel storage must be \( \ge 30 \) m from occupied buildings; crane radius must not overfly residential boundary. These are hard constraints on \( x_{ij} \), not flow costs.
- Tower-crane reach & geometry — All heavy-lift material must be within crane radius from the crane pad. This adds a routing-friendly facility-to-crane distance constraint.
- Noise-restricted zones — Batching plants and compressors near residential boundaries trigger permit penalties; the layout cost includes a regulatory term.
Related Selection & Location Variants
SLP is the intra-site twin of site selection and facility location
Key References
Cited above · DOIs & permanent URLs
Planning a complex urban build or infrastructure site?
From facility placement to crane-reach coordination and dynamic phase-based layouts, OR turns cross-site travel from a hidden cost into a first-class design variable. Let's discuss how Operations Research can improve your site mobilisation.