Зада́ча коммивояжёра (англ. Traveling Salesman Problem – TSP), классическая задача комбинаторной оптимизации, результаты в области точного и приближённого решения которой во многом определили направления развития современной теории комбинаторных алгоритмов и теории вычислительной сложности (см., например, The Traveling Salesman Problem ... 2007).

Задача коммивояжёра и её модификации: задача коммивояжёра с ограничениями предшествования (англ. Precedence Constrained TSP), временными промежутками обслуживания (англ. TSP with Time Windows); ряд близких комбинаторных задач, среди которых обобщённая задача коммивояжёра (англ. Generalized TSP), задача маршрутизации транспортных средств (англ. Vehicle Routing Problem – VRP), задача ориентирования (англ. Orienteering Problem – OP), обладают широким спектром важных приложений в области исследования операций.

Содержательная постановка задачи коммивояжёра на удивление проста: «Задано множество из $n$ городов, каждой паре $v,w$ которых сопоставлена транспортная издержка $c_{vw},$ определяющая стоимость проезда из пункта $v$ в пункт $w$. Требуется указать циклический маршрут, посещающий каждый город в точности один раз и обладающий минимальной стоимостью». Вероятно, поэтому до начала 20 в. задачу коммивояжёра было принято относить к математическим головоломкам. Среди наиболее известных – опубликованная в 1859 г. У. Р. Гамильтоном игра «Вокруг света» (англ. icosian game), связанная с построением гамильтонова обхода множества вершин додекаэдра, и задача о кратчайшем маршруте велосипедиста (англ. bicycle tour) из известной книги С. Лойда (Loyd. 1914).

Формальная постановка в виде задачи комбинаторной оптимизации, по-видимому, впервые была представлена в работе К. Менгера. Систематические исследования в области алгоритмического анализа задачи восходят к классической работе Дж. Данцига, Р. Фалкерсона и С. Джонсона (Dantzig. 1954), а в области моделирования и индустриальных приложений – к работе Дж. Данцига и Дж. Рамсера (Dantzig. 1959). Наиболее подробные обзоры полученных за прошедшие десятилетия теоретических и прикладных результатов можно найти в монографиях (The Traveling Salesman Problem ... 2007; The traveling Salesman Problem ... 1991).

Математическая постановка

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

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

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

Выделяют несколько специальных случаев классической симметричной задачи. Так, постановка, в которой для произвольных вершин $u,$ $v$ и $w$ справедливо неравенство треугольника $$\tag{1}c(v,w)\leqslant c(v,u)+c(u,w),$$называется метрической. Если множество вершин $V$ является подмножеством конечномерного числового пространства, а транспортные издержки определяются евклидовыми расстояниями между вершинами, постановку задачи также принято называть евклидовой.

Целочисленные формулировки

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

Исторически первая и, по-видимому, наиболее исследованная в теоретическом плане формулировка была приведена в работе Дж. Данцига, Р. Фалкерсона и С. Джонсона (Dantzig. 1954). Остановившись для определённости на рассмотрении асимметричной постановки задачи коммивояжёра, сопоставим произвольному гамильтонову контуру характеристический вектор $x\colon E\to\{0,1\},$ значение произвольной координаты $x_{uw}$ которого, соответствующей дуге $e=(v,w),$ задаётся соотношением $$x_{vw}=\begin{cases}1, & \text{если дуга принадлежит данному маршруту,} \\ 0, & \text{в противном случае.} \end{cases}$$Зададимся стандартными обозначениями $$\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)\}$$для исходящего и входящего разрезов произвольного собственного подмножества $\varnothing\neq U\subset V$ и $\delta(U)=\delta^+(U)\cup\delta^-(U)$ для их объединения, а также $\delta^+(v),$ $\delta^-(v)$ и $\delta(v)$ для частного случая разрезов, порождаемого подмножеством $U=\{v\}.$ Приведённая ниже задача булевой линейной оптимизации известна в литературе как модель Данцига – Фалкерсона – Джонсона:

$$\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)\in \delta(U)}x_{vw} \geqslant 2 & (\varnothing\neq U\subset V)\\ \\ &x_{vw}\in \{0,1\}& ((v,w)\in E). \end{array}$$Нередко модель $\text{DFJ}$ рассматривается в эквивалентной постановке, где подсистема $$\sum_{(v,w)\in \delta(U)}x_{vw} \geqslant 2 \quad (\varnothing\neq U\subset V)$$заменяется подсистемой$$\sum_{(v,w):\ v,w\in U}x_{vw} \leqslant |U|-1\quad (U\subset V, |U|\geqslant 2).$$Заметим также, обе подсистемы содержат экспоненциальное (по отношению к числу вершин графа) число неравенств, что в определённом смысле затрудняет непосредственное применение модели для численного решения исходной задачи. Поэтому наряду с данной классической моделью развиваются компактные модели MILP, число ограничений и переменных в которых ограничено сверху некоторым полиномом от $n,$ первой из них и одной из самых компактных, по-видимому, является модель Миллера – Такера – Землина, предложенная в работе Integer Programming Formulation of Traveling Salesman Problems (Miller. 1960).$$\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)\\ \\ & 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}$$Последующие результаты в области совершенствования целочисленных моделей для задачи коммивояжёра получены в работах (Desrochers. 1991; Gouveia. 1999; Sherali. 2002). На сегодня наиболее эффективными (с точки зрения точности нижних оценок соответствующих вещественных релаксаций) считаются результаты, приведённые в книгах New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints (Sarin. 2005) и Combining and projecting flow models for the (precedence constrained) asymmetric traveling salesman problem (Combining and projecting flow models ... 2018).

