Optimized Fuzzy Petri Nets and Their Application for Transport Logistics Problem 1 2 2 Zbigniew SURAJ , Oksana OLAR , Yurii BLOSHKO 1 Department of Computer Science, University of Rzeszów, Str. Prof. S. Pigonia 1, PL-35310 Rzeszów 2 Yuriy Fedkovych Chernivtsi National University, Str. Kotsyubynsky 2, UA-58012 Chernivtsi E-mail: 1zbigniew.suraj@ur.edu.pl, 2oksol79@ukr.net, 2ubloshko@gmail.com Abstract – This paper presents the conception to formalize the task of transport logistics in the form of tables. From these tables, we extract the fuzzy production rules that are the basis for the formation of fuzzy Petri nets. The use of optimized and weighted fuzzy Petri net for solving the transport logistics problem is proposed. The obtained solutions are illustrated by fuzzy Petri net software that simulate the search for the best passenger transport company in the context of transport logistics. Кеу words – decision-making system, weighted fuzzy Petri net, optimized fuzzy Petri net, production rule, transport logistic task. I. Introduction The approach to solve the transport-logistic problem is considered in this paper [1]. The main idea of the proposed approach is to create the concept of a fuzzy Petri net (FPN) for solving transport logistics problem. The use of this approach provides the simplicity and versatility of the solution of the transport and logistics task. This approach is related to the formalization of tasks in the context of transport logistics, which is based on a scheme that provides expert knowledge of vehicles and their properties, the search for the optimal vehicle type and more. The main objects (vehicles) are represented in the table rows, and the corresponding properties are presented in each column of the table. The established relationship between objects and properties is the basis for the formation of rules - products and functions. The acquired knowledge will be used in the PNeS software [2]. Also, the description scheme of the subject field of transport logistics has several levels. According to these levels, production rules are used at both: the internal level of each table and at the external level. This is done to connect the main tables between each other. The number of objects in the tables decreases after each step of computations, as the area of the solution of the transport logistics problem is narrowed. The obtained solutions show that the calculation becomes easier and faster by reducing the number of objects in the net after each step. We take into account all possible ways of describing situations, but by this calculation methodology, the result is much faster and easier due to the avoidance of excessive information. This methodology is based on production rules [3], triangular norms (t-norms and s- norms) [3], fuzzy Petri net [4]. This is all about getting the idea of decision-making in the transport logistics problem. In order to formalize the results and show the practical efficient of this theory, all input data is set in the PNeS software, which describes the net of connection of “Object-feature” tables and the results of calculation [1,5]. Also, this paper contains comparison of classical set of function with a top-vertex set of functions [6]. All calculations and conclusions are included. 1 Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). II. Informally About Transport Logistics Problem Description of the events and situations that arise in the process of solving transport logistics tasks involves consideration of objects (vehicles) and properties together with their change over the time. This means that the description of the tasks of transport logistics contains inaccuracies and uncertain data. The fuzzy Petri net can be used as a model of reasoning: for instance, transitions may denote production rules, and each sequence of firing of transitions may represent an explanation that will be used to find the optimal mode of transport. The actual problem is the question of formalization of expert knowledge, which describe the tasks of transport logistics, which are often fuzzy and inaccurate. Paper "Conception of Fuzzy Petri Net to solve transport logistics problems" presents the approach to select the best type of vehicle (transport) for the passenger transportation with the use of fuzzy Petri nets. The model takes special characteristics as an input data. These characteristics are considered to be important for the passenger (user) in the process of deciding the choice of transport vehicle [1]. However, it is not enough to consider only one type of characteristics of vehicles for the solution of the transport logistics problem. Therefore, it is necessary to take into account existing models of vehicles and their special characteristics as well as transport companies that use them in business. In this connection, it is necessary to make a transition from the highest level, at which the search of the optimal type of transport was carried out, to the lower one. This approach allows finding the best transport company based on the requirements of the best type of transport for the given input values. The implementation of this approach requires the separation of vehicles into separate types, including automobile vehicle, aviation and train (Fig. 1). Also, it is worth mentioning that the topic of transport logistic problem covers a wide range of vehicles, including ships, motor bicycle etc., but in the previous and in this paper we consider only the most used types of transport which were listed in the previous sentence. Additionally, it worth mentioning that we cover only European continent in the question of passenger transportation at this stage. Fig. 1 presents the graph which describes the main task of passenger transportation from the point A to the point B. Fig. 1 The graph of task of passenger transportation Fig. 1 presents the transporting of a passenger as a direct one-way trip. Weights that are marked on the graph represent output values that are received from the Fuzzy Petri Net model. So, the type of transport with the highest value at the output is suggested as the best one to be used. But the trip may have a transfer in some other location – point C. Then the structure becomes a little bit extended. Fig. 2 presents the transporting of a passenger with a transfer in the point C. As we can see from the figure above, the question of choosing the best type of transport becomes a little bit more complicated, because, the main idea remains the same, while the calculations must be done two times: for the trip from A to C and for the trip from C to B. Therefore, there is a need to choose one out of nine combinations of types of transport that will be the best. This structure can 2 Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). be extended with two, three or even more transfer points, but the idea remains the same: to find the best type of transport (one out of three) for the given part of the trip. Fig. 2 The graph of task of passenger transportation with a transfer point The next step in this work is to find the best transport company that is based on the decision what type of transport is the best for some part of the trip. It should be highlighted that most of mentioned in this paper passenger transport companies cover the whole map of Europe. On the other hand, the train branch has some specifics, e.g. almost each European country has its own train company. Trains’ companies are different in each country and there is no general European train company that covers the whole Europe. That is why, we have used Polish railway company structure as an example in this paper. As the structure of railway companies is the same in most European countries, the proposed model can be applied to other railway companies of other countries depending on the request. In this paper, we use three tables to describe system that makes a search for the best transport company. The input for the system are features with corresponding fuzzy degrees that express the importance of each feature at the stage of choosing transport company from one of three types of transport (aviation, automobile vehicle, train). The output shows the best transport company is reflecting the result of computations for the given input values. Production rules of type “IF-THEN” are used to set up connections between tables (at the external level). Also, these rules are used to make a connection inside each table (internal level) between each object with all corresponding properties. The final step of this work is creating PNeS model that directly corresponds to the production rules. Each Petri net consists of places and transitions that are connected by directed arcs. Each transition in FPN contains a triple of triangular norms. Also, this paper aims to show the effectiveness of top vertex (triple of functions (ZtN, ZtN, LsN)) [6]. In order to achieve it, there were created structurally similar nets with the only difference in this triple of functions, where we compare triple of functions (ZtN, ZtN, LsN) to the classical one (ZtN, GtN, ZsN). One more notion that this paper presents is a weighted arc, which describes the strength of the connection from the place to the transition. III. Fuzzy Production Rules Fig. 3 presents expert knowledge tables and interconnections with concepts in the context of finding the best transport company. As a result, there will be received separately 3 branches of vehicles, their models and special characteristics. Also, it is worth researching whether such a division could lead to changes in the calculations and therefore to the different result. So, there will be one more approach, the idea of which is to combine 3 branches of vehicles, their models and special 3 Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). characteristics into one effective model of fuzzy Petri nets and to make a decision of the best transport company based on its results. What is more, there is a need to check if a full model is reasonable in use compared to the one of three separated models. According to this structure between tables in Fig. 3, there is a possibility to create production rules with the dependence between objects and features. If there is a connection between object and feature on the intersection of the table with the value greater than 0 and less than 1, then it means that there is a fuzzy value of this connection. If the connection is equal to 1 then there is a strong connection. The difference between first and second case is that in the first case the connection has a measure of accuracy or for how strong this connection is and in the second case, there are only strictly determined connections (in case of “1” it exists and in case of “0”, it does not). In both cases, a form IF ri THEN dj can be applied. Fig. 3 Interconnection of tables at the level of companies Example of production rule: IF «Classical Train» THEN «PKP TLK». If an object has more than one connected feature (property) then the production rule should be extended to the form: IF ri1 AND (OR)… AND(OR) rin THEN dj. Example of the extended production rule: IF «Speed» AND «Low Price» AND «Comfort» AND «Snack on Board» THEN «Classical Train». As a practical example, we can consider aviation branch from the conception presented in Fig. 3. There were created 30 production rules in total for this experiment: 23 of them referred to Types of transport means and 7 to the Transport companies. Each feature (or column in the table) in the production rule is presented as a place in the Petri net (PN) model. Each input place (feature) that has a logical connection AND is connected with the transition. And each transition is connected to the output place that contains a resulting value. It represents the result of the production rule (i.e. the value of object that is set after THEN). Each level of the PN model represents a table that contains production rules. Each production rule is interconnected with each other. In the same way, we extract rules to make a connection between tables. As far as, all tables are connected with each other, the result in the output place from the previous table becomes an input value for the next table (i.e. object in the previous table becomes a feature in the next one). The number of transitions in the PN refers to the number of production rules. In other words, there are 2 transitions that connect the first (input) level of the PN with the second level of places and it directly corresponds to the first table, which contains two production rules. In the same way second level has 12 passes (transitions) to the third (output) level for the second table that has 12 production rules (Fig. 4). 4 Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). Experts create fuzzy production rules according to the special characteristics of transport means in the range [0,1]. Fuzzy value describes the strength of the connection: if the connection is strong then it has a high value (getting closer to 1), in the same way a weak connection has a low value (getting closer to 0). Fig. 4 FPN model that corresponds to the tables of aviation branch in Fig. 3 IV. Net Representation Model of Passenger Transportation When the conception of the task is described, the tables are created and fuzzy production rules are extracted from them, the final step is to create a net in the PNeS software. Fig. 3 is the base for creating a model in PNeS with the corresponding connections. The paper [6] shows how to use the generalized fuzzy Petri net model in the fuzzy reasoning algorithm. The tangible benefit of this approach compared to the previous one lies in the fact that the user can now more precisely adapt his model to the real-life situation and use it more effectively by choosing the appropriate triples of operators for net transitions (see [6]: Proposition 3, and the definition of the optimized generalized fuzzy Petri net - section 3). The paper [6] presents the results of comparing different combination of triangular norms in order to find the best triple combination to use for each transition. The results of the experiment are the following: (ZtN, GtN, ZsN) - the central vertex (a typical set of triangular norms for fuzzy Petri nets), (ZtN, ZtN, LsN) - top vertex (optimal selection of triangular norms in this case) (LtN, LtN, ZsN) - bottom vertex. Therefore, the notion of Optimized Fuzzy Petri Nets means using top or bottom vertices. If it is being compared to the central vertex, then it is easy to see that the use of triples from top or bottom vertices gives optimized (the best possible) result for the FPN model. We created nets that are presented in Fig. 5 and Fig. 6 according to it. Also, we want to compare different triples of functions and to prove effectiveness of top vertex 5 Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). (triple of functions (ZtN, ZtN, LsN)). In order to achieve it, we compare model in Fig. 5 that contains a classical triple of operators (ZtN, GtN, ZsN) as a base to the model in Fig. 6, which represents a net with a triple of functions (ZtN, ZtN, LsN) that should present the maximum possible value in the output places (resulting values). At first, each input place (property) is being set with the value that was previously given by experts. At second, we apply production rules that were previously extracted from the table, (where each feature was connected to the object) to build up a net. In the model, each input place is connected to the transition by directed arcs as well as each transition is connected to the output place also by directed arcs. According to this scheme there is a transfer from special characteristics to object. As far as, we are dealing with weighted FPN, we carry-over fuzzy values that were on intersections of tables (which were showing the degree of accuracy) to the net. Weights concern arcs between places and transitions (but not vice versa). In order to show the accuracy of the input place that has a connection with this weighted arc, the values of input place and weighted arc are being multiplied and being sent as an input to the transition. Each transition has a threshold function 𝛾(𝑡) and a truth degree function 𝛽(𝑡). Threshold function 𝛾(𝑡) for the first level of transitions is given by experts and is equal to 0.4, while the second level of transitions has value equal to 0.1. It can be explained that these values are allowable and necessary minimum to obtain profitable result. The truth degree function 𝛽 calculated as 𝛽(𝑡) = k/(k+1), where k is a number of input places of 𝑡. Both Fig. 5 and Fig. 6 have the same structure: first column of places is dedicated to the properties in the table (Types of transport/Special Characteristics). The second column of places is the result of the calculations of production rules in the first table and it is the input for the second table (Transport Companies/Types of transport). And the last, the third column of places corresponds to the objects in the table – “Transport Companies/Types of transport”. At the same time, it is the result of the model, where each place has some fuzzy value and as far as we are interested in the best (highest) result, we are looking for the place, which has the highest fuzzy value. As far as we deal with tables of the type “Object/Properties”, transitions in the net can be explained in the following way: the first level of transitions correspond to the connection between objects and features in the first table or it can be also said that the first level represents the connection of the production rules that were extracted from the first table – “Types of transport/Special Characteristics”. In the following way, the second level of transitions represents the connections in the second table – “Transport Companies/Types of transport”. In Fig. 5 we used a classical triple of operators (ZtN, GtN, ZsN). This set of operators is used in the classical manner for the production rules, which uses the conjunction operator AND as a main one. (ZtN) or (Zadeh t-norm) operator should be in the first position and it is described as: TZ(a,b) = min(a,b). (GtN) or (Goguen t-norm) operator is in the second position. This operator can be described as (GtN): TG(a,b) = ab. It is used to increase the input value by multiplication with a value of the truth degree function 𝛽(𝑡). But if 𝛽(𝑡) has a low value, it will lead to decrease of the multiplied value. And the last operator (ZsN) (Zadeh s-norm) is used to obtain the maximum value at the output place. This operator is described in this way: SZ(a, b) = max(a,b). The procedure of calculation repeats until the last table is reached and last transition in the net is checked. In Fig. 6, we have modified the triple of operators to (ZtN, ZtN, LsN). According to Fig. 6, this combination of operators should achieve (result) the maximum possible values at the output. So, we will get the best result, in which we are interested. Zadeh t-norm operator is used in the same way as it was used in the previous model. The only difference is that it used here twice: as a second operator again, instead of (GtN). It leads to the fact that the value becomes saved rather than in the case of (GtN), where it tends to decrease because of multiplication operator. And the third operator (LsN) or (Lukasiewicz s-norm) is a filling operator and is described as: (LtN): SL(a,b) = (1,a+b). In other words, it fulfills the last output place with values, but the sum cannot 6 Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). exceed 1. 7 Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). 8 Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). Fig. 5 FPN model for the Transport Logistic Problem (triple of operators (ZtN, GtN, ZsN)) 9 Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). 10 Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). Fig. 6 FPN model for the Transport Logistic Problem (triple of operators (ZtN, ZtN, LsN)) According to the results, we see the last level (column) of places in the model that has a triple of operators (ZtN, ZtN, LsN) resulted in higher values comparing to the results in a model with a classical triple of operators (ZtN, GtN, ZsN) for the same input values. What is more, higher values were also achieved on the previous level (second column) of places. Following this consequence, we can suggest that all level of places that are in between levels of input and output would also have a higher value in a triple of operators (ZtN, ZtN, LsN) comparing to the triple (ZtN, GtN, ZsN). What is more, according to the values in the output models, we see that the triple of operators (ZtN, GtN, ZsN) gives low and averaged values, while the triple of operators (ZtN, ZtN, LsN) results not only in high values at the output places but also with better and precise presentation of values and it is easier to compare resulting values between each other. As we can see from the models in Fig. 5 and Fig. 6, the highest output value (0.21 and 0.47 in accordance) for the given input features belongs to the classical airline “Lufthansa”. It suggests that it is the best option to travel from point A to point B. At the same time, we see that again in both cases “Hitchhiking” way of transporting is the least successful and is equal to 0.08 and 0.11 in accordance. In both cases, it means that this option is the least useful for the given input properties. Fig. 7 Division of combined tables into three separate tables 11 Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). The next step is to find if a model that is divided into 3 separate groups will lead to the same result as a full one (Fig. 7). Therefore, we divide the model presented in Fig. 6 into 3 separate branches. As a result, we received 3 models (of each branch: aviation, automobile vehicle and train) with top-vertex triple of operators (ZtN, ZtN, LsN). Resulting models are presented in Fig. 8, Fig. 9 and Fig. 10. If we compare Fig 6 to Fig. 8, Fig. 9 and Fig. 10, we can see that the resulting fuzzy values in the output places did not change. What is more, each branch of the full model makes calculation faster and requires less resources of the computer. In the paper “Conception of Fuzzy Petri Net to solve transport logistics problems” [1], the main aim was to choose the best type of transport. When we have a decision of what type of transport is the best that was done in the previos FPN model [1], we can take only one branch of this category from the current full model for the calculation (i.e. to choose one of the models between Fig. 8, Fig. 9 and Fig. 10 rather than make full calculations in Fig. 6). This approach simplifies time and resource consumption of the computer for solving Transport Logistic Problem at this stage and at the same time it gives respectively accurate results for in the search of transport company. Fig. 8 FPN model with a triple of operators (ZtN, ZtN, LsN) containing only aviation branch Also, we want to prove and to guarantee the effectiveness of the top-vertex triple of operators (ZtN, ZtN, LsN) over a classical one (ZtN, GtN, ZsN). In order to achieve it, the model that was presented in Fig. 5 was splitted by the groups in the same way: aviation, automobile vehicle and train brenches. The resulting models are presented in Fig. 11, Fig. 12 and Fig. 13. 12 Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). Fig. 9 FPN model with a triple of operators (ZtN, ZtN, LsN) containing only automobile vehicle branch 13 Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). Fig. 10 FPN model with a triple of operators (ZtN, ZtN, LsN) containing only train branch If we compare result in models between Fig. 8 and Fig. 11, Fig. 9 and Fig. 12, Fig. 10 and Fig. 13 accordingly, we will see that in each case, models that have operators (ZtN, ZtN, LsN) as a base lead to the better result rather than models with a group of operators (ZtN, GtN, ZsN). 14 Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). Fig. 11 FPN model with a triple of operators (ZtN, GtN, ZsN) containing only aviation branch At the same time, the question about dividing a full model into a smaller one (by branches) without changes in result is again confirmed on the example of operators (ZtN, GtN, ZsN). If we compare divided branches of model in Fig. 9, Fig. 10 and Fig. 11 to Fig. 5, we see that fuzzy values, which are at the output places in three divided models are absolutely the same that are in the full model. The idea of division of a full net into smaller branches gives a benefit, because according to the result that were achieved on the previous stage of solving Transport Logistic Problem [1], we use much less production rules now. Therefore, we use less places and transitions, because we already know what type of transport we are interested in. This leads to the smaller consumption of computer resources and time-saving. On the other hand, if we take a full model, yet, we are able to make a comparison between all possible companies and have a wider possibility to make a decision. 15 Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). Fig. 12 FPN model with a triple of operators (ZtN, GtN, ZsN) containing only automobile vehicle branch 16 Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). Fig. 13 FPN model with a triple of operators (ZtN, GtN, ZsN) containing only train branch V. Conclusion Still the problems in transport logistics remain actual with the fact of fast growth of improvements in this industry. Still there is a need in the improvement of the quality of optimized solutions and the need of creation of information flows that combine transport material flows and the processes of their functioning. In this paper, we have presented a scheme of transport logistics problem and a partial solution in the task of transport logistics. Tables of type “Object-Properties” were created in order to achieve this aim. Production rules were extracted from these tables. In accordance to these rules, fuzzy Petri net models were created with two different triples of operators. All necessary calculations were made and results were compared between each other. This paper shows how to combine fuzzy Petri net model to the expert knowledge based on production rules that leads to achieving a proper result. What is more, we applied a fuzzy values on the intersections of tables that allowed us to use a weighted fuzzy Petri net. There, we added these fuzzy values on the arc from a place to a transition, which characterized the strength of the connection. Therefore, it leaded to more accurate result. Also, it was proved on a practical example the use of optimal fuzzy Petri net where a triple of operators (ZtN, ZtN, LsN) give the highest possible result comparing to the classical triple of operators (ZtN, GtN, ZsN). References [1] Suraj Z., Olar O., Bloshko Y.: Conception of Fuzzy Petri Net to Solve Transport Logistics Problems. Current Research in Mathematical and Computer Sciences II, Publisher UWM, Olsztyn, 2018, pp. 303-313. [2] Suraj Z., Grochowalski P.: Petri Nets and PNeS in Modeling and Analysis of Concurrent Systems. In: Proc. the International Workshop on Concurrency, Specification and Programming (CS&P 2017), September 25-27, 2017, Warsaw, Poland, pp. 1-12. [3] Klement E.P., Mesiar R., Pap E.: Triangular Norms. Kluwer, Dordrecht 2000. [4] Suraj Z.: A New Class of Fuzzy Petri Nets for Knowledge Representation and Reasoning. Fundamenta Informaticae, 2013, vol. 128(1-2), 193-207. [5] Lyashkevych V., Olar O., Lyashkevych M.: Software ontology subject domain intelligence diagnostics of computer means. In: Proc. the 7th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS-2013), September 2013, Berlin, Germany, pp. 12-14. [6] Suraj Z.: Toward Optimization of Reasoning Using Generalized Fuzzy Petri Nets. In: Proc. the IJCRS 2018, August 20-24, 2018, Quy Nhon, Vietnam, Lecture Notes in Artificial Intelligence, vol. 11103, pp. 294-308. Springer, 2018. 17 Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).