Образовательные программы компьютерных наук и информатики обязательно включают курс алгоритмов, это элегантные решения сложных проблем. Например, одна из самых интересных проблем комбинаторной оптимизации — задача коммивояжёра (TSP, travelling salesman problem). Суть в поиске самого выгодного маршрута, проходящего через указанные точки ровно по одному разу. Сложность задачи при точном решении брутфорсом составляет O(n!). И для неё тоже придумано несколько элегантных алгоритмов. Хотя поиск самого эффективного продолжается до сих пор.

В реальности уже нет коммивояжёров, путешествующих по городам, профессия ушла в прошлое. Но есть курьеры, таксисты, логисты, грузоперевозчики и просто туристы, которые хотят посетить максимальное количество достопримечательностей. То есть задача по-прежнему актуальна. Как же максимально эффективно настоящие бизнесы решают TSP в реальной жизни?

TSP актуальна для ряда приложений, вот некоторые из них.

Туристические приложения

Это больше всего похоже на задачу коммивояжёра, только здесь у нас путешествует не торговый представитель, а турист. Его задача — обойти как можно больше достопримечательностей на карте.

Сервисы вроде Google Maps, Rome2Rio и туристические приложения используют TSP для построения оптимальных маршрутов.

Конвейер на заводе

Другой пример использования TSP — это оптимизация конвейера на заводе, то есть маршрута перемещения деталей между станками или участками.

Например, робот на заводе должен пройти через несколько точек, эта задача сводится к TSP.

В идеале хотелось бы, чтобы маршрут прокладывался автоматически и с минимальными вычислительными затратами.

Маршруты курьеров

Ещё одно применение TSP — это логистика и доставка, то есть раздача заданий курьерам и планирование их маршрутов. Это прямая задача для курьерских служб и служб доставки, таких как DHL, FedEx и проч. Например, такая система строит маршрут для конкретного курьера, чтобы он посетил все точки с минимальными затратами времени и топлива:

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

Решение таких логистических задач уже сегодня внедряется в реальные системы, которые используют крупнейшие IT-компании. Например, одна из таких задач легла в основу соревнования E-CUP 2025: ML Challenge, проводимого Ozon Tech на платформе Codenrock. Участникам предстоит решить задачу «Логистика: автопланирование курьеров» с призовым фондом ₽7,2 млн:

Описание задачи: «Оптимизируйте доставку. Создайте алгоритм, который распределит 20 000 заказов между 200 курьерами, минимизирует суммарное время их работы с учётом микрополигонов и сократит индивидуальную скорость выполнения заданий».

Эта задача типа VRP (Vehicle Routing Problem) или «распределение с ограничениями», она отличается от классической TSP и имеет большее отношение к реальному бизнесу.

Однако логистика маршрутов важна не только в сфере доставки. В крупных компаниях возникает потребность эффективно планировать перемещения и других сотрудников — тех, кто работает «в полях». Например, это могут быть инженеры, обслуживающие технику на разных торговых точках и филиалах. Или техники, которые заправляют/обслуживают вендинговые машины или банкоматы. В общем, любые «мобильные агенты».

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

Известно около десятка популярных алгоритмов и методов решения TSP.

Самый простой метод на небольшом количестве точек — это брутфорс, когда мы вычисляем все возможные варианты перестановки маршрутов. Однако задача коммивояжёра относится к классу NP-полных задач, а уже при относительно небольшом числе городов (66) количество вариантов решения превышает 10⁹³, то есть не может быть решена брутфорсом никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет (трансвычислительная задача).

На Хабре отдельно рассказывали про метод ветвей и границ (МВГ, англ. branch and bound) — общий алгоритмический метод оптимизации для разных NP-трудных задач, в том числе TSP с умеренным количеством решений (узлов). В той же статье упоминается, что в больших системах для решения TSP используются эвристики и метаэвристики: жадный алгоритм; метод шнурка (геометрическая вариация жадного алгоритма), скользящий перебор (переставляет местами города из небольшой части пути. Затем такое «окно перебора» скользит вдоль всего пути).

МВГ систематически исследует возможные маршруты и обрезает ветви, которые превышают длину текущего лучшего решения, уменьшая пространство поиска и повышая эффективность по сравнению с методом перебора.

