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

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

Оптимизационная версия задачи является NP-трудной, а версия принятия решения (существует ли тур стоимости не более $L$) — NP-полной. Точные алгоритмы позволяют находить оптимальные решения для экземпляров с десятками тысяч городов, эвристики дают близкие к оптимальным результаты для миллионов городов. Задача применяется в логистике, производстве микросхем, секвенировании ДНК и других областях.

История и предпосылки

Ранние упоминания (XIX век)

Практические аспекты задачи упоминались ещё в 1832 году в немецком справочнике для коммивояжёров Der Handlungsreisende, содержавшем примеры туров по Германии и Швейцарии без математической формализации. В XIX веке ирландский математик Уильям Роуэн Гамильтон и британский математик Томас Киркман изучали гамильтоновы циклы — в частности, в связи с icosian game Гамильтона, представлявшей собой задачу обхода вершин додекаэдра.

Математическая формализация (1930-е годы)

Математическая формулировка появилась в 1930-е годы. Карл Менгер в Вене и Гарварде определил задачу как «проблему посыльного» (Botenproblem), рассмотрел алгоритм полного перебора и отметил неоптимальность эвристики ближайшего соседа. В тот же период Меррилл Флад изучал её применительно к маршрутизации школьных автобусов, а Хасслер Уитни в Принстоне назвал её «проблемой 48 штатов».

Термин «traveling salesman problem» впервые появился в 1949 году в отчёте Джулии Робинсон (RAND).

Ключевые прорывы (1954–1976)

В 1954 году Джордж Данциг, Рей Фалкерсон и Селмер Джонсон предложили формулировку задачи в виде целочисленного линейного программирования с отсекающими плоскостями и решили экземпляр с 49 городами США (по одному в каждом из 48 штатов плюс Вашингтон; оптимальный тур — 12 345 миль).

В 1962 году Майкл Хелд и Ричард Карп разработали алгоритм динамического программирования со сложностью $O(n^2\cdot 2^n)$.

В 1972 году Ричард Карп доказал NP-полноту версии принятия решения путём сведения от задачи о гамильтоновом цикле.

В 1976 году Никос Христофидис (независимо Анатолий Сердюков) разработал алгоритм с гарантией аппроксимации $3/2$ для метрического случая — результат, остававшийся лучшим более 40 лет.

Эпоха вычислительных рекордов (1991 — настоящее время)

В 1991 году Герхард Райнельт опубликовал библиотеку тестовых экземпляров TSPLIB, ставшую стандартом для сравнения алгоритмов.

С 1990-х годов развитие метода ветвей и отсечений (branch-and-cut) в решателе Concorde (Дэвид Эпплгейт, Роберт Биксби, Вацлав Хватал, Уильям Кук) позволило решать крупные экземпляры оптимально. Крупнейший оптимально решённый экземпляр — pla85900 (85 900 точек микросхемы, 2006 год, эквивалент ~136 CPU-лет на оборудовании того времени).

Сводная хронология

Год	Событие
1832	Немецкий справочник Der Handlungsreisende с практическими примерами туров
XIX в.	Изучение гамильтоновых циклов (Гамильтон, Киркман)
1930-е	Математическая формализация (Менгер, Уитни, Флад)
1949	Термин «traveling salesman problem» (Джулия Робинсон, RAND)
1954	Решение 49-городского экземпляра методом отсекающих плоскостей (Данциг, Фалкерсон, Джонсон)
1962	Алгоритм динамического программирования (Хелд, Карп)
1972	Доказательство NP-полноты (Карп)
1976	3/2-аппроксимация для метрического случая (Христофидис; Сердюков)
1991	Публикация библиотеки TSPLIB (Райнельт)
1998	PTAS для евклидова TSP (Арора)
2001	Оптимальное решение для 15 112 городов Германии (Concorde)
2006	Оптимальное решение для 85 900 точек микросхемы (Concorde)
2021	Улучшение аппроксимации до $3/2-\epsilon$ (Karlin et al.)

Источники: Applegate et al. (2006); University of Waterloo TSP project.

