Artificial intelligence

Abstract: The aim of this work is to develop methods for solving fuzzy traveling salesman problems based on a multi-criteria approach. The paper considers options for solving multi-criteria traveling salesman problems, methods for reducing the problem to a single-criteria problem, and approaches to forming a compromise route using Prim's algorithm. The paper considers methods for solving a fuzzy problem of finding the fastest route with fuzzy specified values of travel time on a transport system. Fuzzy triangular numbers are used to represent the duration. The fuzzy traveling salesman problem is considered as a multi-criteria problem, for which the convolution method with confidence weighting coefficients is used. A discrete version of setting the weighting coefficients and a continuous analog are considered. Membership indicators of the values of the carrier of each fuzzy number are taken into account. The results of applying the developed method for solving real traveling salesman problems are proposed, and an analysis of the effect of the increase in travel time on the final form of the route is carried out. The developed approach can be used to solve the problem of optimizing transportation in a transport network, taking into account the uncertainty of traffic parameters and indicators of subjective confidence of a traveling salesman regarding the effective choice of travel time costs.

Keywords: multicriterial traveling salesman problems, fuzzy travel time, fuzzy triangular numbers, weighting coefficients, convolution method

References:

1. Zaichenko Yu. P. Operations research / Yu. P. Zaichenko. – Кyiv: «Slovo», 2006. – 815 p.
2. Ajay D. Kshemkalyani, Mukesh Singhal. Distributed Computing: Principles, Algorithms, and Systems. - Cambridge University Press, 2011. DOI: 10.1017/ CBO9780511805318
3. Vanderbei R. J. Linear programming: Foundations and extensions. - Springer, 2014. – 414 р.
4. Golden B., Raghavan S., Wasil E. The Vehicle Routing Problem: Latest Advances and New Challenges. – Springer New York, 2008. DOI: 10.1007/978-0-387-77778-8
5. Hamdy A. Taha. Operations Research: An Introduction (10th Edition). – Pearson Education Limited, 2017. – 849 p.
6. Seth Pettie, Vijaya Ramachandran An optimal mini-mum spanning tree algorithm // Journal of ACM, 2002. – V.49. – Iss. 1. – P.16-34. DOI: 10.1145/505241.50524
7. Zaichenko Yu. P. Fuzzy models and methods in intelligent systems, Кyiv: «Slovo», 2008. – 344 p.
8. Bablu Jana, Tapan Kumar Roy. Multi-Objective Fuzzy Linear Programming and Its Application in Transportation Model // Tamsui Oxford Journal of Mathematical Sciences, 2005. – V.21. – No.2. – P. 243-268.
9. Gavrylenko V. V., Іvohin E. V., Іvоnina К. T., Yushtin К. Е. Models of optimization of transport and network flows in problems of decision support in information management systems / In book «Innovative trends in the development of information management systems and technologies» by general editor Ustenko S. V. - Кyiv, КNEU, 2023.
10. Van Broekhoven, E., De Baets, B. Fast and accurate center of gravity defuzzification of fuzzy system outputs defined on trapezoidal fuzzy partitions // Fuzzy Sets and Systems, 2006. - V. 157. - Iss. 7. – P. 904-918.
11. Syswerda, G., Schedule Optimization Using Genetic Algorithms// In book “Handbook of Genetic Algorithms”, Van Nostran Reynolds, NY, 1991, pp. 332-349.
12. Barraq Subhi Kaml, Mohamed Saad Ibrahim. Solving the Multi-Objective Travelling Salesman Problem with Real Data Application // Journal of Al-Nahrain University, 2018. - Vol.21 (3). – Pp. 146-161. DOI: 10.22401/JNUS.21.3.18.