Доклады Российской академии наук. Математика, информатика, процессы управления, 2023, T. 514, № 2, стр. 91-98

1. ВВЕДЕНИЕ

Задача оптимизации маршрутов (VRP, англ. Vehicle Routing Problem) представляет собой класс задач комбинаторной оптимизации, которые возникают во многих прикладных областях реального мира, таких как логистика, транспортная сфера, распределение товаров на складах и многи другие. Начиная с классической работы [3], было предложено множество точных и эвристических подходов для решения данной задачи (см., например, [4]). На практике в сфере логистики, стандартная задача VRP почти никогда не встречается в чистом виде, вместо этого существует множество вариаций, учитывающих разнообразные ограничения, характерные для логистической деятельности. Кроме того, зачастую задачи являются масштабными и трудными для решения, так как являются NP-сложными [6].

В последние годы наблюдается растущий интерес к использованию нейронных сетей для решения задач оптимизации маршрутов [2, 7, 8]. Во многом это связано с тем, что нейронные сети имеют потенциал решить проблемы масштабируемости этих задач, научившись представлять пространство задачи компактным и эффективным образом.

В данной статье предложен нейронный подход к решению задач вывоза и доставки грузов с ограничениями по временным окнам, вместимости транспортных средств и последовательности доставок (CPDPTW, англ. Capacity Pickup and Delivery Problem with Time Windows). Экспериментальные результаты показывают, что предложенный подход способен находить решения, близкие к оптимальным, и может масштабироваться для задач с тысячами узлов и временными интервалами.

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

Структура статьи следующая:

$ \bullet $ Формулировка задачи (раздел 2)

$ \bullet $ Последние исследования (раздел 3)

$ \bullet $ Предлагаемый подход (раздел 4)

$ \bullet $ Экспериментальные результаты (раздел 5)

$ \bullet $ Заключение (раздел 6)

2. ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИ МАРШРУТОВ С ОГРАНИЧЕНИЯМИ

Задачу вывоза и доставки с временными интервалами и ограничением объема грузов (Capacitated Pickup and Delivery Problem with Time Windows, CPDPTW) можно описать следующим образом.

Пусть $N$ – множество клиентов, $i = 1, \ldots ,n$. Каждый клиент $i$ связан с:

$ \bullet $ спросом ${{d}_{i}}$: количеством груза для забора или доставки;

$ \bullet $ временным окном $[{{a}_{i}},{{b}_{i}}]$: интервалом для забора и доставки у клиента $i$;

$ \bullet $ временем обслуживания $s{{c}_{i}}$: обычно временем обслуживания одного клиента;

$ \bullet $ местом забора ${{P}_{i}}$: пунктом забора груза для клиента $i$;

$ \bullet $ местом доставки ${{D}_{i}}$: пунктом доставки груза для клиента $i$.

Пусть также $M$ – множество транспортных средств, $j = 1, \ldots ,m$. Каждое транспортное средство $j$ имеет:

$ \bullet $ грузоподъемность ${{C}_{j}}$: максимальную нагрузку транспортного средства $j$.

Переменные решения для CPDPTW:

$ \bullet $ ${{x}_{{ij}}}$: бинарная переменная, обозначающая, посещает ли транспортное средство $j$ клиента $i$;

$ \bullet $ ${{u}_{i}}$: накопленный груз у клиента $i$;

$ \bullet $ ${{t}_{i}}$: накопленное время у клиента $i$;

$ \bullet $ ${{z}_{i}}$: бинарная переменная, показывающая, обслужен ли клиент $i$ (не пропущен).

Цель – минимизировать сумму расстояний, пройденных транспортными средствами, и штраф за пропущенных клиентов:

где ${{c}_{{ij}}}$ – стоимость или расстояние от клиента $i$ до клиента $j$, $\lambda $ – коэффициент штрафа.

При оптимизации задачи CPDPTW на решение накладываются ограничения. Каждый клиент посещается только одним транспортным средством $\sum\nolimits_{j = 1}^m {{x}_{{ij}}} = 1$ $\forall i \in N$, только один раз $\sum\nolimits_{i = 1}^n {{x}_{{ij}}} \leqslant 1$ $\forall j \in M$ и в рамках заданного временного окна: ${{a}_{i}} \leqslant {{t}_{i}} + s{{c}_{i}} \leqslant {{b}_{i}}$ $\forall i \in N$. Вместимость – вес товара в каждом средстве ограничен его грузоподъемностью: $\sum\nolimits_{i = 1}^n {{d}_{i}} \cdot {{x}_{{ij}}} \leqslant {{C}_{j}}$ $\forall j \in M$. Для поддержания правильной последовательности вывоза и доставки товаров, требуется ограничение на порядок следования между депо и клиентами: ${{x}_{{ij}}} = 0$ $\forall i \in N$, $j \in M{\kern 1pt} $, где ${{P}_{i}} \ne {{P}_{{i + 1}}}$ или ${{D}_{i}} \ne {{P}_{{i + 1}}}$.

