توسعه يك الگوريتم بهترين مسير در شرايط نايقيني و كمبود داده مبتني بر نظريه فازي شهودي

Developing an Optimal Path Algorithm Based on Intuitionistic Fuzzy theory for Uncertain and Incomplete Network

نظریه مجموعه‌های فازی شهودی، تعمیمی از نظریه مجموعه‌های فازی می‌باشد كه در آن می‌توان علاوه بر تابع عضویت از تابع عدم عضویت هم استفاده كرد. این مزیت موجب شده تا بعضی از محدودیت‌های نظریه فازی معمول مثل پشتیبانی از شك و تردید را برطرف سازد. از طرفی با توجه به اینكه یكی از مسائل موجود در گراف، یافتن كوتاهترین مسیر در شرایط عدم قطعیت و نبود اطلاع كافی از فاصله‌هاست. با توجه به نكات ذكر شده در این مقاله الگوریتم كوتاهترین مسیر دایجسترا برای گراف با یال‌های فازی شهودی در شرایط كمبود اطلاعات تعمیم داده شده است. در روش ارائه شده در مقاله برای مقایسه مسیرها از روش انتگرال-گیری استفاده شده است. در نهایت الگوریتم روی یك شبكه با ابعاد مناسب آزموده شده و با حالت فازی معمولی مقایسه شده است.

Finding the shortest path from origin point to destination point is of vital importance in different cases.  In a network, the length of arcs could show the length of the path, time of the path, or any other parameter. A fuzzy shortest path has a variety of applications. Now suppose that there are arcs with no specified length, or with specified length that vary depending on other parameters such as traffic, accidents etc. Moreover, on certain occasions such as smuggling, security forces may doubt the weight of arcs. In such cases, the use of fuzzy shortest path would not be efficient. The Intuitionistic fuzzy set theory can be considered as a generalization of fuzzy set theory in which non-membership function is used in addition to membership function, independently. Note that in fuzzy theory, no difference is considered between presence of data or reasons in favor or against any given subject. In other words, if membership function of an element be half from the fuzzy set, we cannot infer that information was little or that negative and positive reasons were provided with the same amount. Whereas the Intuitionistic fuzzy set and logic is capable of overcoming a number of the limitations of the fuzzy algorithm theory such as supporting doubts and uncertainty. On the other hand, due to the fact that one of the present issues in the graph is finding the shortest path in terms of uncertainty and lack of adequate information of distances. In this paper, the shortest path of Dijkstra algorithm is expanded for the graph with Intuitionistic fuzzy arcs having incomplete data. In this article, two problems with corresponding solutions are presented. The first challenge is about combining the arcs solved by using triangular Intuitionistic fuzzy numbers. The second problem concerns the method of comparing the arcs. To compare the arcs, there are numerous ways including utilizing centroid, maximum and minimum sets, integral values etc. Finally, integral values method was implemented. The reason for using this method is capability to differ between state of decision-maker like optimism and pessimism. So one can change equal inputs accordance to different condition to give different outputs. In this regards, we provide a numerical example of a road network. This network includes 25 nodes and 46 arcs. It is assumed that the value of arcs is triangular Intuitionistic fuzzy numbers as noted above. Then, the algorithm was tested on the network and was compared with the conventional fuzzy method.  Finally, the result of algorithm has been compared with the figures and tables and presented difference of the fuzzy and intuitionistic fuzzy paths. It should also be noted that in the case of information lack and algebraic uncertainties abound, Intuitionistic fuzzy logic will be useful, bearing more appropriate results compared to cases done with fuzzy logic. That is because the use of this algorithm allows us to analyse the possible routes pessimistically, cautiously, optimistically and moderately. Hence, information and lack of information as well as doubts and uncertainty will also be taken into account. As a result, the use of this algorithm provides results that are more adaptable to the given condition to be implemented by the decision maker.