Solving the Least-Cost Route Cut and Fill Sequencing Problem Using Particle Swarm

Abstract

Several researchers have attempted to formulate and solve different classes of the earthwork allocation problem. Linear programming (LP) and integer programming (IP) techniques have traditionally been applied to minimize transportation costs and mass-haul distances associated with earthwork processes. However, typical formulations of the earthwork allocation problem do not consider the sequence of equipment movement and are, therefore, limited in their ability to establish a practical and workable hauling plan. A more complex problem, which is formulated and solved in this research, is the least-cost route cut and fill problem (LCRCFP). The primary objective of the LCRCFP is to determine the specific route to be traveled and the quantities of soil that construction equipment must haul to meet the desired grade while minimizing the total distance traveled. In this research, the LCRCFP was formulated as a mixed binary optimization problem and solved using a traditional branch-and-bound method and a particle swarm optimization (PSO) technique. Accordingly, this solution can provide efficient and practical hauling plans for construction sites. Furthermore, a linear variation of the problem, which is common for linear roadwork or utility construction, was also formulated and solved. Extensive computational results are reported for several randomly generated instances of the LCRCFP. Realistic problems can be effectively solved using PSO. Thus, the derived plan can be used in mapping and path planning and by on-site engineers. It can also be used for the deployment of unmanned construction equipment in autonomous vehicle control systems.