Earthmoving Optimisation
Mass-Haul LP · Cut-Fill Balance · Transportation Problem
Construction · Logistics & Flow · OperationalEvery highway, dam, railway, and canal starts with moving dirt: excavate where the alignment cuts into a hill, dump where it fills a valley, and truck the difference either from external borrow pits or to external spoil areas. The decision — how much material to haul from each cut station to each fill station, and when to use borrow or spoil — is the classical transportation linear programme. Bruckner drew the first mass-haul diagram in the 1870s; Easa (1988) cast it as a network LP; Moselhi & Alshibani (2008) extended it to mixed material types with compaction factors. The LP is polynomially solvable and scales to projects with hundreds of stations.
Where This Decision Fits
Linear works earthwork planning — the highlighted step is what this page optimises
The Problem
Balance cut and fill along a linear alignment at minimum haul cost
A linear works project has stations \( s = 1, \ldots, S \) along the alignment. At each station, the engineering design specifies a cut volume \( C_s \ge 0 \) (excavation, excess material available) and a fill volume \( F_s \ge 0 \) (embankment, material required). In addition, there are external borrow pits \( B_j \) (suppliers) and spoil areas \( E_k \) (dumps) with their own costs and capacities. The haul cost per cubic metre from source to destination is \( c_{st} \), typically proportional to distance.
Decision variable \( x_{st} \ge 0 \) is the volume hauled from source \( s \) to destination \( t \).
Here \( \mathcal{S}^+ = \{\text{cut stations}\} \cup \{\text{borrow pits}\} \) is the set of sources and \( \mathcal{S}^- = \{\text{fill stations}\} \cup \{\text{spoil areas}\} \) is the set of sinks. Any cut material not hauled to fill is automatically sent to spoil (at positive spoil cost); any unmet fill demand is covered by borrow (at positive borrow cost).
This is a classical transportation problem (Hitchcock 1941, Koopmans 1949) — polynomial-time solvable by the transportation simplex, the network-simplex method, or cost-scaling algorithms. For the typical construction instance with \( S \le 200 \) stations the LP solves in milliseconds. The Bruckner mass-haul diagram (the cumulative plot of \( \sum_{s' \le s} (C_{s'} - F_{s'}) \) against station \( s \)) gives a graphical optimum: minimum-cost haul boundaries correspond to horizontal lines that balance cut and fill within each haul zone.
See Equipment Routing — the CVRP that dispatches the actual dump trucksTry It Yourself
Solve the mass-haul LP for a linear alignment
Mass-Haul Solver
20 stationsThe cumulative (cut − fill) curve. Peaks above zero → excess (becomes spoil if long haul uneconomic). Valleys below zero → deficit (filled from borrow or reverse haul).
Pick a scenario and click Solve.
The Algorithms
From Bruckner's diagram to transportation simplex to network flow
Bruckner Mass-Haul Diagram (1870s)
Manual, O(S) computation of cumulative volumesPlot the cumulative \( M_s = \sum_{s' \le s} (C_{s'} - F_{s'}) \) against station. Draw horizontal "balance lines" at various levels; the lowest horizontal line that leaves the curve above it everywhere between two stations defines a haul zone. Within each zone, all cut material is used by nearby fill — no external borrow or spoil needed. Pedagogically beautiful and still drawn on every civil-engineering exam.
Greedy Nearest-Match
O(S\u00b2)For each cut station (in some order), ship material to the nearest fill station that still has unmet demand. Very simple; the default algorithm on this page. Typically produces cost within 15–25% of LP optimum on real alignments; poor on tricky geometries where reverse hauls are needed.
Transportation Simplex
Polynomial — network simplex is O(V\u00b2 E log(V C))Start with a basic feasible solution from the northwest-corner rule (or Vogel's approximation), then apply stepping-stone cost improvements: identify an entering non-basic variable with negative reduced cost, compute the cycle, pivot. Provably finds the LP optimum. Easa (1988) wrote the construction-specific LP; Jayawardane & Harris (1990) refined it for multi-material earthworks. The second algorithm on this page.
Real-World Complexity
Why real earthmoving goes beyond textbook mass-haul LP
Beyond the Basic Transportation LP
- Material types — Not all cut is usable as fill. Rock, common earth, organic soils, and clays have different engineering properties; fill at a station may demand a specific material. Moselhi & Alshibani (2008)'s multi-material MIP handles this.
- Compaction (shrinkage / swell) factors — 1 m\u00b3 of in-situ earth becomes 1.25–1.35 m\u00b3 once loaded (swell) and 0.85–0.95 m\u00b3 once compacted. Cut and fill volumes live on different scales; the LP uses bank/loose/compacted cubic metres explicitly.
- Grade / access restrictions — Some hauls are blocked by intermediate features (bridges, creeks, bog). The network graph is partial, not complete.
- Temporary stockpiles — Cut may be stockpiled mid-project if fill isn't yet ready. This turns the LP into a multi-period dynamic transportation problem.
- Haul-road cost — Cost per m\u00b3 depends on whether there's a prepared haul road, whether trucks can run at full speed, weather. Dynamic re-optimisation applies.
- Equipment productivity — The LP gives volumes; actual execution requires fleet sizing, cycle-time calculation, and queueing analysis (AbouRizk & Hajjar 1998's simulation models).
- Environmental regulation — Spoil-area permits, erosion-control requirements, and haul-route noise limits add constraints beyond cost.
Related Logistics & Flow Variants
Mass-haul is the first-class transportation LP in construction OR
Key References
Cited above · DOIs & permanent URLs
Earthmoving a highway, dam, or major civil project?
From mass-haul LP to fleet sizing and GPS-integrated automated earthwork, OR turns dirt-moving from rule-of-thumb into optimised logistics. Let's discuss how Operations Research can sharpen your earthworks.