Enhancing CVRP Solver through LLM-driven Automatic Heuristic Design
作者: Zhuoliang Xie, Fei Liu, Zhenkun Wang, Qingfu Zhang
分类: cs.AI
发布日期: 2026-02-26
💡 一句话要点
提出基于LLM的自动启发式算法设计AILS-AHD，提升CVRP求解器性能
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 车辆路径问题 组合优化 大型语言模型 启发式算法 自动设计 迭代局部搜索 物流优化
📋 核心要点
- CVRP作为NP-hard问题，在大规模实例求解中面临计算挑战，现有方法难以兼顾效率与精度。
- AILS-AHD利用LLM动态生成和优化AILS中的破坏启发式算法，并引入LLM加速机制，提升求解效率。
- 实验表明，AILS-AHD在多种规模的CVRP实例上优于现有方法，并在大规模基准测试中取得了新的最优解。
📝 摘要（中文）
本研究提出了一种名为AILS-AHD（基于自动启发式设计的自适应迭代局部搜索）的新方法，利用大型语言模型（LLM）革新CVRP（带容量约束的车辆路径问题）的求解。CVRP是一个基础的组合优化难题，旨在优化车辆容量约束下的车队运营。该方法将进化搜索框架与LLM相结合，在AILS方法中动态生成和优化破坏启发式算法。此外，引入了基于LLM的加速机制以提高计算效率。与最先进的求解器（包括AILS-II和HGS）的综合实验评估表明，AILS-AHD在中型和大型实例中均表现出卓越的性能。值得注意的是，我们的方法为CVRPLib大型基准测试中的10个实例中的8个建立了新的最佳已知解决方案，突显了LLM驱动的启发式设计在推动车辆路径优化领域的潜力。
🔬 方法详解
问题定义：论文旨在解决带容量约束的车辆路径问题（CVRP），这是一个经典的组合优化问题。现有方法，如AILS-II和HGS，在解决大规模CVRP实例时，往往面临计算复杂度高、求解时间长的问题，难以在合理时间内找到高质量的解决方案。此外，手工设计的启发式算法难以适应不同规模和特征的CVRP实例，泛化能力有限。
核心思路：论文的核心思路是利用大型语言模型（LLM）的强大生成和优化能力，自动设计和调整AILS算法中的破坏启发式。通过LLM，可以动态生成适应特定CVRP实例的启发式规则，从而提高搜索效率和解的质量。同时，利用LLM进行加速，进一步提升算法的计算效率。
技术框架：AILS-AHD的整体框架包括以下几个主要模块：1) 基于AILS的进化搜索框架：采用迭代局部搜索算法作为基础框架，进行解的搜索和优化。2) LLM驱动的启发式生成模块：利用LLM生成多种破坏启发式算法，用于破坏当前解，扩大搜索空间。3) LLM驱动的启发式优化模块：利用LLM评估和优化生成的启发式算法，选择更有效的启发式算法用于搜索。4) LLM加速模块：利用LLM进行计算加速，减少算法的运行时间。
关键创新：该论文最重要的技术创新点在于将大型语言模型（LLM）引入到CVRP求解器的设计中，实现了启发式算法的自动生成和优化。与传统的启发式算法设计方法相比，该方法无需人工干预，可以自动适应不同规模和特征的CVRP实例，具有更强的泛化能力和更高的求解效率。
关键设计：论文的关键设计包括：1) 如何设计LLM的prompt，使其能够生成有效的破坏启发式算法。2) 如何利用LLM评估和优化生成的启发式算法，选择更有效的启发式算法用于搜索。3) 如何设计LLM加速模块，减少算法的运行时间。具体的参数设置、损失函数和网络结构等技术细节在论文中未详细描述，属于未知信息。
🖼️ 关键图片
📊 实验亮点
实验结果表明，AILS-AHD在多个CVRP基准测试集上取得了显著的性能提升。特别是在CVRPLib大型基准测试中，AILS-AHD为10个实例中的8个建立了新的最佳已知解决方案，超越了现有的最先进求解器AILS-II和HGS。这充分证明了LLM驱动的启发式设计在解决大规模CVRP问题上的有效性和优越性。
🎯 应用场景
该研究成果可广泛应用于物流配送、交通运输、供应链管理等领域，例如优化快递车辆的配送路线、减少运输成本、提高配送效率。通过LLM自动设计启发式算法，可以快速适应不同的业务场景和需求变化，为企业提供更灵活、高效的车辆路径优化解决方案。未来，该方法有望推广到其他组合优化问题，如旅行商问题、调度问题等。
📄 摘要（原文）
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.