arXiv cs.AI· Andr\'e Hottung, Federico Berto, Chuanbo Hua, Nayeli Gast Zepeda, Daniel Wetzel, Michael R\"omer, Haoran Ye, Davide Zago, Michael Poli, Stefano Massaroli, Jinkyoo Park, Kevin Tierney·· 12 小时前AI 评分41
VRPAgent：LLM 驱动的车辆路径问题启发式算子发现框架
VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problems
AI 导读
VRPAgent 将 LLM 生成的算子嵌入共享元启发式框架，并用遗传搜索迭代优化，在容量约束 VRP、带时间窗 VRP 和奖励收集 VRP 上发现的启发式算子优于手工方法与近期学习方法，且仅需单个 CPU 核心。该框架通过让 LLM 只生成问题特定算子来保证正确性并控制任务复杂度，作者称其是最早推动 VRP 达到 SOTA 的 LLM 方法之一，论文已发表于 TMLR。
正文 · 原文
Authors:André Hottung, Federico Berto, Chuanbo Hua, Nayeli Gast Zepeda, Daniel Wetzel, Michael Römer, Haoran Ye, Davide Zago, Michael Poli, Stefano Massaroli, Jinkyoo Park, Kevin Tierney
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 for VRPs 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 shared metaheuristic framework for VRPs, VRPAgent keeps tasks manageable, guarantees correctness, and still enables the discovery of novel and powerful strategies. Across multiple VRPs, 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 one of the first LLM-based methods to advance the state-of-the-art in VRPs, highlighting a promising future for automated heuristics discovery.
| Comments: | Published in TMLR |
| Subjects: | Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2510.07073 [cs.AI] |
| (or arXiv:2510.07073v2 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2510.07073 arXiv-issued DOI via DataCite |
Submission history
From: André Hottung [view email]
[v1]
Wed, 8 Oct 2025 14:35:09 UTC (1,616 KB)
[v2]
Tue, 20 Oct 2026 11:07:50 UTC (1,670 KB)
来源：arXiv cs.AI · arxiv.org