Вычислительная сложность

Как следует из классической работы Р. Карпа (Karp. 1972), задача коммивояжёра $NP$-трудна в сильном смысле, т. е. наличие точного алгоритма, находящего оптимальное решение задачи за полиномиальное или псевдополиномиальное время от длины записи её условия влечёт равенство $P=NP.$ Результат следует из полиномиальной сводимости к данной задаче $NP$-полной задачи «Гамильтонов цикл». Известно также, что задача коммивояжёра сохраняет труднорешаемость даже в чрезвычайно специфических постановках, например на евклидовой плоскости, как показано в известной работе Х. Пападимитриу (Papadimitriou. 1977).

Точные алгоритмы

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

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

Другой известный подход к построению точных алгоритмов для задачи коммивояжёра и её обобщений опирается на результаты в области полиэдральной теории допустимых маршрутов задачи (The Traveling Salesman Problem ... 2007; The Traveling Salesman Problem ... 1991) и связан с проектированием эффективных методов ветвей и границ (англ. branch-and-bound) и ветвей и отсечений (англ. branch-and-cut) (см., например, Padberg. 1991; Ascheuer. 2000; Hoffman. 2013; Gouveia. 2015; A branch-and-cut algorithm ... 2020; Precedence constrained generalized traveling salesman problem ... 2023).

Эвристические алгоритмы

Несмотря на математическую элегантность и ряд вычислительных преимуществ, использование обсуждавшихся выше алгоритмов ограничено постановками относительно малого размера, ввиду $NP$-трудности исследуемой задачи коммивояжёра. Поэтому история её алгоритмического анализа тесно связана с развитием метаэвристических и эвристических алгоритмов (The Traveling Salesman Problem ... 2007; Handbook of Metaheuristics. 2019). Известно (см., например, Traveling salesman problem heuristics ... 2011; Smith. 2017), что эвристические алгоритмы нередко демонстрируют удивительную производительность, позволяя находить близкие к оптимальным или даже оптимальные решения для постановок задачи большого размера, возникающих в практических приложениях. Кроме того, использование таких алгоритмов в составе методов ветвления в качестве первичных эвристик (англ. primal heuristics), как правило, приводит к существенному ускорению последних.

Наибольшего развития в контексте задачи коммивояжёра получили алгоритмы локального поиска (Helsgaun. 2000; Helsgaun. 2009; Helsgaun. 2014), восходящие к классическому алгоритму С. Лина (Линя) и Б. Кернигана (Lin. 1973) генетические и меметические алгоритмы Г. Гутина и Д. Карапетяна (Gutin. 2010; Gutin. 2011), алгоритмы поиска с переменными окрестностями (англ. Variable Neighborhood Search – VNS) (Hansen. 1999; Hore. 2018; Karakostas. 2022) и алгоритмы адаптивного поиска в больших окрестностях (англ. Adaptive Search in Large Neighborhoods – ALNS) (Smith. 2017; Ropke. 2006).

Приближённые алгоритмы с теоретическими гарантиями

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

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

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

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

В работе 2018 г. О. Свенссоном, Я. Тарнавским и Л. Вегом (Svensson. 2018) для асимметричной задачи с неравенством треугольника впервые предложен приближённый алгоритм с константной оценкой точности $5500.$ В недавней работе этих авторов (Svensson. 2020) и статьях В. Трауб и Й. Вигена (Traub. 2020; Traub. 2022) данную оценку удалось существенно улучшить, до $509$ и $22+\varepsilon$ соответственно. Как в своё время алгоритм Кристофидеса – Сердюкова, эти результаты открыли возможность проектирования эффективных приближённых алгоритмов для широкого класса асимметричных комбинаторных задач (Khachay. 2022). Поэтому теоретическая значимость их вряд ли может быть переоценена, несмотря на то что с практической точки зрения полученные оценки точности по-прежнему представляются далёкими от идеала.

Для более узких специальных случаев задачи наиболее известны результаты С. Ароры (Arora. 1998) и Дж. Митчелла (Mitchell. 1999), впервые обосновавших аппроксимируемость задачи коммивояжёра на евклидовой плоскости в классе полиномиальных приближённых схем (англ. Polynomial Time Approximation Scheme – PTAS). Впоследствии алгоритм С. Ароры удалось обобщить на случай произвольных конечномерных числовых пространств. Наиболее общим на данный момент считается революционный результат Я. Бартала, Л. Готтлиба и Р. Краутгеймера (Bartal. 2016), обосновывающий существование PTAS для задачи коммивояжёра, заданной в метрическом пространстве произвольной фиксированной размерности удвоения. Разработанный этими авторами подход позволил разработать полиномиальные приближённые схемы для целого ряда близких задач комбинаторной оптимизации (см., например, Chan. 2018; Khachay. 2021).