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

Антон Юрійович Левченко

Анотація


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

Ключові слова


загальна задача комівояжера; наближений метод

Повний текст:

PDF

Пристатейна бібліографія ГОСТ


1. Бондаренко М.Ф. Компьютерная дискретная математика / М.Ф. Бондаренко, Н.В. Белоус, А.Г. Руткас. – Харьков : Компания СМИТ, 2004. – 476 с.

2. Панишев А.В. Модели и методы оптимизации замкнутых маршрутов на транспортной сети / А.В. Панишев, А.В. Морозов. – Житомир : ЖДТУ, 2014. – 315 с.

3. Левченко А.Ю. Приближенное решение общей задачи коммивояжера / А.Ю. Левченко // Інформатика та системні науки (ІСН-2011) : матер. Всеукр. науково-практ. конф. (м. Полтава, 17–19 берез. 2011 р.). – Полтава, 2011. – С. 160–163.

4. Information Models of Knowledge, ITHEA, Kiev-Sofia 2010(KDS 2010). Anatoliy Panishev, Anton Levchenko. Cycle routes optimization for not full graph. Pр. 435–441.

5. Левченко А.Ю. Декомпозиція загальної задачі комівояжера та наближений метод її розв’язку / А.Ю. Левченко // Вісник ЖДТУ. – Житомир, 2011. – С. 134–142.

6. Левченко А.Ю. Декомпозиция общей задачи коммивояжера для транспортных сетей / А.Ю. Левченко, И.В. Гаращенко // Труды XI междунар. научно-практ. конф. «Современные информационные и электронные технологии» (г. Одесса, 24–28 мая 2010 г.). – Т. 1. – Одесса, 2010. – С. 31.

7. Електронний ресурс. – Режим доступу : http://comopt.ifi.uni-heidelberg.de/software/ TSPLIB95/

8. Електронний ресурс. – Режим доступу : http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html

9. Електронний ресурс. – Режим доступу : http://neos.mcs.anl.gov/neos/solvers/ co:concorde/TSP.html

10. Електронний ресурс. – Режим доступу : http://www.akira.ruc.dk/~keld/ research/LKH/




DOI: https://doi.org/10.26642/tn-2015-4(75)-101-105

Copyright (c) 2016 Антон Юрійович Левченко

Це видання ліцензовано за ліцензією Creative Commons Із Зазначенням Авторства - Некомерційна 4.0 Міжнародна.