Материал подготовлен автоматически по первоисточникам: ссылки на них — в конце статьи.
Нейросетевой солвер стал устойчивее переносить изменение вместимости машин и размера задачи. В работе Panasonic Connect и Kyoto University, которая не прошла рецензирование и содержит замеры самих авторов, средний разрыв с HGS по шкале вместимости составил 3,00% против 7,22% у BQ. Результат предлагает пересмотреть сам порядок сборки маршрутов, а не только архитектуру нейросети.
Почему сборка по одному маршруту мешает видеть задачу целиком
Большинство нейросетевых солверов для задачи маршрутизации с ограниченной вместимостью машин (CVRP) строят один маршрут за другим. Модель выбирает следующего клиента, пока в машине остаётся место, затем возвращается в депо и начинает новый маршрут.
Оставшаяся вместимость выполняет сразу две функции. Она запрещает недопустимые действия и подсказывает модели, насколько далеко продвинулся текущий маршрут. Но клиенты попадают в него раньше, чем сформируются соседние маршруты, поэтому раннее решение ограничивает последующую перестройку всей схемы.
Новый солвер начинает с отдельных компонентов: каждый клиент сначала считается самостоятельным маршрутом. На каждом шаге модель соединяет концы двух разных компонентов, если их суммарный спрос не превышает вместимость машины. Несколько маршрутов растут параллельно, а их состав определяется вместе с порядком слияний.
Авторы считают каждый промежуточный компонент не открытым отрезком, а маршрутом, который неявно начинается и заканчивается в депо. Благодаря этому любое состояние уже представляет полное допустимое решение стандартной CVRP. Если вычисление остановить между шагами, набор компонентов всё равно можно исполнить как набор отдельных рейсов.
Как стоимость слияния связали с целью оптимизации
При соединении компонентов исчезают два ребра от их концов до депо и появляется одно ребро между клиентами. Выигрыш равен d(0,i) + d(0,j) − d(i,j) — экономии Clarke–Wright. Это точное локальное изменение общей длины, а не оценка, которую нейросеть должна восстановить из обучающих примеров.
Одной такой экономии недостаточно: самое выгодное слияние может закрыть доступ к лучшей последовательности следующих действий. Поэтому итоговая оценка сочетает аналитический выигрыш текущего шага с нейросетевой оценкой всего состояния. Декодер заново обрабатывает депо, доступные концы компонентов и их загрузку после каждого слияния.
Обучение разделили на этапы. Сначала модель по эталонным решениям учится выбирать допустимые соединения без навязанного порядка. Затем порядок всё сильнее определяет сама модель, а на последнем этапе обучение с подкреплением оптимизирует итоговую длину маршрутов. Ту же модель используют при восстановлении решения после удаления части рёбер: отдельные клиенты и сохранившиеся фрагменты представлены одинаковыми компонентами.
Когда параллельная сборка меняет архитектурный план
Модель обучали только на CVRP100 при одной фиксированной вместимости, затем без дообучения проверяли на задачах до CVRP1000 и в диапазоне C=10–500. При самой жёсткой вместимости разрыв с HGS составил 5,42%, тогда как у LEHD — 36,56%. На всей шкале вместимости подход обошёл опубликованные результаты сравниваемых нейросетевых солверов.
Контрольные варианты показывают, что результат нельзя приписать только формуле Clarke–Wright. Многокомпонентная модель без этого сигнала тоже сохранила устойчивость при жёстком ограничении. Авторы связывают провал последовательных нейросетевых солверов с выученным решением о возврате в депо: при смене вместимости привычный сигнал прогресса маршрута перестаёт соответствовать обучению. Эксперименты согласуются с этой гипотезой, но не отделяют её от остальных различий методов.
Для команды, которая разрабатывает собственный конструктивный CVRP-солвер, работа даёт конкретный архитектурный вариант: хранить несколько допустимых маршрутов, оценивать слияния по точному изменению целевой функции и поручать нейросети выбор долгосрочного порядка. Такой подход особенно уместен, если рабочие задачи меняют вместимость машин или число клиентов, а модель нельзя переобучать под каждый режим.
Это не основание сразу заменять производственный оптимизатор. Эксперименты охватывают CVRP с суммарной длиной как целью и переменным числом маршрутов; на крупнейшем размере жадная сборка уступила LEHD. Кроме того, уже закреплённые внутри компонента рёбра нельзя изменить обычным следующим шагом — для крупных исправлений приходится частично разрушать и заново собирать решение.
Практический вывод уже: depot-closed construction стоит рассматривать как альтернативу последовательному декодеру или как оператор восстановления внутри существующего поиска. Перенос потребует изменить представление состояния, набор действий и программу обучения, поэтому это не локальная замена слоя модели.
Источники
Похоже на вашу задачу?
Расскажите, что собираете. За полчаса разложим на этапы и назовём сроки — это бесплатно и ни к чему не обязывает.
