VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918156646219776 |
|---|---|
| author | Hottung, André Berto, Federico Hua, Chuanbo Zepeda, Nayeli Gast Wetzel, Daniel Römer, Michael Ye, Haoran Zago, Davide Poli, Michael Massaroli, Stefano Park, Jinkyoo Tierney, Kevin |
| author_facet | Hottung, André Berto, Federico Hua, Chuanbo Zepeda, Nayeli Gast Wetzel, Daniel Römer, Michael Ye, Haoran Zago, Davide Poli, Michael Massaroli, Stefano Park, Jinkyoo Tierney, Kevin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_07073 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problems Hottung, André Berto, Federico Hua, Chuanbo Zepeda, Nayeli Gast Wetzel, Daniel Römer, Michael Ye, Haoran Zago, Davide Poli, Michael Massaroli, Stefano Park, Jinkyoo Tierney, Kevin Artificial Intelligence 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. |
| title | VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problems |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2510.07073 |