Maximum Dynamic Flow Finding Task with the Given Vitality Degree

Abstract

This paper is devoted to the task of the maximum flow finding with nonzero lower flow bounds taking into account given vitality degree. Transportation network with the flow is considered in fuzzy conditions due to the fuzzy character of the network's parameters. Arcs of the network are assigned by the fuzzy arc capacities and nonzero lower flow bounds, vitality parameters and crisp transit times. All network's parameters can vary over time, therefore, it allows to consider network as dynamic one. The vitality parameter assigned to the arcs means ability of its objects to be resistant to weather conditions, traffic accidents and save and restore objects themselves, arc capacities of the network's sections in case of damage. The nonzero lower flow bounds are used to assess economic reliability of the transportation. Such methods can be applied in the real railways, roads and air roads solving the task of the optimal cargo transportation.

Keywords

• Fuzzy dynamic graph
• fuzzy nonzero lower flow bound
• fuzzy vitality degree

1 Introduction

The flow tasks [1] considered during the study of transportation networks are relevant due to their wide practical application, in particular, when finding the maximum amount of traffic between selected nodes on the road map, determining the routes of the optimal cost.

Important sphere of researches is dynamic networks [2-4], that take into account transit times along the arcs and don’t assume instant flow distribution along the arcs. Another significant tool is considering dependence of arc capacities and lower flow bounds on flow departure time [5] and operating with fully dynamic networks instead of stationary-dynamic ones [6], using the notions of the time-expanded graphs [7-8].

Flow problems are connected with uncertainty of some kind, as changes in environment, measurement errors influence such network parameters, as arc flow bounds and vitality parameters. Therefore, we propose to consider these tasks in fuzzy conditions and we turn to the fuzzy graphs for solving such problems.

Vitality parameter [ 9-10 ] peculiar to arcs of the network usually isn’t taken into account while studying networks. Its conventional definition was introduced by the authors H. Frank and I. Frisch in [ 11 ] as sensitivity of the network to damages. However, vitality applied to the networks is ability of its objects and links among them to be resistant to weather conditions, traffic accidents and its combinations, and save and restore (fully or partially) objects themselves and their connections, arc capacities of the network’s sections in case of damage. Nowadays, vitality of the network isn’t taken into account, while railways and roads include the complex objects, such as stations, distillation ways, culverts, wagon, passenger and cargo managements. Sometimes network’s parameters can be set qualitatively. Thus, one can set the notion “vitality degree” considering the roads and railways. In this case “vitality degree” is considered as probability of trouble-free operation of the road section and some subjective value, such as importance and reliability, etc.

Other words this paper presents method of the maximum flow finding with nonzero lower flow bounds in fuzzy dynamic network with given vitality degree.

The paper is structured as follows. In the Section 2 we give basic definitions and rules. Section 3 presents the proposed method. Section 4 provides numerical example illustrating the main steps of the proposed method. Section 5 is conclusion and future work.

2 Definitions and Rules

The proposed approach is based on the following notion of vitality.

Fuzzy directed path P(xi , xm ) of the graph G  ( X , A) is a sequence of fuzzy directed arcs from the node xi to the node xm :

P(xi , x m )   A  xi , x j  /  xi , x j ,  A  xj , xk  /  xj , xk ,..., A  xl , xm  /  xl , xm  .

Conjunctive durability of the path  (P(xi , xm )) is defined as (P(xi ,xm )) 

& μ  x ,x  .

xα ,xβ P(xi ,xm ) A

Fuzzy directed path P(xi , xm ) is called a simple path between vertices xi and xm if its part is not a path between the same vertices.

Vertex y is called a fuzzy accessible from the vertex x in the graph G  (X , A) if the fuzzy directed path from the node x to the node y exists.

The accessible degree of the node y from the node x, (xy) is defined by the following expression: γ(x, y)  max( (Pα (x, y)), = 1,2,..., p,

α where p is the number of various simple directed paths from vertex x to vertex y.

We consider the degree of fuzzy graph vitality as a degree of strong connection [ 10, 11 ], so it will be defined by the following expression:

~ V (G)  & &  (xi , x j ).

xiX xjX

It means that there is a route between each pair of the graph vertices with a conjunctive strength not less than value V.

Let us introduce basic rules and definitions underlying this method. and arcs

Rule 1 of turning from the time-expanded fuzzy graph to the fuzzy graph without lower flow bounds [ 12 ]

Turn to the fuzzy graph G*p  ( X *p , A*p ) from Gp  ( X p , Ap ) . Introduce the artificial source s* and sink t* and arcs connecting the node-time pair (t,   T) (s,  T) with u* (t, s,  T ,  T )  , l * (t, s,  T ,  T )  0,  * (t, s, T , T )  1. in the graph Gp . For with l (xi , xj , , )  0 : 1) reduce u(xi , xj , , ) u* (xi , xj , , )  u(xi , xj , , )  l (xi , xj , , ) , l (xi , xj , , ) to  * (xi , xj , , )  (xi , xj , , ). 2) Introduce the arcs connecting s* with (xj , ) , and the arcs connecting t* with (xi , ) with u* (s*, xj ,, )  u*(xi ,t, , )  l (xi , xj , , ) to 0 , zero lower fuzzy flow

