Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Civil-Comp Proceedings
ISSN 1759-3433
CCP: 2/3
Edited by: B.H.V. Topping
Paper XXIII.2

Determining the Least Cost Spanning Network for a System of Pipes by the Use of Dynamic Programming

G.A. Waters* and S.J. McKechnie+

*Department of Engineering Science, University of Exeter
+Ove Arup and Partners, London

Full Bibliographic Reference for this paper
G.A. Waters, S.J. McKechnie, "Determining the Least Cost Spanning Network for a System of Pipes by the Use of Dynamic Programming", in B.H.V. Topping, (Editor), "Proceedings of the Second International Conference on Civil and Structural Engineering Computing", Civil-Comp Press, Edinburgh, UK, pp 237-243, 1985. doi:10.4203/ccp.2.23.2
Within Civil Engineering there are many types of network that are designed to convey flow from a number of sources to a single sink, or conversely from a single source to a number of sinks. Examples are sewer systems, water supply networks, irrigation schemes and networks for gas and electricity supply.

Many of these networks are tree-like in structure, (having no loops), and most are such that the cost of a link in the network is dependent on both the length of the link and the flow along it. Furthermore, the dependence of the cost on the flow is almost always a non-linear relationship exhibiting some degree of economy of scale. This relationship is often discontinuous, due, for example, to the availability of sewer pipes only in discrete sizes.

Traditionally, the designer of the network must first choose which out of a very large number of possible layouts he considers most suitable. He may then decide on the pressures (or elevations or potentials depending on the application) he requires at the pipe junctions. Finally he must design the diameter of each link in the network to cope with the expected flows. Any attempt at achieving a least cost scheme is usually limited to the examination of a handful of alternatives.

A method for the simultaneous selection of the layout and pipe diameters for the least cost network that connects a large number of sources to a single sink is described in this paper. The pressure (or elevation or potential) at each pipe junction is treated as a variable, and the method successfully handles any form of cost function. This global optimum solution is achieved by the use of Dynamic Programming.

A computer program is an essential part of the design process, and a description of one that the authors have written in Pascal is included together with examples of its use in the solution of civil engineering network problems.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description