Задача коммивояжёра

Условие задачи коммивояжёра задаётся рёберно-взвешенным (ориентированным) графом ${\displaystyle G=(V,E,c)}$, ${\displaystyle \mid V\mid =n}$, весовая функция ${\displaystyle c\colon E\to \mathbb {R} _{+}}$ которого сопоставляет произвольному ребру ${\displaystyle \left\{v,w\right\}}$ – дуге ${\displaystyle (v,w)}$ транспортную издержку ${\displaystyle c_{vw}=c(v,w)}$. Допустимыми решениями задачи являются гамильтоновы циклы (перестановки множества вершин) ${\displaystyle v_{\pi (1)},v_{\pi (2)},\ldots ,v_{\pi (n)}}$, стоимость которых задаётся соотношением

${\displaystyle c(v_{\pi (n)},c_{\pi (1)})+\sum _{i=1}^{n-1}c(v_{\pi (i)},v_{\pi (i+1)})}$.

Задача состоит в нахождении цикла минимальной стоимости.

Заметим, что без ограничения общности граф ${\displaystyle G}$ может полагаться полным, т. к. произвольные несмежные вершины ${\displaystyle v}$ и ${\displaystyle w}$ легко могут быть соединены ребром достаточно большой стоимости ${\displaystyle c(v,w)=M}$.

Принято различать постановки, заданные на неориентированных и ориентированных графах. По традиции задачей коммивояжёра принято называть именно первую версию задачи, с симметричной функцией транспортных издержек. В свою очередь задачу на ориентированном графе, с несимметричной функцией затрат, называют асимметричной задачей коммивояжёра (англ. Asymmetric Traveling Salesman Problem – ATSP).

Выделяют несколько специальных случаев классической симметричной задачи. Так, постановка, в которой для произвольных вершин ${\displaystyle u}$, ${\displaystyle v}$ и ${\displaystyle w}$ справедливо неравенство треугольника

${\displaystyle c(v,w)\leqslant c(v,u)+c(u,w)}$ (1),

называется метрической. Если множество вершин ${\displaystyle V}$ является подмножеством конечномерного числового пространства, а транспортные издержки определяются евклидовыми расстояниями между вершинами, постановку задачи также принято называть евклидовой.

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

Исторически первая и, по-видимому, наиболее исследованная в теоретическом плане формулировка была приведена в работе Дж. Данцига, Р. Фалкерсона и С. Джонсона (^[7]). Остановившись для определённости на рассмотрении асимметричной постановки задачи коммивояжёра, сопоставим произвольному гамильтонову контуру характеристический вектор ${\displaystyle x\colon E\to \{0,1\}}$, значение произвольной координаты ${\displaystyle x_{uw}}$ которого, соответствующей дуге ${\displaystyle e=(v,w)}$, задаётся соотношением

${\displaystyle x_{vw}={\begin{cases}1,&{\text{если дуга принадлежит данному маршруту,}}\\0,&{\text{в противном случае.}}\end{cases}}}$

Зададимся стандартными обозначениями

${\displaystyle {\begin{aligned}\delta ^{+}(U)=\{(v,w)\in E\colon (v\in U)\wedge (w\not \in U)\},\\\delta ^{-}(U)=\{(v,w)\in E\colon (v\not \in U)\wedge (w\in U)\}\end{aligned}}}$

для исходящего и входящего разрезов произвольного собственного подмножества ${\displaystyle \varnothing \neq U\subset V}$ и ${\displaystyle \delta (U)=\delta ^{+}(U)\cup \delta ^{-}(U)}$ для их объединения, а также ${\displaystyle \delta ^{+}(v)}$, ${\displaystyle \delta ^{-}(v)}$ и ${\displaystyle \delta (v)}$ для частного случая разрезов, порождаемого подмножеством ${\displaystyle U=\{v\}}$. Приведённая ниже задача булевой линейной оптимизации известна в литературе как модель Данцига – Фалкерсона – Джонсона:

${\displaystyle {\begin{array}{rll}{\text{DFJ}}:\min &\sum \limits _{(v,w)\in E}c_{vw}x_{vw},&\\\\{\text{s.t.}}&\sum _{w\in \delta ^{+}(v)}x_{vw}=\sum _{w\in \delta ^{-}(v)}x_{wv}=1&(v\in V)\\\\\%&\sum _{(v,w):\ v,w\in U}x_{vw}\leqslant \mid U\mid -1&(U\subset V,\mid U\mid \geqslant 2)\\&\sum _{(v,w)\in \delta (U)}x_{vw}\geqslant 2&(\varnothing \neq U\subset V)\\\\&x_{vw}\in \{0,1\}&((v,w)\in E).\end{array}}}$

