Євген ІВОХІН, д-р фіз.-мат. наук, проф.
ORCID ID: 0000-0002-5826-7408
e-mail: ivohin@knu.ua
Київський національний університет імені Тараса Шевченка, Київ, Україна
Костянтин ЮШТІН, канд. фіз.-мат. наук, докторант
ORCID ID: 0009-0001-9881-2343
e-mail: gkons@mail.univ.kiev.ua
Київський національний університет імені Тараса Шевченка, Київ, Україна
DOI: https://doi.org/10.17721/AIT.2024.1.03
Анотація
В с т у п . Сформульовано та наведено методику пошуку оптимальної тривалості маршруту для розв’язання задачі комівояжера у випадку визначення часу переміщення між містами у вигляді нечітких трапецієподібних чисел. Метою роботи є розроблення алгоритму на основі оптимізації колонії мурах і використання цього методу для розв’язування задач комівояжера з достатньо великою кількістю міст транспортної мережі.
М е т о д и . Використано метод на основі алгоритму оптимізації мурашиної колонії.
Р е з у л ь т а т и . Для досягнення поставленої мети запропоновано схему реалізації оптимізаційного алгоритму, що за умови невеликої кількості ітерацій дозволяє отримувати наближені до оптимальних розв’язків результати пошуку шляхів у нечіткій задачі комівояжера. Запропонований підхід може бути використаний для пошуку раціонального шляху в ситуаціях із неточно заданою тривалістю переміщень між містами. Показано, що вибір основних параметрів алгоритму оптимізації колонії мурах суттєво не впливає на якість отриманого наближеного розв’язку. Приклади використання алгоритму підтверджують конструктивність підходу для розв’язання задачі комівояжера у випадку нечітко заданої тривалості переміщень.
В и с н о в к и . Запропоновано схему реалізації алгоритму оптимізації мурашиної колонії для пошуку найкращого шляху в задачі комівояжера зі змінною тривалістю переміщень між містами, розроблено комп’ютерну програму, яка дозволяє розв’язувати різні логістичні задачі, в основу яких покладено задачу комівояжера з нечітко визначеними параметрами руху у транспортній мережі.
К л ю ч о в і с л о в а : нечітка задача комівояжера, оптимізаційний метод мурашиної колонії, трапецієподібні нечіткі числа, дефазифікація, оцінювання ефективності.
Опубліковано
2024-12-20
Як цитувати
Євген ІВОХІН, Костянтин ЮШТІН “ ВИКОРИСТАННЯ МУРАШИНОГО АЛГОРИТМУ ДЛЯ РОЗВ’ЯЗАННЯ НЕЧІТКОЇ ЗАДАЧІ КОМІВОЯЖЕРА” Сучасні інформаційні технології №1(3), pp. 23–31, 2024
Номер
Сучасні інформаційні технології № 1 (3), 2024
Розділ
Прикладні інформаційні системи та технології
Список використаних джерел
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.