3. ПОСЛЕДНИЕ ИССЛЕДОВАНИЯ

Классические подходы. Задача сбора и доставки грузов с учетом временных окон и грузоподъемности (Capacitated Pickup and Delivery Problem with Time Windows, CPDPTW) является классической задачей оптимизации маршрутов, возникающей во многих практических приложениях, таких как логистика и транспорт. Задача заключается в нахождении маршрута для транспортного средства, которое посещает набор точек забора и доставки, с учетом ограничений на грузоподъемность и временные окна.

Существует ряд классических подходов для решения задачи CPDPTW. Среди них: точные методы, эвристические подходы, метаэвристические подходы.

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

$ \bullet $ Метод ветвей и границ: универсальный алгоритм может быть использован для решения задач целочисленного программирования, включая CPDPTW. Он систематически исследует пространство решений, чтобы найти оптимальное решение, но может быть вычислительно затратным для задач большой размерности.

$ \bullet $ Динамическое программирование: специализированный алгоритм разбивает задачу на более мелкие подзадачи и решает их рекурсивно. Он эффективно решает задачу CPDPTW для задач с небольшой и средней размерностью.

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

$ \bullet $ Ближайший сосед: простой эвристический метод начинает с базы и жадно выбирает ближайшее место забора или доставки на каждом шаге.

$ \bullet $ Генетический алгоритм: алгоритм поддерживает популяцию решений и применяет генетические операторы, такие как мутация и скрещивание, для создания новых решений.

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

$ \bullet $ Муравьиный алгоритм: алгоритм вдохновлен поведением муравьев при поиске пищи. Алгоритм моделирует взаимодействие муравьев, которые перемещаются по графу маршрутов, оставляя за собой феромонные следы. Муравьи выбирают пути, основываясь на концентрации феромонов и эвристических информаций, которые указывают на “привлекательность” путей. По мере прохождения времени, феромоны испаряются, и муравьи более склонны выбирать короткие пути, которые были успешны в доставке. Со временем алгоритм сходится к оптимальному маршруту, учитывая как локальную, так и глобальную информацию о графе.

$ \bullet $ Метод табу поиска: метаэвристический алгоритм для оптимизации, который использует список “табу” или запрещенных ходов, чтобы избежать застревания в локальных оптимумах. В процессе поиска оптимального решения, алгоритм начинает с какого-либо случайного решения и применяет различные операции изменения этого решения. Однако определенные ходы могут быть временно запрещены (табу), чтобы предотвратить повторение плохих шагов или возвращение к предыдущим состояниям.

Нейронные подходы. Первая модель глубокого обучения для последовательного решения задачи VRP была предложена Nazari и соавт. [12], которые адаптировали сеть Pointer Network (PtrNet) Vinyals и др. [13] для работы с CVRP. Авторы полностью отказались от исходной части модели кодировщика RNN и заменили ее слоем эмбеддинга с общими параметрами. Более новый алгоритм AM от Kool и соавт. [2] заменил эту архитектуру адаптированной моделью трансформера с использованием самовнимания [14]. Прямым улучшением этой модели является подход JAMPR от Falkner и др. [7], где авторы добавили дополнительные сети линейного вложения для текущего пути и позиции грузовиков. Это дополнение позволило алгоритму успешно решать задачи CVRP-TW. Chen и Tian [15] предложили подход для улучшения на основе обучения с подкреплением, который итеративно выбирает область на графе, затем выбирает и применяет установленные локальные эвристики. Этот подход был дополнительно улучшен оператором разрушения, введенным Lu и соавт. [10]. Последняя попытка использовать глубокое обучение для решения задач большой размерности при помощи разделения набора точек на подзадачи и их решения с помощью черного ящика была предложена Li и соавт. [9]. Авторы предложили две версии метода с учителем: регрессионное предсказание возможного улучшения конечной стоимости и классификацию на лучшую подзадачу. Уменьшая размерность и используя классические метаэвристические подходы для каждой подзадачи, авторы смогли продемонстрировать хорошие результаты на задачах с высокой размерностью (1000–2000 точек). Попытки предложить полностью нейросетевое решение для проблемы были предприняты [1] авторами данной работы на основе алгоритма JAMPR. Насколько нам известно, на данный момент наша работа является первой, предлагающей полностью нейронный подход для решения задач большой размерности (около 5000 точек) для решения реальных задач маршрутизации.

4. ПРЕДЛОЖЕННЫЙ ПОДХОД

