SMART ROUTES: СИСТЕМА ДЛЯ РАЗРАБОТКИ И СРАВНЕНИЯ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ ОПТИМИЗАЦИИ МАРШРУТОВ С РЕАЛИСТИЧНЫМИ ОГРАНИЧЕНИЯМИ

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Доступ платный или только для подписчиков

Аннотация

Задача оптимизации маршрутов с реалистичными ограничениями становится крайне актуальной в условиях глобального роста городского населения. Подходы к оптимизации маршрутов, включая точные методы, сталкиваются с проблемой экспоненциальной сложности при увеличении размера задачи оптимизации маршрутов. В работе сравнивается точный решатель SCIP с эвристическими методами (LKH, 2-OPT, 3-OPT, ORTools) и моделью глубокого обучения JAMPR+. Для задач размером 50 глубокое обучение и классические эвристики достигают точности, сравнимой с SCIP, но требуют меньше времени. Для задач размером 100, эвристики и нейронные сети значительно опережают SCIP как по времени, так и по качеству первого найденного решения. Для проведения экспериментов разработана платформа Smart Routes для решения задачи оптимизации маршрутов, которая включает в себя точные, эвристические и нейросетевые модели и облегчает удобное интегрирование собственных алгоритмов и наборов данных.

Об авторах

А. Г СОРОКА

Московский государственный университет им. М.В. Ломоносова

Email: andrew.soroka@student.msu.ru

Г. В МИХЕЛЬСОН

Московский государственный университет им. М.В. Ломоносова

Email: mikhelson.g@gmail.com

А. В МЕЩЕРЯКОВ

Московский государственный университет им. М.В. Ломоносова; Институт космических исследований РАН

Email: mesch@cosmos.ru
канд. физ.-мат. наук

С. В ГЕРАСИМОВ

Московский государственный университет им. М.В. Ломоносова

Email: sergun@gmail.com

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

  1. Laporte G., Nobert Y. A branch and bound algorithm for the capacitated vehicle routing problem // Operations-Research-Spektrum. 1983. V. 5. P. 77–85.
  2. Cook W., Rich J.L. A parallel cutting-plane algorithm for the vehicle routing problem with time windows // Technical Report TR99-04, Computational and Applied Mathematics, Rice University, Housten. 1999.
  3. Augerat P., Naddef D., Belenguer J.M., et al. Computational results with a branch and cut code for the capacitated vehicle routing problem / Research report — IMAG. 1995.
  4. IBM ILOG Cplex V12. 1: User’s Manual for CPLEX // Int. Busin. Machin. Corporat. 2009. V. 46. No. 53. P. 157.
  5. Bestuzheva K., Besancon M., Chen W.-K., et al. The SCIP Optimization Suite 8.0 // Technical Report, Optimization Online. 2021. http://www.optimization-online.org/DB_HTML/2021/12/8728.html
  6. Gurobi Optimization, LLC Gurobi Optimizer Reference Manual // 2023. https://www.gurobi.com
  7. Nazari M., Oroojlooy A., Snyder L., et al. Reinforcement learning for solving the vehicle routing problem // Conf. Advances Neural Inform. Proc. Syst. 2018. V. 31.
  8. Vinyals O., Fortunato M., Jaitly N. Pointer networks // Conf. Advances Neural Inform. Proc. Syst. 2015. V. 28.
  9. Kool W., Hoof H.V., Welling M. Attention, learn to solve routing problems! // 2018. arXiv preprint arXiv:1803.08475.
  10. Vaswani A., Shazeer N., Parmar N., et al. Attention is all you need // Conf. Advances Neural Inform. Proc. Syst. 2017. V. 30.
  11. Falkner J.K., Schmidt-Thieme L. Learning to solve vehicle routing problems with time windows through joint attention // arXiv preprint arXiv:2006.09100. 2020.
  12. Chen X., Tian Y. Learning to perform local rewriting for combinatorial optimization // Conf. Advances Neural Inform. Proc. Syst. 2019. V. 32.
  13. Lu H., Zhang X., Yang S. A learning-based iterative method for solving vehicle routing problems // International conference on learning representations. 2019.
  14. Li S., Yan Z., Wu C. Learning to delegate for large-scale vehicle routing // Conf. Advances Neural Inform. Proc. Syst. 2021. V. 34.
  15. Soroka A.G., Meshcheryakov A.V., Gerasimov S.V. Deep Reinforcement Learning for the Capacitated Pickup and Delivery Problem with Time Windows // Patt. Recognit. Imag. Anal. 2023. V. 33. No. 2. P. 169–178.
  16. Gro¨er C., Golden B., Wasil E. A library of local search heuristics for the vehicle routing problem // Math. Program. Comput. 2010. V. 2. P. 79–101.
  17. Helsgaun K. An effective implementation of the Lin–Kernighan traveling salesman heuristic // Eur. J. Oper. Res. 2000. V. 126. No. 1. P. 106–130.
  18. C¸ etinkaya C., Karaoglan I., G¨okcen H. Two-stage vehicle routing problem with arc time windows: A mixed integer programming formulation and a heuristic approach // Eur. J. Oper. Res. 2013. V. 230. No. 3. P. 539–550.
  19. Tahernejad S., Ralphs T.K., DeNegre S.T. A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation // Math. Program. Comput. 2020. V. 12. P. 529–568.
  20. Perron L. Operations research and constraint programming at google // International Conference on Principles and Practice of Constraint Programming. 2011. P. 2–2.
  21. Solomon M.M. Algorithms for the vehicle routing and scheduling problems with time window constraints // Oper. Res. Inf. 1987. V. 35. No. 2. P. 254–265.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2024