Особливості декомпозиції задачі комівояжера

Abstract

Розроблено алгоритми декомпозиції задачі комівояжера. Запропоновано виділити чотири етапи розв’язання задачі: кластеризація множини вхідних точок, розв’язання часткових задач у виділених кластерах, зшивання часткових розв’язків у загальний розв’язок та його оптимізація. Метод дає змогу зменшити затрати часу на пошук розв’язку з незначними втратами якості. 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.