用图神经网络和自适应惩罚优化量子退火求解带时间窗的车辆路径问题。
GNN-Guided Graph Coarsening and Adaptive QUBO Penalties for the Capacitated Vehicle Routing Problem with Time Windows on a Quantum Annealer
- 用GNN替代人工调参的合并策略，提升不同数据集的可行性。
- 自适应惩罚使约束违反率从33.0降至0.06，显著提升解质量。
- 适合研究量子计算求解组合优化问题的学者与工程师。
图粗化能降低量子退火求解车辆路径问题时产生的大型无约束二次二值优化（QUBO）规模。通过将时间窗兼容的邻近客户合并为超节点，求解简化问题后扩展回原图。针对带容量与时间窗的车辆路径问题（CVRPTW），现有粗化启发式需按家族调参且在随机实例上不可靠。本文在Solomon基准上使用模拟退火与D-Wave Advantage2处理器解决该问题。首先提出自适应惩罚校准：统一缩放效果有限，而控制内部系数范围显著改善原始样本质量。移除非紧约束、归一化紧约束并缩放剩余惩罚，相同求解预算下平均原始约束违反率由33.0降至0.06（p=3.7e-11, n=56）。变量数不变的控制实验表明性能提升源于问题条件改善而非规模减小。其次，用一个配置的图神经网络（GNN）取代人工调参的合并评分，在N=10时所有Solomon家族可行性达100%（对比调参启发式80%）。N=10,...,100范围内可行性为83%对69%，在85/90实例对中表现更好或持平；在N=80,100时差异显著（p=0.002，25/25对）。同时QUBO规模仍保持约5-6倍缩小。最后，硬件实验在固定逻辑变量数下重现了条件改善效应：可行样本率从0.02%升至39%（覆盖13个实例）。经典修复结合局部搜索仍为端到端解成本的参考基准。
原文摘要 · Abstract (English)
Graph coarsening reduces the large Quadratic Unconstrained Binary Optimization (QUBO) formulations arising when vehicle-routing problems are solved by quantum annealing. Nearby customers with compatible time windows are merged into super-nodes, the reduced problem is solved, and the solution is expanded to the original graph. For the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), existing coarsening heuristics require family-specific tuning and remain unreliable on random instances. We address these limitations on the Solomon benchmark using simulated annealing and a D-Wave Advantage2 processor. We first introduce adaptive penalty calibration. Uniform penalty scaling has little effect, whereas controlling the internal coefficient range substantially improves raw samples. Removing non-binding constraints, normalising binding ones, and scaling the remaining penalties reduces mean raw constraint violations from 33.0 to 0.06 at the same solver budget (p=3.7e-11, n=56). A variable-count-preserving control attributes this gain to conditioning rather than problem size. Second, we replace the hand-tuned merge score with a graph neural network (GNN) using one configuration across all families. At N=10, it achieves 100% feasibility across all Solomon families, including R-type (100% vs. 80% for the tuned heuristic). Across N=10,...,100, feasibility is 83% vs. 69%, with the GNN better or tied on 85/90 instance-size pairs. At N=80,100, the difference is significant (p=0.002; 25/25 pairs), while the QUBO remains approximately 5-6 times smaller. Finally, hardware experiments reproduce the conditioning effect at fixed logical variable count: feasible samples increase from 0.02% to 39% across 13 instances. Classical repair with local search remains a reference bound for end-to-end solution cost.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。