Enhancing CVRP Solver through LLM-driven Automatic Heuristic Design

Zhuoliang Xie; Fei Liu; Zhenkun Wang; Qingfu Zhang

cs.AIFeb 26, 2026

Enhancing CVRP Solver through LLM-driven Automatic Heuristic Design

Authors: Zhuoliang Xie, Fei Liu, Zhenkun Wang, Qingfu Zhang

Organizations: Southern University of Science and Technology · City University of Hong Kong

Abstract

The Capacitated Vehicle Routing Problem (CVRP), a fundamental combinatorial optimization challenge, focuses on optimizing fleet operations under vehicle capacity constraints. While extensively studied in operational research, the NP-hard nature of CVRP continues to pose significant computational challenges, particularly for large-scale instances. This study presents AILS-AHD (Adaptive Iterated Local Search with Automatic Heuristic Design), a novel approach that leverages Large Language Models (LLMs) to revolutionize CVRP solving. Our methodology integrates an evolutionary search framework with LLMs to dynamically generate and optimize ruin heuristics within the AILS method. Additionally, we introduce an LLM-based acceleration mechanism to enhance computational efficiency. Comprehensive experimental evaluations against state-of-the-art solvers, including AILS-II and HGS, demonstrate the superior performance of AILS-AHD across both moderate and large-scale instances. Notably, our approach establishes new best-known solutions for 8 out of 10 instances in the CVRPLib large-scale benchmark, underscoring the potential of LLM-driven heuristic design in advancing the field of vehicle routing optimization.

Figures & tables

Figure 1: The AILS-AHD pipeline: (1) LLM-driven evolutionary computation generates ruin heuristics; (2) each candidate heuristic is evaluated via AILS, including initialization, iterated local search and updating; (3) the population is updated based on fitness of the heuristic.

Figure 2: Convergence curve of LLM designed heuristics.

Instance	BKS	HGS	AILS-II	AILS-C	AILS-S	Ours-PFD	Ours-DDD	Ours-EN
Avg. Gap(%) (+/-/=)	0.00	0.109 (40/38/22)	0.0702 (9/1/90)	0.0687 (3/2/95)	0.0804 (30/6/64)	0.0678 (7/3/90)	0.0686 (2/3/95)	0.0672

Table 1: Results achieved on moderate-scale instances.

Figure 3: Convergence curve on moderate-scale CVRP instances.

Panel of Figure 4 — Figure 4: Result on large-scale CVRP instances.

Panel of Figure 5 — Figure 5: Convergence curve and new best-known solution found for Antwerp1.

	TT	TF	FT	FF	U-R	C-R
Vote-1	49.3	19.7	17.9	11.2	60.5	98.1
Vote-3	51.2	17.9	19.7	9.60	60.8	98.4
Vote-5	51.2	18.9	20.5	8.80	60.0	99.4

Table 2: Results of LLM-driven acceleration (%).

Figure 6: Ablation study on the neighborhood expanding factor.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 7 — Figure 7: The prompt operators used in AILS-AHD.

Panel of Figure 9 — Figure 9: Example of prompt engineering used in LLM-driven AHD.

Figure 15: More convergence curves on moderate-scale instances.

Instance	BKS	HGS		AILS-II		Ours-EN
		Best	Avg.(%) (+/-/=)	Best	Avg.(%) (+/-/=)	Best	Avg.(%)
X-n101-k25	27591.0000	27591.0000	27591.0000 $\pm$ 0.00e+00(=)	27591.0000	27591.0000 $\pm$ 0.00e+00(=)	27591.0000	27591.0000 $\pm$ 0.00e+00
X-n106-k14	26362.0000	26376.0000	26376.0000 $\pm$ 0.00e+00(+)	26362.0000	26362.0000 $\pm$ 0.00e+00(=)	26362.0000	26362.0000 $\pm$ 0.00e+00
X-n110-k13	14971.0000	14971.0000	14971.0000 $\pm$ 0.00e+00(=)	14971.0000	14971.0000 $\pm$ 0.00e+00(=)	14971.0000	14971.0000 $\pm$ 0.00e+00
X-n115-k10	12747.0000	12747.0000	12747.0000 $\pm$ 0.00e+00(=)	12747.0000	12747.0000 $\pm$ 0.00e+00(=)	12747.0000	12747.0000 $\pm$ 0.00e+00
X-n120-k6	13332.0000	13332.0000	13332.0000 $\pm$ 0.00e+00(=)	13332.0000	13332.0000 $\pm$ 0.00e+00(=)	13332.0000	13332.0000 $\pm$ 0.00e+00

