arXiv:2506.16428cs.LG2025-06IJCAI被引 10

用边信息替代节点坐标,提升车辆路径问题求解效果。

EFormer: An Effective Edge-based Transformer for Vehicle Routing Problems

论文配图:EFormer: An Effective Edge-based Transformer for Vehicle Routing Problems
图 1 · 摘自论文原文
  • 以边为输入,通过混合评分注意力生成节点嵌入
  • 在合成数据上优于主流基线,大尺度场景表现更优
  • 适合需要真实成本建模的物流优化场景

当前车辆路径问题(VRP)的神经启发式方法多依赖节点坐标作为输入,在实际应用中可能不够有效,因真实成本度量(如基于边的距离)更为相关。为此,我们提出EFormer,一种仅以边为输入的边基础变换器模型。该方法采用带有混合评分注意力机制的预编码模块,将边信息转换为临时节点嵌入。同时提出并行编码策略,包含图编码器与节点编码器,分别处理图和节点嵌入于不同特征空间,从而获得更全面的边间全局关系表征。解码阶段采用并行上下文嵌入与多查询融合,对两种编码嵌入分别计算注意力机制,实现高效路径构建。使用强化学习进行自回归训练。在旅行商问题(TSP)和容量约束车辆路径问题(CVRP)上的大量实验表明,EFormer在合成数据集(包括大规模、多样化分布)上优于现有基线。此外,其在来自TSPLib和CVRPLib的真实世界实例上也展现出强泛化能力。这些结果验证了EFormer核心设计在解决VRP问题上的有效性。

原文摘要 · Abstract (English)

Recent neural heuristics for the Vehicle Routing Problem (VRP) primarily rely on node coordinates as input, which may be less effective in practical scenarios where real cost metrics-such as edge-based distances-are more relevant. To address this limitation, we introduce EFormer, an Edge-based Transformer model that uses edge as the sole input for VRPs. Our approach employs a precoder module with a mixed-score attention mechanism to convert edge information into temporary node embeddings. We also present a parallel encoding strategy characterized by a graph encoder and a node encoder, each responsible for processing graph and node embeddings in distinct feature spaces, respectively. This design yields a more comprehensive representation of the global relationships among edges. In the decoding phase, parallel context embedding and multi-query integration are used to compute separate attention mechanisms over the two encoded embeddings, facilitating efficient path construction. We train EFormer using reinforcement learning in an autoregressive manner. Extensive experiments on the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) reveal that EFormer outperforms established baselines on synthetic datasets, including large-scale and diverse distributions. Moreover, EFormer demonstrates strong generalization on real-world instances from TSPLib and CVRPLib. These findings confirm the effectiveness of EFormer's core design in solving VRPs.

车辆路径边缘建模Transformer强化学习

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。