A dynamic programming approach for the pipe network layout problem. (English) Zbl 1430.90172
Summary: This study addresses the optimization problem with the objective of designing a pipe network. An underground pipe network for geographically dispersed customers must be designed with consideration of the many candidate roads below which pipes are laid. The layout and pipe sizes must then be determined to minimize the pipe network construction cost. However, this problem has attracted little research attention to date. In this study, we first formulate mathematical optimization models under the assumption of a single source node in a planar graph. We then find that the cost-minimized pipe network has a tree structure if the diameter of each pipe is a continuous variable. Thereafter, we develop an exact algorithm based on dynamic programming. The time complexity of the algorithm is polynomial in the number of nodes, but exponential in the number of faces covering all demand nodes for a planar graph. In addition, we propose a method for assigning commercial pipe diameters to the tree using a commercial solver. The computational results for a real-world gas distribution network show that our method provides an efficient solution.
MSC:
| 90B10 | Deterministic network models in operations research |
| 90C35 | Programming involving graphs or networks |
| 90C39 | Dynamic programming |
Keywords:
OR in energy; dynamic programming; pipe network design; minimum concave cost network flow problemReferences:
| [1] | Afshar, M. H., Application of a max-min ant system to joint layout and size optimization of pipe networks, Engineering Optimization, 38, 3, 299-317 (2006) |
| [2] | Afshar, M. H., Evaluation of selection algorithms for simultaneous layout and pipe size optimization of water distribution networks, Scientia Iranica, 14, 1, 23-32 (2007) · Zbl 1179.90215 |
| [3] | Bern, M., Faster exact algorithms for Steiner trees in planar networks, Networks, 20, 1, 109-120 (1990) · Zbl 0687.90088 |
| [4] | Bhaskaran, S.; Salzborn, F. J.M., Optimal design of gas pipeline networks, Journal of the Operational Research Society, 30, 1047-1060 (1979) · Zbl 0422.90046 |
| [5] | Bhave, P. R., Optimal design of water distribution networks (2003), Alpha Science International Ltd: Alpha Science International Ltd Pangbourne, UK |
| [6] | Bhave, P. R.; Lam, C. F., Optimal layout for branching distribution networks, Journal of Transportation Engineering, 109, 4, 534-547 (1983) |
| [7] | Bondy, A.; Murty, U. S.R., Graph theory (2008), Springer-Verlag: Springer-Verlag London, UK · Zbl 1134.05001 |
| [8] | Borradaile, G.; Klein, P. N.; Mathieu, C., Steiner tree in planar graphs: An O (n log n) approximation scheme with singly-exponential dependence on epsilon, Lecture Notes in Computer Science, 4619, 275-286 (2007) · Zbl 1209.68633 |
| [9] | Boyne, G. G., The optimum design of fluid distribution networks with particular reference to low pressure gas distribution networks, International Journal for Numerical Methods in Engineering, 5, 2, 253-270 (1972) |
| [10] | Davidson, J. W.; Goulter, I. C., Microcomputer workstation for design of rural natural gas distribution systems, Microcomputers in Civil Engineering, 4, 1, 61-73 (1989) |
| [11] | Davidson, J. W.; Goulter, I., Heuristic for layout design of rural gas systems, Journal of Computing in Civil Engineering, 5, 3, 315-332 (1991) |
| [12] | Davidson, J. W.; Goulter, I., Rule-based design of layout of rural natural gas networks, Journal of Computing in Civil Engineering, 5, 3, 300-314 (1991) |
| [13] | De Corte, A.; Sörensen, K., Optimization of gravity-fed water distribution network design: A critical review, European Journal of Operational Research, 228, 1, 1-10 (2013) · Zbl 1332.90392 |
| [14] | Dreyfus, S. E.; Wagner, R. A., The Steiner problem in graphs, Networks, 1, 3, 195-207 (1971) · Zbl 0229.05125 |
| [15] | D’Ambrosio, C.; Lodi, A.; Wiese, S.; Bragalli, C., Mathematical programming techniques in water network optimization, European Journal of Operational Research, 243, 3, 774-788 (2015) · Zbl 1346.90211 |
| [16] | Erickson, R. E.; Monma, C. L.; Veinott, A. F., Send-and-split method for minimum-concave-cost network flows, Mathematics of Operations Research, 12, 4, 634-664 (1987) · Zbl 0667.90036 |
| [17] | Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness (1979), W.H. Freeman & Co: W.H. Freeman & Co New York, NY · Zbl 0411.68039 |
| [18] | Geem, Z. W.; Park, Y., Optimal layout for branched networks using harmony search, (Proceedings of the 5th WSEAS international conference on applied computer science. Proceedings of the 5th WSEAS international conference on applied computer science, Hangzhou, China (2006)), 364-367 |
| [19] | Gonçalves, G. M.; Gouveia, L.; Pato, M. V., An improved decomposition-based heuristic to design a water distribution network for an irrigation system, Annals of Operations Research, 219, 1, 141-167 (2014) · Zbl 1301.90009 |
| [20] | Gonçalves, G. M.; Vaz Pato, M., A three-phase procedure for designing an irrigation system’s water distribution network, Annals of Operations Research, 94, 1, 163-179 (2000) · Zbl 0997.90004 |
| [21] | Guisewite, G. M., Network problems, (Horst, R.; Pardalos, P. M., Handbook of global optimization (1995), Kluwer Academic Publishers: Kluwer Academic Publishers London), 609-648 · Zbl 0832.90117 |
| [22] | Guisewite, G. M.; Pardalos, P. M., Minimum concave-cost network flow problems: Applications, complexity, and algorithms, Annals of Operations Research, 25, 75-99 (1990) · Zbl 0724.90022 |
| [23] | Gurobi Optimization. (2015). Gurobi 5.6.2. http://www.gurobi.com/; Gurobi Optimization. (2015). Gurobi 5.6.2. http://www.gurobi.com/ |
| [24] | Hansen, C. T.; Madsen, K.; Nielsen, H. B., Optimization of pipe networks, Mathematical Programming, 52, 1, 45-58 (1991) · Zbl 0728.90032 |
| [25] | Henzinger, M. R.; Klein, P.; Rao, S.; Subramanian, S., Faster shortest-path algorithms for planar graphs, Journal of Computer and System Sciences, 55, 1, 3-23 (1997) · Zbl 0880.68099 |
| [26] | Koch, T.; Hiller, B.; Pfetsch, M. E.; Schewe, L., Evaluating gas network capacities (2015), SIAM · Zbl 1322.90007 |
| [27] | Korte, B.; Vygen, J., Combinatorial optimization: Theory and algorithms (2012), Springer-Verlag Berlin Heidelberg: Springer-Verlag Berlin Heidelberg BerlinHeidelberg · Zbl 1237.90001 |
| [28] | Lejano, R. P., Optimizing the layout and design of branched pipeline water distribution systems, Irrigation and Drainage Systems, 20, 1, 125-137 (2006) |
| [29] | MathWorks (2012). MATLAB R2012a. https://www.mathworks.com/; MathWorks (2012). MATLAB R2012a. https://www.mathworks.com/ |
| [30] | Maher, S. J., Fischer, T., Gally, T., Gamrath, G., Gleixner, A., Gottwald, R. L., Hendel, G., Koch, T., Lübbecke, M. E., Miltenberger, M., Müller, B., Pfetsch, M. E., Puchert, C., Rehfeldt, D., Schenker, S., Schwarz, R., Serrano, F., Shinano, Y., Weninger, D., Witt, J. T., & Witzig, J. (2017). The SCIP Optimization Suite 4.0. Technical Report 17-12. ZIB.; Maher, S. J., Fischer, T., Gally, T., Gamrath, G., Gleixner, A., Gottwald, R. L., Hendel, G., Koch, T., Lübbecke, M. E., Miltenberger, M., Müller, B., Pfetsch, M. E., Puchert, C., Rehfeldt, D., Schenker, S., Schwarz, R., Serrano, F., Shinano, Y., Weninger, D., Witt, J. T., & Witzig, J. (2017). The SCIP Optimization Suite 4.0. Technical Report 17-12. ZIB. |
| [31] | Mays, L. W., Reliability analysis of water distribution systems (1989), ASCE Publications |
| [32] | Morgan, D. R.; Goulter, I. C., Optimal urban water distribution design, Water Resources Research, 21, 5, 642-652 (1985) |
| [33] | Rothfarb, B.; Frank, H.; Rosenbaum, D. M.; Steiglitz, K.; Kleitman, D. J., Optimal design of offshore natural-gas pipeline systems, Operations Research, 18, 6, 992-1020 (1970) |
| [34] | Saleh, S. H.A.; Tanyimboh, T. T., Coupled topology and pipe size optimization of water distribution systems, Water Resources Management, 27, 14, 4795-4814 (2013) |
| [35] | Shiono, N.; Suzuki, H., Optimal pipe-sizing problem of tree-shaped gas distribution networks, European Journal of Operational Research, 252, 2, 550-560 (2016) · Zbl 1346.90227 |
| [36] | The Japan Gas Association. (2011). An outline of the city gas industry-supply system edition (in Japanese); The Japan Gas Association. (2011). An outline of the city gas industry-supply system edition (in Japanese) |
| [37] | Walters, G. A., The design of the optimal layout for a sewer network, Engineering Optimization, 9, 1, 37-50 (1985) |
| [38] | Walters, G. A.; Lohbeck, T., Optimal layout of tree networks using genetic algorithms, Engineering Optimization, 22, 1, 27-48 (1993) |
| [39] | Walters, G. A.; Smith, D. K., Evolutionary design algorithm for optimal layout of tree networks, Engineering Optimization, 24, 4, 261-281 (1995) |
| [40] | Yates, D. F.; Templeman, A. B.; Boffey, T. B., The computational complexity of the problem of determining least capital cost designs for water supply networks, Engineering Optimization, 7, 143-155 (1984) |
| [41] | Zangwill, W. I., Minimum concave cost flows in certain networks, Management Science, 14, 7, 429-450 (1968) · Zbl 0159.49102 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
