Обобщённая задача коммивояжёра — задача комбинаторной оптимизации, являющаяся обобщением хорошо известной задачи коммивояжёра . Исходными данными для задачи является множество вершин, разбиение этого множества на так называемые кластеры, а также матрица стоимостей перехода из одной вершины в другую. Задача заключается в нахождении кратчайшего замкнутого пути, который бы посетил по одной вершине в каждом кластере (существует также модификация, когда путь должен посетить хотя бы по одной вершине в каждом кластере).

В зависимости от свойств матрицы стоимостей, задача может быть симметричной, если матрица симметричная, или асимметричной в противном случае. Одним из наиболее часто рассматриваемых частных случаев симметричной задачи является евклидова или планарная задача, когда каждая вершина имеет свои координаты в пространстве, и стоимость перехода между вершинами соответствует евклидову расстоянию между соответствующими точками в пространстве.

Как и задача коммивояжёра , обобщённая задача коммивояжёра относится к классу NP-трудных задач . Для доказательства достаточно рассмотреть частный случай задачи, когда каждый кластер содержит ровно одну вершину, и задача сводится к простой задаче коммивояжёра, которая является NP-трудной.

Методы решения

Точные методы

Известно два эффективных метода точного решения обобщённой задачи коммивояжёра: Brunch-and-Cut , а также метод приведения обобщённой задачи к обычной задаче коммивояжёра, способы решения которой хорошо изучены .

В 2002 году показано , что обобщённая задача коммивояжера может быть сведена к обыкновенной задаче коммивояжера той же размерности заменой матрицы весов ^{[ источник не указан 3244 дня ]} .

Эвристические методы

Простые эвристические методы

К простейшим эвристическим методам решения обобщённой задачи коммивояжёра следует отнести жадный алгоритм , на каждом шаге выбирающий ребро наименьшей стоимости из множества рёбер, не нарушающих корректности решения, а также более эффективный метод ближайшего соседа (Nearest Neighbour), начинающий с произвольной вершины и на каждом шаге добавляющий к решению вершину, наиболее близкую к последней добавленной. Существуют также и другие эвристики, являющиеся модификациями известных эвристик для обычной задачи коммивояжёра.

В частности, часто используются следующие виды локального поиска :

• , широко применяемый во многих задачах комбинаторной оптимизации, сводится к удалению двух рёбер из тура и вставке двух новых рёбер, не нарушающих корректности решения (в случае 2-opt вставляемые рёбра определены однозначно). Тур считается локальным минимумом, если в нём не существует ни одной пары рёбер, замена которых привела бы к улучшению решения. Таким образом, и размер окрестности, и сложность эвристики составляют ${\displaystyle O(m^{2})}$ , где ${\displaystyle m}$ — это число кластеров.
• подобен 2-opt, однако на каждом удаляется не два, а три ребра. В случае 3-opt, для восстановления корректности тура существует восемь нетривиальных способов вставки новых рёбер. Один из этих способов сохраняет направление каждого из фрагментов тура, что является важным свойством для асимметричных задач. Размер окрестности, и сложность эвристики составляют ${\displaystyle O(m^{3})}$ .
• Существуют естественные модификации 2-opt и 3-opt алгоритмов, дополнительно включающие поиск оптимальных вершин внутри изменяемых кластеров.
• «Insertion» является частным случаем 3-opt. На каждой итерации алгоритм удаляет вершину и пытается найти более выгодную для неё позицию. Сложность алгоритма составляет ${\displaystyle O(m^{2})}$ . Широко применяется модификация, рассматривающая вставку не только удалённой вершины, но и любой другой вершины соответствующего кластера.
• Кластерная оптимизация — локальный поиск, специфичный для обобщённой задачи коммивояжёра. Суть алгоритма заключается в нахождении кратчайшего пути через заданную последовательность кластеров. Иными словами, окрестность алгоритма включает в себя все туры, отличающиеся от исходного не более чем выбором вершин внутри каждого из кластеров. Размер исследуемой окрестности составляет:

${\displaystyle \prod _{i=1}^{m}|C_{i}|\,,}$ где ${\displaystyle C_{i}}$ — это кластер под номером ${\displaystyle i}$ . Применяя поиск кратчайшего пути в специально построенном графе, алгоритм находит локальный минимум за ${\displaystyle O(ms^{3})}$ , где ${\displaystyle s=\max _{i}|C_{i}|}$ . Таким образом, Cluster Optimization относится к классу , то есть исследует экспоненциальную окрестность за полиномиальное время.

Метаэвристики

Хорошо исследована область генетических алгоритмов, показавших свою эффективность для данной задачи. Первая работа в этой области принадлежит Снайдеру и Даскину , в дальнейшем важные результаты получены Зильбергольцем и Голденом , Гютеном и Карапетяном .

Примечания