用大模型自动设计启发式算法，提升车辆路径问题求解效果
Enhancing CVRP Solver through LLM-driven Automatic Heuristic Design
- 用大模型动态生成并优化破坏性启发式策略
- 在10个大规模测试集上创下8个新最优解
- 适合对智能优化算法感兴趣的研究者
容量限制车辆路径问题（CVRP）是运筹学中的基础组合优化难题，旨在满足车辆容量约束下优化车队调度。尽管研究广泛，其NP难特性仍给大规模实例带来显著计算挑战。本文提出AILS-AHD（自适应迭代局部搜索与自动启发式设计），利用大语言模型（LLMs）革新CVRP求解方法。该方法将进化搜索框架与LLM结合，动态生成并优化AILS中的破坏启发式策略，并引入基于LLM的加速机制以提升计算效率。在包括AILS-II和HGS在内的先进求解器对比中，AILS-AHD在中等与大规模实例上均表现优异。特别地，在CVRPLib大规模基准测试中，该方法为10个实例中的8个建立了新的最优解，验证了大模型驱动启发式设计在车辆路径优化领域的巨大潜力。
原文摘要 · Abstract (English)
The Capacitated Vehicle Routing Problem (CVRP), a fundamental combinatorial optimization challenge, focuses on optimizing fleet operations under vehicle capacity constraints. While extensively studied in operational research, the NP-hard nature of CVRP continues to pose significant computational challenges, particularly for large-scale instances. This study presents AILS-AHD (Adaptive Iterated Local Search with Automatic Heuristic Design), a novel approach that leverages Large Language Models (LLMs) to revolutionize CVRP solving. Our methodology integrates an evolutionary search framework with LLMs to dynamically generate and optimize ruin heuristics within the AILS method. Additionally, we introduce an LLM-based acceleration mechanism to enhance computational efficiency. Comprehensive experimental evaluations against state-of-the-art solvers, including AILS-II and HGS, demonstrate the superior performance of AILS-AHD across both moderate and large-scale instances. Notably, our approach establishes new best-known solutions for 8 out of 10 instances in the CVRPLib large-scale benchmark, underscoring the potential of LLM-driven heuristic design in advancing the field of vehicle routing optimization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。