В рамках предыдущей работы [1] мы строили полностью нейросетевой подход на базе алгоритма JAMPR, пытаясь обучить алгоритм решать задачи CPDPTW большой размерности (<1000 точек). Мы столкнулись с тем, что алгоритм способен обучаться давать быстрые субоптимальные решения для задач малого размера (50 точек), но при увеличении размера теряет качество. Основной причиной является необходимость обучать нейронную сеть. Если для 50 точек модель обучалась две недели и смогла превзойти лучшие решения эвристических подходов, то увеличение объема точек сказывалось негативно на качестве, требуя для поддержания уровня результатов экспоненциально больше времени. Мы решили использовать нейросетевой подход разбиения задачи на малые подзадачи размера 50 точек при помощи алгоритма (L2D) Learning to Delegate [9] и уже их оптимизировать нашей лучшей моделью на основе JAMPR. Таким образом, модель обучалась в два шага: сначала нейронная сеть [1] тренируется на примерах задач CPDPTW размерности 50 точек, после этого алгоритм L2D обучается разбивать исходную проблему на подзадачи. Данные генерируются во время обучения из распределения на основе статистики R201, известного эталонного набора Соломона [16]. Алгоритм таким образом способен решать задачи CPDPTW большого размера без переобучения модели, сохраняя качество предсказаний. Время обучения модели JAMPR составило 14 дней, алгоритм L2D обучался чуть менее недели. Итого суммарное время обучение L2D + JAMMPR_50 составило 21 день.

5. ЭКСПЕРИМЕНТАЛЬНЫЕ РЕЗУЛЬТАТЫ

В экспериментальной части мы сравним между собой несколько методов решения задачи CPDPTW среднего и большого размера – от 200 до 5000 клиенттов. Мы рассматриваем следующие подходы:

$ \bullet $ классические эвристические методы – OR-Tools, LKH [5],

$ \bullet $ гибридный эвристико-нейросетевой подход L2D [9],

$ \bullet $ полностью нейросетевая модель (предложенная нами выше).

Был проведен ряд экспериментов, чтобы определить, насколько хорошо данные модели справляются с задачей вывоза и доставки товаров с времеными окнами и ограничениями по грузоподъемности (CPDPTW). Для каждого размера (200, 1000, 5000 точек) были сгенерированы по 100 экземпляров задачи CPDPTW. На поиск решения каждой из задачи каждому методу был отведен лимит в 1000 с. Все экземпляры задач были получены из порождающего распределения на основе статистики R201 (хорошо известного эталонного набора Соломона [16]). Мы использовали “мягкую” (soft) постановку задачи CPDPTW (с возможностью пропускать клиентов, получая штраф в величину стоимости). Для того, чтобы показать, насколько хорошо алгоритмы справляются с экземплярами задач в течение всего времени оптимизации, мы измеряли, как меняется стоимость пути по прошествии времени оптимизации. Также мы расссчитывали процент нерешенных задач для каждого метода. Глава ниже устроена следующим образом. Сначала мы опишем полученные экспериментальные результаты в виде графиков и таблицы. Далее мы обсудим, в чем основные достоинства предложенного нами метода. Мы ответим на вопрос, почему эвристики показывают себя не с лучшей стороны, а также опишем плюсы и минусы использования нейросетевых подходов при решении задач CPDPTW. Глава завершается общими рекомендациями по использованию нейросетевых алгоритмов в условиях реального мира.

Ниже представлены графики зависимости стоимости от времени оптимизации задачи CPDPTW. Для всех моделей с размерами 200, 1000 и 5000 точек лимит оптимизации установлен в 1000 с. Стоимость измеряется как процент относительно лучшего результата лучшей модели в каждой конкретной задаче. Мы относим задачи из 200 точек к задачам среднего размера и 1000, 5000 точек к задачам большого размера. В качестве бейзлайна использовались классические эвристические подходы OR-Tools и LKH [5]. Также бейзлайном выступает последний нейросетевой SotA подход для задач большой размерности: L2D (LKH_50) [9] с решателем эвристикой, оптимизирующей задачу размера 50. Алгоритм L2D(JAMPR_50) – это обученный на задаче размера 50 JAMPR + L2D.

На рис. 1 представлен график для задачи размером 200 точек. Видно, что нейросетевые модели предоставляют быстрые субоптимальные решения, постепенно сходящиеся к результатам эвристических методов. Производительность всех моделей становится одинаковой через 75 с оптимизации, при этом модель LKH демонстрирует лучшие результаты среди эвристических методов. Однако в начальные секунды оптимизации лучшая нейросетевая модель превосходит LKH на 30%. Для больших размерностей (1000 точек), рис. 2 демонстрирует аналогичную тенденцию: быстрые субоптимальные решения от нейросетевых моделей с постепенной асимптотической сходимостью по сравнению с OR-Tools. OR-Tools отстает от всех подходов, постепенно приближаясь к лучшим моделям. Модель L2D(JAMPR_50) достигает лучшего результата, обходя модель L2D(LKH) в первые 250 с оптимизации. Для задач больших размеров нейросетевые подходы последовательно превосходят эвристики на протяжении всего процесса оптимизации. На рис. 3 для 5000 точек эвристики не смогли решить большинство задач, что привело к худшей производительности. В то же время рис. 4 показывает связь между количеством нерешенных задач и размером задачи по истечении 1000 с, отведенных на решение каждой задачи. Можно заметить, что эвристические подходы оставляют все большее количество нерешенных экземпляров с увеличением размера задачи, нейросетевые методы не решают на порядок меньше задач.

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

