Optimal routes of pipeline supply from pumping station to consumers using graph theory.

Milos, Teodor ; Alexandrescu, Aurora ; Dobanda, Eugen 等

1. INTRODUCTION

Any network flow can be represented as a mathematical model related topological graph. Topological graph of the network is represented in plane spatial structure composed of interconnected components and piping components. Through scope of investment and energy consumption, optimal routs have a significant share in the systems of water supply, and their rational design behaves more optimization processes, among which an important place held optimize their route (Nayyar, 2000). In current practice of design, setting the optimal solution is, usually, by analytical study of various variants selected from many possible intuitive decisions, whose error is inversely proportional to the degree of experience of the designer (Alexandrescu, 2003). Modern mathematical disciplines, by operational calculation, put at specialist's disposition a vast apparatus of scientific analysis in determining the optimal decisions for the design of water supply (Anton et all, 2002). In this context, describes a deterministic mathematical model optimization of the routes of the water supply, based on the theory of graphs.

2. THEORETICAL ASPECTS

In accordance with graph theory, number of independent rings M in a network is equals to the cyclomatic number of network graph, given by Euler's relationship:

M = T - N + 1 (1)

where T and N is the number of sections and nodes of network.

Graph theory method allows registering the entire main geometrical characteristics and the network shape using a matrix. Thus, undirected graph of a network can be described by transition matrix, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], with the number of rows and columns equal to the number of vertices N and [a.sub.ij] elements given by the relationship:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

Incidence matrix (vertices matrix), [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], relating the arches and vertices of the network oriented graph, illustrating the network interconnection nodes and lines with the number of peaks N, and the columns at the arcs T. The elements [a.sub.ij] of this matrix are defined with relations:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

Matrix of membership (cycles matrix) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] relating the arcs and graph directed cycles of a network, indicating membership pipes to network ring and having on the lines, order number of rings M, and the columns at the arcs T. The elements [a.sub.ij] of this matrix are defined relations:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

Pipeline topology can be fully and unequivocally described with the incidence matrix and the matrix of membership.

3. CALCULATION ALGORITHM

Since this optimization problem may be one or more solutions, has developed an algorithm based on graph theory that generates all minimal trees with nodes of the graph formed with the nodes where consumers are located and the connections between them, thereby causing all optimal solutions.

Be undirected related graph G = (X, U) with X = (1,2 ,..., n), where each edge [u.sup.i.sub.j] [member of] U has an associated value [lambda],([u.sup.i.sub.j]) > 0 in conventional units, according to the optimization criterion adopted. This graph is attached to matrix C of order n whose elements are:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

Tags peaks edges [u.sup.i.sub.j] which are part of the tree graph minimum amounts and the corresponding values [c.sub.ij] are retained in a matrix M, which under a tree that has at least n-1 edges will have three columns and n-1 lines. This matrix is constructed in the following steps:

1) Determine the minimum elements of each line of matrix C.

2) Choose one of the lines for which the minimum element is unique and is denoted by r, s to its indices.

3) Record the first line of matrix M, values r, s, [c.sub.rs] and these elements is marked with [c.sub.rs] and [c.sub.sr], from the matrix C.

4) Determine minimum unmarked elements of matrix C lines which are marked at least one element is denoted by r, s indices minimal element or one of them if there is more.

5) If on line s of matrix C exists marked elements, then is marked elements [c.sub.rs], [c.sub.sr] too and proceed to step 6, but if on the line s of the matrix C has no items marked for each [c.sub.is] element located on a line is marked and equal [c.sub.rs] it added a new line to matrix M consisting of values i, s, [c.sub.is] and is marked elements [c.sub.is], [c.sub.si] from matrix C, then proceed to step 6.

6) Proceed to step 4 or stop calculations as there are no lines or matrix C with nothing unmarked element.

If the matrix M, it follows a line number greater than the order of the graph considered minimal tree problem has several solutions. In this case, allow first matrix lines so that the second column items are sorted ascending. The second column will be found only index of n-1 edges of the graph. If we note the absolute frequencies of these indices on the second column of the matrix M with [F.sub.i] and the cumulative frequencies with [F.sup.*.sub.i] (i = 1,2, ... n-1), minimal number of trees of the graph [n.sub.a], has value on the relationship:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

To identify the minimal tree is constructed with a matrix A with n-1 lines and [n.sub.a] column in the following stages:

7) Be each absolute frequencies [F.sub.i] are assigned to variable [V.sub.i,k] whose values are the elements of the crowd

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

8) Each line i of the matrix A record [n.sub.a] / [F.sub.i] times elements [V.sub.i,k] as crowd Ni such as matrix A have finally obtained with the lexicographic ordered columns.

Each column of matrix A is matrix M lines indices containing one edge characteristics of optimal trees.

Described algorithm was developed based on the language Borland Pascal 7, Kruskal program (Kruskal, 1956).

Using this optimization program results make savings of pipelines, embankments and pumping power and a more homogeneous distribution of flow and pressure in the network.

4. CASE STUDY

An example application described above algorithm for determining optimal routes for a pipeline, with possible routes graph of order n = 8 in Figure 1, which is attached cost matrix C (Sarbu, 1996).

[FIGURE 1 OMITTED]

[FIGURE 2 OMITTED]

Indices crowd that lines are marked at least one item is denoted by L. Following algorithm steps of optimization routes result successively:

Minimum elements of the first line [c.sub.13] = 80 is unique, according to phase two: M = [1 3 80] and shall be marked the elements [c.sub.13], [c.sub.31], in the matrix C so that L = {1, 3}.

On each column finding the lines clues of the matrix M containing one edge characteristics of optimal trees.

Thus, the first column elements of A states that one of the minimal graph trees is of corresponding lines 1, 2, 3, 4, 6, 7, 9 of the matrix M. This tree is thus composed of edges [u.sup.3.sub.2], [u.sup.1.sub.3], [u.sup.8.sub.4], [u.sup.2.sub.5], [u.sup.5.sub.6], [u.sup.5.sub.7], [u.sup.6.sub.8] (Figure 2). This result is easily reached using Kruskal computer program. Optimal solution to be applied in practice is taking into account other criteria. For this we can impose hydraulic conditions.

5. CONCLUSIONS

--This study highlights how the economic fact of a technical problem can be optimized using mathematic-informatics structure type graph.

--Mathematical model is easily programmable in an evolved language, obtaining immediate results. The only problem is populating the matrix attached graph.

--Kruskal algorithm was originally designed for the economy, but the adaptation was possible because the optimal path in the economy is a virtual way and here is a real way.

6. ACKNOWLEDGEMENT

This work has been supported by National Centre of Management Programs, Project No. 1365/21-041/2007.

7. REFERENCES

Alexandrescu, A. (2003). Concerning optimization's working of the pumping station for water feedings, 18th International Conference on Hydraulics and Pneumatics, Prague, Czech Rep., Sbornik, ISBN 80-02-01567-3, pp. 263-268

Anton, L.; Baya A.; Milos T. & Resiga R. (2002). Experimental Fluid Mechanics, Vol. 1, Publishing house "Academic Horizonts", ISBN 973-8391-72-5, Timisoara, Romania

Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7:48-50, 1956

Nayyar, M.L. (2000). Piping Handbook, 7th Edition, McGraw-Hill, ISBN: 978-0-07-047106-1, New York, San Francisco, Tokyo, Toronto

Sarbu, I. (1996). Energetically Optimization of Water Distribution Systems, Publishing house of Romanian Academy, ISBN: 973-27-0575-2, Bucharest, Romania