USING THE ANT COLONY ALGORITHM TO SOLVE THE FUZZY TRAVELLING SALESMAN PROBLEM

Authors

  • Eugene IVOHIN Taras Shevchenko National University of Kyiv image/svg+xml Author
  • Kostantіn YUSHTIN Taras Shevchenko National University of Kyiv image/svg+xml Author
  • Valeriy HAVRILENKO National Transport University image/svg+xml Author
  • Maxym BOHUSLAVSKYI National Transport University image/svg+xml Author

DOI:

https://doi.org/10.17721/3041-2323.2024.185-202

Keywords:

fuzzy traveling salesman problem, ant colony optimization method, trapezoidal fuzzy numbers, defuzzification, performance evaluation

Abstract

The traveling salesman problem (TSP) is a classical combinatorial optimization problem that involves finding the shortest or fastest route among a set of cities. To formalize the uncertainty and imprecision in input data, often caused by subjective evaluations of the travel time intervals, this paper employs fuzzy numbers. The form of these fuzzy numbers is based on a Gaussian-like approach. This work examines the specifics of applying the ant colony optimization (ACO) algorithm and proposes an approach for its optimal use. The impact of the algorithm's parameters on the quality of the approximated best solution is analyzed. The problem is illustrated with
numerical examples involving a sufficiently large number of cities in the transportation network.

References

Bouamama, S., Blum, C., & Fages, J. (2019). An algorithm based on ant colony optimization for the minimum connected dominating set problem. Applied Soft Computing, 80, 672–686. https://doi.org/10.1016/j.asoc.2019.04.032

Dantzig, G. B., Fulkerson, D. R., & Johnson, S. M. (1954). Solution of a largescale traveling salesman problem. Operations Research, 2, 393–410. https://doi.org/10.1287/opre.2.4.393

Dorigo, M. (1992). Optimization, learning and natural algorithms [Doctoral dissertation]. Politecnico di Milano.

Dorigo, M. (2004). Ant colony optimization. MIT Press.

Dorigo, M., & Di Caro, G. A. (1999). Ant algorithms for discrete optimization. Artificial Life, 5(2), 137–172. https://doi.org/10.1162/106454699568728

Dorigo, M., & Di Caro, G. A. (1998). AntNet: Distributed stigmergetic control for communications networks. Journal of Artificial Intelligence Research, 9, 317–365. https://doi.org/10.1613/jair.525

Dubois, D., & Prade, H. (1987). The mean value of a fuzzy number. Fuzzy Sets and Systems, 24(3), 279–300. https://doi.org/10.1016/0165-0114(87)90189-9

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. Radio Electronics, Computer Science, Control, 3, 141–147. https://doi.org/10.15588/1607-3274-2023-3-16

Karaboga, D. (2009). A new design method based on artificial bee colony algorithm for digital IIR filters. Journal of the Franklin Institute, 346(4), 328–348. https://doi.org/10.1016/j.jfranklin.2008.11.003

Kennedy, J., & Eberhart, R. C. (2001). Swarm intelligence. Morgan Kaufmann.

Stützle, T., & Hoos, H. (2000). MAX–MIN ant system. Future Generation Computer Systems, 16(8), 889–914. https://doi.org/10.1016/S0167-739X(00)00043-1

Yang, L., Wang, X., He, Z., Wang, S., & Lin, J. (2024). Review of traveling salesman problem solution methods. In Bio-Inspired Computing: Theories and Applications (pp. 3–16). Communications in Computer and Information Science. https://doi.org/10.1007/978-3-031-50887-5_1

Title

Downloads

Published

01.10.2024

Issue

Vol. 1 No. 1 (2024): APPLIED INFORMATION SYSTEMS AND TECHNOLOGIES IN THE DIGITAL SOCIETY

Section

Статті

License

Copyright (c) 2024 Applied information systems and technologies in the digital society

Creative Commons License

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