Truck routing cut and fill problem in roadworks using integer programming
DOI:
https://doi.org/10.14295/transportes.v28i5.2032Keywords:
Earthmoving, Vehicle, Routing Problem, Mathematical Programming.Abstract
Planning activities of materials distribution in earthworks may represent a gain in the work as a whole. One way to savings in the construction is to minimize the total distance travelled by equipment, for example the trucks between the cut and fill in earthmoving areas. Some studies have been reported on the optimization of material distribution between cut and fill areas, but only a few were applied in real projects considering multiple trucks, moreover they do not do any analysis based on the distance between stations. This paper aims at presenting an integer programming model that minimizes the distance travelled by dump trucks in distribution activities of earthwork materials. The developed model was based on a classical operational research problem named vehicle routing problem, which focus on the minimization of the travelled way by a fleet of vehicles. The proposed approach was applied in two case studies whose findings highlight significant gains, in terms of flexibility of the planning process. Engineers, planners and analysts have an important computational tool to support decision-making by using this model.
Downloads
References
Bogenberger, C.; Dell’amico, M.; Fuellerer, G.; Hoefinger, G.; Iori, M.; Novellani, S. and Panicucci, B. (2015) two-phase earthwork optimization model for highway construction. Journal of construction engineering and management. 2015, 141(6): 05015003. https://doi.org/10.1061/(asce)co.1943-7862.0000973
Christian, J. and Caldera, H. (1988). Earthmoving cost optimization by operational research. Canadian journal of civil engineer-ing, 15:679-684. https://doi.org/10.1139/l88-088
Easa, S. M. (1987). Earthwork Allocations with Nonconstant Unit Costs. Journal of construction engineering and manage-ment.113,34–50. https://doi.org/10.1061/(asce)0733-9364(1987)113:1(34)
Easa, S. M. (1989). Earthmoving Cost Optimization by Operational Research: Discussion. Canadian journal of civil engineering 16(3), 408. https://doi.org/10.1139/l89-064
El-Rayes, K. and Moselhi, O. (2001). Optimizing Resource Utilization For Repetitive Construction Projects. Journal of construc-tion engineering and management, vol. 127, no. 1, January/February, 2001. https://doi.org/10.1061/(asce)0733-9364(2001)127:1(18)
Falcão, V. A.; Nobre Júnior, E. F. and Prata, B. de A. (2016a). Optimization Techniques Applied to Earthmoving and Highway Construction: A Survey. International Review of Civil Engineering (I.RE.C.E.), Vol. 7, N. 5 ISSN 2036 – 9913. September 2016. doi: 10.15866/irece.V7i5.10294.
Falcão, V. A.; Nobre Júnior and E. F. E Prata, B. de A. (2016b) Modelo de roteirização para a distribuição de materiais de ter-raplenagem baseado em programação inteira. Journal of transport literature. 10(3), 20-24. doi: 10.1590/2238-1031.jtl.v10n3a4
Gwaka, H.S.; Seob, J. and Leea, D.E. (2018) Optimal cut-fill pairing and sequencing method in earthwork operation. Automa-tion in construction 87 (2018) 60–73. https://doi.org/10.1016/j.autcon.2017.12.010
Hare, L. W.; Koch, V. R. and Lucet, Y. (2011) models and algorithms to improve earthwork operations in road design using mixed integer linear programming. European journal of operational research, 215, 470-480. https://doi.org/10.1016/j.ejor.2011.06.011
Henderson, D.; Vaughan, D. E.; Jacobson, S. H.; Wakefield, R. R. and Sewell, E. C. (2003) Solving the Shortest Route Cut and Fill Problem Using Simulated Annealing. European journal of operational research 145 (2003) 72–84. Https://Doi.Org/10.1016/S0377-2217(02)00206-0
Hwang, S.; Son, J., and Lee, S. (2014) Development of Scheduling Model for Earth Work Using Genetic Algorithm. KSCE Journal of Civil Engineering (2014) 18(6):1618-1624.doi 10.1007/S12205-014-0398-1
IBM ILOG AMPL (2010) Version 12.2. User’s Guidestandard (Command-Line). Version Including CPLEX Directives. May 2010. Available in: http://ampl.com/booklets/amplcplex122userguide.pdf. (Access in 30/10/2014).
Jayawardane, A. K. W. and Price, A. D. F. (1994a) A New Approach For Optimizing Earth Moving Operations, Part I, In: Pro-ceedings of institution of civil engineers - transport, 105, Pp. 195-207. https://doi.org/10.1680/itran.1994.26795
Jayawardane, A. K. W. and Price, A. D. F (1994b) A New Approach For Optimizing Earth Moving Operations, Part Ii, In: Pro-ceedings of institution of civil engineers - transport, 105, Pp. 249-258. https://doi.org/10.1680/itran.1994.27136
Jayawardane, A. K. W., and Harris, F. C. (1990) Further development of integer programming in earthwork optimization. Journal of construction engineering and management. 1990.116:18-34. https://doi.org/10.1061/(asce)0733-9364(1990)116:1(18)
Kantorovitch, L. (1958) On the translocation of masses. Management science vol. 5, no. 1 (oct., 1958), pp. 1-4. Https://www.jstor.org/stable/2626967
Lim, A; Rodrigues, B and Zhang, J. (2005) Tabu search embedded simulated annealing for the shortest route cut and fill problem. Journal of the operational research society (2005) 56, 816–824. doi:10.1057/palgrave.jors.2601900
Lima, R. X. de; Nobre Júnior, E. F.; Prata, B. de A. and Weissmann, J. (2013) Distribution of materials in road earthmoving and paving: a mathematical programming approach. Journal of construction engineering and management. 2013.139:1046-1054. DOI: 10.1061/(asce)co.1943-7862.0000666
Mayer, R. H. and Stark , R. M. (1981) Earthmoving Logistics. Journal of the construction division, Vol. 107, No. 2, June 1981, pp. 297-312. https://cedb.asce.org/cedbsearch/record.jsp?dockey=0010248
Morais, B.A. and Falcão, V.A. (2019) Otimização de equipamentos em obras de terraplanagem utilizando programação linear inteira. Transportes. ISSN: 2237-1346. Volume 27. Número 4. 2019. doi:10.14295/transportes.v27i4.1814
Nandgaonkar, S. M. (1981) Earthwork transportation allocations: operations research. Journal of the construction division ASCE, vol.107, no. 2, 1981, pp 373-392. https://cedb.asce.org/cedbsearch/record.jsp?dockey=0010265
Nassar, K. and Hosny, O. (2012) Solving the least-cost route cut and fill sequencing problem using particle swarm. Journal of construction engineering and management, Vol. 138, No. 8, August 1, 2012. ©ASCE, ISSN 0733-9364/2012/8-931–942. https://doi.org/10.1061/(asce)co.1943-7862.0000512
Rashidi, A., Rashidi Nejad, H. and Maghiar, M. (2014) Productivity estimation of bulldozers using generalized linear mixed models. KSCE journal of civil engineering (2014) 18(6):1580-1589. doi 10.1007/s12205-014-0354-0
Yi, C. and Lu, M (2016) A mixed-integer linear programming approach for temporary haul road design in rough-grading projects, Automation in construction (2016), http://dx.doi.org/10.1016/j.autcon.2016.08.022
Downloads
Published
How to Cite
Issue
Section
License
Authors who submit papers for publication by TRANSPORTES agree to the following terms:
- Authors retain copyright and grant TRANSPORTES the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors may enter into separate, additional contractual arrangements for the non-exclusive distribution of this journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in TRANSPORTES.
- Authors are allowed and encouraged to post their work online (e.g., in institutional repositories or on their website) after publication of the article. Authors are encouraged to use links to TRANSPORTES (e.g., DOIs or direct links) when posting the article online, as TRANSPORTES is freely available to all readers.
- Authors have secured all necessary clearances and written permissions to published the work and grant copyright under the terms of this agreement. Furthermore, the authors assume full responsibility for any copyright infringements related to the article, exonerating ANPET and TRANSPORTES of any responsibility regarding copyright infringement.
- Authors assume full responsibility for the contents of the article submitted for review, including all necessary clearances for divulgation of data and results, exonerating ANPET and TRANSPORTES of any responsibility regarding to this aspect.