Appendix

Table 3: Results achieves on the moderate-scale instances among compared methods.

Instance	BKS	HGS		AILS-II		Ours-EN
		Best	Avg.(%) (+/-/=)	Best	Avg.(%) (+/-/=)	Best	Avg.(%)
X-n733-k159	136187.0000	136457.0000	136457.0000 $\pm$ 0.00e+00(+)	136213.0000	136286.0667 $\pm$ 3.70e+01(=)	136211.0000	136281.1333 $\pm$ 4.26e+01
X-n749-k98	77269.0000	77796.0000	77798.5667 $\pm$ 4.65e+00(+)	77334.0000	77395.9333 $\pm$ 3.78e+01(=)	77335.0000	77405.4333 $\pm$ 4.56e+01
X-n766-k71	114417.0000	114754.0000	114754.0000 $\pm$ 0.00e+00(+)	114427.0000	114477.9333 $\pm$ 4.37e+01(=)	114426.0000	114466.9000 $\pm$ 3.49e+01
X-n783-k48	72386.0000	72759.0000	72759.0000 $\pm$ 0.00e+00(+)	72423.0000	72482.0667 $\pm$ 4.73e+01(=)	72427.0000	72480.4667 $\pm$ 3.83e+01
X-n801-k40	73311.0000	73474.0000	73474.0000 $\pm$ 0.00e+00(+)	73311.0000	73364.3000 $\pm$ 3.44e+01(=)	73311.0000	73369.7000 $\pm$ 3.91e+01

Appendix

Table 4: Results achieves on the moderate-scale instances among compared methods – continue.

Instance	BKS	Ours-PFD		Ours-DDD		Ours-EN
		Best	Avg.(%) (+/-/=)	Best	Avg.(%) (+/-/=)	Best	Avg.(%)
X-n101-k25	27591.00	27591.00	27591.00 $\pm$ 0.00e+00(=)	27591.00	27591.00 $\pm$ 0.00e+00(=)	27591.00	27591.00 $\pm$ 0.00e+00
X-n106-k14	26362.00	26362.00	26362.00 $\pm$ 0.00e+00(=)	26362.00	26362.00 $\pm$ 0.00e+00(=)	26362.00	26362.00 $\pm$ 0.00e+00
X-n110-k13	14971.00	14971.00	14971.00 $\pm$ 0.00e+00(=)	14971.00	14971.00 $\pm$ 0.00e+00(=)	14971.00	14971.00 $\pm$ 0.00e+00
X-n115-k10	12747.00	12747.00	12747.00 $\pm$ 0.00e+00(=)	12747.00	12747.00 $\pm$ 0.00e+00(=)	12747.00	12747.00 $\pm$ 0.00e+00
X-n120-k6	13332.00	13332.00	13332.00 $\pm$ 0.00e+00(=)	13332.00	13332.00 $\pm$ 0.00e+00(=)	13332.00	13332.00 $\pm$ 0.00e+00

Appendix

Table 5: Comparison of results on moderate-scale instances among the top-3 designed heuristics.

Instance	BKS	Ours-PFD		Ours-DDD		Ours-EN
		Best	Avg.(%) (+/-/=)	Best	Avg.(%) (+/-/=)	Best	Avg.(%)
