[go: up one dir, main page]
Skip to main content
SpringerLink
Log in

An improved decomposition-based heuristic to design a water distribution network for an irrigation system

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

In this paper the authors address a pressurized water distribution network design problem for irrigation purposes. Two mixed binary nonlinear programming models are proposed for this NP-hard problem. Furthermore, a heuristic algorithm is presented for the problem, which considers a decomposition sequential scheme, based on linearization of the second model, coupled with constructive and local search procedures designed to achieve improved feasible solutions. To evaluate the robustness of the method we tested it on several instances generated from a real application. The best solutions obtained are finally compared with solutions provided by standard software. These computational experiments enable the authors to conclude that the decomposition sequential heuristic is a good approach to this difficult real problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Algorithm 1
Algorithm 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  • Al-Khayyal, F. A., & Falk, J. E. (1983). Jointly constrained biconvex programming. Mathematics of Operations Research, 8(2), 273–286.

    Article  Google Scholar 

  • Alperovits, E., & Shamir, U. (1977). Design of optimal water distribution systems. Water Resources Research, 13(6), 885–900.

    Article  Google Scholar 

  • Bragalli, C., D’Ambrosio, C., Lee, J., Lodi, A., & Toth, P. (2006). An MINLP solution method for a water network problem (IBM Research Report, RC23893 (W0602-210)). February 28, pp. 1–17.

  • CPLEX Optimization (2007). ©ILOG USA.

  • GAMS: The Solver Manuals (2004). ©GAMS Development Corporation.

  • Gonçalves, G. M., & Pato, M. V. (2000). A three-phase procedure for designing an irrigation system’s water distribution network. Annals of Operations Research, 94, 163–179.

    Article  Google Scholar 

  • Gonçalves, G. M. (2008). Modelos de Optimização para o Desenho de uma Rede de Distribuição de Água sob Pressão em Sistemas de Rega. Ph.D. Dissertation, Lisboa.

  • Hansen, C. T., Madsen, K., & Nielsen, H. B. (1991). Optimization of pipe networks. Mathematical Programming, 52, 45–58.

    Article  Google Scholar 

  • Ionescu, V., Pantu, D., Berar, U., & Hutanu, V. (1981). Optimizing the dimensioning of a ramified network of pipe lines with flow variable in time. Economic Computation & Economic Cybernetics Studies & Research, 15(3), 41–49.

    Google Scholar 

  • Karmeli, D., Gadish, Y., & Meyers, S. (1968). Design of optimal water distribution networks. Journal of the Pipeline Division, 94, 1–10.

    Google Scholar 

  • Karp, R. M. (1972). In R. Miller & J. Thatcher (Eds.), Complexity of computer computations. New York: Plenum.

    Google Scholar 

  • Kessler, A., & Shamir, U. (1991). Decomposition technique for optimal design of water supply networks. Engineering Optimization, 17, 1–19.

    Article  Google Scholar 

  • Knowles, T., Gupta, I., & Hassan, M. (1976). Decomposition of water distribution networks. AIIE Transactions, 8(4), 443–448.

    Article  Google Scholar 

  • Labye, Y., Olson, M., Galand, A., & Tsiourtis, N. (1988). FAO irrigation and drenage paper 44. Design and optimization of irrigation distribution networks. Rome: Food and Agriculture Organization of the United Nations.

    Google Scholar 

  • Loganathan, G. V., Sherali, H. D., & Shah, M. P. (1990). A two-phase network design heuristic for minimum cost water distribution systems under a reliability constraint. Engineering Optimization, 15, 311–336.

    Article  Google Scholar 

  • McCormick, G. P. (1976). Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems. Mathematical Programming, 10, 147–175.

    Article  Google Scholar 

  • Sherali, H. D., & Smith, E. P. (1997). A global optimization approach to a water distribution network design problem. Journal of Global Optimization, 11, 107–132.

    Article  Google Scholar 

  • Takahashi, H., & Matsuyama, A. (1980). An approximate solution for the Steiner problem in graphs. Mathematica Japonica, 24(6), 573–577.

    Google Scholar 

  • Zhang, J., & Zhu, D. (1996). A bilevel programming method for pipe network optimization. SIAM Journal on Optimization, 6(3), 838–857.

    Article  Google Scholar 

Download references

Acknowledgements

This work is supported by Portuguese National Funding from FCT—Fundação para a Ciência e a Tecnologia, under the project: PEst-OE/MAT/UI0152.

The authors are grateful to the referees for the extensive suggestions that have considerably improved the paper.

Author information

Authors and Affiliations

  1. Departamento de Matemática, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa, 2829-516, Monte da Caparica, Portugal

    Graça Marques Gonçalves

  2. Centro de Investigação Operacional, Faculdade de Ciências, Universidade de Lisboa, 1749-016, Lisboa, Portugal

    Graça Marques Gonçalves, Luís Gouveia & Margarida Vaz Pato

  3. Departamento de Estatística e Investigação Operacional, Faculdade de Ciências, Universidade de Lisboa, 1749-016, Lisboa, Portugal

    Luís Gouveia

  4. Departamento de Matemática, Instituto Superior de Economia e Gestão, Universidade Técnica de Lisboa, 1200-781, Lisboa, Portugal

    Margarida Vaz Pato

Authors
  1. Graça Marques Gonçalves
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Luís Gouveia
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Margarida Vaz Pato
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Graça Marques Gonçalves.

Appendix: Input data

Appendix: Input data

Table 8 Costs of the pipes commercially available (Cimianto, Sociedade Técnica de Hidráulica, S.A.)
Full size table
Table 9 Bounds for the water speed on pipes (Labye et al. 1988)
Full size table

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gonçalves, G.M., Gouveia, L. & Pato, M.V. An improved decomposition-based heuristic to design a water distribution network for an irrigation system. Ann Oper Res 219, 141–167 (2014). https://doi.org/10.1007/s10479-011-1036-7

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-011-1036-7

Keywords

Search

Navigation