A dynamic programming approach for the pipe network layout problem

Naoshi Shiono, Hisatoshi Suzuki and Yasufumi Saruwatari

European Journal of Operational Research, 2019, vol. 277, issue 1, 52-61

Abstract: 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.

Keywords: OR in energy; Dynamic programming; Pipe network design; Minimum concave cost network flow problem (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719301845
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:277:y:2019:i:1:p:52-61

DOI: 10.1016/j.ejor.2019.02.036

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().