Базилевич Р., Кузь Б. Особливості декомпозиції задачі комівояжера

УДК 519.16

Р. Базилевич, Б. Кузь
Національний університет “Львівська політехніка”,
кафедра програмного забезпечення

ОСОБЛИВОСТІ ДЕКОМПОЗИЦІЇ ЗАДАЧІ КОМІВОЯЖЕРА

© Базилевич Р., Кузь Б., 2011

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

Decomposition algorithms for TSP are developed. The paper proposes to split the full problem into four stages: decomposition into clusters, finding the partial solutions for each cluster, merging partial solution into full solution and its optimization. Approach could reduce the computation time with small quality losses.
Keywords: traveling salesman problem, combinatorial optimization, decomposition

Література – 6