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:
- The authors retain the copyright and grant Transportes the right of first publication of the manuscript, without any financial charge, and waive any other remuneration for its publication by ANPET.
- Upon publication by Transportes, the manuscript is automatically licensed under the Creative Commons License CC BY 4.0 license. This license permits the work to be shared with proper attribution to the authors and its original publication in this journal.
- Authors are authorized to enter into additional separate contracts for the non-exclusive distribution of the version of the manuscript published in this journal (e.g., publishing in an institutional repository or as a book chapter), with recognition of the initial publication in this journal, provided that such a contract does not imply an endorsement of the content of the manuscript or the new medium by ANPET.
- Authors are permitted and encouraged to publish and distribute their work online (e.g., in institutional repositories or on their personal websites) after the editorial process is complete. As Transportes provides open access to all published issues, authors are encouraged to use links to the DOI of their article in these cases.
- Authors guarantee that they have obtained the necessary authorization from their employers for the transfer of rights under this agreement, if these employers hold any copyright over the manuscript. Additionally, authors assume all responsibility for any copyright infringements by these employers, releasing ANPET and Transportes from any responsibility in this regard.
- Authors assume full responsibility for the content of the manuscript, including the necessary and appropriate authorizations for the disclosure of collected data and obtained results, releasing ANPET and Transportes from any responsibility in this regard.