Нередко модель ${\displaystyle {\text{DFJ}}}$ рассматривается в эквивалентной постановке, где подсистема

${\displaystyle \sum _{(v,w)\in \delta (U)}x_{vw}\geqslant 2\quad (\varnothing \neq U\subset V)}$

заменяется подсистемой

${\displaystyle \sum _{(v,w):\ v,w\in U}x_{vw}\leqslant \mid U\mid -1\quad (U\subset V,\mid U\mid \geqslant 2)}$.

Заметим также, обе подсистемы содержат экспоненциальное (по отношению к числу вершин графа) число неравенств, что в определённом смысле затрудняет непосредственное применение модели для численного решения исходной задачи. Поэтому наряду с данной классической моделью развиваются компактные модели MILP, число ограничений и переменных в которых ограничено сверху некоторым полиномом от ${\displaystyle n}$, первой из них и одной из самых компактных, по-видимому, является модель Миллера – Такера – Землина, предложенная в работе Integer Programming Formulation of Traveling Salesman Problems (^[8]).

${\displaystyle {\begin{array}{rll}{\text{MTZ}}:\min &\sum \limits _{(v,w)\in E}c_{vw}x_{vw},&\\\\{\text{s.t.}}&\sum _{w\in \delta ^{+}(v)}x_{vw}=\sum _{w\in \delta ^{-}(v)}x_{wv}=1&(v\in V)\\\\\%&\sum _{(v,w):\ v,w\in U}x_{vw}\leqslant \mid U\mid -1&(U\subset V,\mid U\mid \geqslant 2)\\\%&\sum _{(v,w)\in \delta (U)}x_{vw}\geqslant 2&(\varnothing \neq U\subset V)\\&y_{v}-y_{w}+(n-1)x_{vw}\leqslant n-2&(v,w\in V\setminus \{v_{1}\},v\neq w)\\\\&x_{vw}\in \{0,1\}&((v,w)\in E)\\\\&y_{v}\in \mathbb {Z} _{+}&(v\in V\setminus \{v_{1}\}).\end{array}}}$

Последующие результаты в области совершенствования целочисленных моделей для задачи коммивояжёра получены в работах (^[9]; ^[10]; ^[11]). На сегодня наиболее эффективными (с точки зрения точности нижних оценок соответствующих вещественных релаксаций) считаются результаты, приведённые в книгах New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints (^[12]) и Combining and projecting flow models for the (precedence constrained) asymmetric traveling salesman problem (^[13]).

Как следует из классической работы Р. Карпа (^[14]), задача коммивояжёра ${\displaystyle NP}$-трудна в сильном смысле, т. е. наличие точного алгоритма, находящего оптимальное решение задачи за полиномиальное или псевдополиномиальное время от длины записи её условия влечёт равенство ${\displaystyle P=NP}$. Результат следует из полиномиальной сводимости к данной задаче ${\displaystyle NP}$-полной задачи «Гамильтонов цикл». Известно также, что задача коммивояжёра сохраняет труднорешаемость даже в чрезвычайно специфических постановках, например на евклидовой плоскости, как показано в известной работе Х. Пападимитриу (^[15]).

Как и для многих задач комбинаторной оптимизации, оптимальное решение задачи коммивояжёра может быть найдено полным перебором, путём перечисления всех перестановок вершин графа ${\displaystyle G}$, с трудоёмкостью ${\displaystyle O((n-1)!)}$. См. также «О большое».

Один из известных подходов к проектированию точных алгоритмов для задачи коммивояжёра опирается на фундаментальные результаты Р. Беллмана (^[16]) и М. Хелда – Р. Карпа (^[17]) и связан с развитием метода динамического программирования (см., например, Меламед. 1989; Ченцов. 1998). Классическая схема динамического программирования находит оптимальное решение задачи за время ${\displaystyle O(n^{2}\,2^{n})}$ и при затратах памяти ${\displaystyle O({\sqrt {n}}\,2^{n})}$.

Другой известный подход к построению точных алгоритмов для задачи коммивояжёра и её обобщений опирается на результаты в области полиэдральной теории допустимых маршрутов задачи (^[18]; ^[19]) и связан с проектированием эффективных методов ветвей и границ (англ. branch-and-bound) и ветвей и отсечений (англ. branch-and-cut) (см., например, ^[20]; ^[21]; ^[22]; ^[23]; ^[24]; ^[25]).

