Email this article 
Smart Routes: A System for Development and Comparison of Algorithms for Solving Vehicle Routing Problems with Realistic Constraints
- Authors: Soroka A.G1, Mikhelson G.V1, Mescheryakov A.V1,2, Gerasimov S.V1
-
Affiliations:
- Московский государственный университет им. М.В. Ломоносова
- Институт космических исследований РАН
- Issue: No 3 (2024)
- Pages: 101-118
- Section: Topical issue
- URL: https://rjmseer.com/0005-2310/article/view/646932
- DOI: https://doi.org/10.31857/S0005231024030083
- EDN: https://elibrary.ru/TOTOOH
- ID: 646932
Cite item
Open Access
Access granted
Subscription or Fee Access
Abstract
Задача оптимизации маршрутов с реалистичными ограничениями становится крайне актуальной в условиях глобального роста городского населения. Подходы к оптимизации маршрутов, включая точные методы, сталкиваются с проблемой экспоненциальной сложности при увеличении размера задачи оптимизации маршрутов. В работе сравнивается точный решатель SCIP с эвристическими методами (LKH, 2-OPT, 3-OPT, ORTools) и моделью глубокого обучения JAMPR+. Для задач размером 50 глубокое обучение и классические эвристики достигают точности, сравнимой с SCIP, но требуют меньше времени. Для задач размером 100, эвристики и нейронные сети значительно опережают SCIP как по времени, так и по качеству первого найденного решения. Для проведения экспериментов разработана платформа Smart Routes для решения задачи оптимизации маршрутов, которая включает в себя точные, эвристические и нейросетевые модели и облегчает удобное интегрирование собственных алгоритмов и наборов данных.
Keywords
About the authors
A. G Soroka
Московский государственный университет им. М.В. Ломоносова
Email: andrew.soroka@student.msu.ru
G. V Mikhelson
Московский государственный университет им. М.В. Ломоносова
Email: mikhelson.g@gmail.com
A. V Mescheryakov
Московский государственный университет им. М.В. Ломоносова; Институт космических исследований РАН
Email: mesch@cosmos.ru
канд. физ.-мат. наук
S. V Gerasimov
Московский государственный университет им. М.В. Ломоносова
Email: sergun@gmail.com
References
- Laporte G., Nobert Y. A branch and bound algorithm for the capacitated vehicle routing problem // Operations-Research-Spektrum. 1983. V. 5. P. 77–85.
- 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.
- 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.
- IBM ILOG Cplex V12. 1: User’s Manual for CPLEX // Int. Busin. Machin. Corporat. 2009. V. 46. No. 53. P. 157.
- 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
- Gurobi Optimization, LLC Gurobi Optimizer Reference Manual // 2023. https://www.gurobi.com
- 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.
- Vinyals O., Fortunato M., Jaitly N. Pointer networks // Conf. Advances Neural Inform. Proc. Syst. 2015. V. 28.
- Kool W., Hoof H.V., Welling M. Attention, learn to solve routing problems! // 2018. arXiv preprint arXiv:1803.08475.
- Vaswani A., Shazeer N., Parmar N., et al. Attention is all you need // Conf. Advances Neural Inform. Proc. Syst. 2017. V. 30.
- Falkner J.K., Schmidt-Thieme L. Learning to solve vehicle routing problems with time windows through joint attention // arXiv preprint arXiv:2006.09100. 2020.
- Chen X., Tian Y. Learning to perform local rewriting for combinatorial optimization // Conf. Advances Neural Inform. Proc. Syst. 2019. V. 32.
- Lu H., Zhang X., Yang S. A learning-based iterative method for solving vehicle routing problems // International conference on learning representations. 2019.
- Li S., Yan Z., Wu C. Learning to delegate for large-scale vehicle routing // Conf. Advances Neural Inform. Proc. Syst. 2021. V. 34.
- 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.
- 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.
- Helsgaun K. An effective implementation of the Lin–Kernighan traveling salesman heuristic // Eur. J. Oper. Res. 2000. V. 126. No. 1. P. 106–130.
- 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.
- 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.
- Perron L. Operations research and constraint programming at google // International Conference on Principles and Practice of Constraint Programming. 2011. P. 2–2.
- 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.
Supplementary files
