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

Abstract

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