Solution of the traveling salesman problem based on the annealing method with the fuzziness of the time perception

Authors

DOI:

https://doi.org/10.17721/1812-5409.2023/2.39

Keywords:

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

Abstract

This paper investigates the use of fuzzy numbers and the annealing method to improve the results of the traveling salesman problem (TSP) by more accurately representing real-world circumstances, where the value of the objective function represents the subjective perception of the length of the time interval required to travel between cities. TSP is a classic combinatorial optimization problem that involves finding the shortest route between a set of cities. Fuzzy numbers are used to model input inaccuracy and uncertainty, as they allow for a more detailed representation of real-world constraints and factors that may affect the problem. The annealing method is used to optimize the TSP solution by gradually decreasing the temperature of the system, which allows exploring different solutions and avoiding getting stuck in local minima. To demonstrate the effectiveness of this approach, a Python program was developed that was used to compare the results of the TSP problem using crisp and fuzzy numbers using the annealing method. The results show that the use of fuzzy numbers, particularly triangular and parabolic, with the annealing method leads to a significant improvement in the results of the TSP problem compared to the use of crisp numbers, assuming a model is called realistic if it has possible deviations from the expected fixed mean. Computational results of the program are presented and analyzed, demonstrating the potential of this approach for real-world optimization problems involving imprecise or uncertain data and which can be particularly applied to the optimization of processes with subjective time perception.

Pages of the article in the issue: 226 - 231

Language of the article: Ukrainian

References

Schirmer, A. (2011). How emotions change time. Frontiers in Integrative Neuroscience, 5, p.58.

Schrijver, Alexander (2005). On the history of combinatorial optimization (till 1960). In K. Aardal; G.L. Nemhauser; R. Weismantel (eds.). Handbook of Discrete Optimization (PDF). Amsterdam: Elsevier. pp. 1–68.

Matai, R., Singh, S. P., & Mittal, M. L. (2010). Traveling salesman problem: an overview of applications, formulations, and solution approaches. Traveling salesman problem, theory and applications, 1. pp. 11–17.

Grabusts, P., Musatovs, J., & Golenkov, V. (2019). The application of simulated annealing method for optimal route detection between objects. Procedia Computer Science, 149, pp. 95- 101.

Heilpern, S. (1997). Representation and application of fuzzy numbers. Fuzzy sets and Systems, 91(2), pp. 259-268.

Zadeh L. (1965). Fuzzy sets, Information and Control, 8: pp. 338–353.

Allahviranloo, Tofigh, and Rahim Saneifard (2012). Defuzzification method for ranking fuzzy numbers based on center of gravity: pp. 57-67.

Nejad, Ali Mahmodi, and Mashaallah Mashinchi (2011). Ranking fuzzy numbers based on the areas on the left and the right sides of fuzzy number. Computers & Mathematics with Applications 61, no. 2: pp. 431-442.

Downloads

Published

2023-12-23

How to Cite

Rets, V. O. (2023). Solution of the traveling salesman problem based on the annealing method with the fuzziness of the time perception. Bulletin of Taras Shevchenko National University of Kyiv. Physical and Mathematical Sciences, (2), 226–231. https://doi.org/10.17721/1812-5409.2023/2.39

Issue

Section

Computer Science and Informatics