VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problems

André Hottung; Federico Berto; Chuanbo Hua; Nayeli Gast Zepeda; Daniel Wetzel; Michael Römer; Haoran Ye; Davide Zago

cs.AIOct 8, 2025

VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problems

Authors: André Hottung, Federico Berto, Chuanbo Hua, Nayeli Gast Zepeda, Daniel Wetzel, Michael Römer, Haoran Ye, Davide Zago,

Organizations: Bielefeld University · Radical Numerics · KAIST · Peking University ·

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.

Figures & tables

Method			N=500			N=1000			N=2000
Method			Obj. $\downarrow$	Gap $\downarrow$	Time	Obj. $\downarrow$	Gap $\downarrow$	Time	Obj. $\downarrow$	Gap $\downarrow$	Time
CVRP	SISRs	CPU	36.65	-	60	41.14	-	120	56.04	-	240
	HGS	CPU	36.66	0.00%	60	41.51	0.84%	121	57.38	2.33%	241
	LKH $3$	CPU	37.25	1.66%	174	42.16	2.46%	408	58.12	3.70%	1448
	NVIDIA cuOpt	CPU+GPU	37.38	1.98%	60	42.71	3.78%	121	59.22	5.66%	241
	Gurobi	CPU	47.85	30.53%	60	87.36	111.88%	120	-	OOM	-

Table 1: Performance on test data. The gap is calculated relative to SISRs. Runtime is reported on a per-instance basis in seconds. The best results (i.e., those with the lowest objective function value) are shown in bold , and the second-best are underlined .

\dagger

indicates that VRPAgent significantly outperforms both SISRs and NDS according to two-sided paired Wilcoxon signed-rank tests (

p<0.05

). * Indicates that a feasible solution was not found for all instances. OOM indicates that the corresponding solver yielded an out-of-memory error.

		Average gap (%)		Paired comparison
Size $N$	# Inst.	SISRs	VRPAgent	$W/T/L$	$\Delta$ (pp)	$p$
100–250	32	0.122%	0.133%	17/3/12	+0.011	0.581
250–500	36	0.285%	0.215%	26/0/10	-0.069	0.003
500–750	19	0.276%	0.238%	16/0/3	-0.038	0.004
750+	13	0.269%	0.221%	12/0/1	-0.048	0.002
All	100	0.229%	0.194%	71/3/26	-0.035	9.9e-06

Table 2: Performance on the real-world-like CVRPLib X dataset. Results are averaged by customer count.

Figure 2: Performance on the CVRP for different LLMs. Detailed cost calculations are provided in Appendix D .

Figure 3: Average objective on the development sets over the course of the discovery process.

Figure 4: Ablation results.

Panel of Figure 5 — Figure 5: Results of the sensitivity analyses.

Figure 6: Objective values during heuristic discovery for VRPTW and PCVRP with and without warm-starts from the best CVRP heuristic.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

	Problem	Baseline	Mean gap	95% CI	$W/T/L$	$p$ -value
N=500	CVRP	SISRs	-0.123%	[-0.167%, -0.080%]	86/0/42	1.5e-06
	CVRP	NDS	0.080%	[0.038%, 0.122%]	54/0/74	0.002
	VRPTW	SISRs	-0.239%	[-0.286%, -0.192%]	188/0/62	1.2e-19
	VRPTW	NDS	0.064%	[0.022%, 0.105%]	108/0/142	0.002
	PCVRP	SISRs	-0.094%	[-0.122%, -0.065%]	170/0/80	7.2e-10
	PCVRP	NDS	0.135%	[0.110%, 0.159%]	53/0/197	1.2e-20

Appendix

Table 3: Paired comparison of VRPAgent with SISRs and NDS. Negative gaps favor VRPAgent; bold

p

-values indicate a significant improvement at

\alpha=0.05

		SISRs		VRPAgent				SISRs		VRPAgent
