Fuzzy Strategy for Flow Problems
Real situations allow to establish that flow capacities as well as flows themselves have a fuzzy character. An analysis of formed risk can concern underestimation and re-evaluation of capacity or real flow importance. The strategy of flow paths sequence determination is worked out under fuzzy parame...
Saved in:
| Published in: | Электронное моделирование |
|---|---|
| Date: | 2007 |
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2007
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/101785 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Fuzzy Strategy for Flow Problems / A. Ptak, M. Machura, U.Gornik // Электронное моделирование. — 2007. — Т. 29, № 4. — С. 61-67. — Бібліогр.: 8 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859618773671084032 |
|---|---|
| author | Ptak, A. Machura, M. Gornik, U. |
| author_facet | Ptak, A. Machura, M. Gornik, U. |
| citation_txt | Fuzzy Strategy for Flow Problems / A. Ptak, M. Machura, U.Gornik // Электронное моделирование. — 2007. — Т. 29, № 4. — С. 61-67. — Бібліогр.: 8 назв. — англ. |
| collection | DSpace DC |
| container_title | Электронное моделирование |
| description | Real situations allow to establish that flow capacities as well as flows themselves have a fuzzy character. An analysis of formed risk can concern underestimation and re-evaluation of capacity or real flow importance. The strategy of flow paths sequence determination is worked out under fuzzy parameter conditions.
В реальных ситуациях емкости потоков, как и сами потоки, имеют нечеткий характер. Дан анализ рисков недооценки или переоценки емкости или реального значения потока. Выработана стратегия определения последовательности пути потока в условиях нечетких параметров.
У реальних ситуаціях ємність потоків, як і самі потоки, мають нечіткий характер. Дано аналіз ризиків недооцінки чи переоцінки ємності чи реального значення потоку. Вироблено стратегію визначення послідовності шляху потоку в умовах нечітких параметрів.
|
| first_indexed | 2025-11-28T23:58:48Z |
| format | Article |
| fulltext |
A. Ptak*, M. Machura**, U. Gornik***
* Institute of Ewromethis and Computer Science
** Institute of Mathematics and Computer Science,
*** Czestochowa University of Technology
(E-mail:olaptak@zim.pcz.pl)
Fuzzy Strategy for Flow Problems
Real situations allow to establish that flow capacities as well as flows themselves have a fuzzy
character. An analysis of formed risk can concern underestimation and re-evaluation of capacity
or real flow importance. The strategy of flow paths sequence determination is worked out under
fuzzy parameter conditions.
 ðåàëüíûõ ñèòóàöèÿõ åìêîñòè ïîòîêîâ, êàê è ñàìè ïîòîêè, èìåþò íå÷åòêèé õàðàêòåð. Äàí
