Досліджено алгоритм для оптимізації розв’язання задачі комівояжера. Зменшення довжини шляху забезпечується обміном ребер, які відповідають умові оптимізації.
The algorithm for TSP solution optimization is investigated. Tour minimization is performed by swapping of edges, which satisfy optimization criteria.
Запропоновано метод об’єднання часткових розв’язків, отриманих для локальних областей, утворених кластеризацією робочого поля для задачі комівояжера в загальний розв’язок. Метод зменшує затрати часу на пошуки розв’язку для задач великих та надвеликих розмірностей із незначними втратами якості, порівняно з результатами, отриманими за допомогою найкращих евристичних алгоритмів.
Описано три підходи до кластеризації робочого поля для задачі комівояжера, що забезпечує поділ множини точок на частини з заданими обмеженнями. Один із відомих алгоритмів використовується для отримання розв’язків в кожному кластері з подальшим зшиванням часткових розв’язків.
Article describes three approaches to clustering set of points of TSP into subsets with given constraints. One of the well-known basic algorithms is used for solutions at every cluster with further joining of partial solutions.
Запропоновано новий метод приєднання часкових розв’язків у підмножинах при декомпозиції задачі комівояжера. Алгоритм передбачає розбиття вхідної множини точок на підмножини. Процес розв’язання починається в певній підмножині, де розв’язок
відомий. Розв’язок у наступній (сусідній) підмножині утворюється за допомогою розширення існуючого розв’язку.
Розглянуто можливість використання колективу автономних агентів для розв’я- зання задач комбінаторної оптимізації на прикладі розв’язання задачі комівояжера.