IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v228y2013i1p1-10.html
   My bibliography  Save this article

Optimisation of gravity-fed water distribution network design: A critical review

Author

Listed:
  • De Corte, Annelies
  • Sörensen, Kenneth

Abstract

This paper surveys the literature on the optimisation of water distribution network design. The water distribution network design (WDND) optimisation problem entails finding the material and diameter of each pipe in the network so that the total cost of the network is minimised without violating any hydraulic constraints. This is a difficult combinatorial optimisation problem, in which decision variables are discrete and both cost function and constraints are non-linear. Over the past 30years, a large number of methods, especially in the field of (meta) heuristics, have been developed to solve this problem, most of which obtain good results on the available benchmark networks. In addition to outlining the basic features of each method, a detailed computational comparison is presented. Based on this comparison, some issues with the current state of the art in this domain are discussed, and some future research directions are suggested. Additionally, the need for an adequate set of benchmark instances is motivated, and the minimal requirements for an instance set generator are discussed.

Suggested Citation

  • De Corte, Annelies & Sörensen, Kenneth, 2013. "Optimisation of gravity-fed water distribution network design: A critical review," European Journal of Operational Research, Elsevier, vol. 228(1), pages 1-10.
    • Handle: RePEc:eee:ejores:v:228:y:2013:i:1:p:1-10
    DOI: 10.1016/j.ejor.2012.11.046
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221712008983
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2012.11.046?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. Reuven Rubinstein, 1999. "The Cross-Entropy Method for Combinatorial and Continuous Optimization," Methodology and Computing in Applied Probability, Springer, vol. 1(2), pages 127-190, September.
    2. Fred Glover, 1989. "Tabu Search---Part I," INFORMS Journal on Computing, INFORMS, vol. 1(3), pages 190-206, August.
    3. da Conceicao Cunha, Maria & Ribeiro, Luisa, 2004. "Tabu search algorithms for water network optimization," European Journal of Operational Research, Elsevier, vol. 157(3), pages 746-758, September.
    4. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms," Transportation Science, INFORMS, vol. 39(1), pages 104-118, February.
    5. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    6. Szeto, W.Y. & Wu, Yongzhong & Ho, Sin C., 2011. "An artificial bee colony algorithm for the capacitated vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 215(1), pages 126-135, November.
    7. J. Reca & J. Martínez & C. Gil & R. Baños, 2008. "Application of Several Meta-Heuristic Techniques to the Optimization of Real Looped Water Distribution Networks," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 22(10), pages 1367-1379, October.
    8. Kolisch, Rainer & Hartmann, Sonke, 2006. "Experimental investigation of heuristics for resource-constrained project scheduling: An update," European Journal of Operational Research, Elsevier, vol. 174(1), pages 23-37, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Shiono, Naoshi & Suzuki, Hisatoshi, 2016. "Optimal pipe-sizing problem of tree-shaped gas distribution networks," European Journal of Operational Research, Elsevier, vol. 252(2), pages 550-560.
    2. Annelies De Corte & Kenneth Sörensen, 2014. "HydroGen: an Artificial Water Distribution Network Generator," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 28(2), pages 333-350, January.
    3. DE CORTE, Annelies & SÖRENSEN, Kenneth, 2014. "An iterated local search algorithm for water distribution network design optimisation," Working Papers 2014018, University of Antwerp, Faculty of Business and Economics.
    4. Wang, S. & Huang, G.H., 2014. "An integrated approach for water resources decision making under interactive and compound uncertainties," Omega, Elsevier, vol. 44(C), pages 32-40.
    5. DE CORTE, Annelies & SÖRENSEN, Kenneth, 2015. "A lean optimization algorithm for water distribution network design optimization," Working Papers 2015020, University of Antwerp, Faculty of Business and Economics.
    6. Kamil Świętochowski & Martyna Świętochowska & Marek Kalenik & Joanna Gwoździej-Mazur, 2023. "Analysis of the Use of a Low-Power Photovoltaic System to Power a Water Pumping Station in a Tourist Town," Energies, MDPI, vol. 16(21), pages 1-14, November.
    7. Weyland, Dennis, 2015. "A critical analysis of the harmony search algorithm—How not to solve sudoku," Operations Research Perspectives, Elsevier, vol. 2(C), pages 97-105.
    8. Liang, Yingzong & Hui, Chi Wai, 2018. "Convexification for natural gas transmission networks optimization," Energy, Elsevier, vol. 158(C), pages 1001-1016.
    9. González-Bravo, Ramón & Fuentes-Cortés, Luis Fabián & Ponce-Ortega, José María, 2017. "Defining priorities in the design of power and water distribution networks," Energy, Elsevier, vol. 137(C), pages 1026-1040.
    10. Shiono, Naoshi & Suzuki, Hisatoshi & Saruwatari, Yasufumi, 2019. "A dynamic programming approach for the pipe network layout problem," European Journal of Operational Research, Elsevier, vol. 277(1), pages 52-61.
    11. Naoum-Sawaya, Joe & Ghaddar, Bissan & Arandia, Ernesto & Eck, Bradley, 2015. "Simulation-optimization approaches for water pump scheduling and pipe replacement problems," European Journal of Operational Research, Elsevier, vol. 246(1), pages 293-306.

    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. DE CORTE, Annelies & SÖRENSEN, Kenneth, 2012. "Optimisation of water distribution network design: a critical review," Working Papers 2012016, University of Antwerp, Faculty of Business and Economics.
    2. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    3. Lai, David S.W. & Caliskan Demirag, Ozgun & Leung, Janny M.Y., 2016. "A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 86(C), pages 32-52.
    4. Zhang, Ruiyou & Yun, Won Young & Moon, Il Kyeong, 2011. "Modeling and optimization of a container drayage problem with resource constraints," International Journal of Production Economics, Elsevier, vol. 133(1), pages 351-359, September.
    5. Gmira, Maha & Gendreau, Michel & Lodi, Andrea & Potvin, Jean-Yves, 2021. "Tabu search for the time-dependent vehicle routing problem with time windows on a road network," European Journal of Operational Research, Elsevier, vol. 288(1), pages 129-140.
    6. Ma, Hong & Cheang, Brenda & Lim, Andrew & Zhang, Lei & Zhu, Yi, 2012. "An investigation into the vehicle routing problem with time windows and link capacity constraints," Omega, Elsevier, vol. 40(3), pages 336-347.
    7. Tai-Yu Ma, 2011. "A cross entropy multiagent learning algorithm for solving vehicle routing problems with time windows," Post-Print halshs-00592118, HAL.
    8. Asbach, Lasse & Dorndorf, Ulrich & Pesch, Erwin, 2009. "Analysis, modeling and solution of the concrete delivery problem," European Journal of Operational Research, Elsevier, vol. 193(3), pages 820-835, March.
    9. Schmid, Verena & Doerner, Karl F. & Laporte, Gilbert, 2013. "Rich routing problems arising in supply chain management," European Journal of Operational Research, Elsevier, vol. 224(3), pages 435-448.
    10. Gerhard Hiermann & Matthias Prandtstetter & Andrea Rendl & Jakob Puchinger & Günther Raidl, 2015. "Metaheuristics for solving a multimodal home-healthcare scheduling problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 23(1), pages 89-113, March.
    11. Chou, Chang-Chi & Chiang, Wen-Chu & Chen, Albert Y., 2022. "Emergency medical response in mass casualty incidents considering the traffic congestions in proximity on-site and hospital delays," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    12. Ullrich, Christian A., 2013. "Integrated machine scheduling and vehicle routing with time windows," European Journal of Operational Research, Elsevier, vol. 227(1), pages 152-165.
    13. Qi, Mingyao & Lin, Wei-Hua & Li, Nan & Miao, Lixin, 2012. "A spatiotemporal partitioning approach for large-scale vehicle routing problems with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 248-257.
    14. Zhiping Zuo & Yanhui Li & Jing Fu & Jianlin Wu, 2019. "Human Resource Scheduling Model and Algorithm with Time Windows and Multi-Skill Constraints," Mathematics, MDPI, vol. 7(7), pages 1-18, July.
    15. Baals, Julian & Emde, Simon & Turkensteen, Marcel, 2023. "Minimizing earliness-tardiness costs in supplier networks—A just-in-time truck routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 707-741.
    16. Ulrike Ritzinger & Jakob Puchinger & Richard Hartl, 2016. "Dynamic programming based metaheuristics for the dial-a-ride problem," Annals of Operations Research, Springer, vol. 236(2), pages 341-358, January.
    17. John E. Fontecha & Oscar O. Guaje & Daniel Duque & Raha Akhavan-Tabatabaei & Juan P. Rodríguez & Andrés L. Medaglia, 2020. "Combined maintenance and routing optimization for large-scale sewage cleaning," Annals of Operations Research, Springer, vol. 286(1), pages 441-474, March.
    18. Subramanyam, Anirudh & Wang, Akang & Gounaris, Chrysanthos E., 2018. "A scenario decomposition algorithm for strategic time window assignment vehicle routing problems," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 296-317.
    19. Mohammad Torkjazi & Nathan Huynh, 2019. "Effectiveness of Dynamic Insertion Scheduling Strategy for Demand-Responsive Paratransit Vehicles Using Agent-Based Simulation," Sustainability, MDPI, vol. 11(19), pages 1-12, September.
    20. Julia Rieck & Jürgen Zimmermann, 2010. "A new mixed integer linear model for a rich vehicle routing problem with docking constraints," Annals of Operations Research, Springer, vol. 181(1), pages 337-358, December.

    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:eee:ejores:v:228:y:2013:i:1:p:1-10. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.