通过聚类客户点加速求解带时间窗的车辆路径问题。
Graph-Coarsening Approach for the Capacitated Vehicle Routing Problem with Time Windows
- 将客户按时空距离聚合成节点，降低问题规模。
- 在56个基准实例上，计算时间显著缩短，且不丢失解的可行性。
- 对密集型数据集效果尤佳，适合物流优化与量子计算应用。
带时间窗的容量车辆路径问题（CVRPTW）是物流领域经典的NP难优化问题，大规模实例对精确求解器仍具计算挑战。本文提出一种多层图粗化与精化策略，基于时空距离度量将客户聚合为元节点，降低问题规模后使用经典启发式算法和量子退火硬件求解，再还原至原始空间并重新计算到达时间与约束违反情况。在Solomon基准测试集上的实验表明，该方法显著减少计算时间，同时保持经典启发式算法的解质量。对于量子求解器，在全部56个Solomon实例上（分别在N=5和N=10客户数下），粗化始终降低计算时间；在聚类型（C型）实例中，还同时减少车辆数量与路线时长，且无可行性损失。粗化效果高度依赖实例结构：C型实例可实现100%后粗化可行性并获得可观质量提升，而窄窗随机型（R型）实例因结构限制难以深度粗化。
原文摘要 · Abstract (English)
The Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) is a fundamental NP-hard optimization problem in logistics. Solving large-scale instances remains computationally challenging for exact solvers. This paper introduces a multilevel graph coarsening and refinement strategy that aggregates customers into meta-nodes based on a spatio-temporal distance metric. The reduced problem is solved using both classical heuristics and quantum annealing hardware, then expanded back into the original space with arrival times recomputed and constraint violations recorded. Comprehensive experiments on Solomon benchmarks demonstrate that our method significantly reduces computation time while preserving solution quality for classical heuristics. For quantum solvers, experiments across all 56 Solomon instances at $N=5$ and $N=10$ customers show that coarsening consistently reduces computation time and, on clustered (C-type) instances, simultaneously reduces vehicle count and route duration with no feasibility loss. Coarsening effectiveness is strongly instance-structure dependent: C-type instances achieve %100 post-coarsening feasibility with measurable quality improvements, while narrow-window random (R-type) instances present structural constraints that limit achievable coarsening depth.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。