Теоретические основы

Формальная постановка задачи

Задача формулируется на полном графе $G=(V,E)$ с $|V|=n$ вершинами и весами $c:E\to {\mathbb{ℝ}}_{\ge 0}$. Цель — найти гамильтонов цикл минимальной суммарной стоимости:

$\underset{\pi \in \mathrm{\Pi }}{\min }\sum _{i=1}^n{c}_{\pi (i),\pi (i+1)}$

где $\mathrm{\Pi }$ — множество всех гамильтоновых циклов, $\pi (n+1)=\pi (1)$.

Различают несколько важных вариантов задачи:

• Симметричная ЗК — $c_{ij}=c_{ji}$ (неориентированный граф).
• Асимметричная ЗК — веса произвольны (ориентированный граф).
• Метрическая ЗК — выполняется неравенство треугольника: $c_{ij}+c_{jk}\ge c_{ik}$.
• Евклидова ЗК — города представлены точками в плоскости, расстояния — евклидовы.

Формулировка целочисленного линейного программирования

Стандартная формулировка DFJ (Данциг–Фалкерсон–Джонсон, 1954):

$\min \sum _{i\ne j}{c}_{ij}{x}_{ij}$

при ограничениях:

$\sum _{j\ne i}{x}_{ij}=1,\sum _{i\ne j}{x}_{ij}=1(\mathrm{\forall }i\in V)\text{(степенные ограничения)}$

$$\begin{gathered} \sum _{i,j\in S, \\ i\ne j}{x}_{ij}\le |S|-1(\mathrm{\forall }S\subset V,2\le |S|\le n-2)\text{(устранение подтуров)} \end{gathered}$$

$x_{ij}\in \{0,1\}$

Число ограничений устранения подтуров экспоненциально ($2^n$), поэтому на практике они генерируются динамически в ходе решения LP-релаксации.

Альтернативная формулировка MTZ (Миллер–Такер–Землин) использует переменные порядка посещения и имеет полиномиальное число ограничений, но более слабую LP-релаксацию.

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

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

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

Существенным недостатком данной постановки является очень большое число ограничений на устранение подтуров: их количество растёт экспоненциально с увеличением числа городов. По этой причине на практике такие ограничения обычно не задаются заранее полностью, а добавляются по мере необходимости в ходе решения LP-релаксации.

Альтернативой является формулировка Миллера—Такера—Землина (MTZ), в которой вместо явного перечисления ограничений на подтуры используются дополнительные переменные, задающие порядок посещения городов. Это позволяет получить полиномиальное число ограничений и сделать модель более компактной. Однако такая формулировка обычно даёт более слабую LP-релаксацию по сравнению с DFJ.

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

• Версия принятия решения принадлежит классу NP-полных задач (Карп, 1972).
• Оптимизационная версия NP-трудна даже для евклидовых расстояний (Papadimitriou, 1977).
• Метрический TSP является APX-полным: для него не существует PTAS, если P ≠ NP.
• Для евклидова TSP существует полиномиальная схема приближённого решения (PTAS) с гарантией $1+\epsilon$ для произвольного $\epsilon >0$ (Арора, 1998).

Асимптотические результаты

Для $n$ случайных точек, равномерно распределённых в единичном квадрате, асимптотическая длина оптимального тура описывается теоремой Бирдвуда–Халтон–Хаммерсли (1959):

$L_n\sim \beta \sqrt{n}$

где $\beta$ — константа Бирдвуда–Халтон–Хаммерсли; по численным оценкам, $\beta \approx 0,7124$.

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

Методы решения ЗК делятся на три класса: точные, приближённые (с гарантированной оценкой качества) и эвристические (без строгих гарантий).

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

Полный перебор. Простейший метод — перечисление всех $(n-1)!$ возможных туров. Сложность $O(n!)$ делает его непрактичным уже при $n>15$.

Динамическое программирование Хелда–Карпа (1962). Использует принцип оптимальности Беллмана: для каждого подмножества $S\subseteq V$ и конечной вершины $j\in S$ вычисляется стоимость кратчайшего пути, посещающего все вершины $S$ и оканчивающегося в $j$. Сложность по времени и памяти — $O(n^2\cdot 2^n)$, что практично до $n\approx 20-30$.