bounds  * (xi , xj , , )  (xi , xj , , ). l * (s*, xj ,, )  l * (xi ,t, ,)  0 , Definition 1 of the fuzzy residual network of the time-expanded graph.

Fuzzy residual network G*p  ( X *p , A*p ) is the network without lower flow bounds G*p  ( X *p , A*p ) , which is constructed according to the following rules: if v* (xi , x j , , )  vreq ,  * (xi , x j , , )  u* (xi , x j , , ),  If  * (xi , x j , , )  0,  v(xi , x j , , )  vreq . ,then include the corresponding arc from (xi* , ) to (x*j , ) in G* p with u* (xi , xj , , )  u* (xi , xj , , )  *(xi , xj , , ) and  * (xi , xj , , )  * (xi , xj , , ) .

Then include the corresponding arc from (x*j , ) to (xi* , ) in G* p with u* (xj , xi ,, )   *(xi , xj , , ) and  * (xj , xi ,, )   * (xi , xj , , ) .

Rule 2 of transition from the time-expanded fuzzy graph without lower flow bounds with the found maximum flow to the graph with the feasible flow

Turn to the graph Gp from the graph G*p as following: reject artificial nodes and arcs, connecting them with other nodes. The feasible flow vector   ( (xi , xj , , )) of the value  is defined as:  (xi , xj , , )   *(xi , xj , , )  l (xi , xj , , ) , where  * (xi , xj , , ) – the flows, going along the arcs of the graph G*p after deleting all artificial nodes and connecting arcs.

Rule 3 of the fuzzy residual network constructing with the feasible flow vector for all arcs, if  (xi , xj , , )  u(xi , xj , , ), then include the corresponding arc (xi , ) from the node-time pair to the node-time pair (xj , ) in Gp ( ) with arc capacity u (xi , xj , , )  u(xi , xj , , )  (xi , xj , , ) and transit time   (xi , xj , , )  (xi , xj , , ) . For all arcs, if  (xi , xj , , )  l (xi , xj , , ) , then include the corresponding arc, going from the node-time pair (xj , ) to the node-time pair (xi , ) in

Gp ( ) u (xj , xi ,, )   (xi , xj , , )  l (xi , xj , , )   (xj , xi ,, )   (xi , xj , , ) . with and arc transit capacity time

Therefore, the proposed method of the maximum flow finding with nonzero lower flow bounds in fuzzy dynamic network consists in the maximum flow finding in the network without lower flow bounds. We turn to the time-expanded fuzzy graph and consequently to the graph without lower flow bounds for it and try to find the maximum flow in the graph. Based on the formulated rules and definitions, turn to the maximum flow finding with nonzero lower flow bounds in dynamic network in terms of partial uncertainty. 3 Presented Method of the Maximum Flow Finding Task with Nonzero Lower Flow Bounds in the Fuzzy Dynamic Network

Let us introduce the task of the maximum flow finding with nonzero lower flow bounds in dynamic network in terms of partial uncertainty and given vitality degree, represented by the model (1)-(6).

Maximize  ( p) (1) p    ij ( )   0  xjГ (xi ) p    ij ( )   0  xjГ (xi ) p    ij ( )   0  xjГ (xi )

 xjГ1(xi )

 xjГ1(xi )

 xjГ1(xi )

  ji (  ji ( ))   ( p), xi  s,     ji (  ji ( ))   0, xi  s, t; T ,     ji (  ji ( ))    ( p), xi  t,   lij ( )  ij ( )  uij ( ),  ij ( )  p, T, vij ( )  vreq , s( )  st ( )  p, T. (2) (3) (4) (5) (6)

Step 1. Go to the time-expanded fuzzy static graph Gp from the given fuzzy dynamic graph G .

Step 2. Turn to the graph G*p  ( X *p , A*p ) according to the rule 1.

Step 3. Build a fuzzy residual network G*p due to the definition 1.

Step 4. Search the augmenting shortest path (in terms of the number of arcs) P* p from the artificial source s* to the artificial sink t* in the constructed fuzzy residual network according to the breadth-first-search.

4.1 Go to the step 5 if the augmenting path Pp* is found. 4.2 The flow value  * 

 l (xi , x j , , ) is obtained, which is the l (xj , xi , , )0 maximum flow in G*p , if the path is failed to find. Exit.

