arXiv:2507.21386cs.LGcs.AI2025-07被引 3

提出ECHO模型,高效求解复杂车辆路径问题。

Efficient Neural Combinatorial Optimization Solver for the Min-max Heterogeneous Capacitated Vehicle Routing Problem

  • 双模态编码捕捉节点局部拓扑关系
  • 无参数交叉注意力提升决策全局性,降低短视风险
  • 数据增强策略稳定训练,适合多车异构场景

众多神经组合优化(NCO)求解器被提出用于解决车辆路径问题(VRP),但多数仅针对单一车辆变体,忽略了更贴近现实的最小最大异构容量车辆路径问题(MMHCVRP),该问题涉及多辆车。现有MMHCVRP求解器在每个解码步骤中仅选择一辆车及其下一个访问节点,常做出短视决策,并忽略关键属性如局部拓扑关系、车辆排列不变性和节点对称性,导致性能不佳。为此,我们提出ECHO,一种高效的NCO求解器。首先,利用所提出的双模态节点编码器捕捉节点间的局部拓扑关系;其次,为缓解短视决策,引入无参数交叉注意力机制,优先考虑前一解码步骤选定的车辆;最后,结合车辆排列不变性和节点对称性,设计定制化数据增强策略以稳定强化学习训练过程。通过大量实验验证,ECHO在不同车辆数和节点数下均优于当前最优的NCO求解器,且在规模和分布模式上表现出良好泛化能力。消融实验证明了各项设计的有效性。

原文摘要 · Abstract (English)

Numerous Neural Combinatorial Optimization (NCO) solvers have been proposed to address Vehicle Routing Problems (VRPs). However, most of these solvers focus exclusively on single-vehicle VRP variants, overlooking the more realistic min-max Heterogeneous Capacitated Vehicle Routing Problem (MMHCVRP), which involves multiple vehicles. Existing MMHCVRP solvers typically select a vehicle and its next node to visit at each decoding step, but often make myopic decoding decisions and overlook key properties of MMHCVRP, including local topological relationships, vehicle permutation invariance, and node symmetry, resulting in suboptimal performance. To better address these limitations, we propose ECHO, an efficient NCO solver. First, ECHO exploits the proposed dual-modality node encoder to capture local topological relationships among nodes. Subsequently, to mitigate myopic decisions, ECHO employs the proposed Parameter-Free Cross-Attention mechanism to prioritize the vehicle selected in the preceding decoding step. Finally, leveraging vehicle permutation invariance and node symmetry, we introduce a tailored data augment strategy for MMHCVRP to stabilize the Reinforcement Learning training process. To assess the performance of ECHO, we conduct extensive experiments. The experimental results demonstrate that ECHO outperforms state-of-the-art NCO solvers across varying numbers of vehicles and nodes, and exhibits well-performing generalization across both scales and distribution patterns. Finally, ablation studies validate the effectiveness of all proposed methods.

组合优化车辆路径神经求解器

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