arXiv:2412.00346cs.AI2024-12被引 30

提出新型路由求解器CaDA,能高效处理多种带约束的车辆路径问题。

CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention

  • 引入约束提示与双注意力机制,精准建模不同问题变体
  • 在16种VRP任务上均达当前最佳性能,显著优于现有方法
  • 适合需要跨问题通用求解的工业优化场景

车辆路径问题(VRPs)是重要的组合优化问题,具有广泛的实际应用价值。近年来,神经组合优化(NCO)通过大规模数据训练深度学习模型来学习车辆路径启发式算法,展现出高效性与减少人工设计的优势。然而,将NCO应用于包含多种约束的多样化现实场景时,仍需具备跨问题泛化能力。现有NCO方法通常采用统一模型且缺乏约束特异性结构,限制了跨问题表现;而多任务方法多为约束无关模型,仅依赖全局连接,难以聚焦关键节点,导致表征学习效率低下。本文提出约束感知双注意力模型(CaDA),通过引入约束提示有效表示不同问题变体,并设计双注意力机制:全局分支捕捉图级信息,稀疏分支专注最相关节点。我们在16种不同的VRP上全面评估该模型,并与现有跨问题求解器对比。结果表明,CaDA在所有任务上均达到当前最优水平。消融实验进一步验证了各组件对跨问题学习性能的正向贡献。

原文摘要 · Abstract (English)

Vehicle Routing Problems (VRPs) are significant Combinatorial Optimization (CO) problems holding substantial practical importance. Recently, Neural Combinatorial Optimization (NCO), which involves training deep learning models on extensive data to learn vehicle routing heuristics, has emerged as a promising approach due to its efficiency and the reduced need for manual algorithm design. However, applying NCO across diverse real-world scenarios with various constraints necessitates cross-problem capabilities. Current NCO methods typically employ a unified model lacking a constraint-specific structure, thereby restricting their cross-problem performance. Current multi-task methods for VRPs typically employ a constraint-unaware model, limiting their cross-problem performance. Furthermore, they rely solely on global connectivity, which fails to focus on key nodes and leads to inefficient representation learning. This paper introduces a Constraint-Aware Dual-Attention Model (CaDA), designed to address these limitations. CaDA incorporates a constraint prompt that efficiently represents different problem variants. Additionally, it features a dual-attention mechanism with a global branch for capturing broader graph-wide information and a sparse branch that selectively focuses on the most relevant nodes. We comprehensively evaluate our model on 16 different VRPs and compare its performance against existing cross-problem VRP solvers. CaDA achieves state-of-the-art results across all the VRPs. Our ablation study further confirms that each component of CaDA contributes positively to its cross-problem learning performance.

组合优化神经求解器车辆路径双注意力

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