IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v68y2017i9d10.1057_s41274-016-0140-0.html
   My bibliography  Save this article

A polynomial algorithm for the earthwork allocation problem with borrow and waste site selection

Author

Listed:
  • Hüseyin Güden

    (Eastern Mediterranean University)

  • Haldun Süral

    (Middle East Technical University)

Abstract

In road construction projects, earthwork is planned together with horizontal and vertical alignments. This study focuses on earthwork operations that basically include cutting the hills and filling the holes on the road path. The candidate borrow and waste sites can also be used to obtain or heap earth when the available cut and fill amounts are not balanced or operating these sites reduces the total earthwork cost. Total earthwork cost contains the transportation cost and the overall cost related to opening the candidate sites. The problem is to determine which borrow and waste sites to operate, and the earth flows between cut, fill, waste, and borrow sites such that the total cost is minimized. It is shown that the problem is a generalization of the well-known lot-sizing problem. A fixed charge network flow problem formulation is presented, and a polynomial time dynamic programming algorithm is developed for solving the problem.

Suggested Citation

  • Hüseyin Güden & Haldun Süral, 2017. "A polynomial algorithm for the earthwork allocation problem with borrow and waste site selection," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(9), pages 1085-1093, September.
    • Handle: RePEc:pal:jorsoc:v:68:y:2017:i:9:d:10.1057_s41274-016-0140-0
    DOI: 10.1057/s41274-016-0140-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/s41274-016-0140-0
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/s41274-016-0140-0?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Willard I. Zangwill, 1969. "A Backlogging Model and a Multi-Echelon Model of a Dynamic Economic Lot Size Production System--A Network Approach," Management Science, INFORMS, vol. 15(9), pages 506-527, May.
    2. C H Cheng & M S Madan & Y Gupta & S So, 2001. "Solving the capacitated lot-sizing problem with backorder consideration," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(8), pages 952-959, August.
    3. Prakash Mirchandani & Rajeev Kohli & Arie Tamir, 1996. "Capacitated Location Problems on a Line," Transportation Science, INFORMS, vol. 30(1), pages 75-80, February.
    4. Robert F. Love, 1976. "Note--One-Dimensional Facility Location-Allocation using Dynamic Programming," Management Science, INFORMS, vol. 22(5), pages 614-617, January.
    5. Burdett, R.L. & Kozan, E., 2014. "An integrated approach for earthwork allocation, sequencing and routing," European Journal of Operational Research, Elsevier, vol. 238(3), pages 741-759.
    6. POCHET, Yves & WOLSEY, Laurence A., 1988. "Lot-size models with backlogging: strong reformulations and cutting planes," LIDAM Reprints CORE 791, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    7. Jack Brimberg & Abraham Mehrez, 2001. "Location and sizing of facilities on a line," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 9(2), pages 271-280, December.
    8. Adlakha, Veena & Kowalski, Krzysztof, 1999. "On the fixed-charge transportation problem," Omega, Elsevier, vol. 27(3), pages 381-388, June.
    9. Moreb, Ahmad A., 1996. "Linear programming model for finding optimal roadway grades that minimize earthwork cost," European Journal of Operational Research, Elsevier, vol. 93(1), pages 148-154, August.
    10. Hare, Warren L. & Koch, Valentin R. & Lucet, Yves, 2011. "Models and algorithms to improve earthwork operations in road design using mixed integer linear programming," European Journal of Operational Research, Elsevier, vol. 215(2), pages 470-480, December.
    11. Jack Brimberg & Charles ReVelle, 1998. "Solving the plant location problem on a line by linear programming," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 6(2), pages 277-286, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Güden, Hüseyin & Süral, Haldun, 2014. "Locating mobile facilities in railway construction management," Omega, Elsevier, vol. 45(C), pages 71-79.
    2. Wu, Tao & Shi, Leyuan & Geunes, Joseph & AkartunalI, Kerem, 2011. "An optimization framework for solving capacitated multi-level lot-sizing problems with backlogging," European Journal of Operational Research, Elsevier, vol. 214(2), pages 428-441, October.
    3. Hare, Warren & Lucet, Yves & Rahman, Faisal, 2015. "A mixed-integer linear programming model to optimize the vertical alignment considering blocks and side-slopes in road construction," European Journal of Operational Research, Elsevier, vol. 241(3), pages 631-641.
    4. Laurence A. Wolsey, 2002. "Solving Multi-Item Lot-Sizing Problems with an MIP Solver Using Classification and Reformulation," Management Science, INFORMS, vol. 48(12), pages 1587-1602, December.
    5. Kerem Akartunalı & Ioannis Fragkos & Andrew J. Miller & Tao Wu, 2016. "Local Cuts and Two-Period Convex Hull Closures for Big-Bucket Lot-Sizing Problems," INFORMS Journal on Computing, INFORMS, vol. 28(4), pages 766-780, November.
    6. Mauro Dell’Amico & Guenther Fuellerer & Gerhard Höfinger & Manuel Iori & Stefano Novellani, 2016. "A Decision Support System for Highway Construction: The Autostrada Pedemontana Lombarda," Interfaces, INFORMS, vol. 46(3), pages 245-263, April.
    7. Jans, Raf & Degraeve, Zeger, 2007. "Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1855-1875, March.
    8. Kis, Tamás & Kovács, András, 2013. "Exact solution approaches for bilevel lot-sizing," European Journal of Operational Research, Elsevier, vol. 226(2), pages 237-245.
    9. Kerem Akartunalı & Andrew Miller, 2012. "A computational analysis of lower bounds for big bucket production planning problems," Computational Optimization and Applications, Springer, vol. 53(3), pages 729-753, December.
    10. Luis A. Guardiola & Ana Meca & Justo Puerto, 2021. "Unitary Owen Points in Cooperative Lot-Sizing Models with Backlogging," Mathematics, MDPI, vol. 9(8), pages 1-19, April.
    11. Dominique Monnet & Warren Hare & Yves Lucet, 2020. "Fast feasibility check of the multi-material vertical alignment problem in road design," Computational Optimization and Applications, Springer, vol. 75(2), pages 515-536, March.
    12. Jans, R.F. & Degraeve, Z., 2005. "Modeling Industrial Lot Sizing Problems: A Review," ERIM Report Series Research in Management ERS-2005-049-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    13. Dominique Monnet & Warren Hare & Yves Lucet, 2022. "A successive relaxation algorithm to solve a MILP involving piecewise linear functions with application to road design," Computational Optimization and Applications, Springer, vol. 81(3), pages 741-767, April.
    14. Minjiao Zhang & Simge Küçükyavuz & Hande Yaman, 2012. "A Polyhedral Study of Multiechelon Lot Sizing with Intermediate Demands," Operations Research, INFORMS, vol. 60(4), pages 918-935, August.
    15. Brahimi, Nadjib & Dauzere-Peres, Stephane & Najid, Najib M. & Nordli, Atle, 2006. "Single item lot sizing problems," European Journal of Operational Research, Elsevier, vol. 168(1), pages 1-16, January.
    16. VAN VYVE, Mathieu & WOLSEY, Laurence & YAMAN, Hande, 2012. "Relaxations for two-level multi-item lot-sizing problem," LIDAM Discussion Papers CORE 2012031, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    17. Yuchen Jiang & Juan Xu & Siqian Shen & Cong Shi, 2017. "Production planning problems with joint service-level guarantee: a computational study," International Journal of Production Research, Taylor & Francis Journals, vol. 55(1), pages 38-58, January.
    18. Stan van Hoesel & H. Edwin Romeijn & Dolores Romero Morales & Albert P. M. Wagelmans, 2005. "Integrated Lot Sizing in Serial Supply Chains with Production Capacities," Management Science, INFORMS, vol. 51(11), pages 1706-1719, November.
    19. Melega, Gislaine Mara & de Araujo, Silvio Alexandre & Jans, Raf, 2018. "Classification and literature review of integrated lot-sizing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 271(1), pages 1-19.
    20. Xiao, Yiyong & Kaku, Ikou & Zhao, Qiuhong & Zhang, Renqian, 2011. "A reduced variable neighborhood search algorithm for uncapacitated multilevel lot-sizing problems," European Journal of Operational Research, Elsevier, vol. 214(2), pages 223-231, October.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:pal:jorsoc:v:68:y:2017:i:9:d:10.1057_s41274-016-0140-0. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.palgrave-journals.com/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.