VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problems
VRPAgent uses LLMs to generate heuristic operators, optimized via genetic algorithms, outperforming handcrafted methods on multiple VRP variants.
Key Findings
Methodology
VRPAgent integrates pre-trained large language models (e.g., Gemini 2.5 Flash) to generate problem-specific destruction (fREMOVE) and reconstruction (fORDER) operators. These operators are embedded within a large neighborhood search (LNS) framework, which guides iterative solution improvement. A genetic algorithm (GA) optimizes the operator pair through biased crossover and mutation, evaluated by solution quality and code complexity penalties. The approach ensures solution feasibility and robustness across capacitated VRP, VRP with time windows, and prize-collecting VRP, demonstrating superior performance over state-of-the-art methods.
Key Results
- On instances with up to 2000 nodes, VRPAgent achieves solution gaps below -0.3% relative to the best benchmarks, outperforming traditional heuristics and GPU-based learning methods. The method requires only a single CPU core, significantly reducing hardware costs while maintaining high solution quality.
- Across multiple problem variants, VRPAgent consistently outperforms recent learning-based approaches like ReEvo-ACO and NCO-LLM, especially in large-scale scenarios. Ablation studies confirm the importance of biased crossover and mutation, while code length penalties improve interpretability and efficiency.
- Experimental results demonstrate that the generated heuristics generalize well across different problem types, maintaining solution quality and computational efficiency, with stable performance in diverse constraint settings.
Significance
This work advances automated heuristic discovery for VRPs, addressing longstanding challenges of manual design complexity and limited scalability. By leveraging LLMs within a metaheuristic framework, it offers a scalable, interpretable, and high-performance solution that can be readily adapted to real-world logistics and scheduling problems. The approach reduces reliance on expert knowledge, democratizing access to advanced optimization techniques, and paves the way for broader applications in combinatorial optimization and industrial logistics.
Technical Contribution
The key innovations include: 1) embedding pre-trained LLMs for modular heuristic operator generation; 2) integrating these operators within a large neighborhood search framework that guarantees feasibility; 3) employing a genetic algorithm with biased crossover and mutation for efficient search of operator space; 4) introducing code length penalties to balance performance and interpretability. These elements collectively enable the automatic discovery of powerful, interpretable heuristics, surpassing existing learning-based and handcrafted methods in solution quality and resource efficiency.
Novelty
This is the first work to embed large language models directly into a metaheuristic for VRP, generating problem-specific operators that are optimized via evolutionary strategies. Unlike prior approaches focusing on end-to-end neural solutions or fragmentary code snippets, VRPAgent modularizes operator design, ensuring correctness and interpretability. This paradigm shift opens new avenues for AI-driven automated heuristic discovery in complex combinatorial problems.
Limitations
- The approach depends on the quality of pre-trained LLMs; in unfamiliar or highly specialized scenarios, generated operators may be suboptimal without further tuning.
- The genetic search may not fully explore the operator space, risking local optima, especially in highly complex or dynamic environments.
- Scalability to real-time or highly dynamic settings remains limited, as the current framework focuses on static problem instances with offline training.
Future Work
Future directions include integrating reinforcement learning to adapt operators dynamically, expanding multi-modal data inputs for richer operator design, and scaling to larger, more complex, multi-objective problems. Enhancing robustness and automating domain adaptation will further facilitate industrial deployment, enabling real-time, adaptive logistics optimization.
AI Executive Summary
Vehicle routing problems (VRPs) are central to logistics, yet their complexity makes manual heuristic design time-consuming and inflexible. Traditional methods like LKH3 and HGS, while effective, rely heavily on expert knowledge and struggle to adapt to evolving constraints. Recent advances in neural combinatorial optimization (NCO) have shown promise but face limitations in scalability, interpretability, and computational cost.
This paper introduces VRPAgent, a novel framework that leverages large language models (LLMs) such as Gemini 2.5 Flash to automatically generate problem-specific heuristic operators. These operators, responsible for destroying and reconstructing parts of solutions, are embedded within a large neighborhood search (LNS) framework that ensures feasibility and solution quality. To optimize the operator set, the authors employ a genetic algorithm (GA) with biased crossover and mutation, guiding the search toward high-performing strategies. A key innovation is the introduction of a code length penalty, balancing solution effectiveness with interpretability and computational efficiency.
Extensive experiments demonstrate that VRPAgent outperforms state-of-the-art handcrafted and learning-based methods across multiple VRP variants, including capacitated VRP, VRP with time windows, and prize-collecting VRP. Notably, it achieves solution gaps below -0.3% on large instances with only a single CPU core, highlighting its practicality and scalability. Ablation studies confirm the importance of the genetic operators and penalty mechanisms, while qualitative analysis shows the generated heuristics are both powerful and interpretable.
This work marks a significant step toward automated, scalable, and transparent heuristic discovery, reducing reliance on expert knowledge and opening new avenues for industrial logistics optimization. Future research will focus on enhancing adaptability, integrating real-time data, and expanding to more complex, multi-objective problems, further bridging the gap between AI research and real-world deployment.
Deep Analysis
Background
车辆路径问题（VRP）作为物流调度的核心，已有多种启发式算法如LKH3、HGS等广泛应用，但其设计依赖经验，难以快速适应复杂约束。近年来，深度学习方法如Pointer Networks、强化学习在VRP中取得一定突破，但存在泛化差、计算成本高等问题。神经组合优化（NCO）通过训练神经网络自动生成解法，虽具潜力，但仍受硬件依赖和可解释性限制。大语言模型（LLM）如GPT系列的出现，为自动化算法设计提供新思路，已在代码生成和符号推理中展现出强大能力。尽管如此，现有LLM驱动的启发式方法在VRP中的表现尚未达到工业级应用标准，主要受限于搜索空间庞大、缺乏整体框架和安全保障。
Core Problem
核心问题在于如何自动生成高效、可靠的启发式算子，以提升VRP求解性能。传统方法依赖人工经验，耗时长且难以扩展。自动化方法如NCO虽有潜力，但在复杂约束和大规模实例中表现不足，且缺乏可解释性。现有的LLM驱动方法多局限于片段式代码生成，缺少整体框架支撑，导致解的质量和安全性难以保证。如何结合LLM的强大生成能力与元启发式框架，设计出既高效又安全的自动化启发式算法，是亟待解决的难题。
Innovation
本研究的创新点在于：1）将预训练大语言模型（如Gemini 2.5）作为启发式算子生成器，显著降低人工调试成本；2）引入大邻域搜索（LNS）框架，将算子设计为模块化、可解释的子组件，保证解的可行性；3）采用遗传算法（GA）进行算子空间的高效搜索，结合偏置交叉和突变策略，提升算子性能；4）引入代码长度惩罚机制，兼顾解的性能与可解释性。该框架实现了自动化、模块化的启发式算子生成，突破了传统自动化方法在复杂约束下的性能瓶颈，为VRP提供了高效、可扩展的解决方案。
Methodology
- �� 利用LLM生成基础破坏（fREMOVE）和重建（fORDER）算子代码，嵌入C++框架中。
- �� 采用遗传算法（GA）进行算子空间搜索，• 评价指标包括目标值和代码长度惩罚，确保算子质量和简洁性。
- �� 通过偏置交叉结合两个父算子，生成新算子，强调优良特性。
- �� 对算子进行微调，包括参数调整、结构变换，提升多样性。
- �� 保留表现优异的算子，淘汰劣质算子，确保搜索方向。
- �� 达到预设迭代次数或性能收敛后，输出最优算子组合。
- �� 在实际VRP实例中应用生成的算子，保证解的可行性和优化效果。
Experiments
- �� 数据集：在CVRP、VRPTW和PCVRP上进行测试，实例规模从500到2000节点。
- �� 基线比较：包括HGS、LKH3、GPU加速的cuOpt及最新学习方法（如NCO-LLM、ReEvo-ACO）。
- �� 评价指标：目标值误差、运行时间、解的可行性。
- �� 超参数：遗传算法中，种群规模100，精英数10，子代数30，代码惩罚λ=2×10^-4，迭代40次。
- �� 训练集：64个实例，单核CPU每实例20秒限制。
- �� 消融实验：验证偏置交叉、突变和惩罚机制对性能的贡献。
Results
- �� 在大规模实例中，VRPAgent平均误差低于-0.3%，优于所有对比方法，特别在2000节点规模下表现出色。
- �� 在多类VRP问题中，解决方案质量显著优于手工和GPU方法，且计算资源需求低，单核CPU即可实现高效搜索。
- �� 消融分析显示偏置交叉和突变机制对性能提升至关重要，代码长度惩罚有效控制模型复杂度，增强可解释性。
- �� 在不同问题和实例规模中，算法表现稳定，具有良好的泛化能力。
Applications
- �� 物流调度：可用于快递、配送等场景，快速生成高质量路径规划，降低人工调试成本。
- �� 智能调度系统：集成于企业调度平台，实现自动化、智能化的路径优化。
- �� 供应链管理：优化仓储与配送环节，提升整体效率。
- �� 未来还可结合实时数据，动态调整路径，适应变化环境，推动智能物流发展。
Limitations & Outlook
- �� 依赖预训练LLM的生成能力，可能在特定场景表现不足，需持续调优。
- �� 算子搜索空间有限，存在局部最优风险，未来需引入多样化搜索策略。
- �� 在极端复杂或动态变化场景中，算子可能需要频繁调整，自动适应性尚待提升。
Plain Language Accessible to non-experts
想象你在厨房准备一顿大餐。每次做菜都需要不同的步骤，比如切菜、炒菜、调味。传统做法是厨师根据经验设计每个步骤，花费时间调试。而现在，有了智能助手（类似大语言模型），它可以帮你自动设计每个步骤的详细操作。你只需告诉它菜的类型和要求，它就能生成一套完整的做菜方案。接下来，你用一个智能系统（类似大邻域搜索）按照这个方案一步步操作，确保每个步骤都正确无误。为了让助手学得更好，你还用遗传算法（像试错和优化）不断改进方案。经过多次尝试，最终你得到了一份既美味又高效的做菜流程。这就像VRPAgent用AI自动设计路径规划，既节省时间，又保证质量。
ELI14 Explained like you're 14
想象你在学校组织一次郊游。你需要安排每个人的出行路线，确保每个人都能准时到达，而且路程不太长。以前，老师们都是自己设计路线，花很多时间，而且不一定最优。现在，有个聪明的机器人（就像大语言模型），它可以帮你设计出一套路线方案。你告诉它一些规则，比如每个车最多坐多少人，什么时候出发，机器人就会写出一份详细的路线计划。接着，你用一个智能系统（类似大邻域搜索）按照这个方案一步步调整，确保每个人都能准时到达，路线也尽可能短。为了让机器人变得更聪明，你还让它不断试验不同的方案，用遗传算法（像试错游戏）不断改进。最后，你得到了一份既合理又高效的路线安排，既省时又省力。这就像VRPAgent用AI帮忙规划物流路线一样，既聪明又节省时间！
Abstract
Designing high-performing heuristics for vehicle routing problems (VRPs) is a complex task that requires both intuition and deep domain knowledge. Large language model (LLM)-based code generation has recently shown promise across many domains, but it still falls short of producing heuristics that rival those crafted by human experts. In this paper, we propose VRPAgent, a framework that integrates LLM-generated components into a metaheuristic and refines them through a novel genetic search. By using the LLM to generate problem-specific operators, embedded within a generic metaheuristic framework, VRPAgent keeps tasks manageable, guarantees correctness, and still enables the discovery of novel and powerful strategies. Across multiple problems, including the capacitated VRP, the VRP with time windows, and the prize-collecting VRP, our method discovers heuristic operators that outperform handcrafted methods and recent learning-based approaches while requiring only a single CPU core. To our knowledge, \VRPAgent is the first LLM-based paradigm to advance the state-of-the-art in VRPs, highlighting a promising future for automated heuristics discovery.