Step 5. Pass the minimum from the arc capacities  p*  min[u(Pp* )] , u(Pp* )  min[u* (xi , xj , , ) , (xi , ), (xj , )  Pp* along this path Pp* .

Step 6. Update the fuzzy flow values in the graph G*p : replace the fuzzy flow  * (xj , xi , , ) along the corresponding arcs going from (x*j , ) to (xi*, ) from G*p by  * (xj , xi , , )  p* for arcs connecting node-time pair (xi* , ) with (x*j , ) in G*p , such as ((xi* , ), (x*j , ))  A*p , ((xi* , ), (x*j , ))  A*p and replace the fuzzy flow  * (xi , xj , , ) along the arcs going from (xi*, ) to (x*j , ) from G*p by  * (xi , xj , , )  p* for arcs connecting node-time pair (xi* , ) with (x*j , ) in G*p , such as ((xi* , ), (x*j , ))  A*p , ((xi* , ), (x*j , ))  A*p .

Replace  * (xi , xj , , ) by  * (xi , xj , , )  p* Pp* .

Step 7. Compare flow value  * (xi , xj , , )  p* Pp* and 7.1. If the flow value  * (xi , xj , , )  p* Pp* is less than  l (xj , xi , , )0

 l (xj , xi , , )0 l (xi , x j , , ) : l (xi , x j , , ) , go to the step 3.

7.2. If the flow value  * (xi , xj , , )  p* Pp* is equal to (II) The maximum flow  (xi , xj , , )  p Pp  ( p) in Gp ( ) is found if the path is failed to find, then the maximum flow in “time-expanded” static fuzzy graph can be found at the step 12.

Step 10. Pass the flow value  p  min[u(Pp )] , u(Pp )  min[u (xi , xj , , ) , (xi , ), (xj , )  Pp along the found path.

Step 11. Update the flow values in the graph Gp ( ) .

Step 12. Turn to the initial dynamic graph G as follows: reject the artificial nodes s' , t ' and arcs, connecting them with other nods.

4 Numerical Example

Let us describe the proposed algorithm. For example, assume that the original fuzzy dynamic network is shown in Fig. 1. It is necessary to find the maximum flow in the initial dynamic graph with the given vitality degree no less than 0, 7 and represent the result in the form of the triangular number.

Fuzzy upper flow bounds uij , depending on the flow departure time  are shown in the Table I. Fuzzy lower flow bounds lij , depending on the flow departure time  are shown in the Table II. Time parameters  ij depending on the flow departure time  are shown in the Table III. Fuzzy vitality parameters vij , depending on the flow departure time  are shown in the Table IV.

x4 x1 x5

We obtain graph with the maximum flow in Fig. 4. Therefore, the task has a solution and we turn to the initial time-expanded graph with the feasible flow in Fig. flow units, x2 x3 5. Finding the augmenting paths and pushing the flows among them, we obtain graph with the maximum flow in Fig. 6.

The maximum flow in the initial graph with the vitality degree no less than 0, 7 is 25 10  35 flow units.

Let us define deviation borders of the obtained fuzzy number “near 35 ”.

Since the calculations with fuzzy numbers are cumbersome and result in strong blurring of the resulting number’s borders, we suggest to operate fuzzy numbers according to the method, described in [8]. In this case we will operate the central values of fuzzy numbers, blurring the result at the final step and presenting it as a triangular the number.

Therefore, deviation borders of the obtained fuzzy number “near 35 ” corresponded to the maximum flow in the graph G are calculated according to the basic values of arc capacities in Fig. 7.

The detected result is between two adjacent basic values of the arc capacities: 31 with the left deviation l1L  8 , right deviation – l1R  7 and 44 with the left deviation l2L  9 , right deviation – l2R  10 . We obtain deviations : l1L  8 , l1R  7 .

Therefore, the maximum flow in the fuzzy dynamic graph with the given vitality degree no less than 0, 7 can be represented by fuzzy triangular number (27, 35,42) units. Time periods

2 ,1

,1 x1

,1 [u(xi , x j , , ),l (xi , x j , , ), v( xi , x j , , ) xi x j [7], 0,8 ,1 [ 10 ], 0,8 3 x1 [25], 0, 6

x2 [35], 0, 7

x3 [30], 0, 6 x4 x5 [40],0,7

s* [7], 0,8 s e d o N Fig. 5. Graph Gp with the feasible flow xi Time periods 1 2

3 [ 10 ], 0,8x1 x1 x1 [7], 0, 7x2 [ 10 ], 0,8 x2 x2 xx43 [7],0,8 xx43 [ 10 ],0,7 xx43 x5 x5 x5 [ (xi , x j , , ), v(xi , x j , , )] x j x j 0 x1 x2 x4 x5 s e d o x3 N [25],0,8 x1 [ 10 ],0,7x2 [25],0,8 x2 1 x3 x5 x4 [ 10 ],0,8 2 x1 x3 x4 x5 [25],0,7 3 x1 x2 x3 x4 x5 [ (xi, xj, , ),v(xi, xj, ,)] xi xj

5 Conclusion and Future Work

Paper presents proposed algorithm of the maximum flow finding with nonzero lower flow bounds and vitality degrees in the fuzzy dynamic network with the required vitality degree based on the formulated definitions and rules. The considered network is represented as fuzzy graph with parameters, depending on the flow departure time and varying over time. Given lower flow bounds are used for assessing economic reliability of transportation. Given vitality degree reflects ability of its objects to be resistant to weather conditions, traffic accidents and save and restore objects themselves, arc capacities of the network’s sections in case of damage. The proposed method has important practical value in transportation implementing on the real types of roads. In the future works we will propose methods of increasing the vitality degree in fuzzy dynamic networks.

Acknowledgments. This work has been supported by the Russian Foundation for Basic Research, Project № 16-01-00090 a, and the Ministry of Education and Science of the Russian Federation under Project № 213.01-11/2014-48 (Base part, State task 2014/174)

References

Goldberg A. V. , Tardos E. , Tarjan R. E. ( 1990 ) Network Flow Algorithms . In: Korte B., Lovasz L. , Proemel H.J. , and Schrijver A . (eds) Paths, Flows and VLSI-Design. Springer Verlag, 1990 , pp. 101 - 164 .

Glockner G. D. Nemhauser G. L. , Tovey . C. A. ( 2001 ) Dynamic Network Flow with Uncertain Arc Capacities: Decomposition Algorithm and Computational Results . Comp.

Opt. and Appl , vol. 18 ( 3 ), pp. 233 - 250 .

Ciurea E. ( 1997 ) Two problems concerning dynamic flows in node and arc capacitated networks . Computer Science Journal of Moldova , vol. 5 , № 3 ( 15 ), pp. 298 - 308 .

Lovetskii S. , Melamed I. ( 1987 ) Dynamic flows in networks Automation and Remote Control , vol. 48 ( 11 ), pp. 1417 - 1434 ; Translated from Avtomatika i Telemekhanika ( 1987 ), vol. 11 , pp. 7 - 29 .

Fonoberova M. A. Lozovanu D. D. ( 2004 ) The maximum flow in dynamic networks .

Computer Science Journal of Moldova , vol. 12 , № 3 ( 36 ), pp. 387 - 396 .

Bozhenyuk A. , Gerasimenko E. , Rozenberg I. , Perfilieva I. ( 2015 ) Method for the minimum cost maximum flow determining in fuzzy dynamic network with nonzero flow bounds . In: Alonso José M. , Bustince H. , Reformat M .( eds) Proceedings of the 2015 Conference of the International Fuzzy Systems Association and the European Society for Fuzzy Logic and Technology , 30th June-3rd July , Gijón, Asturias (Spain) , vol. 89 , Atlantic Press , 2015 , pp. 385 - 392 .

Silver M. R ., de Weck O. L. ( 2007 ) Time-expanded decision networks: A framework for designing evolvable complex systems . Systems Engineering , vol. 10 , no. 2 , pp. 167 - 188 .

Bozhenyuk А. , Gerasimenko E. , Rozenberg I. ( 2012 ) The methods of maximum flow and minimum cost flow finding in fuzzy network . In: Kuznetsov S. O. Ignatov D.I. , Poelmans . J. Proceedings of the Concept Discovery in Unstructured Data (CDUD 2012 ) : workshop co-located with the 10th International Conference on Formal Concept Analysis (ICFCA 2012 ), May 2012 , Leuven, Belgium, pp. 1 - 12 .

Bozhenyuk A. , Rozenberg I. , Starostina T. ( 2006 ) A method of increase of vitality degree of fuzzy graph . In: Proceedings of 13th Zittau Fuzzy Colloquium, September 13 -15.

Zittau : Hochschule Zittau/Goerlitz, pp. 235 - 240 .

10. Bozheniuk V. , Bozhenyuk A. , Belyakov S. ( 2015 ) Optimum allocation of centers in fuzzy transportation networks with the largest vitality degree . In: Proceedings of the 2015 Conference of the International Fuzzy System Association and the European Society for Fuzzy Logic and Technology: Atlantis Press , pp. 1006 - 1011 .

11. Frank H. , Frisch I. T ( 1971 ) Communication, Transmission, and Transportation Networks . Addison Wesley , Reading, Mass.

12. Bozhenyuk A. , Gerasimenko E. ( 2014 ) Flows finding in networks in fuzzy conditions . In Kahraman Cengiz and Öztaysi Basar( eds). Supply Chain Management Under Fuzzines, Studies in Fuzziness and Soft Computing , vol. 313 , part III ,. Berlin, Heidelberg: SpringerVerlag, pp. 269 - 291 .