对比多种算法解决带时间窗的车辆路径问题，发现深度学习与启发式方法在效率上显著优于精确求解器。
Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints
- 构建Smart Routes平台集成精确、启发式与深度学习模型，支持自定义算法与数据集
- 规模50时，深度学习与启发式算法接近SCIP最优解，耗时更少；规模100时，SCIP慢约13倍
- 在相同时间内，SCIP首次可行解质量差约50%，适合大规模实时优化场景
随着全球城市人口增长，考虑现实约束的路径优化问题日益重要。尽管存在理论上可得最优解的方法，但随着问题规模增大，其指数级复杂度使应用变得困难。本文研究带时间窗的容量受限车辆路径问题（CVRPTW），对比精确求解器SCIP与启发式算法（如LKH、2-OPT、3-OPT）、ORTools框架及深度学习模型JAMPR的性能。实验表明：当问题规模为50时，深度学习与经典启发式算法的解接近SCIP最优解，但耗时更短；当规模增至100时，SCIP在相同路径成本下运行速度慢约13倍，且在相同时间内首次可行解质量差约50%。为此，本文开发了Smart Routes平台，整合精确、启发式与深度学习模型，支持自定义算法和数据集的便捷集成。
原文摘要 · Abstract (English)
The problem of route optimization with realistic constraints is becoming extremely relevant in the face of global urban population growth. While we are aware of approaches that theoretically provide an exact optimal solution, their application becomes challenging as the problem size increases because of exponential complexity. We investigate the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) and compare solutions obtaining by exact solver SCIP with heuristic algorithms such as LKH, 2-OPT, 3-OPT, the ORTools framework, and the deep learning model JAMPR. We demonstrate that for problem of size 50 deep learning and classical heuristic solutions became close to SCIP exact solution but requires less time. Additionally for problems with size 100, SCIP exact methods around 13 times slower that neural and classical heuristics with the same route cost and on around 50% worse for the first feasible solution on the same time. To conduct experiments, we developed the Smart Routes platform for solving route optimization problems, which includes exact, heuristic, and deep learning models, and facilitates convenient integration of custom algorithms and datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。