Instance	BKS	Obj.	Gap%	Obj.	Gap%	Instance	BKS	Obj.	Gap%	Obj.	Gap%
X-n101-k25	27591	27591	0.000	27591	0.000	X-n336-k84	139111	139515	0.291	139377	0.192
X-n106-k14	26362	26383	0.080	26366	0.017	X-n344-k43	42050	42110	0.145	42146	0.229
X-n110-k13	14971	14971	0.000	14971	0.000	X-n351-k40	25896	25982	0.336	25992	0.373
X-n115-k10	12747	12747	0.000	12747	0.000	X-n359-k29	51505	51575	0.137	51570	0.127
X-n120-k6	13332	13332	0.000	13332	0.005	X-n367-k17	22814	22866	0.228	22829	0.067

Appendix

Table 4: Comparisons on the X set of CVRPLib: best-known solutions (BKS), SISRs and VRPAgent costs, and their percentage gaps. Results show the average performance across 10 runs.

Model	Open Source	Token Usage		Costs ($)		Total Costs ($)	Source
Model	Open Source	Input	Output	Input	Output	Total Costs ($)	Source
Gemini 2.0 Flash	✗	2.5M	1.2M	0.10	0.40	0.73	Vertex AI
Gemini 2.5 Flash	✗	4.1M	7.1M	0.30	2.50	18.98	Vertex AI
gpt-oss (120B)	✓	4.0M	2.5M	0.09	0.36	1.26	Clarifai
gemma 3 (27B)	✓	2.5M	1.2M	0.09	0.16	0.42	DeepInfra
Qwen3 (30B)	✓	1.5M	4.4M	0.08	0.29	1.40	Clarifai

Appendix

Table 5: Comparison of token usage and cost estimates across models per run (as of Sep. 2025) with inference providers sources.

Figure 7: Percentage of operators that compile successfully and produce valid solutions (success rate) throughout the main discovery runs.

Configuration	Mean	Std	CI95	p-value
Default Configuration	36.70378	0.003310	0.002368	—
- w/o Initial Segment Removal	36.70551	0.003138	0.002245	0.375000
- w/o Adjacent Tour Node Expansion	36.70705	0.002539	0.001816	0.064453
- w/o Route Segment Removal	36.71770	0.003249	0.002324	0.001953
- w/o Nearest Neighbor Expansion	37.72012	0.018678	0.013362	0.001953

Appendix

Table 6: Ablation of removal strategies for the CVRP.

Configuration	Mean	Std	CI95	p-value
Default Configuration	36.70378	0.003310	0.002368	—
- w/o Nearest Neighbor Chain	36.70083	0.001283	0.000918	0.037109
- w/o Demand	36.70116	0.003045	0.002178	0.130859
- w/o Weighted Demand-Distance Score	36.70196	0.001920	0.001374	0.173071
- w/o Random Shuffle	36.70390	0.002159	0.001545	0.625000
- w/o Polar Angle	36.70499	0.001673	0.001197	0.431641

Appendix

Table 7: Ablation of ordering strategies for the CVRP.

Configuration	Mean	Std	CI95	p-value
Default Configuration	47.46744	0.005987	0.004283	—
- w/o Random Jump Expansion	47.46464	0.004139	0.002961	0.375000
- w/o Tour Neighbor Expansion	47.61712	0.003621	0.002590	0.001953
- w/o Nearest Neighbor Expansion	48.16588	0.005831	0.004171	0.001953

Appendix

Table 8: Ablation of selection strategies for the VRPTW.

Configuration	Mean	Std	CI95	p-value
Default Configuration	47.46744	0.005987	0.004283	—
- w/o Demand	47.46509	0.003528	0.002524	0.556641
- w/o Time Window Width	47.46617	0.002892	0.002069	0.431641
- w/o Arrival Time Slack	47.46631	0.006066	0.004339	0.695312
- w/o Multi-Attribute Score	47.46645	0.006211	0.004443	1.000000
- w/o Depot Distance	47.46671	0.007461	0.005337	1.000000

Appendix

Table 9: Ablation of ordering strategies for the VRPTW.

Configuration	Mean	Std	CI95	p-value
Default Configuration	42.73483	0.003547	0.002538	—
- w/o Multi-Source Expansion	42.73821	0.001865	0.001334	0.027344
- w/o Biased Seed Selection	42.75303	0.002260	0.001617	0.001953
- w/o Tour-Based Neighbor Expansion	42.97553	0.003856	0.002758	0.001953

