让神经网络搞定非对称路径规划,提升真实场景适用性
RADAR: Learning to Route with Asymmetry-aware DistAnce Representations
- 用SVD提取非对称距离矩阵的静态特征,生成紧凑嵌入
- 引入Sinkhorn归一化注意力,动态建模节点间双向依赖
- 在合成与真实数据上均显著优于基线,泛化能力强
近期神经求解器在车辆路径问题(VRPs)上表现优异,但主要假设距离为对称欧氏距离,限制了其在真实场景中的应用。核心挑战在于如何编码非对称距离矩阵中的关系特征。早期方法直接编码矩阵,但嵌入不紧凑且泛化能力差。本文提出RADAR,一种可扩展的神经框架,使现有神经VRP求解器具备处理非对称输入的能力。RADAR从静态和动态两个角度应对非对称性:首先对非对称距离矩阵进行奇异值分解(SVD),初始化蕴含节点往返成本差异的紧凑通用嵌入;其次在编码过程中,用Sinkhorn归一化替代标准softmax,使注意力权重同时感知行、列距离,建模动态非对称性。在多种合成与真实世界基准上的实验表明,RADAR在分布内与分布外实例上均优于强基线,展现出卓越的泛化能力和求解性能。
原文摘要 · Abstract (English)
Recent neural solvers have achieved strong performance on vehicle routing problems (VRPs), yet they mainly assume symmetric Euclidean distances, restricting applicability to real-world scenarios. A core challenge is encoding the relational features in asymmetric distance matrices of VRPs. Early attempts directly encoded these matrices but often failed to produce compact embeddings and generalized poorly at scale. In this paper, we propose RADAR, a scalable neural framework that augments existing neural VRP solvers with the ability to handle asymmetric inputs. RADAR addresses asymmetry from both static and dynamic perspectives. It leverages Singular Value Decomposition (SVD) on the asymmetric distance matrix to initialize compact and generalizable embeddings that inherently encode the static asymmetry in the inbound and outbound costs of each node. To further model dynamic asymmetry in embedding interactions during encoding, it replaces the standard softmax with Sinkhorn normalization that imposes joint row and column distance awareness in attention weights. Extensive experiments on synthetic and real-world benchmarks across various VRPs show that RADAR outperforms strong baselines on both in-distribution and out-of-distribution instances, demonstrating robust generalization and superior performance in solving asymmetric VRPs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。