X-n294-k50	47161.00	47169.00	47209.33 $\pm$ 2.76e+01(=)	47167.00	47201.50 $\pm$ 2.38e+01(=)	47169.00	47212.73 $\pm$ 2.78e+01
X-n298-k31	34231.00	34231.00	34262.40 $\pm$ 2.22e+01(=)	34231.00	34250.97 $\pm$ 2.09e+01(-)	34231.00	34262.57 $\pm$ 2.30e+01
X-n303-k21	21736.00	21748.00	21767.17 $\pm$ 3.28e+01(=)	21742.00	21763.77 $\pm$ 3.26e+01(=)	21747.00	21758.83 $\pm$ 3.12e+01
X-n308-k13	25859.00	25859.00	25871.93 $\pm$ 2.02e+01(=)	25859.00	25873.40 $\pm$ 2.42e+01(=)	25861.00	25871.90 $\pm$ 2.01e+01
X-n313-k71	94043.00	94044.00	94089.33 $\pm$ 4.23e+01(=)	94044.00	94089.57 $\pm$ 3.44e+01(=)	94044.00	94101.50 $\pm$ 3.76e+01

Appendix

Table 6: Comparison of Results on Moderate-Scale Instances Among the Top-3 Designed Heuristics – continue.

Figure 16: Convergence curves of the new best-known solutions. The x-axis represents the CPU time percentage, while the y-axis shows

\log(1+\text{Gap\%})

. The red dashed line indicates the baseline (gap = 0%).

Figure 17: Visualization of the vehicle routes for the new best-known solutions.

Resource	Type	Link	License
HGS [ 4 ]	Code	https://github.com/chkwon/PyHygese	MIT License
AILS-II [ 20 ]	Code	https://github.com/vinymax10/AILS-CVRP	MIT License
CVRPLIB Moderate-scale [ 11 ]	Dataset	http://vrp.galgos.inf.puc-rio.br/index.php/en/	Available for academic research use
CVRPLIB Large-scale [ 10 ]	Dataset	http://vrp.galgos.inf.puc-rio.br/index.php/en/	Available for academic research use

Appendix

Table 7: List of licenses for the codes and datasets we used in this work

Explore similar work

Automated Large-scale CVRP Solver Design via LLM-assisted Flexible MCTS
May 5, 2026Tong Guo, Caishun Chen, Yew Soon OngAutomated Algorithm Discovery Large Language Model-Guided Optimization
College of Computing and Data Science, Nanyang Technological University, Singapore
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

May 5, 2026J/K move · Enter open · S save

Automated Large-scale CVRP Solver Design via LLM-assisted Flexible MCTS

Tong Guo, Caishun Chen, Yew Soon Ong

College of Computing and Data Science, Nanyang Technological University, Singapore

Automated Algorithm Discovery Large Language Model-Guided Optimization Combinatorial Optimization Monte Carlo Tree Search Vehicle Routing

Open paper AskPDF arXiv

Solving large-scale CVRP (LSCVRP) with hundreds to thousands of nodes remains difficult for even state-of-the-art solvers. Divide-and-conquer can scale by decomposing the instance into size-reduced subproblems, but designing decomposition logic and configuring sub-solvers is highly expertise- and labor-intensive. Large Language Models (LLMs) have emerged as promising tools for automated algorithm design. However, existing LLM-driven approaches struggle with LSCVRP primarily due to the difficulty in generating sophisticated search strategies within a limited context window. To bridge this gap, we propose the LLM-assisted Flexible Monte Carlo Tree Search (LaF-MCTS), a novel framework that automates the design of high-performance LSCVRP solvers. We develop a three-tier decision hierarchy to enable incremental design of decomposition policies and sub-solvers for LSCVRP. To enable efficient search within the algorithmic hypothesis space, we introduce semantic pruning to eliminate semantically and structurally redundant codes, and branch regrowth to regenerate codes and preserve diversity. Extensive experiments on CVRPLib demonstrate that LaF-MCTS autonomously composes and optimizes decomposition-enhanced solvers that surpasses various state-of-the-art CVRP solvers.

Abstract

Explore similar work

Automated Large-scale CVRP Solver Design via LLM-assisted Flexible MCTS

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

Reinforcement Learning Enhanced LLM Agents for Complex Vehicle Routing Problems

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