ABOUT OF THE ANNEALING METHOD USING FOR THE TRAVELING SALESMAN PROBLEM SOLUTION WITH THE FUZZY TIME PERCEPTION

Authors

  • E. V. Ivohin Taras Shevchenko National University of Kyiv, Kyiv, Ukraine, Ukraine
  • L. T. Adzhubey Taras Shevchenko National University of Kyiv, Kyiv, Ukraine, Ukraine
  • M. F. Makhno Taras Shevchenko National University of Kyiv, Kyiv, Ukraine, Ukraine
  • V. O. Rets Taras Shevchenko National University of Kyiv, Kyiv, Ukraine, Ukraine

DOI:

https://doi.org/10.15588/1607-3274-2024-4-5

Keywords:

traveling salesman problem, fuzzy numbers, simulated annealing, combinatorial optimization, subjective perception of time, imprecision, uncertainty

Abstract

Context. The article considers a technique for the use of fuzzy numbers and the annealing method for solving the 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 duration of movement. The task of formalizing the algorithm for solving the traveling salesman problem by the annealing method using fuzzy numbers for subjective time perception is posed. The use of fuzzy numbers to increase the accuracy to represent real-world circumstances is proposed.

Objective. The goal of the work is to develop an algorithm for solving the traveling salesman problem based on the implementation of the annealing method with fuzzy numbers representing the subjective time perception for traveling between the cities with the minimum perceived duration of movement along the route.

Method. This paper proposes a method for solving the traveling salesman problem by the annealing method with fuzzy numbers for subjective time perception. A scheme for formalizing the procedure for solving the traveling salesman problem with the minimal perceived duration of movement along the route is described. A variant of the original traveling salesman problem is proposed, which consists in using fuzzy numbers to represent the uncertainty and subjective time perception in traveling between cities as opposed to regular crisp numbers to show regular distance and/or time of traveling. The results of the proposed algorithm for calculating solutions to the traveling salesman problem with minimization of the perceived duration of movement are presented, the obtained solutions are compared with the solutions found by other heuristic methods.

Results. The method for solving the traveling salesman problem using the annealing method with fuzzy numbers for subjective time perception is developed. A variant of the original traveling salesman problem is proposed, which consists in using fuzzy numbers to represent the uncertainty and subjective time perception in traveling between cities as opposed to regular crisp numbers to show regular distance and/or time of traveling. The application of fuzzy numbers makes it possible to perform calculation over possibly uncertain or subjective data, making results more accurate in the case of realistic deviations from the expected mean values in distance coverage. The results of the proposed algorithm for calculating solutions to the traveling salesman problem with minimization of the perceived duration of movement are presented, the obtained solutions are compared with the solutions found by other heuristic methods.

Conclusions. The paper considers a method for formalizing the algorithm for solving the traveling salesman problem using fuzzy numbers for subjective time perception. The use of fuzzy numbers to increase the accuracy to represent real-world circumstances is proposed. The scheme for formalizing the procedure for solving the traveling salesman problem with the minimal perceived duration of movement along the route is described. A variant of the original traveling salesman problem is proposed, which consists in using fuzzy numbers to represent the uncertainty and subjective time perception in traveling between cities as opposed to regular crisp numbers to show regular distance and/or time of traveling.

Author Biographies

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

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

L. T. Adzhubey, Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

PhD, Associate Professor, Associate Professor of the Department of Computational Mathematics

M. F. Makhno, Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

PhD, Associate Professor, Ass. Professor of the Department of System Analysis and Decision Support Theory

V. O. Rets, Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

Postgraduate student of the Department of System Analysis and Decision Support Theory

References

Schirmer A. How emotions change time, Frontiers in Integrative Neuroscience, 2011, № 5, Р. 58. DOI: https://doi.org/10.3389/fnint.2011.00058

Schrijver A. Theory of Linear and Integer Programming. Wiley, 1998, 484 p. DOI: 10.2307/253980

Matai R. Singh S. P., Mittal M. L. Traveling salesman problem: an overview of applications, formulations, and solution approaches, Traveling salesman problem, theory and applications, 2010, № 1, pp. 11–17. DOI:10.5772/12909

Vanderbei R. J. Linear programming: Foundations and extensions. Springer, 2014, 414 р. DOI: 10.1007/978-3-03039415-8

Korte B., Vygen J. Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics). Berlin, Heidelberg, Springer, 2018, 455 p. DOI: 10.1007/978-3-66256039-6

Moss L. T., Atre Shaku Business Intelligence Roadmap: The Complete Project Lifecycle for Decision-Support Applications. Addison-Wesley Professional, 2003, 576 p. ISBN: 978-0-201-78420-6

Buontempo F. Genetic Algorithms and Machine Learning for Programmers. Pragmatic Bookshelf, 2019, 236 p. ISBN: 9781680506204

Kshemkalyani A. D., Singhal Mukesh Distributed Computing: Principles, Algorithms, and Systems. Cambridge University Press, 2008, 756 р. DOI: 10.1017/CBO9780511805318

Rai S., Ettam R.K.Simulation-based optimization using simulated annealing for optimal equipment selection within print production environments, 2013 Winter Simulation Conference: Simulation: Making Decisions in a Complex World, December, 2013: proceedings, 2013, pp. 1097–1108. DOI: 10.1109/WSC.2013.6721499

Grabusts P., Musatovs J., Golenkov V. The application of simulated annealing method for optimal route detection between objects, Procedia Computer Science, 2019,V. 149, pp. 95–101. DOI: https://doi.org/10.1016/j.procs.2019.01.112

Heilpern S. Representation and application of fuzzy numbers, Fuzzy sets and Systems, 1997, №91(2), pp. 259–268. DOI: https://doi.org/10.1016/S0165-0114(97)00146-2

Zadeh L.А. Fuzzy sets, Information and Control, 1965, №8. pp. 338–353. DOI: http://dx.doi.org/10.1016/S00199958(65)90241-X

Tofigh А., Saneifard R. Defuzzification method for ranking fuzzy numbers based on center of gravity, Iranian Journal of Fuzzy Systems, 2012, №9(6), pp. 57–67. DOI: 10.22111/IJFS.2012.113

Nejad A. M., Mashinchi M. Ranking fuzzy numbers based on the areas on the left and the right sides of fuzzy number, Computers & Mathematics with Applications, 2011, Vol. 61, №2, pp. 431–442. DOI:10.1016/j.camwa.2010.11.020

Downloads

Published

2024-12-26

How to Cite

Ivohin, E. V., Adzhubey, L. T., Makhno, M. F., & Rets, V. O. (2024). ABOUT OF THE ANNEALING METHOD USING FOR THE TRAVELING SALESMAN PROBLEM SOLUTION WITH THE FUZZY TIME PERCEPTION . Radio Electronics, Computer Science, Control, (4), 56–63. https://doi.org/10.15588/1607-3274-2024-4-5

Issue

No. 4 (2024): Radio Electronics, Computer Science, Control

Section

Mathematical and computer modelling

License

Copyright (c) 2024 E. V. Ivohin, L. T. Adzhubey, M. F. Makhno, V. O. Rets

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) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.