用超图重构路由搜索，提升大规模路径优化精度
Destroy and Repair Using Hyper Graphs for Routing
- 基于超图设计破坏-重建策略，扩大局部搜索范围
- 在10000节点的TSP上达当前最优，且泛化性强
- 适合需要高效解大规模路径问题的研究者
神经组合优化近期在解决旅行商问题（TSP）和容量约束车辆路径问题（CVRP）方面展现出潜力，无需手工设计。该领域方法主要分为迭代与非迭代两类：非迭代方法难以直接生成近优解，而现有迭代方法受限于狭窄的邻域搜索，导致结果次优。为此，本文提出一种新框架——基于超图的破坏-重建（DRHG），通过将连续完整边压缩为超边，使模型更关注被破坏部分，并降低全节点编码复杂度。实验表明，DRHG在最多10,000节点的TSP任务中达到当前最优性能，并在真实世界数据集TSPLib和CVRPLib上表现出良好泛化能力。
原文摘要 · Abstract (English)
Recent advancements in Neural Combinatorial Optimization (NCO) have shown promise in solving routing problems like the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) without handcrafted designs. Research in this domain has explored two primary categories of methods: iterative and non-iterative. While non-iterative methods struggle to generate near-optimal solutions directly, iterative methods simplify the task by learning local search steps. However, existing iterative methods are often limited by restricted neighborhood searches, leading to suboptimal results. To address this limitation, we propose a novel approach that extends the search to larger neighborhoods by learning a destroy-and-repair strategy. Specifically, we introduce a Destroy-and-Repair framework based on Hyper-Graphs (DRHG). This framework reduces consecutive intact edges to hyper-edges, allowing the model to pay more attention to the destroyed part and decrease the complexity of encoding all nodes. Experiments demonstrate that DRHG achieves stateof-the-art performance on TSP with up to 10,000 nodes and shows strong generalization to real-world TSPLib and CVRPLib problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。