1. На главную
  2. Электронные версии
  3. Доклады Российской академии наук. Математика, информатика, процессы управления
  4. T. 514, № 2, 2023

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

ОПТИМИЗАЦИЯ МАРШРУТОВ БОЛЬШОЙ РАЗМЕРНОСТИ С ИСПОЛЬЗОВАНИЕМ ГЛУБОКИХ НЕЙРОННЫХ СЕТЕЙ

А. Г. Сорока 1, *, А. В. Мещеряков 2, 1, **

1 Московский государственный университет имени М.В. Ломоносова; Факультет вычислительной математики и кибернетики
Москва, Россия

2 Институт космических исследований Российской академии наук
Москва, Россия

* E-mail: andrew.soroka@student.msu.ru
** E-mail: mesch@cosmos.ru

Поступила в редакцию 05.09.2023
После доработки 15.09.2023
Принята к публикации 18.10.2023

Аннотация

Логистическая задача вывоза и доставки товаров по большому числу точек с ограничениями реального мира (в виде наличия временных окон при исполнении заказов и ограниченной вместимости транспортных средств) возникает, в настоящее время, в областях курьерской доставки, планирования грузоперевозок, маршрутизации. С учетом глобализации и роста бизнеса, потребность в оптимальных и быстрых методах планирования маршрутов, учитывающих ограничения реального мира, крайне велика. Точные методы применимы только на задачах небольшой размерности (<50); классические подходы, основанные на эвристиках, позволяют найти субоптимальное решение, но также не справляются с увеличением размера задач >1000 [1]). В настоящей работе мы впервые предложили использовать полностью нейросетевые модели для решения логистических задач большой размерности с ограничениями реального мира. Наш подход предполагает последовательное использование двух нейронных сетей: 1-я нейросетевая модель обучается разбивать задачу большой размерности на подзадачи, 2-я модель обучается оптимизировать маршруты в рамках подзадач. Экспериментальные результаты на размере задач 200, 1000, 5000 показывают, что предложенный подход превосходит существующие модели (как эвристические, так и гибридные) в данной области, предоставляя быстрое субоптимальное решение для всех размеров задач. Результаты предложенной модели значительно (до 30%) превосходят эвристики (OR-Tools, LKH), превосходят результаты лучших гибридных подходов, а также обеспечивают значительно меньший процент нерешенных логистических задач по сравнению с подходами на основе эвристик.

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

Список литературы

  1. Soroka A., Meshcheryakov A., Gerasimov S. Deep Reinforcement Learning solution for pickup and delivery routing problems with time window and capacity constraints.

  2. Kool W., Van Hoof H., Welling M. Attention, learn to solve routing problems! // arXiv preprint arXiv:1803.08475. 2018.

  3. Dantzig G., Fulkerson R., Johnson S. Solution of a large-scale traveling-salesman problem // Journal of the operations research society of America. 1954. V. 2. № 4. C. 393–410.

  4. Braekers K., Ramaekers K., Van Nieuwenhuyse I. The vehicle routing problem: State of the art classification and review // Computers & industrial engineering. 2016. V. 99. C. 300–313.

  5. Helsgaun K. An effective implementation of the Lin–Kernighan traveling salesman heuristic // European journal of operational research. 2000. V. 126. № 1. C. 106–130.

  6. Wolsey L.A., Nemhauser G.L. Integer and combinatorial optimization. John Wiley & Sons, 1999. V. 55.

  7. Falkner J.K., Schmidt-Thieme L. Learning to solve vehicle routing problems with time windows through joint attention // arXiv preprint arXiv:2006.09100. 2020.

  8. Kool W. et al. Deep policy dynamic programming for vehicle routing problems // International conference on integration of constraint programming, artificial intelligence, and operations research. Cham : Springer International Publishing, 2022. C. 190–213.

  9. Li S., Yan Z., Wu C. Learning to delegate for large-scale vehicle routing // Advances in Neural Information Processing Systems. 2021. V. 34. P. 26198–26211.

  10. Lu H., Zhang X., Yang S. A learning-based iterative method for solving vehicle routing problems // International conference on learning representations. 2019.

  11. Chen X., Tian Y. Learning to perform local rewriting for combinatorial optimization // Advances in Neural Information Processing Systems. 2019. V. 32.

  12. Nazari M. et al. Reinforcement learning for solving the vehicle routing problem // Advances in neural information processing systems. 2018. V. 31.

  13. Vinyals O., Fortunato M., Jaitly N. Pointer networks // Advances in neural information processing systems. 2015. V. 28.

  14. Vaswani A. et al. Attention is all you need // Advances in neural information processing systems. 2017. V. 30.

  15. Chen X., Tian Y. Learning to perform local rewriting for combinatorial optimization // Advances in Neural Information Processing Systems. 2019. V. 32.

  16. Solomon M.M. Algorithms for the vehicle routing and scheduling problems with time window constraints // Operations research. 1987. V. 35. № 2. P. 254–265.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Доклады Российской академии наук. Математика, информатика, процессы управления

Архивы выпусков Информация о журнале Отправить рукопись в журнал