Developing an efficient algorithm for balancing mass-haul diagrams

A number of linear and integer programming techniques have been used to minimize the total cost of earthwork by considering the various factors involved in the process. Although these models often ensure a global optimum for the problem, they required sophisticated formulations and are quite involved in their setup and definition as well as being expensive computationally and therefore may be of limited use in real life. In construction practice, Mass-haul diagrams (MD) have been an essential tool for planning earthwork construction for many applications including roadwork, piping, and other linear infrastructure facilities. One of the most common heuristics that is used widely by practicing engineers in the field to balance the MD is the “shortest-haul-first” strategy. Balancing the MD using this heuristic is usually carried out either graphically on the drawing, or manually by computing values from the mass-haul diagram itself. However performing this approach graphically or manually is fairly tedious and time consuming. In addition manual and graphical approaches are prone to error. More importantly, if the project considered has a large number of stations (in the order of hundreds), then performing this balance manually becomes impractical. A robust algorithm is therefore needed that can automatically balance the MD. The research discussed here presents a formal definition of an algorithm that uses a sequential pruning technique for automatically computing balances of mass-haul diagrams. It is shown that the new algorithm is more efficient than existing integer programming techniques and computationally runs in level of complexity of O(log n) time in most cases. Thus this algorithm can handle problems with a large number of stations within a reasonable amount of time. In addition, a computer implementation and extensive computational experiments are provided. Suggestions for how this algorithm can be used in cost-based or grade-based optimization of hauling distances and quantities are discussed.

► We present a definition of an algorithm that uses a sequential pruning technique to compute balances of mass-haul diagrams.
► The algorithm is more efficient than existing integer programming techniques and runs in level of complexity of O(log n).
► Future efforts can focus on using the algorithm for minimizing the overall cost of earthwork operations.
► The computer implementation could be easily developed as a plug-in for commercial earthwork software.