| Download | - View final version: Learning heuristics to solve dynamic vehicle routing problems using large language models (PDF, 989 KiB)
|
|---|
| DOI | Resolve DOI: https://doi.org/10.1145/3748636.3764603 |
|---|
| Author | Search for: Wang, Andrew1ORCID identifier: https://orcid.org/0009-0002-2781-8219; Search for: Li, Xiaoyan2ORCID identifier: https://orcid.org/0000-0002-0215-819X; Search for: Wang, Yunli3ORCID identifier: https://orcid.org/0000-0002-2320-954X |
|---|
| Affiliation | - University of Waterloo
- University of Toronto
- National Research Council Canada. Digital Technologies
|
|---|
| Funder | Search for: National Research Council Canada |
|---|
| Format | Text, Article |
|---|
| Conference | SIGSPATIAL '25: 33rd ACM International Conference on Advances in Geographic Information Systems, November 3-6, 2025, Minneapolis, Minnesota, United States |
|---|
| Subject | automatic algorithm design; dynamic vehicle routing problems; large language models |
|---|
| Abstract | Modern logistics companies face significant challenges in efficiently managing dynamic transportation systems, particularly in addressing Dynamic Vehicle Routing Problems (DVRP). These complex problems require specialized expertise for effective algorithm design. Traditional approaches often rely on manual algorithm design for specific routing problems. Reinforcement learning (RL)-based methods, though capable of learning heuristics for diverse routing problems, suffer from poor training efficiency and weak generalization to out-of-distribution (OOD) scenarios. To address these limitations, we leverage the strong generalization capabilities of large language models (LLMs) and adopt an LLM-based heuristic learning approach for DVRP. Our method learns heuristics and autonomously generates executable code within an evolutionary framework, requiring fewer than 10 samples for training. This enables fast training while maintaining robust performance on large-scale OOD instances. Comprehensive experiments across multiple routing problems - including Vehicle Routing Problems (VRP), VRP with Time Windows (VRPTW), DVRP, and DVRP with Time Windows (DVRPTW) - demonstrate that our approach learns effective heuristics and consistently surpasses Greedy baselines. Moreover, in constrained optimization tasks (VRPTW and DVRPTW), our method attains higher feasibility rates than Greedy baselines and approaches the performance of expert-designed heuristics. The proposed method presents a promising and scalable solution with significant potential for real-world industrial deployment1. |
|---|
| Publication date | 2025-12-12 |
|---|
| Publisher | ACM |
|---|
| Licence | |
|---|
| In | |
|---|
| Language | English |
|---|
| Peer reviewed | Yes |
|---|
| Export citation | Export as RIS |
|---|
| Report a correction | Report a correction (opens in a new tab) |
|---|
| Record identifier | 0f6c3da8-ed6c-497a-be08-5fabf1b6dc59 |
|---|
| Record created | 2026-02-17 |
|---|
| Record modified | 2026-03-04 |
|---|
