Solving the Least-Cost Route Cut and Fill Sequencing Problem Using Particle Swarm
Publication: Journal of Construction Engineering and Management
Volume 138, Issue 8
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.
Get full access to this article
View all available purchase options and get full access to this article.
References
Cheng, W. F., Liu, L., and Satish, M. G. (2006). “Discussion of determination of haul distance and direction in mass excavation.” J. Constr. Eng. Manage.JCEMD4, 132(8), 895–896.
Easa, M. S. (1987). “Earthwork allocations with non-constant unit costs.” J. Constr. Eng. Manage.JCEMD4, 113(1), 34–50.
Easa, M. S. (1988). “Earthwork allocations with linear unit costs.” J. Constr. Eng. Manage.JCEMD4, 114(4), 641–655.
Eberhart, R., and Shi, Y. (1998). “Comparison between genetic algorithms and particle swarm optimization.” Proc., 7th Annual Conf. on Evolutionary Programming, Springer, Berlin, 611–618.
El beltagi, E., Hegazy, T., and Grierson, D. (2005). “Comparison among five evolutionary-based optimization algorithms.” Adv. Eng. Inf., 19(1), 43–53.
Henderson, D., Vaughan, S. H., Jacobson, D. E., Wakefield, R. R., and Sewell, E. C. (2003). “Solving the shortest route cut and fill problem using simulated annealing.” Eur. J. Oper. Res.EJORDT, 145(1), 72–84.
IBM. (2010). ILOG CPLEX optimization studio, IBM Corporation Software Group, New York.
Jayawardane, A. K. W., and Harris, F. C. (1990). “Further development of integer programming in earthwork optimization.” J. Constr. Eng. Manage.JCEMD4, 116(1), 18–34.
Ji, Y., Borrmann, A., Rank, E., Seipp, F., and Ruzika, S. (2010). “Mathematical modeling of earthwork optimization problems.” Proc. Int. Conf. on Computing in Civil and Building Engineering, Nottingham Univ. Press, Nottingham, U.K.
Ji, Y., Borrmann, A., Rank, E., Wimmer, J., and Günthner, W. (2009). “An integrated 3d simulation framework for earthwork processes.” Proc., 26th CIB-W78 Conf. on Managing IT in Construction, Istanbul, Turkey.
Karimi, S., Mousavi, J., Kaveh, A., and Afshar, A. (2007). “Fuzzy optimization model for earthwork allocations with imprecise parameters.” J. Constr. Eng. Manage.JCEMD4, 133(2), 181–190.
Kennedy, J. (1997). “The particle swarm: Social adaptation of knowledge.” Proc., IEEE Int. Conf. on Evolutionary Computation (Indianapolis, Indiana), IEEE Service Center, Piscataway, NJ.
Kim, S. K., and Russel, J. S. (2003). “Framework for an intelligent earthwork system. Part I: Task identification/scheduling and resource allocation methodology.” Autom. Constr.AUCOES, 12(1), 15–27.
Marzouk, M., and Moselhi, O. (2004). “Multi objective optimization of earthmoving operations.” J. Constr. Eng. Manage.JCEMD4, 130(1), 105–113.
Mayer, R., and Stark, R. (1981). “Earthmoving logistics.” J. Constr. Div.JCCEAZ, 102(CO2), 297–312.
Moselhi, O., and Alshibani, A. (2009). “Optimization of earthmoving operations in heavy civil engineering projects.” J. Constr. Eng. Manage.JCEMD4, 135(10), 948–954.
Shi, Y., and Eberhart, R. (1998). “A modified particle swarm optimizer.” Proc., IEEE Int. Conf. on Evolutionary Computation, IEEE Service Center, Piscataway, NJ.
Son, J., Mattila, K. G., and Myers, D. S. (2005). “Determination of haul distance and direction in mass excavation.” J. Constr. Eng. Manage.JCEMD4, 131(3), 302–309.
Stark, R., and Mayer, R. (1983). Quantitative construction management: Uses of linear optimization, Wiley, New York.
Information & Authors
Information
Published In
Journal of Construction Engineering and Management
Volume 138 • Issue 8 • August 2012
Pages: 931 - 942
Copyright
© 2012. American Society of Civil Engineers.
History
Received: Nov 28, 2010
Accepted: Nov 21, 2011
Published online: Nov 23, 2011
Published in print: Aug 1, 2012
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.