Abstract (ukr):
Запропоновано підхід до декомпозиції загальної задачі комівояжера (ЗЗК) на задачі меншої
розмірності, що дозволяє суттєво прискорити процедуру пошуку розв’язку. Крім того,
пропонується швидкодіючий наближений метод розв’язку ЗЗК, який полягає у послідовному
виконанні двох відомих алгоритмів комбінаторної оптимізації. Спочатку ЗЗК зводиться до
метричної симетричної задачі комівояжера (СЗК) поліноміальним перетворенням вихідного
зваженого графа в повний метричний граф. Потім знаходиться наближене рішення метричної
СЗК, що дозволяє визначити шуканий маршрут.