ДЕКОМПОЗИЦІЯ ЗАГАЛЬНОЇ ЗАДАЧІ КОМІВОЯЖЕРА ТА НАБЛИЖЕНИЙ МЕТОД ЇЇ РОЗВ’ЯЗКУ

Abstract

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