Решение задачи множественного коммивояжёра с несколькими депо и замкнутыми маршрутами с помощью иерархической кластеризации k-means++ и нейронных комбинаторных сетей

Умнее маршруты для множества водителей

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

Сложность: много депо и много водителей

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

Пределы классического поиска и простого деления

В течение многих лет инженеры полагались на «метаэвристики», такие как генетические алгоритмы, поиск по принципу колонии муравьёв и рой частиц. Эти методы имитируют природные процессы, чтобы исследовать множество кандидатных маршрутов и постепенно улучшать их. Они гибки, но имеют два существенных недостатка: они не дают жёстких гарантий по качеству решения и могут сильно замедляться на больших картах, особенно когда для каждой новой задачи приходится запускать поиск заново. Популярный приём ускорения — сначала сгруппировать города по регионам с помощью таких инструментов, как k-means, а затем решить меньшую задачу в пределах каждого кластера. Эта стратегия «разделил — решил» помогает, но итоговое качество по-прежнему ограничено базовым поисковым методом, и попытки добиться лучших маршрутов обычно ведут к ещё большему времени выполнения.

Обучение сети прокладывать маршруты и помощь в масштабировании

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

Как работает двухфазный метод

Предложенный метод, называемый KHC-NCN, начинается с использования улучшенной версии k-means для распределения городов по депо и водителям. Если образовавшийся регион содержит слишком много городов для надёжной работы нейросети, метод автоматически дополнительно делит этот регион на более мелкие части, каждая — близкого размера к тому, что встречалось в обучении сети. Координаты в каждой части масштабируются в стандартный квадрат, чтобы они ещё больше напоминали обучающую выборку. Затем нейронная сеть формирует маршрут для каждой маленькой части. Наконец, шаг объединения сшивает эти подмаршруты в единый цикл для каждого водителя, применяя простые геометрические правила для соединения частей там, где это добавляет наименьшее дополнительное расстояние.

Скорость и качество на реальных эталонных картах

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

Что это значит для практической маршрутизации

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

Цитирование: Zhao, CS., Wong, LP. & Fung, C. Solving multi-depot closed-path multiple traveling salesman problem using k-means++ hierarchical clustering and neural combinatorial networks. Sci Rep 16, 15631 (2026). https://doi.org/10.1038/s41598-026-45824-3

Ключевые слова: маршрутизация транспортных средств, нейронные сети, кластеризация, оптимизация, логистика