àíàëèç ðèñêîâ íåäîîöåíêè èëè ïåðåîöåíêè åìêîñòè èëè ðåàëüíîãî çíà÷åíèÿ ïîòîêà.
Âûðàáîòàíà ñòðàòåãèÿ îïðåäåëåíèÿ ïîñëåäîâàòåëüíîñòè ïóòè ïîòîêà â óñëîâèÿõ íå÷åòêèõ
ïàðàìåòðîâ.
K e y w o r d s: maximal flow, fuzzy sets.
Structures and characteristics of flow paths. The flow network has a set num-
ber of nodes and edges (nv, ne). It is possible to create a set of paths with usage of
an algorithm, an example is presented in Fig. 1 [1—3].
The presented algorithm is based on information concerning the flow net-
work shown, for example, in form of the flow capacity matrix a[i, j] [3, 4]. The
source s and the sink t are also defined. The first two nested loops allow the se-
lection of nodes neighboring at currently analyzed reference point. If that point
(node?) is the sink t, then one goes towards the successive flow path (label cd). In
the node where the path forks, each new direction is continuation of a new path.
This is expressed by the counter k. Real connection is verified when the weight
(flow capacity) of a given edge is checked: whether it is different from «�» (lack
of connection), «0» (full use of flow capacity through the realization of flows),
«–» (the same node; edge length is zero). When above mentioned conditions are
fulfilled, then a successive edge is added to currently created flow path (with the
number i + k – 1). The matrix of weights presenting the flow capacities of suc-
cessive edges of every path (w) is also created. If the added node is the sink, then
the path is finished (record of path). Each fork increases the number of the path
by k – 1, where, in this case, k denotes the number of edges going out of the cur-
rent node. The number of successive edges (p) is the same for all paths. It is real-
ized in the external loop at the change of path number (i). The algorithm perfor-
mance can be traced on the example shown in Fig. 2.
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 4 61
A. Ptak, M. Machura, U. Gornik
62 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 4
s � start node (source)
e� end node (sink)
nsc � number of created path
sc i j[ , ] �j-th node of i-th path
p� current node of path
k � auxiliary number of path
i� numbering of paths
j� numbering of nodes
Path record
Node adding
Check of added node
Create path
s t,
nsc = p k sc nsc p s1; = 0; = 0, ( , ) =
nsc = nsc + k
p p
� 1
= +1
sc i+k p = j w i+k p a sc i p j( 1, +1) ; ( 1, +1) = ( ( , ), )� �
a sc i p j( ( , ), ) � ���� �« »
i = l nsc(1)
v = l p(1) + 1
j = l n(1)
j = t
sc i p t( , ) �
cd
N T
T
TN
N
cd
sc i+k v[ 1, ]�
k k= +1
Path creation algorithm
A
Fig.1. Algorithm of creation of flow paths
w (i, j) 1 2 3 4 5 6 7 8
1 5 2 8
2 6 9 4
3 6
4 8 11 12
5 10 9
6 7 8
7 7
8
N o t e. Number (where) i — row vector number (where from); j — column
Table 1. Weight matrix of network connections
The method of selection of successive paths for flow realization decides on
the approach to the optimal solution. It is possible to start from the longest paths
or from paths with the largest (or smallest) flow capacity [5, 6].
Path selection heuristics for realization of flows. Selection of paths with
the minimal flow capacity does not always allow the determination of total net-
work saturation [2, 7]. The sum of small flows can stop larger flows. For the ex-
ample in Fig. 2, data concerning characteristics can be presented in the following
way (Tables 1—3).One can classify the following characteristics:
l (i) is a path length (number of edges),where i is a path number;
p (i) is a path flow capacity;
dispersion of flow capacity values (variance or standard deviation) for net-
work is rs, for each path is r (i) and each layer is wr (j), where j is a layer number;
d (i) is a edge location (layer number) with the smallest flow capacity in a
given path;
k (j) is a number of nodes in every layer (location distribution of edges in
network).
Having a set of data, one can construct criteria set, which permits testing
network saturation. Examples of such sets include paths selection criteria for
successive flows realization until the moment of losing connection between the
source and the sink [8]. Possible path selection mechanisms are:
Fuzzy strategy for flow problems
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 4 63
2
4
a
b
1
6
5
3
7
1
1
1
1
1
1
1
1
1
1
1
1
1
2
3
4
2
2
4
3
2
4
2
2
2
4
6
5
3
5
6
8
5
5
3
3
6
3
7
8
7
5
7
4
8
8
5
5
4 8
8
8
7 8
8
8
7 8
7 85
8
8
Fig. 2. Example of the algorithm performance: a — net-
work graph; b — creating paths
a) maximal path length; minimal flow capacity; maximal flow capacity dis-
persion; minimal edge weight in neighborhood of layer with the smallest flow
capacity dispersion;
b) maximal flow capacity; minimal flow capacity dispersion; minimal path
length; maximal distance with minimal weight from the source and the sink;
c) minimal flow capacity; minimal weight in maximal fork; maximal disper-
sion in layer with minimal weight; minimal weight out of the source and the sink;
A. Ptak, M. Machura, U. Gornik
64 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 4
Layer number 1 2 3
wr(j) 4,96 6,8 3,5
Table 3. Layers characteristic
Fig. 3. Influence of criteria (1, 2, 3 and 4) on rank characteristic of paths (1, ..., 6)
Path
namber
Node number
l (i) p (i) r (i) d (i)
1 2 3 4 5
1 5 4 8 3 4 2,86 2
2 2 6 10 7 4 2 8,19 1
3 8 8 6 10 7 5 6 1,76 3
4 5 9 10 7 4 5 3,69 1
5 5 6 6 10 7 5 5 2,96 1
6 8 11 7 3 7 2,89 3
7 8 12 2 8 4,00 1
8 5 4 7 11 7 5 4 5,76 2
9 2 6 9 3 2 8,22 1
10 5 9 9 3 5 3,56 1
11 8 8 6 9 4 6 1,19 3
12 5 6 6 9 4 5 2,25 1
Table 2. Paths characteristic
d) minimal path length; maximal flow capacity; maximal flow capacity dis-
persion; minimal weight in layer with maximal flow capacity dispersion.
The terms «maximal» and «minimal» in criteria sets were used for simplifi-
cation, pointing only at the tendency of paths ordering. Furthermore, each crite-
rion is connected with a specific weight wk (z, i), where z is a criteria set code; i is
a criterion successive number. The following expression defines the final char-
acteristic of the analyzed path:
EV z p x i wk z i
i
np
( , ) ( ) ( , )�
�
�
1
,
where i is a path number; np is a criteria number in set z; x (i) is a path location num-
ber in order, according to selected (i-th) criterion, set of paths. The criteria weights in
selected successive sets are decreasing: wk (z, 1) > wk (z, 2) > ... > wk (z, np).
The influence of individual criterion on the final estimation of path useful-
ness for the flow realization is diversified (Fig. 3). The paths in 6-1-3-5-2-4 or-
der were selected for the flow realization.
Thus, the selection of concrete heuristic for network saturation test [8] co-
mes down to the selection of the criteria set, which depends on network charac-
teristics (paths and layers).
Influence of fuzziness of flow capacity parameters on results of paths
scheduling. Fuzziness of flow capacity influences paths selection sequence for
Fuzzy strategy for flow problems
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 4 65
Fig. 4. Influence of flow capacity fuzziness on path characteristic according to selected criteria
set (a) and on selection sequence of paths (b) (with reference to situation shown in Fig. 3)
the realization of flows [1]. Fig. 4 presents an example of influence of fuzziness
on paths selection sequence.
After selecting a path, one can realize the flow operation subtracting the
path flow capacity from the current flow capacity value of all the edges:
p(j)
(i) = p(j)
(i) – p i( )
�
,
where j — edge number; i — path number; (+
, –
) — flow fuzziness parame-
ters [5]. Flow realization along the path is shown in Fig. 5.
Conclusions. To estimate the scale of fuzziness influence on the network
saturation level, it is necessary to analyze all permutations of lower and upper
flows limitations for every edge of all paths making additions with lower and up-
per flow capacity limitations.
The number of path permutations is in the pessimistic variant (for every set
of paths one realizes as many flows — from the source to the sink — as paths)
equals nsc!
The number of variations of edges, taking into consideration lower and up-
per flow capacity of each of them, equals 2
nkr s( )
; where nkr (s) — number of
edges of s-th path.
Fuzziness of flow conditions through the selected path dictates allowance
for lower and upper flow limit.
Optimization of network saturation requires analyzing 2 2
1
nsc nkr s
s
nsc
!
( )
�
� data
sets.
Ó ðåàëüíèõ ñèòóàö³ÿõ ºìí³ñòü ïîòîê³â, ÿê ³ ñàì³ ïîòîêè, ìàþòü íå÷³òêèé õàðàêòåð. Äàíî
àíàë³ç ðèçèê³â íåäîîö³íêè ÷è ïåðåîö³íêè ºìíîñò³ ÷è ðåàëüíîãî çíà÷åííÿ ïîòîêó. Âèðîá-
ëåíî ñòðàòåã³þ âèçíà÷åííÿ ïîñë³äîâíîñò³ øëÿõó ïîòîêó â óìîâàõ íå÷³òêèõ ïàðàìåòð³â.
A. Ptak, M. Machura, U. Gornik
66 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 4
Real flow
Fuzzy flow (use of flow
capacity)
Residual flow capacity
�
�
�
1 edge 2 edge 3 edge 4 edge
Fig. 5. Correction of network segments flow capacity at fuzzy flow realization
1. Baldwin J.F., Martin T.P. Fuzzy Modelling in an Intelligent Data Browser//Proc. Int. Conf.,
FUZZ-IEEE/IFES’95. Yokohama, Japan. — 1995. — Vol.4. — P.1885—1895.
2. Dempster A.P. Upper and lower probabilities induced by a multi-valued mapping//Ann.
Math. Stat.— 1967.— Vol. 38. — P. 325—339.
3. Karg R.L., Thompson G.L. A heuristic approach to solving traveling salesman problems//
Management Science. — 1964. — Vol.10, No 2. — P. 225—248.
4. Yager R.R. Non-numeric multi-criteria multi-person decision making//Group Decision and
Negotiation. — 1993. — 2. — P. 81—93.
5. Abel D. Fuzzy control — eine Einfuhrung ins Unscharfe//Automatisierungstechnik. —
1991. — Vol. 3. — P. 433—438 (in German).
6. Yager R.R. Modeling uncertainty using partial information//Information Sciences.—
1999.— 121. — P. 271—294.
7. Mizumoto, Masahary, Tanaka Kokichi. Fuzzy sets and their operations//Inf . and Contr. —
Vol. 48, No 1. — P. 30—48.
8. Aracil J., Garcia-Cerezo A., Ollero A. Fuzzy control of dynamical systems// Stability analysis
based on the conicity criterion. — Proc. 4-th Itern. Fuzzy Systems Association Congress. —
Brussels. — P. 5—8.
Ïîñòóïèëà 12.03.07
Fuzzy strategy for flow problems
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 4 67
|
| id | nasplib_isofts_kiev_ua-123456789-101785 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | English |
| last_indexed | 2025-11-28T23:58:48Z |
| publishDate | 2007 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Ptak, A. Machura, M. Gornik, U. 2016-06-07T09:06:34Z 2016-06-07T09:06:34Z 2007 Fuzzy Strategy for Flow Problems / A. Ptak, M. Machura, U.Gornik // Электронное моделирование. — 2007. — Т. 29, № 4. — С. 61-67. — Бібліогр.: 8 назв. — англ. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/101785 Real situations allow to establish that flow capacities as well as flows themselves have a fuzzy character. An analysis of formed risk can concern underestimation and re-evaluation of capacity or real flow importance. The strategy of flow paths sequence determination is worked out under fuzzy parameter conditions. В реальных ситуациях емкости потоков, как и сами потоки, имеют нечеткий характер. Дан анализ рисков недооценки или переоценки емкости или реального значения потока. Выработана стратегия определения последовательности пути потока в условиях нечетких параметров. У реальних ситуаціях ємність потоків, як і самі потоки, мають нечіткий характер. Дано аналіз ризиків недооцінки чи переоцінки ємності чи реального значення потоку. Вироблено стратегію визначення послідовності шляху потоку в умовах нечітких параметрів. en Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Fuzzy Strategy for Flow Problems Нечеткие стратегии в проблеме управления потоками Article published earlier |
| spellingShingle | Fuzzy Strategy for Flow Problems Ptak, A. Machura, M. Gornik, U. |
| title | Fuzzy Strategy for Flow Problems |
| title_alt | Нечеткие стратегии в проблеме управления потоками |
| title_full | Fuzzy Strategy for Flow Problems |
| title_fullStr | Fuzzy Strategy for Flow Problems |
| title_full_unstemmed | Fuzzy Strategy for Flow Problems |
| title_short | Fuzzy Strategy for Flow Problems |
| title_sort | fuzzy strategy for flow problems |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/101785 |
| work_keys_str_mv | AT ptaka fuzzystrategyforflowproblems AT machuram fuzzystrategyforflowproblems AT gorniku fuzzystrategyforflowproblems AT ptaka nečetkiestrategiivproblemeupravleniâpotokami AT machuram nečetkiestrategiivproblemeupravleniâpotokami AT gorniku nečetkiestrategiivproblemeupravleniâpotokami |