Optimization Model for Earthwork Allocations Considering the Construction of Multiple Haul Roads: GIS-Based Integrated Approach
Publication: Journal of Construction Engineering and Management
Volume 150, Issue 4
Abstract
An essential process in earthworks is projecting effective routes for material allocation. In highway construction, haul road planning is a challenge for practitioners once there are few consolidated methodologies to rationally select existing haul routes or construct new ones. Some authors indicated geographic information system (GIS)-based methods for routing through least-cost algorithms. However, most proposed methodologies overlook the logistics related to allocations, not considering supply–demand relations in their criteria. Consequently, through a case study in Brazil, we present an earthwork optimization system that integrated established mathematical programming techniques for allocation and a GIS-based algorithm for haul road construction. In summary, we formulated a model capable of selecting different routes based on their impact on earthworks logistics cost. Thus, we built several paths between source and demand points utilizing two methods. First, based on recent literature, we used a GIS-based least-cost algorithm using the measuring attractiveness by a categorical-based evaluation technique (MACBETH) as a multicriteria support system incorporating multiple economic and environmental parameters. Second, we built routes based on Euclidian distance between the same source and demand points, analyzing if the savings in operational costs would payoff additional expenses of choosing a shorter route. After applying our methodology to the case study, we observed that the proposed procedure presented a lower budget in a reasonable processing time compared with the original project. Therefore, we inferred that the strategy of proposing path alternatives can be significantly efficient when applied to highways. Based on the results, we also found opportunities for improvement of our GIS step once it generated long paths when the distance between source and demand was short.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
All data that support the findings of this study are available in supplemental materials. Any other information is available upon request.
Acknowledgments
This research was supported by the Coordination for the Improvement of Higher Education Personnel (CAPES).
References
Alshibani, A., and O. Moselhi. 2012. “Fleet selection for earthmoving projects using optimization-based simulation.” Can. J. Civ. Eng. 39 (6): 619–630. https://doi.org/10.1139/l2012-042.
Atkinson, D. M., P. Deadman, D. Dudycha, and S. Traynor. 2005. “Multi-criteria evaluation and least cost path analysis for an arctic all-weather road.” Egypt. J. Remote Sens. Space. Sci. 25 (4): 287–307. https://doi.org/10.1016/j.apgeog.2005.08.001.
Bana e Costa, C. A., E. C. Correa, J. De Corte, and J. Vansnick. 2002. “Facilitating bid evaluation in public call for tenders: A socio-technical approach.” Omega (Oxford) 30 (3): 227–242. https://doi.org/10.1016/S0305-0483(02)00029-4.
Bana e Costa, C. A., J. M. De Corte, and J. C. Vansnick. 2003. Macbeth LSE. London: London School of Economics.
Bogenberger, C., M. Dell’Amico, G. Fuellerer, G. Hoefinger, M. Iori, S. Novellani, and B. Panicucci. 2015. “Two-phase earthwork optimization model for highway construction.” J. Constr. Eng. Manage. 141 (6): 1–11. https://doi.org/10.1061/(ASCE)CO.1943-7862.0000973.
Brazil. 1998. Act No. 9.605, 12 February 1998. Regulating Criminal and Administrative Penalties relating to behaviour and activities harmful to the environment, and sets forth other provisions. [In Portuguese.] Brasília, Brazil: Federative Republic of Brazil.
Choi, Y., H. Park, C. Sunwoo, and K. C. Clarke. 2008. “Multi-criteria evaluation and least-cost path analysis for optimal haulage routing of dump trucks in large scale open-pit mines.” Int. J. Geogr. Inf. Sci. 23 (12): 1541–1567. https://doi.org/10.1080/13658810802385245.
Collischonn, W., and J. V. Pilar. 2000. “A direction dependent least-cost-path algorithm for roads and canals.” Int. J. Geogr. Inf. Sci. 14 (4): 397–406. https://doi.org/10.1080/13658810050024304.
de Lima, R. X., E. F. N. Júnior, B. A. Prata, and J. Weissmann. 2013. “Distribution of materials in road earthmoving and paving: A mathematical programming approach.” J. Constr. Eng. Manage. 139 (Aug): 1046–1054. https://doi.org/10.1061/(ASCE)CO.1943-7862.0000666.
Dell’Amico, M., G. Fuellerer, G. Höfinger, M. Iori, and S. Novellani. 2016. “A decision support system for highway construction: The Autostrada Pedemontana Lombarda.” Interfaces 46 (3): 245–263. https://doi.org/10.1287/inte.2016.0847.
Dijkstra, E. W. 1959. “A note on two problems in connexion with graphs.” Numer. Math. 1: 269–271. https://doi.org/10.1007/BF01386390.
DNIT (National Department of Transportation Infrastructure). 2009. DNIT 108/2009-ES: Earthworks–Fill pits–Service specifications. [In Portuguese.] Brasilia, Brazil: DNIT.
DNIT (National Department of Transportation Infrastructure). 2022. System of referential construction costs (SICRO). [In Portuguese.] Brasilia, Brazil: DNIT.
Douglas, D. H. 1994. “Least-cost path in GIS using an accumulated cost surface and slopelines.” Cartographica: Int. J. Geogr. Inf. Geovisualization 31 (Jun): 37–51. https://doi.org/10.3138/D327-0323-2JUT-016M.
Effat, H. A., and O. A. Hassan. 2013. “Designing and evaluation of three alternatives highway routes using the analytical hierarchy process and the least-cost path analysis, application in Sinai Peninsula, Egypt.” Egypt. J. Remote Sens. Space. Sci. 16 (2): 141–151. https://doi.org/10.1016/j.ejrs.2013.08.001.
Fernandes, P. G., E. F. N. Júnior, and B. A. Prata. 2022. “Optimization of earthworks planning: A systematic mapping study.” Can. J. Civ. Eng. 49 (12): 1781–1795. https://doi.org/10.1139/cjce-2022-0185.
Gwak, H. S., J. Seo, and D. E. Lee. 2018. “Optimal cut-fill pairing and sequencing method in earthwork operation.” Autom. Constr. 87 (Dec): 60–73. https://doi.org/10.1016/j.autcon.2017.12.010.
Gwak, H. S., C. Y. Yi, and D. E. Lee. 2016. “Stochastic optimal haul-route searching method based on genetic algorithm and simulation.” J. Comput. Civ. Eng. 30 (3): 1–12. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000496.
Hare, W. L., V. R. Koch, and Y. Lucet. 2011. “Models and algorithms to improve earthwork operations in road design using mixed integer linear programming.” Eur. J. Oper. Res. 215 (2): 470–480. https://doi.org/10.1016/j.ejor.2011.06.011.
Henderson, D., D. Vaughan, S. Jacobson, R. Wakefield, and E. Sewell. 2003. “Solving the shortest route cut and fill problem using simulated annealing.” Eur. J. Oper. Res. 145 (1): 72–84. https://doi.org/10.1016/S0377-2217(02)00206-0.
Jayawardane, A. K. W., and F. C. Harris. 1990. “Further development of integer programming in earthwork optimization.” J. Constr. Eng. Manage. 116 (1): 18–34. https://doi.org/10.1061/(ASCE)0733-9364(1990)116:1(18).
Jayawardane, A. K. W., and A. D. F. Price. 1994. “A new approach for optimizing earth moving operations: Part II.” Proc. Inst. Civ. Eng. Transp. 105 (4): 249–258. https://doi.org/10.1680/itran.1994.27136.
Kang, S., and J. Seo. 2012. “GIS method for haul road layout planning in large earthmoving projects: Framework and analysis.” J. Constr. Eng. Manage. 139 (5): 236–246. https://doi.org/10.1061/(ASCE)CO.1943-7862.0000561.
Kantorovitch, L. 1958. “On the translocation of masses.” Manage. Sci. 5 (1): 1–4. https://doi.org/10.1287/mnsc.5.1.1.
Lim, A., B. Rodrigues, and J. Zhang. 2005. “Tabu search embedded simulated annealing for the shortest route cut and fill problem.” J. Oper. Res. Soc. 56 (7): 816–824. https://doi.org/10.1057/palgrave.jors.2601900.
Liu, C., and M. Lu. 2015. “Optimizing earthmoving job planning based on evaluation of temporary haul road networks design for mass earthworks projects.” J. Constr. Eng. Manage. 141 (3): 1–14. https://doi.org/10.1061/(ASCE)CO.1943-7862.0000940.
Liu, C., M. Lu, and S. Johnson. 2013. “Simulation and optimization of temporary road network in mass earthmoving projects.” In Proc., 2013 Winter Simulation Conf., 3181–3190. New York: IEEE Press.
Mahini, A., and S. Abedian. 2014. “Routing of road network through least cost pathway algorithm to minimize impacts on environment.” J. Indian Soc. Remote Sens. 42 (Apr): 517–527. https://doi.org/10.1007/s12524-013-0351-7.
Marzouk, M., and O. Moselhi. 2002. “Simulation optimization for earthmoving operations using genetic algorithms.” Constr. Manage. Econ. 20 (6): 535–543. https://doi.org/10.1080/01446190210156064.
Marzouk, M., and O. Moselhi. 2003. “Constraint-based genetic algorithm for earthmoving fleet selection.” Can. J. Civ. Eng. 30 (4): 673–683. https://doi.org/10.1139/l03-006.
Marzouk, M., and O. Moselhi. 2004. “Multiobjective optimization of earthmoving operations.” J. Constr. Eng. Manage. 130 (1): 105–113. https://doi.org/10.1061/(ASCE)0733-9364(2004)130:1(105).
Mayer, R. H., and R. M. Stark. 1981. “Earthmoving logistics.” J. Constr. Div. 107 (2): 297–312. https://doi.org/10.1061/JCCEAZ.0000963.
Moselhi, O., and A. Alshibani. 2007. “Crew optimization in planning and control of earthmoving operations using spatial technologies.” J. Inf. Technol. Constr. 12 (7): 121–137.
Moselhi, O., and A. Alshibani. 2009. “Optimization of earthmoving operations in heavy civil engineering projects.” J. Constr. Eng. Manage. 135 (10): 948–954. https://doi.org/10.1061/(ASCE)0733-9364(2009)135:10(948).
Nandgaonkar, S. M. 1981. “Earthwork transportation allocations: Operations research.” J. Constr. Div. 107 (2): 373–392. https://doi.org/10.1061/JCCEAZ.0000969.
Nassar, K., E. A. Aly, and H. Osman. 2011. “Developing an efficient algorithm for balancing mass-haul diagrams.” Autom. Constr. 20 (8): 1185–1192. https://doi.org/10.1016/j.autcon.2011.05.002.
Nassar, K., and O. Hosny. 2012. “Solving the least-cost route cut and fill sequencing problem using particle swarm.” J. Constr. Eng. Manage. 138 (8): 931–942. https://doi.org/10.1061/(ASCE)CO.1943-7862.0000512.
Perry, C., and M. Iliff. 1983. “From the shadows: Earthmoving on construction projects.” Interfaces 13 (1): 79–84. https://doi.org/10.1287/inte.13.1.79.
SFB (Brazilian Forest Service). 2019. Permanent preservation area. [In Portuguese.] Brasilia, Brazil: SFB.
Songshan, L., G. W. A. Lim, and F. Wang. 2005. “The shortest route cut and fill problem in linear topological structure.” In Proc., ACM Symp., 409–410. New York: Association for Computing Machinery.
Yi, C., and M. Lu. 2016. “A mixed-integer linear programming approach for temporary haul road design in rough-grading projects.” Autom. Constr. 71 (2): 314–324. https://doi.org/10.1016/j.autcon.2016.08.022.
Yi, C., and M. Lu. 2019. “Mixed-integer linear programming-based sensitivity analysis in optimization of temporary haul road layout design for earthmoving operations.” J. Comput. Civ. Eng. 33 (3): 1–14. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000838.
Yu, C., J. Lee, and M. Munro-Stasiuk. 2010. “Research article: Extensions to least-cost path algorithms for roadway planning.” Int. J. Geogr. Inf. Sci. 17 (4): 361–376. https://doi.org/10.1080/1365881031000072645.
Information & Authors
Information
Published In
Copyright
© 2024 American Society of Civil Engineers.
History
Received: May 1, 2023
Accepted: Nov 2, 2023
Published online: Jan 31, 2024
Published in print: Apr 1, 2024
Discussion open until: Jun 30, 2024
ASCE Technical Topics:
- Algorithms
- Case studies
- Construction engineering
- Construction industry
- Construction management
- Construction methods
- Construction sites
- Earthwork
- Engineering fundamentals
- Geographic information systems
- Geomatics
- Highway and road management
- Highway transportation
- Highways and roads
- Infrastructure
- Infrastructure construction
- Mathematics
- Methodology (by type)
- Models (by type)
- Optimization models
- Research methods (by type)
- Surveying methods
- Transportation engineering
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.