Івохін, Євген ВікторовичЄвген ВікторовичІвохінЮштін Костянтин2025-03-242025-03-242024Івохін Є., Юштін К. Використання мурашиного алгоритму для розв'язання нечіткої задачі комівояжера. Сучасні інформаційні технології. 2024. № 1(3). С. 23-31.10.17721/AIT.2024.1.03https://ir.library.knu.ua/handle/15071834/6108В с т у п . Сформульовано та наведено методику пошуку оптимальної тривалості маршруту для розв’язання задачі комівояжера у випадку визначення часу переміщення між містами у вигляді нечітких трапецієподібних чисел. Метою роботи є розроблення алгоритму на основі оптимізації колонії мурах і використання цього методу для розв’язування задач комівояжера з достатньо великою кількістю міст транспортної мережі. М е т о д и . Використано метод на основі алгоритму оптимізації мурашиної колонії. Р е з у л ь т а т и . Для досягнення поставленої мети запропоновано схему реалізації оптимізаційного алгоритму, що за умови невеликої кількості ітерацій дозволяє отримувати наближені до оптимальних розв’язків результати пошуку шляхів у нечіткій задачі комівояжера. Запропонований підхід може бути використаний для пошуку раціонального шляху в ситуаціях із неточно заданою тривалістю переміщень між містами. Показано, що вибір основних параметрів алгоритму оптимізації колонії мурах суттєво не впливає на якість отриманого наближеного розв’язку. Приклади використання алгоритму підтверджують конструктивність підходу для розв’язання задачі комівояжера у випадку нечітко заданої тривалості переміщень. В и с н о в к и . Запропоновано схему реалізації алгоритму оптимізації мурашиної колонії для пошуку найкращого шляху в задачі комівояжера зі змінною тривалістю переміщень між містами, розроблено комп’ютерну програму, яка дозволяє розв’язувати різні логістичні задачі, в основу яких покладено задачу комівояжера з нечітко визначеними параметрами руху у транспортній мережі.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 develop 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.ukнечітка задача комівояжераоптимізаційний метод мурашиної колоніїтрапецієподібні нечіткі числадефазифікаціяоцінювання ефективностіfuzzy traveling salesman problemant colony optimization methodtrapezoidal fuzzy numbersdefuzzificationperformance evaluationСтаття