ABOUT RATIONAL METHODS FOR FINDING OPTIMAL ROUTES IN FUZZY TRAVELING SALESMAN PROBLEMS

Authors

  • E. V. Ivohin Taras Shevchenko National University of Kyiv, Kyiv, Ukraine
  • V. V. Gavrylenko National Transport University, Kyiv, Ukraine
  • K. E. Yushtin Taras Shevchenko National University of Kyiv, Kyiv, Ukraine
  • K. E. Ivohina National Transport University, Kyiv, Ukraine

DOI:

https://doi.org/10.15588/1607-3274-2026-1-11

Keywords:

fuzzy traveling salesman problem, fuzzy numbers, subjective perception of duration, uncertainty, solution methods, multicriteria approach, defuzzification

Abstract

Context. This paper presents the results of a study on the use of triangular fuzzy numbers for determining time-optimal routes in the traveling salesman problem under fuzzy representations of travel duration in a transportation network. To formalize the uncertainty and imprecision of input data – associated with the subjectivity in estimating the time intervals required to travel between individual cities-triangular fuzzy numbers are employed. Various approaches to solving fuzzy traveling salesman problems are examined.
Objective. The goal of the work is to develop algorithms for solving the fuzzy traveling salesman problem based on the implementation of the Bellman-Zadeh parametric optimization methods, the use of a two-criteria approach with a given weight function and the refinement of the scheme for calculating the center of gravity of the membership function graph for a given curve density.
Method. The article considers methods for solving the fuzzy traveling salesman problem, which is formulated as the problem of finding a route to visit a given number of cities without repetitions with a minimum travel time. The parameters of the problem for formalizing the uncertainty and inaccuracy of input data associated with the influence of subjectivity in assessing the duration of time intervals required to travel between individual cities are presented as fuzzy triangular numbers. Different approaches to solving fuzzy traveling salesman problems are considered. The application of the Bellman-Zadeh method, methods taking into account refinements of defuzzified data, and methods based on a multicriteria approach is formalized. Computational experiments are carried out.
Results. Rational algorithms for solving the fuzzy traveling salesman problem based on the Bellman-Zadeh parametric optimization model, multicriteria approach and methods for refining the results of defuzzification of fuzzy data have been developed. In the conducted numerical experiments on solving the traveling salesman problem, fuzzy input data are based on the method for calculating the center of gravity (CoG), the center of gravity of homogeneous and non-homogeneous curves, which are determined by the membership function and the specified reliability values of subjective data. A comparison of the results obtained based on solving the crisp traveling salesman problem and the results based on defuzzified duration values for the fuzzy traveling salesman problem is carried out, according to the results of which the dependence of the solution on the defuzzification method is confirmed.
Conclusions. The article considers the method of formalizing the algorithm for solving the fuzzy traveling salesman problem with the minimum duration of movement along the route based on the Belman-Zadeh method, methods taking into account the refinements of defuzzified data and methods based on the multicriteria approach. Fuzzy triangular numbers are used to formalize the uncertainty of the input data when assessing the duration of movement between individual towns of the transport network. It was made a conclusion about the feasibility of using fuzzy numbers when solving fuzzy traveling salesman problems in real conditions of logistics transportation

Author Biographies

E. V. Ivohin, Taras Shevchenko National University of Kyiv, Kyiv

Dr. Sc., Professor, Professor of the Department of System Analysis and Decision Support Theory

V. V. Gavrylenko, National Transport University, Kyiv

Dr. Sc., Professor, Professor of the Department of Information Systems and Technologies

K. E. Yushtin, Taras Shevchenko National University of Kyiv, Kyiv

PhD, Post-doctoral Student of the Department of System Analysis and Decision Support Theory

K. E. Ivohina, National Transport University, Kyiv

Post-graduate student of the Department of Information Systems and Technologies

References

Zadeh L. A. Fuzzy sets, Information and Control, 1965, No. 8, pp. 338–353.

Ghiani G., Laporte G., Musmanno R. Introduction to Logistics Systems Planning and Control. John Wiley & Sons, Ltd, 2013, 377 р. DOI:10.1002/9781118492185

Davendra D. Traveling salesman problem: theory and applications. Books on Demand, 2010, 338 p.

Gavrylenko V. V., Ivohin E. V., Ivohina K. E., Yushtin K. E. Optimization models of transport and network flows in the problems of supporting decision-making in information management systems, In “Innovative trends in the development of information control systems and technologies”. Under the general editorship of Doctor of Economics, Professor Ustenko S. V. Kyiv, KNEU named after Vadym Hetman, 2024, pp. 233–255. https://ir.kneu.edu.ua/handle/2010/46976

