用大模型生成路由策略,自动优化出超越人工的解法。
VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problems
- 让大模型生成特定问题算子,嵌入元启发式框架中。
- 在多个路由问题上超越人工与学习方法,仅需单核CPU。
- 首次实现大模型驱动的启发式算法突破,适合算法设计者参考。
为车辆路径问题(VRP)设计高性能启发式算法是复杂且依赖经验的任务。尽管大语言模型(LLM)在代码生成方面展现出潜力,但其生成的启发式仍难以媲美人类专家设计。本文提出VRPAgent框架,将LLM生成的算子整合进元启发式,并通过新型遗传搜索进行优化。该方法利用LLM生成问题相关算子,嵌入通用元启发式框架中,既保持任务可管理性,又确保正确性,同时发现新颖且高效的策略。在容量约束VRP、带时间窗VRP和奖赏收集型VRP等多个问题上,该方法生成的算子性能优于人工设计及近期学习方法,且仅需单个CPU核心。据我们所知,这是首个基于大模型推进VRP领域前沿的范式,展现了自动化启发式发现的广阔前景。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。