Ветвление и отсечения (Branch-and-cut). Основной метод для крупных экземпляров. Сочетает ветвление и границы с динамической генерацией отсекающих неравенств (subtour elimination, comb inequalities, clique-tree inequalities и др.) для усиления LP-релаксации DFJ-формулировки. Решатель Concorde является наиболее известной реализацией этого подхода.

Приближённые алгоритмы

Удвоение минимального остовного дерева. Построение MST, удвоение его рёбер, нахождение эйлерова цикла и сокращение (shortcutting) повторных вершин. Даёт 2-аппроксимацию для метрического TSP.

Алгоритм Христофидиса–Сердюкова (1976). Улучшает предыдущий подход: после построения MST находится минимальное совершенное паросочетание на вершинах нечётной степени, затем строится эйлеров тур и выполняется сокращение. Гарантия — не более $3/2\cdot \mathrm{O}\mathrm{P}\mathrm{T}$ для метрического TSP:

$C_{\text{алг}}\le \frac{3}{2}\cdot C_{\text{opt}}$

Этот результат оставался лучшим более 40 лет. В 2021 году Karlin, Klein и Oveis Gharan улучшили гарантию до $3/2-\epsilon$ с очень малым $\epsilon >10^{-36}$.

PTAS для евклидова случая. Алгоритм Ароры (1998) и Митчелла обеспечивает гарантию $(1+\epsilon )\cdot \mathrm{O}\mathrm{P}\mathrm{T}$ за время, полиномиальное по $n$ при фиксированном $\epsilon$.

Эвристики и метаэвристики

Алгоритм ближайшего соседа. Жадная конструктивная эвристика: из текущего города переход к ближайшему непосещённому. Сложность $O(n^2)$, аппроксимация — $\mathrm{\Theta }(\log n)$ в худшем случае для метрического TSP.

k-opt. Локальный поиск путём замены $k$ рёбер тура: 2-opt удаляет два ребра и переподключает фрагменты, 3-opt — три ребра.

Алгоритм Лина–Кернигана (1973) и LKH. Переменный k-opt с адаптивным выбором числа заменяемых рёбер. Модификация Хельсгауна (LKH) является одним из наиболее эффективных эвристических решателей: для экземпляров с миллионами городов решения отклоняются от оптимума в пределах 1–3 %.

Метаэвристики. К ним относятся:

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

Сравнение подходов

Метод	Сложность	Гарантия качества	Практический размер
Полный перебор	$O(n!)$	Точный	$n\le 15$
Динамическое программирование (Хелд–Карп)	$O(n^2\cdot 2^n)$	Точный	$n\le 25-30$
Branch-and-cut (Concorde)	Экспоненциальная (в худшем случае)	Точный	$n\le 85900$ (рекорд)
Удвоение MST	Полиномиальная	$\le 2\cdot \mathrm{O}\mathrm{P}\mathrm{T}$	Неограниченно
Христофидис–Сердюков	Полиномиальная	$\le 1,5\cdot \mathrm{O}\mathrm{P}\mathrm{T}$	Неограниченно
PTAS (Арора)	Полиномиальная при фикс. $\epsilon$	$\le (1+\epsilon )\cdot \mathrm{O}\mathrm{P}\mathrm{T}$	Евклидов случай
LKH	$O(n^{2,2})$ (эмпирич.)	Нет гарантии	Миллионы городов

Источники: Applegate et al. (2006); Laporte (1992); Cook (2012).

Ключевые результаты и вычислительные рекорды

Библиотека TSPLIB

Библиотека TSPLIB содержит более 100 экземпляров различной сложности — от десятков до 85 900 городов, включая геометрические, VLSI и реальные экземпляры. Все экземпляры TSPLIB решены оптимально.