Kumar A., Gupta A. Methods for solving fuzzy assignment problems and fuzzy travelling salesman problems with different membership functions, Fuzzy Information and Engineering, 2011, No. 3(1), pp. 3–21.

Bellman R. E., Zadeh L. A. Decision making in fuzzy environment, Management science, 1970, No. 17, pp. 144–164.

Zimmermann H.-J. Fuzzy programming and linear programming with several objective functions, Fuzzy Sets and Systems, 1978, No.1, pp. 45–55.

Christofides N. Vehicle routing in the traveling salesman problem. Lawler, Lenstra, RinooyKan and Shmoys, John Wiley eds., 1985, pp. 431–448.

Fuling Тien. Applying interactive fuzzy multi-objective Linear programming to transportation planning decisions, Journal of information and optimization sciences, 2006, No. 27(1), pp. 107–126.

Kosheleva O., Kreinovich V. Why Bellman-Zadeh approach to fuzzy optimization, Applied Mathematical Sciences, 2018, Vol. 12, No. 11, pp. 517–522.

Yushtin K., Іvohin E. About defuzzification methods influence on fuzzy traveling salesman problem’s solving, Artificial Intelligence, 2024, No. 1 (98), pp. 64–72. DOI: 10.15407/jai2024.01.064

Іvohin E., Gavrylenko V., Ivohina K. One approach to solving the fuzzy traveling salesman problem based on a multicriteria approach, Artificial Intelligence, 2025, No. 2 (103), pp. 84–94. DOI: 10.15407/jai2025 .02.084

Ivohin E., Yushtin K. A method for solving a single fuzzy multicriteria traveling salesman problem, Artificial Intelligence, 2024, No. 4 (101), pp. 142–150. DOI: 10.15407/jai2024.04.142

Bablu Jana, Tapan Kumar Roy Multi-objective fuzzy linear programming and its application in transportation model, Tamsui Oxford Journal of Mathematical Sciences, 2005, No. 21(2), pp. 243–268.

Kaufman A., Gupta M. M. Introduction to fuzzy arithmetic: theory and applications. Van Nostrand Reinhold Co. Inc., Workingham, Berkshire, 2003, 351 p.

Zimmermann H.-J. Fuzzy set theory and its application. Kluwer, Boston, 1992, 525 p. DOI: 10.1007/ 978-94-010-0646-0

Voskoglou M. G. Fuzzy sets, fuzzy logic and their applications, Mathematics, 2020, 452 p. DOI: 10.3390/ books978-3-03928-521-1

Van Broekhoven E., De Baets B. Fast and accurate center of gravity defuzzification of fuzzy system outputs defined on trape-zoidal fuzzy partitions, Fuzzy Sets and Systems, 2006, Vol. 157, No. 7, pp. 904–918.

Mendel J., Robert J. Type-2 fuzzy sets made simple, IEEE Transactions on Fuzzy Systems, 2002, No. 10 (2), pp. 117–127. DOI: 10.1109/91.995115.

Ivohin E., Gavrylenko V., Ivohina K. On the recursive algorithm for solving the traveling salesman problem on the basis of the data flow optimization method, Radio Electronics, Computer Science, Control, 2023, No. 3, pp. 141–147. DOI:10.15588/1607-3274-2023-3-14.

Ivohin E. V., Yushtin K. E. Solving the fuzzy traveling salesman problem using genetic algorithm with clustering by ward’s method, Conference Intelligent Transport Systems: Ecology, Safety, Quality, Comfort: ITS ESQC-2024: proceedings. Springer, 2024, Vol. 1, pp. 199–210. DOI: 10.1007/978-3-031-87376-8

Downloads

Published

2026-03-27

How to Cite

Ivohin, E. V. ., Gavrylenko, V. V. ., Yushtin, K. E. ., & Ivohina, K. E. . (2026). ABOUT RATIONAL METHODS FOR FINDING OPTIMAL ROUTES IN FUZZY TRAVELING SALESMAN PROBLEMS. Radio Electronics, Computer Science, Control, (1), 121–133. https://doi.org/10.15588/1607-3274-2026-1-11

Issue

No. 1 (2026): Radio Electronics, Computer Science, Control

Section

Progressive information technologies

License

Copyright (c) 2026 E. V. Ivohin, V. V. Gavrylenko, K. E. Yushtin, K. E. Ivohina

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Creative Commons Licensing Notifications in the Copyright Notices

The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.

The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.

The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.

Authors who publish with this journal agree to the following terms:

  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) as it can lead to productive exchanges, as well as earlier and greater citation of published work.