Optimal routes of pipeline supply from source to consumer objective using graph theory.

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

1. INTRODUCTION

Through scope of investment and energy consumption, adductions have a significant share in the systems of water supply, and their rational design requires more optimization processes, among which an important place is held by optimizing their route (Nayyar, 2000). In current practice of design, setting the optimal solution is, usually, by analytical study of two or three 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. In this context, we describe a deterministic mathematical model optimization of the route of the water supply adduction, based on the theory of graphs.

2. CALCULATION ALGORITHM

Modeling this problem is achieved through representation of connected directed graph G=(X, U) consisting of the source as the origin, route as required arcs and points as vertices. For each arc [u.sup.i.sub.j] [member of] U is associated a number [lambda]([u.sup.i.sub.j]) [greater than or equal to] 0, in conventional units, depending on the optimization criterion was adopted. The optimum route is given by the path with lowest cost, the minimum value of which is determined by applying the algorithm Bellman-Kalaba, (Bellman-Kalaba, 1965). Graph G= (X, U) is attached to a matrixM whose elements [m.sub.ij] are:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

The optimal route is the best path [mu] of graph, with total value:

[lambda]([mu]) = [summation over ([u.sup.i.sub.j][member of][mu]] [lambda] ([u.sup.i.sub.j]) [right arrow] min (2)

If we define [V.sub.i] as the minimum value of the road [[mu].sup.i.sub.n], (i = [bar.0, n]) existing from the tip of [x.sub.i] to the tip of [x.sub.n]:

[V.sub.i] = [lambda]([[mu].sup.i.sub.n]), (i = [bar.0, n]) (3)

Hence:

[V.sub.n] = 0 (4)

then, under the principle of optimality:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

To solve system (5) we proceed iteratively, defining [V.sup.k.sub.i] the value of [V.sub.i] obtained at iteration k, namely:

[V.sup.0.sub.i] = [m.sub.in] (i = [bar.0, n - 1]); [V.sup.0.sub.n] = 0 (6)

Calculate:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

and then:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

Ordinal iteration of k expressed by relations (8) gives finite values only for roads of length at most k + 1 arriving at [x.sub.n], choosing between them the minimal one.

From one iteration to the next:

[V.sup.k.sub.i] [less than or equal to] [V.sup.k-1.sub.i], [for all]j (9)

Numbers [V.sup.k.sub.i] (i [not equal to] n ; k = 0,1, ...) form a monotone decreasing pattern so that we reach the minimum, necessary, after a finite number of iterations not exceeding n - 1. So the algorithm stops when it reaches an iteration k, such that [V.sup.k.sub.i] = [V.sup.k+1.sub.i], (i = [bar.0,n]), and the minimum road value between the peaks [x.sub.0] and [X.sub.n] is [V.sup.k.sub.0] = [V.sup.k+1.sub.0]. To identify which roads have the found minimum values, we deduce from (8) that along them, on the last iterations we have:

[V.sup.k.sub.i] = [m.sub.ij] + [V.sup.k-1.sub.j] = [m.sub.ij] + [V.sup.k.sub.j] (10)

Based on the algorithm described, computer program named BEL_KAL was designed in Borland PASCAL language, (Anton et al, 2002). As the data output sequence results road peaks of minimum values and value of the road.

[FIGURE 1 OMITTED]

3. CASE STUDY

It exemplifies the application of Bellman-Kalaba algorithm to determine the optimal route for location L from the source S1, (Sarbu, 1996) (fig. 1).

Modeling problem is achieved through representation of connected directed graph G = (X, U) of order n = 7, consisting of the source point of origin, route as required arcs and points as vertices. For each arc [u.sup.i.sub.j] [member of] U is assigned a cost in conventional units (fig. 2) and matrix M attached to graph G = (X, U) are the elements [m.sub.i,j] defined by relations:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

where [lambda]([u.sup.i.sub.j]) is the value attributed to edge [u.sup.i.sub.j] [member of] U.

 1 2 3 4 5

M =

1 0 42 53 [infinity] [infinity]
2 [infinity] 0 [infinity] [infinity] 73
3 [infinity] [infinity] 0 92 61
4 [infinity] [infinity] [infinity] 0 [infinity]
5 [infinity] [infinity] [infinity] [infinity] 0
6 [infinity] [infinity] [infinity] [infinity] [infinity]
7 [infinity] [infinity] [infinity] [infinity] [infinity]

 6 7 [V.sup.0.sub.i] [V.sup.1.sub.i]

M =

1 [infinity] [infinity] [infinity] [infinity]
2 73 [infinity] [infinity] 153
3 82 [infinity] [infinity] 153
4 [infinity] 61 61 61
5 e 92 92 92
6 0 82 82 82
7 [infinity] 0 0 0

 [V.sup.2.sub.i] [V.sup.3.sub.i]

M =

1 197 197
2 153 153
3 153 153
4 61 61
5 92 92
6 82 82
7 0 0

Route with minimum total cost is given by way of minimum value in this graph, which is determined using Bellman-Kalaba algorithm.

For each [V.sup.k.sub.i] (k = 0,1, ...) a column is added to the previous matrix in which values are inserted properly.

It follows successively:

a) Calculate the values [V.sup.0.sub.i] = [m.sub.i7] (i = 1, ..., 7), which pass into the column [V.sup.0.sub.i].

b) Calculate values [V.sup.1.sub.i] for (i = 1, ..., 7), (j = 1, ... 7), which is passing in that column:

c) Calculate values V2 for (i = 1, ..., 7), (j = 1, ..., 7), etc.

d) To calculate the values corresponding to column [V.sup.3.sub.i] for (i = 1, ..., 7), (j = 1, ..., 7), and analogue, finaly are obtined:

[FIGURE 2 OMITTED]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)

Since [V.sup.k.sub.i] = [V.sup.k-1.sub.i] (i = 1, ..., 7), algorithm stops and the road is the minimum of [V.sup.2.sub.1] = [V.sup.3.sub.1] = 197. This value is reached on the way (1, 2, 6, 7), thus resulting in optimal route of adduction as: [S.sub.1], A, C and L. To resolve this problem the computer program BEL_KAL was used.

4. CONCLUSION

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

--Bellman-Kalaba 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.

5. ACKNOWLEDGEMENTS

This work has been supported by National Centre of Management Programs, Project No. 1365/21-041/2007 and Grant type "IDEI", CNCSIS Department, Contract No. 35-68/2007.

6. 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 Horizons", Timisoara, Romania, ISBN 973-8391-72-5

Bellman, R.; Kalaba, R. (1965). Dynamic Programming and Modern Control Theory, McGraw-Hill, New York

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 Rumanian Academy, ISBN: 973-27-0575-2, Bucharest, Romania