Сравнительный анализ алгоритмов решения обобщенной задачи коммивояжера

Обобщенная задача коммивояжера является расширением широко-известной NP-трудной задачи коммивояжера. В обобщенной задаче коммивояжера все множество городов разделено на так называемые кластеры. Задача заключается в нахождении минимального по длине маршрута, проходящего через каждый кластер ровно один раз. Стоит отметить, что вышеописанная задача является классическим вариантом обобщенной задачи коммивояжера. Существуют варианты задачи, где каждый город может принадлежать разным кластерами; маршрут может проходить через несколько городов в кластере; может быть задано несколько коммивояжеров, для каждого из которых нужно найти свой маршрут. Это лишь немногие виды задач, которые существуют. Даже для классического варианта обобщенной задачи коммивояжера существует несколько подходов к решению задач: преобразование исходной задачи в смежную задачу маршрутизации; сокращение размерности исходной задачи; точные и приближенные алгоритмы решения. Целью работы является изучение обобщенной задачи коммивояжера, а также исследование временных и точностных характеристик различных подходов к решению данной задачи. Задачами работы являются: Изучение различных вариантов обобщенной задачи коммивояжера; Изучение различных подходов решения обобщенной задачи коммивояжера; Исследование временных и точностных характеристик алгоритмов преобразования исходной задачи в смежные задачи маршрутизации, алгоритмов сокращения размерности и приближенных алгоритмов решения задачи. В результате проведенной работы был предложен новый алгоритм CM-Search неточной трансформации, который позволяет получить, в среднем, отклонение 7.6% от оптимального при решении преобразованной задачи алгоритмом GLKH. Как показали проведенные эксперименты, алгоритм GLKH является лидеров среди эвристических алгоритмов и способен решить задачу с отклонением от оптимального в среднем 0% (на протестированном наборе).