=Paper=
{{Paper
|id=Vol-1687/project4
|storemode=property
|title=Motion Control in the Mechanical Transport System with Fuzzy Given
Distance and Time
|pdfUrl=https://ceur-ws.org/Vol-1687/proposal4.pdf
|volume=Vol-1687
|authors=Marina Savelyeva,Marina Belyakova
|dblpUrl=https://dblp.org/rec/conf/cla/SavelyevaB16
}}
==Motion Control in the Mechanical Transport System with Fuzzy Given
Distance and Time==
https://ceur-ws.org/Vol-1687/proposal4.pdf
Motion Control in Mechanical Transport Systems with
Fuzzy Given Distance and Time
Marina Savelyeva1, Marina Belyakova1
1
Southern Federal University, Taganrog, Russia
marina.n.savelyeva@gmail.com,beliacov@yandex.ru
Abstract. We investigate traffic management in the mechanical transport
system. A major factor in the management of the MTS is search of the optimal
route. Therefore, this article is described the routing in the MTS taking into
account the inaccuracies and uncertainties of transportation options. We have
developed a routing algorithm that takes into account the temporal fuzzy nature
of the variables. We have illustrated the example of the developed routing
algorithm.
Keywords. Routing algorithm, mechanical transport systems, fuzzy temporal
graph
1. Introduction
Mechanical transport system (MTS) is a class of transport systems using conveyors
for moving cargo [1]. Conveyors form a network, where nodes are switches direction.
The switch is a mechanical device that directs the load unit from one conveyor output
to one input of the adjacent conveyors [2]. Example of such systems is the MTS
delivery of luggage at airports. The total number of conveyors and switches in these
systems can be quite large, which suggests several options for each cargo transport
unit. The main element in the management of MTS is a routing, which enables us to
construct the optimal path taking into account various parameters.
2. Formulation of the problem
We have following problem taking into account the changing reality and inaccuracies
of incoming information. It is necessary to build a set of optimal routes for each of the
MTS units. Information about received routes is stored in each node of MTS. And for
determination of optimal route is used as a time parameter, and the parameter range.
These parameters are presented in fuzzy form. The initial data are given on the MTS
by expert to analyze the system.
𝐿∗ = min min{ 𝑤 𝑡 < 𝑠! , 𝑥! > , 𝑤 𝑡 < 𝑥! , 𝑥! > , 𝑤 𝑡 < 𝑥! , 𝑟! > } (1)
! ! !
102 Marina Savelyeva and Marina Belyakova
3. Routing Algorithm in MTS under fuzzy given distance and
time
There are various ways to implement the routing of mechanical transport systems
taking into account only the distance parameter, such as Ford's algorithm, Floyd’
algorithm and etc [3]. We consider the algorithm that contains both parameters. The
parameters are presented in fuzzy form. For the decision of problem, it is advisable to
use the apparatus of the theory of graphs, namely based on fuzzy temporal graph.
Fuzzy temporal graph is a triple 𝐺 = (𝑋, 𝑈! , 𝑇), where X is set of vertices of the
number of vertices c 𝑋 = n, T = {1,2, … , N}is the set of natural numbers,
determining (discrete) time; 𝑈! = {< 𝜇! (𝑥! , 𝑥! )| 𝑥! , 𝑥! >} is fuzzy set of edges,
where 𝑥! , 𝑥! ∈ 𝑋, 𝜇! 𝑥! , 𝑥! ∈ [0,1] is the value of the membership function 𝜇! for the
edge 𝑥! , 𝑥! at time 𝑡 ∈ 𝑇, and at different times for the same edge 𝑥! , 𝑥! values of
the membership function (in general) different. Vertex 𝑥! is fuzzy adjacent vertex 𝑥!
on the moment of time 𝑡 ∈ 𝑇, if the condition 𝜇! 𝑥! , 𝑥! > 0 [4].
Step 1. To form the matrix D! (dimension N×N, where N is number of vertices in
the graph). Each element i, j of the matrix d!!" (𝑡) determines the length of the shortest
arc leading from vertex i to vertex j. In the absence of such an arc put in d!!" (𝑡) = ∞.
Step 2. Here 𝐷 ! denotes the dimension of the matrix 𝑚×𝑚 with d! !" (𝑡), 𝑚 =
1, 𝑚 − 1. To determine successively the elements of the matrix 𝐷 ! from elements of
the matrix of 𝐷 !!! for 𝑚, taking values 1, 2, … , 𝑁:
! ! !!!
𝑑!" 𝑡 = min 𝑑!" 𝑡 + 𝑑!" 𝑡 𝑗 = 1, 𝑚 − 1 (2)
!!!,!!!
! !!! !
𝑑!" 𝑡 = min 𝑑!" 𝑡 + 𝑑!" 𝑡 𝑖 = 1, 𝑚 − 1 (3)
!!!,!!!
! ! ! !!!
𝑑!" 𝑡 = min 𝑑!" 𝑡 + 𝑑!" 𝑡 , 𝑑!" 𝑡 𝑖, 𝑗 = 1, 𝑚 − 1 (4)
Moreover, for all 𝑖 and put 𝑚
𝑑!!! 𝑡 = 0 (5)
As a result of the algorithm in the beginning is searched for the minimum
distance, and then made to minimize the time.
Step 3. After the algorithm to produce defuzzification [5].
4. Example of illustration the routing algorithm in MTS with
fuzzy given parameters and temporal dependence
You need to find the shortest routes to all nodes. Data are presented in fuzzy form. In
round brackets is the distance, in square brackets indicates the time. Figure 1 shows
example of MTS.
Marina Savelyeva and Marina Belyakova 103
The initial matrix of distance and time as follows (equation (6)):
1 2 3
1 0,0,0 0,0,0 3,4,6 1,3,5 4,5,6 [2,3,4]
2 − 0,0,0 0,0,0 −
𝐷! 𝑡 = 3 − − 0,0,0 [0,0,0]
4 2,4,5 3,4,5 − −
5 − 2,5,7 3,5,6 −
6 − − −
4 5 6 (6)
1 − − −
2 − 2,5,7 3,5,6 −
3 − − 5,6,7 2,3,5
4 0,0,0 [0,0,0] − −
5 − 0,0,0 [0,0,0] 4,6,8 2,3,4
6 3,4,7 1,3,4 4,6,8 2,3,4 0,0,0 [0,0,0]
2 (2,5,7)[(3,5,6)] 5
(6
(3,4,6)[(1,3,5)]
,8
,1
2)
[( 4
,6
,8
)]
(4,6,8)[(2,3,4)]
1 (2,4,5)[(3,4,5)] 4
(4,5,6)[(2,3,4)]
(3
,4
,7
)[(
1,
3,
4)
]
3 (5,6,7)[(2,3,5)] 6
Fig. 1 – Illustration example of MTS scheme
Using the formula (5) of the algorithm we get equation (7).
!
𝑑!! 𝑡 =0 (7)
So we get the matrix 𝐷! 𝑡 below
1
𝐷! 𝑡 = (8)
1 0,0,0 0,0,0
104 Marina Savelyeva and Marina Belyakova
Then the next phase for the elements use the formula (2) at the beginning, we
obtain
! ! !
𝑑!" 𝑡 = min{𝑑!" 𝑡 + 𝑑!! 𝑡 } = min ∞ + 0,0,0 0,0,0 =∞ (9)
!
Consequently, instead of element 𝑑!" 𝑡 in the matrix 𝐷 ! 𝑡 we have element “–“.
The next step we use the formula (3):
! ! !
𝑑!" 𝑡 = min{𝑑!! 𝑡 + 𝑑!" 𝑡 } = min 0,0,0 0,0,0 + 3,4,6 [1,3,5]
= 3,4,6 [1,3,5](𝑟𝑜𝑢𝑡𝑒 𝑓𝑟𝑜𝑚 1 𝑡𝑜 2) (10)
Then we use formula (5)
! !
𝑑!! (𝑡) = 0, 𝑑!! (𝑡) = 0 (11)
Fill matrix 𝐷 ! 𝑡
1 2
𝐷! 𝑡 = 1 0,0,0 0,0,0 3,4,6 1,3,5 (12)
2 − 0,0,0 0,0,0
We turn to the calculation of the matrix 𝐷 ! 𝑡 . Similarly, the use early in the
formula (2):
! ! ! ! !
𝑑!" 𝑡 = min{𝑑!" 𝑡 + 𝑑!! 𝑡 ; 𝑑!" 𝑡 + 𝑑!" 𝑡 }
= min ∞ + 0,0,0 0,0,0 ; ∞ + ∞ = ∞ (13)
! ! ! ! !
𝑑!" 𝑡 = min{𝑑!" 𝑡 + 𝑑!" 𝑡 ; 𝑑!" 𝑡 + 𝑑!! 𝑡 }
= min ∞ + 3,4,6 [1,3,5]; ∞ + 0,0,0 0,0,0 =∞ (14)
Using equation (3) we obtain the following values of the elements of the matrix:
! ! ! ! !
𝑑!" 𝑡 = min{𝑑!! 𝑡 + 𝑑!" 𝑡 ; 𝑑!" 𝑡 + 𝑑!" 𝑡 }
= min 0,0,0 0,0,0 + ∞; 3,4,6 1,3,5 + ∞ = ∞ (15)
! ! ! ! !
𝑑!" 𝑡 = min{𝑑!" 𝑡 + 𝑑!" 𝑡 ; 𝑑!! 𝑡 + 𝑑!" 𝑡 }
= min ∞ + ∞; 0,0,0 0,0,0 + ∞ = ∞ (16)
We recalculate values of the matrix by the formula (4) with the new values
obtained in the previous step.
Marina Savelyeva and Marina Belyakova 105
! ! ! !
𝑑!" 𝑡 = min{𝑑!" 𝑡 ; 𝑑!" 𝑡 + 𝑑!" 𝑡 } = min 3,4,6 [1,3,5]; ∞ + ∞
= 3,4,6 [1,3,5](𝑟𝑜𝑢𝑡𝑒 1,2 ) (17)
! ! ! !
𝑑!" 𝑡 = min{𝑑!" 𝑡 ; 𝑑!" 𝑡 + 𝑑!" 𝑡 } = min ∞; ∞ + ∞ = ∞ (18)
For further calculation of matrix elements we use the formula (5):
! ! !
𝑑!! 𝑡 = 0, 𝑑!! 𝑡 = 0, 𝑑!! (𝑡) = 0 (19)
Fill the matrix 𝐷 ! 𝑡
1 2 3
1 0,0,0 0,0,0 3,4,6 1,3,5 4,5,6 [2,3,4]
𝐷! 𝑡 = (20)
2 − 0,0,0 0,0,0 −
3 − − 0,0,0 [0,0,0]
We repeat similar iterations for the calculation of the matrix 𝐷 ! 𝑡 . Similarly, we
use early in the formula (2):
! ! ! ! ! ! !
𝑑!" 𝑡 = min{𝑑!" 𝑡 + 𝑑!! 𝑡 ; 𝑑!" 𝑡 + 𝑑!" 𝑡 ; 𝑑!" 𝑡 + 𝑑!" 𝑡 }
= min 2,4,5 3,4,5 + 0,0,0 0,0,0 ; ∞ + ∞; ∞ + ∞ (21)
= 2,4,5 3,4,5 (𝑟𝑜𝑢𝑡𝑒 4,1 )
! ! ! ! ! ! !
𝑑!" 𝑡 = min{𝑑!" 𝑡 + 𝑑!" 𝑡 ; 𝑑!" 𝑡 + 𝑑!! 𝑡 ; 𝑑!" 𝑡 + 𝑑!" 𝑡 }
= min 2,4,5 3,4,5 + 3,4,6 [1,3,5]; ∞
+ 0,0,0 [0,0,0]; ∞ + ∞ (22)
= 5,8,11 [4,7,10](𝑟𝑜𝑢𝑡𝑒 4,1 → (1,2))
! ! ! ! ! ! !
𝑑!" 𝑡 = min{𝑑!" 𝑡 + 𝑑!" 𝑡 ; 𝑑!" 𝑡 + 𝑑!" 𝑡 ; 𝑑!" 𝑡 + 𝑑!! 𝑡 }
= min 2,4,5 3,4,5 + 4,5,6 [2,3,4]; ∞ + ∞; ∞
+ 0,0,0 0,0,0 = 6,9,11 [5,7,9](𝑟𝑜𝑢𝑡𝑒 4,1 (23)
→ (1,3))
Using equation (3), we obtain the following values of the elements of the matrix:
106 Marina Savelyeva and Marina Belyakova
! ! ! ! ! ! !
𝑑!" 𝑡 = min{𝑑!! 𝑡 + 𝑑!" 𝑡 ; 𝑑!" 𝑡 + 𝑑!" 𝑡 ; 𝑑!" 𝑡 + 𝑑!" 𝑡 }
= min 0,0,0 0,0,0 + ∞; 3,4,6 1,3,5 + ∞; ∞ + ∞
(24)
=∞
! ! ! ! ! ! !
𝑑!" 𝑡 = min{𝑑!" 𝑡 + 𝑑!" 𝑡 ; 𝑑!! 𝑡 + 𝑑!" 𝑡 ; 𝑑!" 𝑡 + 𝑑!" 𝑡 }
= min ∞ + ∞; 0,0,0 0,0,0 + ∞; ∞ + ∞ = ∞ (25)
! ! ! ! ! ! !
𝑑!" 𝑡 = min{𝑑!" 𝑡 + 𝑑!" 𝑡 ; 𝑑!" 𝑡 + 𝑑!" 𝑡 ; 𝑑!! 𝑡 + 𝑑!" 𝑡 }
= min ∞ + ∞; ∞ + ∞; 0,0,0 0,0,0 + ∞ = ∞ (26)
We recalculate values of the matrix by the formula (4) with the new values
obtained in the previous step.
! ! ! !
𝑑!" 𝑡 = min{𝑑!" 𝑡 ; 𝑑!" 𝑡 + 𝑑!" 𝑡 }
= min 3,4,6 [1,3,5]; ∞ + 5,8,11 [4,7,10]
(27)
= 3,4,6 [1,3,5](𝑟𝑜𝑢𝑡𝑒 1,2 )
! ! ! !
𝑑!" 𝑡 = min{𝑑!" 𝑡 ; 𝑑!" 𝑡 + 𝑑!" 𝑡 }
= min 4,5,6 2,3,4 ; ∞ + 6,9,11 5,7,9
(28)
= 4,5,6 [2,3,4](𝑟𝑜𝑢𝑡𝑒 1,3 )
! ! ! !
𝑑!" 𝑡 = min{𝑑!" 𝑡 ; 𝑑!" 𝑡 + 𝑑!" 𝑡 } = min ∞; ∞ + 2,4,5 3,4,5
=∞ (29)
! ! ! !
𝑑!" 𝑡 = min{𝑑!" 𝑡 ; 𝑑!" 𝑡 + 𝑑!" 𝑡 } = min ∞; ∞ + 6,9,11 [5,7,9]
=∞ (30)
For further calculation of matrix elements we use the formula (5):
! ! ! ! (31)
𝑑!! 𝑡 = 0, 𝑑!! 𝑡 = 0, 𝑑!! (𝑡) = 0, 𝑑!! (𝑡) = 0
Fill the matrix 𝐷 ! 𝑡
Marina Savelyeva and Marina Belyakova 107
1 2 3 4
1 0,0,0 0,0,0 3,4,6 1,3,5 4,5,6 [2,3,4] −
𝐷! 𝑡 = 2 − 0,0,0 0,0,0 − − (32)
3 − − 0,0,0 [0,0,0] −
4 2,4,5 3,4,5 5,8,11 4,7,10 6,9,11 [5,7,9] 0,0,0 [0,0,0]
As a result, similar calculations obtain intermediate matrix of routes 𝐷 ! 𝑡 .
1 2
1 0,0,0 0,0,0 3,4,6 1,3,5
! 2 − 0,0,0 0,0,0
𝐷 𝑡 =
3 − −
4 2,4,5 3,4,5 5,8,11 4,7,10
5 − 2,5,7 3,5,6
(33)
3 4 5
1 4,5,6 2,3,4 − 5,9,13 4,8,11
2 − − 2,5,7 3,5,6
3 0,0,0 0,0,0 − −
4 6,9,11 5,7,9 0,0,0 0,0,0 7,13,18 7,12,16
5 − − 0,0,0 0,0,0
Using the 𝐷 ! 𝑡 intermediate matrix performs calculations and obtain the resulting
matrix routes.
𝐷! 𝑡
1 2 3
1 0,0,0 0,0,0 3,4,6 1,3,5 4,5,6 [2,3,4]
2 11,19,27 [9,15,19] 0,0,0 0,0,0 15,24,33 [11,18,23]
= 3 10,14,19 [6,10,14] 11,17,22 [7,11,15] 0,0,0 [0,0,0]
4 2,4,5 3,4,5 5,8,11 4,7,10 6,9,11 [5,7,9]
5 9,11,20 [6,10,13] 2,5,7 3,5,6 13,19,26 [8,13,17]
6 5,8,12 [4,7,9] 6,11,15 [5,8,10] 19,13,18 [6,10,13]
(34)
4 5 6
1 12,15,20 [5,9,13] 5,9,13 [4,8,11] 9,11,13 [4,6,9]
2 9,15,22 [6,11,14] 2,5,7 [3,5,6] (6,11,15)]6,8,10]
3 8,10,14 [3,6,9] 9,12,15 [4,6,9] 5,6,7 [2,3,5]
4 0,0,0 0,0,0 7,13,18 [7,12,16] 11,15,18 [7,10,14]
5 7,10,15 [3,6,8] 0,0,0 [0,0,0] 4,6,8 [2,3,4]
6 3,4,7 [6,10,13] 4,6,8 [2,3,4] 0,0,0 [0,0,0]
5. Conclusion
108 Marina Savelyeva and Marina Belyakova
The specific management tool of MTS is routing. The proposed routing algorithm is
applicable to any mechanical transport system. The use of the described routing
method gives the best effect for MTS, which are operated in the unstable conditions
for major changes of cargo flow intensity. This case of temporal dependence reflects
the real environmental situation and its cost.
Acknowledgments. This work has been supported by the Russian Foundation for
Basic Research, Project № 14-01-00032.
References
1. Black G. Intelligent Distributed execution and cyber-physical design of Baggage
Handling automation with IEC 61499/ G. Black, V. Vyatkin // Proc. IEEE Int. Conf. on
Industrial Informatics.– 2011.- pp. 573 – 578.
2. Belyakov S. Routing in the mechanical transport systems on the basis of knowledge /
S. Belyakov, A. Bozhenyuk, I. Rozenberg // 14th IEEE International Symposium on
Computational Intelligence and Informatics CINTI 2013, Budapest, Hungary, November
19-21, 2013.-pp.159-262
3. Cormen T. H., Leiserson, C E., Rivest, R. L., Stein C. Introduction to Algorithms. —
3rd. — MIT Press.- 2009
4. Kostakos V. Temporal graphs. In Proc. of Physica A: Statistical Mechanics and its
Applications, vol.388, Issue 6, Elsevier, 2008, p.1007-1023.
5. Zimmermann, H.J. Fuzzy Set Theory and Its Applications. / H.J. Zimmermann. – 3rd
ed. – Kluwer Academic Publishers – 1996. – 435 p.