Eugene IVOHIN, DSc (Phys. & Math.), Prof.
ORCID ID: 0000-0002-5826-7408
e-mail: ivohin@knu.ua
Taras Shevchenko National University of Kyiv, Kyiv, Ukraine
Kostyantyn YUSНTIN, Doctoral Student
ORCID ID: 0009-0001-9881-2343
e-mail: gkons@mail.univ.kiev.ua
Taras Shevchenko National University of Kyiv, Kyiv, Ukraine
DOI: https://doi.org/10.17721/AIT.2024.1.03
Abstract
B a c k g r o u n d . The method of finding the optimal route length for the traveling salesman problem in the case of determining the time of movement between cities in the form of fuzzy trapezoidal numbers is formulated and given. The purpose of the work is to devel op an algorithm based on the optimization of an ant colony and use this method to solve problems of a traveling salesman with a sufficiently large number of cities in the transport network.
M e t h o d s . The method based on the ant colony optimization algorithm was used.
R e s u l t s . In order to achieve the goal, a scheme for the implementation of the optimization algorithm is proposed, which, under the condition of a small number of iterations, allows obtaining results close to optimal solutions in the vague problem of the traveling salesman. The proposed approach can be used to find a rational path in situations with an imprecisely specified duration of movements between cities. It is shown that the selection of the main parameters of the ant colony optimization algorithm does not significantly affect the quality of the obtained approximate solution. Examples of the use of the algorithm confirm the constructiveness of the approach to solving the traveling salesman problem in the case of a vaguely specified duration of movements.
C o n c l u s i o n s . A scheme for the implementation of the ant colony optimization algorithm for finding the best path in the problem of a traveling salesman with variable duration of movements between cities is proposed, a computer program has been developed that allows solving various logistics problems, which are based on the problem of a traveling salesman with vaguely defined movement parameters in the transport network.
K e y w o r d s : fuzzy traveling salesman problem, ant colony optimization method, trapezoidal fuzzy numbers, defuzzification, performance evaluation.
Published
2024-12-20
How to Cite
Eugene IVOHIN, Kostyantyn YUSНTIN “ USE OF ANT COLONY OPTIMIZATION ALGORITHM FOR SOLVING FUZZY PROBLEM OF TRAVELING SALESMAN” Advanced Information Technology, vol.1(3), pp. 23–31, 2024
Issue
Advanced Information Technology № 1 (3), 2024
Section
Applied information systems and technology
References
Bell, J., & McMullen, P. (2004). Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics, 18(1), 41–48. Bonavear, E., & Dorigo, M. (1999). Swarm Intelligence: from Natural to Artificial Systems. Oxford University Press.
Bullnheimer, B., Hartl, R. F., & Strauss, C. (1999). A New Rank-Based Version of the Ant System: A Computational Study. Central European Journal for Operations Research and Economics, 1(7), 25–38.
Dantzig, G. B., Fulkerson, D. R., & Johnson, S. M. (1954). Solution of a Large-scale Traveling Salesman Problem. Operations Research, 2.
Dorigo, М., Maniezzo, V., & Colorni, A. (1991). Positive feedback as a search strategy Dipartimento di Elettronica, Politecnico di Milano,Tech. Rep. 91-016. Dorigo, М., Maniezzo, V., & Colorni, A. (1996). The Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics. Part B. Cybernetics, 26(1), 29–41.
Ivohin, E. V., Gavrylenko, V. V., & Ivohina, K. E. (2023). On the recursive algorithm for solving the traveling salesman problem on the basis of the data flow optimization method. Radioelectronics, Computer Science, Control, 3, 141–147.
Kumar, A., & Gupta, A. (2011). Methods for solving fuzzy assignment problems and fuzzy travelling salesman problems with different membership functions. Fuzzy Information and Engineering, 3(1), 3–21.
Raspinelli, J. M., Lopes, H. S., & Freitas, A. A. (2002). Data Mining with an Ant Colony Optimization Algorithm. IEEE Trans. On Evolutionary Computation. Special issue on Ant Colony Algorithms, 6(4), 321–332.
Schoonderwoerd, R., Holland, O., Bruten, J., & Rothkranz, L. (1996). Ant-based load balancing in telecommunication networks. Adaptive Behavior, 5(2). Zhao, D., Luo, L., & Zhang, K. (2010). An improved ant colony optimization for the communication network routing problem. Mathematical and Computer Modelling, 52(11–12), 1976–1981.