Примечание: TSPLIB (Traveling Salesman Problem Library, часто называемая TSPLIB95) — это одна из самых авторитетных и широко используемых в мире библиотек стандартных тестовых экземпляров для Задачи коммивояжёра (TSP) и близких к ней комбинаторных задач оптимизации. Она служит де-факто золотым стандартом benchmarking’а в этой области уже более 35 лет (с 1991 года) и позволяет объективно сравнивать алгоритмы, обеспечивать воспроизводимость результатов и отслеживать научный прогресс.

Рекорды оптимальных решений

Год	Экземпляр	Число городов/точек	Метод	Длина тура	Источник
1954	49 штатов США	49	Отсекающие плоскости (DFJ)	12 345 миль	Dantzig et al.
~1987	—	2 392	Branch-and-cut	—	Padberg, Rinaldi
2001	Города Германии	15 112	Branch-and-cut (Concorde)	—	Applegate et al.
2004	Города Швеции	24 978	Concorde	~72 500 км	Applegate et al.
2005	Печатная плата	33 810	Concorde	66 048 945	Applegate et al.
2006	Микросхема (pla85900)	85 900	Concorde	142 382 641	Applegate et al.

Решение экземпляра pla85900 потребовало эквивалента ~136 CPU-лет на оборудовании 2006 года. Для случайных евклидовых экземпляров время работы Concorde растёт экспоненциально с $n$, однако реальные структурированные экземпляры часто оказываются значительно легче.

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

Эвристики LKH (Хельсгаун) решают экземпляры с миллионами городов за приемлемое время с отклонением от оптимума в пределах 1–3 %. Для стандартных экземпляров TSPLIB эвристики часто находят оптимальные или близкие к оптимальным решения.

Применение

Задача коммивояжёра возникает как модель или подзадача в широком спектре практических областей.

Логистика и транспорт

ЗК является ядром задачи маршрутизации транспортных средств (Vehicle Routing Problem, VRP). Оптимизация маршрутов доставки, курьерских служб и почтовых отправлений непосредственно сводится к вариантам ЗК. Многочисленные реальные логистические системы используют эвристики для ЗК в качестве компонентов маршрутизации.

Производство микросхем и печатных плат

В производстве печатных плат задача моделирует минимизацию перемещений сверлильной головки: города — отверстия, стоимость — время перемещения. Аналогичная задача возникает при укладке проводов и проектировании СБИС (VLSI). Именно экземпляр из этой области (pla85900) является крупнейшим оптимально решённым.

Геномика и биоинформатика

В геномике упорядочивание фрагментов ДНК по перекрытиям (задача кратчайшей надстроки, shortest superstring problem) редуцируется к ЗК. Фрагменты выступают в роли городов, а перекрытия — в роли расстояний.

Другие области

• Астрономия — минимизация перемещений телескопа между объектами наблюдения.
• Складская логистика — маршруты комплектации заказов.
• Кристаллография — определение структуры кристаллов методом рентгеновской дифракции.
• Робототехника — планирование траекторий.

Варианты и обобщения

Классическая ЗК породила ряд обобщений и вариантов, каждый из которых имеет собственные приложения и теоретические результаты:

• Множественная ЗК (mTSP) — несколько коммивояжёров обслуживают общее множество городов.
• Обобщённая ЗК (GTSP) — города разбиты на кластеры; требуется посетить хотя бы один город из каждого кластера.
• ЗК с временными окнами — каждый город должен быть посещён в определённый временной интервал.
• Prize-collecting TSP — за посещение городов начисляется выигрыш; штраф за пропуск.
• Асимметричная ЗК — стоимость проезда зависит от направления.

Ограничения и открытые проблемы

• NP-трудность. Точные алгоритмы имеют экспоненциальную сложность в худшем случае. Решение экземпляров с $n>10^5$ требует значительных вычислительных ресурсов и специализированных методов, хотя Concorde демонстрирует масштабируемость до $n\approx 10^5$ для структурированных данных.
• Аппроксимационный барьер. Для общего метрического TSP отсутствует PTAS; лучшая известная постоянная аппроксимации — около $3/2$ с малыми улучшениями (до $123/122$ в нижней границе сложности аппроксимации). Для неметрического TSP не существует полиномиального аппроксимационного алгоритма с постоянным коэффициентом (если P ≠ NP).
• Отсутствие гарантий у эвристик. Эвристики LKH и метаэвристики эмпирически эффективны, но не дают строгих гарантий качества решения.
• Память и масштабируемость. Динамическое программирование Хелда–Карпа ограничено памятью ($O(n\cdot 2^n)$). Branch-and-cut требует хранения proof-файлов для сертификации оптимальности крупных экземпляров.

