- Код статьи
- 10.31857/S0005231024030083-1
- DOI
- 10.31857/S0005231024030083
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том / Номер выпуска 3
- Страницы
- 101-118
- Аннотация
- Задача оптимизации маршрутов с реалистичными ограничениями становится крайне актуальной в условиях глобального роста городского населения. Подходы к оптимизации маршрутов, включая точные методы, сталкиваются с проблемой экспоненциальной сложности при увеличении размера задачи оптимизации маршрутов. В работе сравнивается точный решатель SCIP с эвристическими методами (LKH, 2-OPT, 3-OPT, ORTools) и моделью глубокого обучения JAMPR+. Для задач размером 50 глубокое обучение и классические эвристики достигают точности, сравнимой с SCIP, но требуют меньше времени. Для задач размером 100, эвристики и нейронные сети значительно опережают SCIP как по времени, так и по качеству первого найденного решения. Для проведения экспериментов разработана платформа Smart Routes для решения задачи оптимизации маршрутов, которая включает в себя точные, эвристические и нейросетевые модели и облегчает удобное интегрирование собственных алгоритмов и наборов данных.
- Ключевые слова
- система оптимизации маршрутов эвристики точные решения глубокое обучение с подкреплением
- Дата публикации
- 15.03.2024
- Год выхода
- 2024
- Всего подписок
- 0
- Всего просмотров
- 9
Библиография
- 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.