Appendix

Table 10: Ablation of selection strategies for the PCVRP.

Configuration	Mean	Std	CI95	p-value
Default Configuration	42.73483	0.003547	0.002538	—
- w/o Prize-Distance Scoring	42.73103	0.002071	0.001481	0.013672
- w/o Prize-Focused Scoring	42.73353	0.002825	0.002021	0.492188
- w/o Random Shuffle	42.73397	0.001956	0.001399	0.921875
- w/o Distance-Demand Scoring	42.74467	0.003440	0.002461	0.003906
- w/o Pivot Proximity	42.86265	0.002567	0.001837	0.001953

Appendix

Table 11: Ablation of ordering strategies PCVRP.

Vehicle Routing

Vehicle routing studies how to assign and sequence trips for fleets while meeting capacity, time, energy, and service constraints.

See all 133 papers

PyVRP $^+$ : LLM-Driven Metacognitive Heuristic Evolution for Hybrid Genetic Search in Vehicle Routing Problems
Apr 9, 2026Manuj Malik, Jianan Zhou, Shashank Reddy Chirra +1Automated Heuristic Design Large Language Model-Guided Optimization
Singapore Management University Singapore, Singapore · Nanyang Technological University Singapore, Singapore · University of Oxford Oxford, England
Reinforcement Learning Enhanced LLM Agents for Complex Vehicle Routing Problems
Sep 1, 2026Yi Chen, Zikang Yu, Jiahai Wang +3Multi-Agent System Optimization LLM-Guided RL
School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, China · Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore
Enhancing CVRP Solver through LLM-driven Automatic Heuristic Design
Feb 26, 2026Zhuoliang Xie, Fei Liu, Zhenkun Wang +1Vehicle Routing Automated Heuristic Design
Southern University of Science and Technology · City University of Hong Kong

Apr 9, 2026J/K move · Enter open · S save

PyVRP $^+$ : LLM-Driven Metacognitive Heuristic Evolution for Hybrid Genetic Search in Vehicle Routing Problems

Manuj Malik, Jianan Zhou, Shashank Reddy Chirra, Zhiguang Cao

Singapore Management University Singapore, Singapore · Nanyang Technological University Singapore, Singapore · University of Oxford Oxford, England

Automated Heuristic Design Large Language Model-Guided Optimization Vehicle Routing Evolutionary Optimization Genetic Algorithms

Open paper AskPDF arXiv

Designing high-performing metaheuristics for NP-hard combinatorial optimization problems, such as the Vehicle Routing Problem (VRP), remains a significant challenge, often requiring extensive domain expertise and manual tuning. Recent advances have demonstrated the potential of large language models (LLMs) to automate this process through evolutionary search. However, existing methods are largely reactive, relying on immediate performance feedback to guide what are essentially black-box code mutations. Our work departs from this paradigm by introducing Metacognitive Evolutionary Programming (MEP), a framework that elevates the LLM to a strategic discovery agent. Instead of merely reacting to performance scores, MEP compels the LLM to engage in a structured Reason-Act-Reflect cycle, forcing it to explicitly diagnose failures, formulate design hypotheses, and implement solutions grounded in pre-supplied domain knowledge. By applying MEP to evolve core components of the state-of-the-art Hybrid Genetic Search (HGS) algorithm, we discover novel heuristics that significantly outperform the original baseline. By steering the LLM to reason strategically about the exploration-exploitation trade-off, our approach discovers more effective and efficient heuristics applicable across a wide spectrum of VRP variants. Our results show that MEP discovers heuristics that yield significant performance gains over the original HGS baseline, improving solution quality by up to 2.70% and reducing runtime by over 45% on challenging VRP variants.

Abstract

Vehicle Routing

Explore similar work

PyVRP+^++: LLM-Driven Metacognitive Heuristic Evolution for Hybrid Genetic Search in Vehicle Routing Problems

Reinforcement Learning Enhanced LLM Agents for Complex Vehicle Routing Problems

Enhancing CVRP Solver through LLM-driven Automatic Heuristic Design

PyVRP $^+$ : LLM-Driven Metacognitive Heuristic Evolution for Hybrid Genetic Search in Vehicle Routing Problems