Ключевые открытые проблемы включают: возможность существенного улучшения аппроксимационных констант для метрического TSP, связь с проблемой P vs NP, а также эффективность квантовых алгоритмов для ЗК.

Этические и регуляторные аспекты

Прямые этические или регуляторные аспекты для абстрактной задачи отсутствуют. В приложениях (логистика, транспорт) оптимизация маршрутов влияет на затраты энергии и выбросы, но специального регулирования для ЗК не существует. Воспроизводимость результатов обеспечивается открытыми библиотеками: TSPLIB свободно доступна для исследований, решатель Concorde распространяется для академического использования. Стандарты воспроизводимости в вычислительной математике поддерживаются хранением proof-файлов оптимальности (как в случае pla85900).

Перспективы и направления исследований

Направления дальнейших исследований включают:

• Гибридные методы — интеграция машинного обучения с классическими эвристиками для ускорения генерации отсекающих плоскостей и улучшения начальных решений.
• Квантовые алгоритмы — предварительные оценки (Ambainis et al., сложность $O(1,728^n)$) и квантовые приближённые методы (QAOA).
• Улучшение аппроксимаций — поиск лучших постоянных для метрического TSP и специальных метрик (графическая, планарная).
• Параллельные и распределённые вычисления — масштабирование точных и эвристических методов.
• Нейросетевые подходы — end-to-end обучение решателей для больших экземпляров (обзоры 2024–2025 годов отмечают прогресс, но пока без гарантий качества).
• Варианты и обобщения — mTSP, ЗК с временными окнами, интеграция с реальными ограничениями в логистических системах.

См. также

• Задача маршрутизации транспорта
• Комбинаторная оптимизация
• Динамическое программирование

Литература

• Dantzig G. B., Fulkerson R., Johnson S. M. Solution of a Large-Scale Traveling-Salesman Problem // Operations Research. 1954. Vol. 2, No. 4. P. 393–410.
• Karp R. M. Reducibility Among Combinatorial Problems // Complexity of Computer Computations. 1972. P. 85–103.
• Christofides N. Worst-case analysis of a new heuristic for the travelling salesman problem // Management Sciences Research Report No. 388. Carnegie Mellon University, 1976.
• Held M., Karp R. M. A dynamic programming approach to sequencing problems // Journal of the SIAM. 1962. Vol. 10, No. 1. P. 196–210.
• Reinelt G. TSPLIB — A Traveling Salesman Problem Library // ORSA Journal on Computing. 1991. Vol. 3, No. 4. P. 376–384.
• Beardwood J., Halton J. H., Hammersley J. M. The Shortest Path Through Many Points // Proc. Cambridge Phil. Soc. 1959. Vol. 55, No. 4. P. 299–327.
• Arora S. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems // Journal of the ACM. 1998. Vol. 45, No. 5. P. 753–782.
• Laporte G. The traveling salesman problem: An overview of exact and approximate algorithms // European Journal of Operational Research. 1992. Vol. 59, No. 2. P. 231–247.
• Applegate D. L., Bixby R. E., Chvátal V., Cook W. J. The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2006.
• Cook W. J. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press, 2012.
• Saller S. et al. A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme // arXiv:2311.00604, 2023.

Ссылки

• https://www.math.uwaterloo.ca/tsp/ — University of Waterloo TSP project
• https://www.math.uwaterloo.ca/tsp/concorde.html — Concorde TSP Solver
• http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ — TSPLIB
• https://doi.org/10.1287/opre.2.4.393 — Dantzig et al. (1954), оригинальная статья