Некоторые другие алгоритмы и методы для приближённого решения TSP в больших системах:

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

• Генетические алгоритмы используют принципы естественного отбора и генетики для эволюции кандидатных решений на протяжении поколений, комбинируя и мутируя маршруты для улучшения качества решений (эволюционный подход). Такой метод подходит для сложных вариантов TSP на больших массивах точек, где точные методы непрактичны, а генетические алгоритмы обеспечивают достаточно качественную аппроксимацию. Это эвристический подход, здесь сложность составляет не O(n!), как в брутфорсе, а зависит от настроек и числа итераций.

На Github можно найти много примеров кода для решения TSP с помощью генетических алгоритмов.

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

Кроме TSP, имитация отжига применяется также в обучении нейросетей и решении других комбинаторных задач.

• Эвристика Лина—Кернигана считается одной из самых эффективных для решения TSP. Основная идея в том, чтобы найти некоторое допустимое решение, после чего выделить два множества дуг — таких, что если все дуги первого множества удалить из найденного тура и заменить их дугами из второго множества, то результатом будет тур, который лучше (дешевле) предыдущего. Процесс переноса дуг повторяется до тех пор, пока становится невозможно сформировать такие два множества дуг.

• Алгоритм Кристофидеса для случаев, когда расстояния образуют метрическое пространство (симметричны и удовлетворяют неравенству треугольника). Решается за полиномиальное время O(n³).

• Алгоритм Хелда−Карпа это алгоритм динамического программирования, который применяется в системах с небольшим количеством точек, где важна точность решения. Основная идея заключается в вычислении и запоминании пути от исходного города и до каждого из остальных городов, затем суммирования этой величины с путём из каждого из остальных городов до оставшихся городов и т. д. Преимущество данного метода заключается в сокращении полного объёма вычислений до O(n^2 * 2^n).

Научное сообщество много сил уделяет проблеме TSP, вот некоторые из последних научных статей с попытками решить задачу:

• «Ускорение маршрутизации транспорта методами ML»: исследователи MIT применяют методы ML для решения крупных NP-полных задач, разбивая их на подзадачи.

• «Метод нулевого суффикса»: решение классической симметричной TSP.

• «Биогеографический алгоритм оптимизации»: метод разработан на основе стратегии миграции животных.

• «Метаэвристический перезапускаемый итеративный локальный поиск» (MRSILS): авторы утверждают, что MRSILS при использовании кластеров эффективнее генетических алгоритмов.

• «Многоцелевой эволюционный алгоритм»: решение mTSP (вариант TSP с множеством агентов) с помощью генетического алгоритма и фреймворка NSGA-II (Non-dominated Sorting Genetic Algorithm II).

• «Решение TSP в мультиагентной системе».

Из этих работ можно позаимствовать некоторые эффективные подходы, в том числе методами машинного обучения.

Решение TSP в прикладном ПО

В сети есть несколько решателей (солверов) для TSP. Например, Concorde — современный точный солвер на С, который объединяет методы отсечения, ветвления и границ, а также сложные эвристики для эффективного поиска оптимальных решений крупных задач. Он использовался для получения оптимальных решений всех 110 задач TSPLIB, самая крупная — на 85 900 городов.

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

Concorde поддерживает решатель линейного программирования Qsopt, Исполняемые версии Concorde с QSopt для Linux и Solaris теперь доступны.

Работает также NEOS-сервер Concorde, позволяющий решать TSP онлайн, путём загрузки файлов.

Есть несколько игр для решения TSP вручную (в образовательных целях).

Некоторые стартапы даже предоставляют коммерческие сервисы вроде Routific Engine API для решения TSP в реальных приложениях, то есть для маршрутизации транспорта и курьеров.

Кроме Routific, базовые методы решения TSP предлагает Mapbox Web Services API (в данный момент до 12 точек, лимиты могут увеличиться со временем) и Google Maps Directions API (сейчас до 23 точек, без учёта времени, круговых поездок и вместимости) и др. Самые простые и неоптимальные маршруты до десяти точек строит бесплатная версия Google Maps. С помощью сторонних инструментов несколько маршрутов (каждый до десяти точек) можно объединить вручную.

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

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