用图神经网络指导删点策略，提升车辆路径问题求解效率。
Hybrid Node-Destroyer Model with Large Neighborhood Search for Solving the Capacitated Vehicle Routing Problem
- 用GNN识别重要节点，指导大邻域搜索的删点操作。
- 在3万节点的大规模实例上仍保持高效，优于基线算法。
- 无需重新训练，可直接应用于不同规模问题。
本文提出一种迭代学习的混合优化求解器，用于增强元启发式算法在解决容量限制车辆路径问题（CVRP）时的性能。该方法融合了基于图神经网络（GNN）的节点删除模型，通过分析问题与解的图结构特征，智能选择需删除的客户节点，以引导大邻域搜索（LNS）算子。该机制有效降低运算复杂度，缩小搜索空间。所提方法专用于CVRP，且无需针对不同规模问题重新训练。实验表明，该混合机制能显著提升多种基线元启发式算法的性能，在标准测试集上获得更优解，并在含最多30,000个客户节点的超大规模实例中展现出良好可扩展性。
原文摘要 · Abstract (English)
In this research, we propose an iterative learning hybrid optimization solver developed to strengthen the performance of metaheuristic algorithms in solving the Capacitated Vehicle Routing Problem (CVRP). The iterative hybrid mechanism integrates the proposed Node-Destroyer Model, a machine learning hybrid model that utilized Graph Neural Networks (GNNs) such identifies and selects customer nodes to guide the Large Neighborhood Search (LNS) operator within the metaheuristic optimization frameworks. This model leverages the structural properties of the problem and solution that can be represented as a graph, to guide strategic selections concerning node removal. The proposed approach reduces operational complexity and scales down the search space involved in the optimization process. The hybrid approach is applied specifically to the CVRP and does not require retraining across problem instances of different sizes. The proposed hybrid mechanism is able to improve the performance of baseline metaheuristic algorithms. Our approach not only enhances the solution quality for standard CVRP benchmarks but also proves scalability on very large-scale instances with up to 30,000 customer nodes. Experimental evaluations on benchmark datasets show that the proposed hybrid mechanism is capable of improving different baseline algorithms, achieving better quality of solutions under similar settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。