解决神经组合优化在车辆路径问题中的约束过拟合问题
Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degrees
- 设计多专家架构，显式建模不同约束紧度下的解法策略
- 在多种约束紧度下，对带容量和时间窗的车辆路径问题表现更优
- 适合需要鲁棒解法的物流调度场景，尤其在约束变化时
近期神经组合优化（NCO）方法在无需领域知识的情况下展现出强大的求解能力。然而，现有方法通常使用固定约束值的训练与测试数据，缺乏对约束紧度影响性能的研究。本文以容量约束车辆路径问题（CVRP）为例，实证分析了不同容量约束紧度下NCO方法的表现。结果表明，现有方法严重过拟合容量约束，仅在少数约束值下表现良好，其他情况下性能显著下降。为此，本文提出一种高效训练方案，显式考虑约束紧度的变化，并引入多专家模块以学习通用适应性求解策略。实验结果显示，所提方法有效缓解过拟合问题，在不同约束紧度的CVRP与带时间窗的CVRP（CVRPTW）上均取得优异表现。
原文摘要 · Abstract (English)
Recent neural combinatorial optimization (NCO) methods have shown promising problem-solving ability without requiring domain-specific expertise. Most existing NCO methods use training and testing data with a fixed constraint value and lack research on the effect of constraint tightness on the performance of NCO methods. This paper takes the capacity-constrained vehicle routing problem (CVRP) as an example to empirically analyze the NCO performance under different tightness degrees of the capacity constraint. Our analysis reveals that existing NCO methods overfit the capacity constraint, and they can only perform satisfactorily on a small range of the constraint values but poorly on other values. To tackle this drawback of existing NCO methods, we develop an efficient training scheme that explicitly considers varying degrees of constraint tightness and proposes a multi-expert module to learn a generally adaptable solving strategy. Experimental results show that the proposed method can effectively overcome the overfitting issue, demonstrating superior performances on the CVRP and CVRP with time windows (CVRPTW) with various constraint tightness degrees.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。