Подход превосходит классические эвристики в первые секунды оптимизации на 30% для задач среднего размера, предоставляя таким образом быстрое субоптимальное решение. Мы отмечаем, что в дальнейшем решения сходятся к одной стоимости пути. Однако, как было показано в [1], данный результат для нейросетей может быть улучшен при наличии достаточного времени для обучения модели. Для задач большой размерности наш алгоритм превосходит классические эвристики на всем времени оптимизации решений. На задачах размера 5000 (рис. 3) предложенный подход дает быстрое субоптимальное решение, и превосходит классические подходы на 35% метрики GAP по истечению всего отведенного времени оптимизации, в то же время, уменьшая процент нерешенных задач на порядок (рис. 4). Таким образом, мы отмечаем превосходство предложенного подхода над классическими эвристичекими методами.

По сравнению с гибридным нейронно-эвристическим алгоритмом L2D(LKH_50) наш подход показывает сопоставимые по точности результаты для всего отведенного времени на оптимизацию для всех размеров задач, не уступая в проценте нерешенных задач. Более того, предложенный алгоритм позволяет получать более оптимальное решение для задач средней (рис. 1) и большой размерности (рис. 2, 3) в первые секунды оптимизации, обеспечивая таким образом более быстрое субоптимальное решение. Данный факт позволяет говорить о превосходстве нашего подхода по сравнению с SotA алгоритмом.

Почему эвристики не находят решений для значительной доли экземпляров большой размерности? Мы считаем основной причиной плохого результата эвристик (рис. 4) для задач большого размера – их “медлительность”. Модели не способны получить оптимальный результат за отведенное время, при этом давая лучший результат на средних размерах задачи (рис. 1), где отведенного разумного лимита достаточно. Тем не менее мы отмечаем, что нейронные сети способны превзойти эвристики за счет увеличения времени на обучение. Мы показали это в нашей предыдущей статье [1]. Таким образом, нейросетевые подходы являются предпочтительным методом при наличии ресурсов на обучение моделей, в то время как классические подходы являются надежным бейзлайном при их отсутствии.

В чем особенности использования нейронных сетей? Нейросетевые подходы способны давать быстрое субоптимальное решение для всех размеров задач (рис. 1–3). Они также способны давать лучшие результаты на всем времени оптимизации при достаточном обучении [1]. Кроме того, они являются робастными в смысле сохранения процента нерешенных задач (рис. 4). Основной недостаток: нейростевые эвристики требуют большого времени на обучение. Кроме того, нейронные сети требуют графических ускорителей для своей быстрой работы, что может повлечь дополнительные расходы на аппаратуру. Тем не менее они предоставляют свободу выбора: можно пожертвовать оптимальностью решений за счет сокращения времени на обучение. В табл. 1 представлены сравнительные результаты всех рассмотренных подходов.

Как полученные результаты влияют на применение в реальных условиях? Можно сразу отметить, что крауегольным камнем является время. При наличии достаточного времени для обучения (2 нед для задачи размера 50, от 4 нед для задачи размера 200 и т.д.) лучший результат будет у обученных нейросетевых подходов. При разумном ограниченном времени на обучение решателя стоит обращать внимание на ограничения времени оптимизации задачи. Нейронные сети смогут предоставить лучшее решение на горизонте 75 с для задач средних размеров, в то же время будут бесспорным лидером для задач больших размеров. При отсутствии времени на обучение решателей, очевидно, классические подходы являются единственным пригодным подходом.

6. ЗАКЛЮЧЕНИЕ

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

Из результатов нашей работы следует, что нейросетевые модели обеспечивают быстрые субоптимальные решения. Для задач средних размеров (200–1000 точек) нейросетевые модели превосходят эвристики уже в первые секунды оптимизации, а для задач больших размеров (>1000 точек) нейронные подходы последовательно демонстрируют лучшие результаты на протяжении всего процесса оптимизации. Мы также отмечаем, что с увеличением количества точек классические подходы, в отличие от нейросетевых, перестают справляться с проблемами, увеличивая процент нерешенных задач на порядок. Более того, для больших размеров задач (около 5000 точек) большинство рассмотренных эвристических алгоритмов не способны представить ни единого решения, в отличие от предложенного нейростевого подхода.

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