An integrated approach for earthwork allocation, sequencing and routing

• An integrated earthwork allocation, sequencing and routing problem was solved.
• The solution approach is graph theoretic. A digraph models the dynamically changing terrain.
• The digraph is continually altered and is evaluated to quantify the real cost and effort of haulage.
• Parallel processing of the digraph is very effective and greatly reduces computational time.
• Solutions are constructed by advanced constructive algorithms and meta-heuristic techniques.

Planning techniques for large scale earthworks have been considered in this article. To improve these activities a “block theoretic” approach was developed that provides an integrated solution consisting of an allocation of cuts to fills and a sequence of cuts and fills over time. It considers the constantly changing terrain by computing haulage routes dynamically. Consequently more realistic haulage costs are used in the decision making process. A digraph is utilised to describe the terrain surface which has been partitioned into uniform grids. It reflects the true state of the terrain, and is altered after each cut and fill. A shortest path algorithm is successively applied to calculate the cost of each haul, and these costs are summed over the entire sequence, to provide a total cost of haulage. To solve this integrated optimisation problem a variety of solution techniques were applied, including constructive algorithms, meta-heuristics and parallel programming. The extensive numerical investigations have successfully shown the applicability of our approach to real sized earthwork problems.