Несмотря на математическую элегантность и ряд вычислительных преимуществ, использование обсуждавшихся выше алгоритмов ограничено постановками относительно малого размера, ввиду ${\displaystyle NP}$-трудности исследуемой задачи коммивояжёра. Поэтому история её алгоритмического анализа тесно связана с развитием метаэвристических и эвристических алгоритмов (^[26]; ^[27]). Известно (см., например, ^[28]; ^[29]), что эвристические алгоритмы нередко демонстрируют удивительную производительность, позволяя находить близкие к оптимальным или даже оптимальные решения для постановок задачи большого размера, возникающих в практических приложениях. Кроме того, использование таких алгоритмов в составе методов ветвления в качестве первичных эвристик (англ. primal heuristics), как правило, приводит к существенному ускорению последних.

Наибольшего развития в контексте задачи коммивояжёра получили алгоритмы локального поиска (^[30]; ^[31]; ^[32]), восходящие к классическому алгоритму С. Лина (Линя) и Б. Кернигана (^[33]) генетические и меметические алгоритмы Г. Гутина и Д. Карапетяна (^[34]; ^[35]), алгоритмы поиска с переменными окрестностями (англ. Variable Neighborhood Search – VNS) (^[36]; ^[37]; ^[38]) и алгоритмы адаптивного поиска в больших окрестностях (англ. Adaptive Search in Large Neighborhoods – ALNS) (^[39]; ^[40]).

Общая постановка задачи коммивояжёра не аппроксимируема в классе приближённых алгоритмов с полиномиальной трудоёмкостью. В частности, как следует из работы P-Complete Approximation Problems (^[41]), наличие полиномиального приближённого алгоритма с точностью ${\displaystyle O(2^{\operatorname {poly} (n)})}$ влечёт равенство ${\displaystyle P=NP}$.

Многие важные частные случаи задачи, наоборот, успешно аппроксимируются в классе полиномиальных алгоритмов. Действительно, постановки задачи (симметричная и асимметричная), функции транспортных издержек которых удовлетворяют неравенству треугольника ${\displaystyle (1)}$, принадлежат классу ${\displaystyle {\text{APX}}}$ оптимизационных задач, обладающих полиномиальными приближёнными алгоритмами с фиксированными (константными) оценками точности.

Для метрической задачи коммивояжёра хорошо известен ${\displaystyle 3/2}$-приближённый алгоритм Кристофидеса – Сердюкова (Christofides. 1975; Сердюков. 1978) с трудоёмкостью ${\displaystyle O(n^{3})}$, состоящий в последовательном решении трёх вспомогательных экстремальных задач на графах: поиска остовного дерева минимального веса, совершённого паросочетания минимальной стоимости и кратчайшего эйлерова цикла, каждая из которых полиномиально разрешима.

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

В работе 2018 г. О. Свенссоном, Я. Тарнавским и Л. Вегом (^[42]) для асимметричной задачи с неравенством треугольника впервые предложен приближённый алгоритм с константной оценкой точности ${\displaystyle 5500}$. В недавней работе этих авторов (^[43]) и статьях В. Трауб и Й. Вигена (^[44]; ^[45]) данную оценку удалось существенно улучшить, до ${\displaystyle 509}$ и ${\displaystyle 22+\varepsilon }$ соответственно. Как в своё время алгоритм Кристофидеса – Сердюкова, эти результаты открыли возможность проектирования эффективных приближённых алгоритмов для широкого класса асимметричных комбинаторных задач (^[46]). Поэтому теоретическая значимость их вряд ли может быть переоценена, несмотря на то что с практической точки зрения полученные оценки точности по-прежнему представляются далёкими от идеала.

Для более узких специальных случаев задачи наиболее известны результаты С. Ароры (^[47]) и Дж. Митчелла (^[48]), впервые обосновавших аппроксимируемость задачи коммивояжёра на евклидовой плоскости в классе полиномиальных приближённых схем (англ. Polynomial Time Approximation Scheme – PTAS). Впоследствии алгоритм С. Ароры удалось обобщить на случай произвольных конечномерных числовых пространств. Наиболее общим на данный момент считается революционный результат Я. Бартала, Л. Готтлиба и Р. Краутгеймера (^[49]), обосновывающий существование PTAS для задачи коммивояжёра, заданной в метрическом пространстве произвольной фиксированной размерности удвоения. Разработанный этими авторами подход позволил разработать полиномиальные приближённые схемы для целого ряда близких задач комбинаторной оптимизации (см., например, ^[50]; ^[51]).