摘要
众多神经组合优化(NCO)求解器被提出用于解决车辆路径问题(VRPs)。然而，大多数求解器仅关注单车辆VRP变体，忽视了更现实的最小最大异构容量车辆路径问题(MMHCVRP)——该问题涉及多车辆协同。现有MMHCVRP求解器通常在每个解码步骤选择车辆及其下一个访问节点，但往往做出短视的解码决策，且忽略了MMHCVRP的关键特性，包括局部拓扑关系、车辆排列不变性和节点对称性，导致次优性能。
为更好解决这些局限，本文提出ECHO高效NCO求解器：首先通过双模态节点编码器捕捉节点间局部拓扑关系；其次采用无参数交叉注意力机制优先处理前序解码步骤选中的车辆以避免短视决策；最后利用车辆排列不变性和节点对称性，设计MMHCVRP专用数据增强策略以稳定强化学习训练过程。实验表明，ECHO在不同车辆和节点规模下均优于当前最优NCO求解器，且在规模和分布模式上均表现出良好的泛化能力。消融研究验证了所有提出方法的有效性。
关键技术
- 双模态节点编码器
- 通过融合空间坐标和拓扑特征的双通道编码，精确建模节点间的局部空间关系。
- 无参数交叉注意力机制
- 动态计算历史选择车辆与当前候选车辆的关联权重，避免传统注意力机制中的参数冗余问题。
- 对称性增强训练策略
- 基于车辆排列不变性原理，对训练数据进行随机车辆序列重排；依据节点对称性生成镜像路径样本，提升模型鲁棒性。
实验验证
在标准MMHCVRP基准测试中，ECHO相比传统OR-Tools求解器平均缩短路径长度12.7%，较最新神经方法NAR4VRP提升4.3%的解决方案质量。在200节点规模的泛化测试中，未见过的大规模实例上仍保持89%的原始性能。 更多精彩内容 请关注我的个人公众号 公众号（办公AI智能小助手）
