Optimal cut-fill pairing and sequencing method in earthwork operation

Earthwork operations consist of repeated cycles of excavating, moving, and backfilling processes, in which rock-earth block is excavated from its cut pit, moved to a fill pit, and then backfilled into its corresponding fill prism. An efficient earth allocation plan reduces the total earthwork cost. This paper presents a computational method called Optimal cut-fill Pairing and Sequencing (OPS) which identifies the most economical EAP. It identifies the optimal cut-fill pairs and their sequence which minimizes the total earthwork cost by hybridizing the mixed integer linear programming (MILP) and evolutionary algorithm (i.e., harmony search). The proposed method is of value to earthwork managers because it identifies the most favorable EAP by accounting for the rock-earth type of each and every prism, the series of prisms occupying each and every cut and fill pits, and the moving directions (i.e., the order of cut-fill prism pairs), expeditiously. This study is also of relevance to researchers because it provides a white box which defines the mathematical formula and computational procedures to identify the global solution in detail. Two test cases confirm the usability and validity of the computational method.