Алгоритм розв’язання задачі комівояжера великої розмірності методом «Тора»

2010;
: pp. 179 - 182
Authors: 

Р.П. Базилевич, Р.К. Кутельмах, Б. Кузь

Національний університет «Львівська політехніка», кафедра програмного забезпечення

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

Article describes approach to forming TSP solution from partial results. Approach reduces the cost of time to find solution for large size problems with small quality losses with comparison by the best heuristic algorithms.

  1. Helsgaun K. An effective implementation of the Lin–Kernighan Traveling Salesman Heuristic. – 2002.
  2. Базилевич Р.П., Кутельмах Р.К. Алгоритм оптимізації розв’язків задачі комівояжера у локальній області // Радіоелектронні і комп’ютерні системи. – Харків, 2009. – № 7 (41). – С. 41–45.
  3. Базилевич Р.П., Кутельмах Р.К. Оптимізація розв’язків задачі комівояжера методом послідовного сканування // Вісн. Нац. ун-ту «Львівська політехніка». – 2009. – № 638. – С. 254–260.
  4. Делоне Б.Н. О пустоте сферы // Изв. АН СССР. ОМЕН. – 1934. – № 4. – С. 793–800
  5. Kaplan C.S., Bosch R. TSP Art // Proceedings of Bridges 2005: Mathematical Connections in Art, Music and Science.