Just Initialize: A Training-Free Initialization Component for Large-Scale Routing Optimization

Jiale Zhao; Sirui Mao; Zimu Chen; Wentao Yang; Zihan Wang; Xuefeng Huang; Junji Cheng; Liyuanjun Lai

cs.AISep 28, 2026

Just Initialize: A Training-Free Initialization Component for Large-Scale Routing Optimization

Authors: Jiale Zhao, Sirui Mao, Zimu Chen, Wentao Yang, Zihan Wang, Xuefeng Huang, Junji Cheng, Liyuanjun Lai

Organizations: School of Automation Science and Electrical Engineering, Beihang University, Beijing, China · School of Computer Science and Engineering, Beihang University, Beijing, China · School of Cyber Science and Technology, Beihang University, Beijing, China · School of Mechanical Engineering and Automation, Beihang University, Beijing, China

Abstract

Large-scale routing problems are difficult to solve efficiently as their search spaces grow rapidly with problem size. Existing approaches primarily improve the optimization procedure itself, often at increasing computational cost. We instead shift the focus to a useful initialization that can be refined into a high-quality solution with limited downstream refinement. We propose Just Initialize, a training-free and solver-agnostic initialization component for large-scale routing optimization. Just Initialize compresses a large routing instance into a compact surrogate space, optimizes its global routing structure, and recovers the resulting solution as an optimization-friendly starting point in the original space. Extensive experiments on Traveling Salesman Problems (TSPs), Capacitated Vehicle Routing Problems (CVRPs), Vehicle Routing Problems with Time Windows (VRPTWs), and Prize-Collecting Traveling Salesman Problems (PCTSPs) demonstrate that Just Initialize achieves high-quality solutions comparable to or better than state-of-the-art methods while substantially reducing computational cost across instances ranging from 1K to 100K nodes, including an average speedup of approximately 70 $\times$ , sub-second runtimes on 10K-node instances, and runtimes within tens of seconds on 100K-node instances.

Figures & tables

Figure 1: Rethinking large-scale routing optimization. (a) Conventional paradigm and our paradigm. (b) Performance comparison with SOTA methods on 100K-node TSP instances.

Figure 2: Overview of Just Initialize. The framework compresses the original solution space, optimizes in a compact space, recovers an optimization-friendly initialization, and performs lightweight refinement in the original space.

Method	TSP5K			TSP10K			TSP20K			TSP50K			TSP100K
Method	Obj. $\downarrow$	Gap	Time	Obj. $\downarrow$	Gap	Time	Obj. $\downarrow$	Gap	Time	Obj. $\downarrow$	Gap	Time	Obj. $\downarrow$	Gap	Time
LKH-3 (Reference)	50.88	–	–	71.76	–	–	101.39	–	–	159.98	–	–	225.95	–	–
POMO (no aug.)	88.33	73.62	50.6 s	133.64	86.23	6.5 min	OOM			OOM			OOM
POMO ( $\times 8$ aug.)	87.62	72.23	7.7 min	OOM			OOM			OOM			OOM
LEHD (greedy)	59.50	16.94	1.2 min	90.26	25.77	7.9 min	OOM			OOM			OOM
INViT	54.22	6.57	46.1 s	76.76	6.97	1.5 min	108.57	7.08	3.1 min	171.42	7.15	8.3 min	242.13	7.16	18.5 min

Table 1: Comparison results on large-scale TSP and CVRP instances. Obj. and Gap denote the solution objective and relative gap, respectively. Bold marks the lowest Gap and Time at each scale before rounding; gray highlights our method. OOM: results that exceed GPU memory limits. OOT: the method fails to finish within the predefined time limit.

Method	VRPTW2K			VRPTW5K			VRPTW10K			VRPTW20K
	Obj. $\downarrow$	Gap	Time	Obj. $\downarrow$	Gap	Time	Obj. $\downarrow$	Gap	Time	Obj. $\downarrow$	Gap	Time
HGS-PyVRP (Reference)	335.93	-	-	823.85	-	-	1419.13	-	-	2479.68	-	-
OR-Tools	352.83	5.03	30.0 min	891.49	8.21	2.0 min	1498.60	5.60	10.0 min	2584.07	4.21	30.0 min
VROOM	342.08	1.83	6.0 min	831.43	0.92	14.7 min	-	OOM	-	-	OOM	-
ALNS	381.58	13.59	3.8 h	901.13	9.38	3.6 h	1520.17	7.12	3.1 h	2615.07	5.46	3.3 h
JI+Refine (Ours)	362.91	8.25	2.9 s	863.80	5.16	9.6 s	1478.16	4.43	9.3 s	2574.90	3.96	15.8 s

Table 2: Comparison results on large-scale VRPTW and PCTSP instances.

	1K		5K		10K		20K		50K		100K
Solver	Gap	Time	Gap	Time	Gap	Time	Gap	Time	Gap	Time	Gap	Time
2-opt	11.22	0.03 s	11.74	0.3 s	11.70	0.5 s	11.64	1.5 s	11.70	9.9 s	11.67	42.9 s
JI+2-opt	8.63	0.02 s	9.24	0.2 s	9.24	0.1 s	9.21	0.2 s	9.21	0.8 s	9.10	3.3 s
VND	5.22	4.3 s	5.57	35.5 s	5.51	42.5 s	5.78	42.4 s	6.64	1.4 min	8.17	1.2 min
JI+VND	4.44	2.7 s	4.77	24.3 s	4.85	28.9 s	5.05	35.4 s	5.93	34.9 s	6.08	1.1 min
ILS	6.99	1.4 s	8.76	41.3 s	9.18	40.1 s	10.03	41.8 s	10.74	1.4 min	11.21	1.4 min

Table 3: Search performance with different initializations and refinement procedures. Bold values indicate the better result within each solver pair before rounding.

	Full		w/o compress		w/o solve		w/o restore
Scale	Gap (%)	Time (s)	Gap (%)	Time (s)	Gap (%)	Time (s)	Gap (%)	Time (s)
1K	2.84	0.03	3.59 (+0.75)	0.04	3.39 (+0.55)	0.05	3.90 (+1.06)	0.03
5K	3.62	0.16	4.26 (+0.64)	0.18	3.68 (+0.06)	0.16	4.44 (+0.82)	0.17
10K	3.49	0.36	4.83 (+1.34)	0.47	3.60 (+0.11)	0.35	4.66 (+1.17)	0.41
20K	3.70	0.89	4.88 (+1.18)	1.20	3.74 (+0.04)	0.91	4.87 (+1.17)	1.11
50K	3.67	4.23	4.82 (+1.15)	7.23	4.25 (+0.58)	4.12	4.96 (+1.29)	5.30

Table 4: JI ablation on uniform TSP instances. Numbers in parentheses denote the gap increase relative to the full model. All results are averaged over three seeds.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Parameter	Value	Role
$K_{c}$	$\min\{64,m\}$	Candidate width for compact-solution construction
$K_{\mathrm{local}}$	$\min\{24,m\}$	Candidate width for compact-space local search
$K_{\mathrm{merge}}$	$\min\{32,m\}$	Candidate width for route merging, when applicable
$S$	$1$	Number of refinement trials used to estimate $\widehat{J}_{B}$
$\tau$	Low temperature	Controls the concentration of recovery sampling
$B_{\mu}$	Bounded	Maximum number of post-recovery refinement steps

Appendix

Table 5: Shared implementation parameters of Just Initialize.

m

denotes the number of compact units.

Family	Sizes $\times$ instances	Sampling and fixed settings	Generation seed
TSP uniform	1K, 5K, 10K, 20K, 50K, 100K $\times 16$	Independent uniform two-dimensional coordinates	$s_{U}(n,i)$
TSP extended	1K, 10K, 100K $\times 16$ per distribution	Clustered, explosion, or implosion coordinates	$s_{E}(n,i)$
CVRP	1K, 5K, 10K, 20K, 50K, 100K $\times 16$	Depot/customers $\sim U[0,1]^{2}$ ; demand $\sim U_{\mathbb{Z}}[1,9]$	$s_{R}(n,i)$
VRPTW	1K, 2K, 5K, 10K $\times 16$ ; 20K $\times 8$	CVRP-style coordinates and demands; depot window $[0,3]$ ; service time $0.2$	$s_{R}(n,i)$
PCTSP	1K, 2K, 5K, 10K $\times 16$ ; 20K $\times 8$	Depot/customers $\sim U[0,1]^{2}$ ; prize $\sim U[0,4/n]$ ; penalty $\sim U[0,1.2/\sqrt{n}]$ ; quota $1$	$s_{R}(n,i)$

Appendix

Table 6: Instance generation settings for the full collections.

U[a,b]

denotes a continuous uniform distribution and

U_{\mathbb{Z}}[a,b]

an integer uniform distribution.

Method	1K			10K			100K
	Obj. $\downarrow$	Gap (%)	Time	Obj. $\downarrow$	Gap (%)	Time	Obj. $\downarrow$	Gap (%)	Time
LKH-3 (2.0 h)	14.22	–	–	40.67	–	–	120.22	–	–
Concorde	14.22	0.00	1.7 min	40.86	0.48	3.0 min	121.35	0.94	3.0 min
POMO (no aug.)	22.32	56.96	0.6 s	109.77	169.91	6.5 min	OOM
POMO ( $\times 8$ aug.)	20.96	47.41	3.1 s	OOM			OOM
LEHD (greedy)	15.51	9.07	4.5 s	54.95	35.11	8.0 min	OOM

Appendix

Table 7: TSP results on clustered distributions (16 instances per size). Bold marks the lowest gap and solve time at each size, excluding Concorde; gray highlights Ours.

Method	1K			10K			100K
	Obj. $\downarrow$	Gap (%)	Time	Obj. $\downarrow$	Gap (%)	Time	Obj. $\downarrow$	Gap (%)	Time
LKH-3 (2.0 h)	17.01	–	–	40.26	–	–	108.17	–	–
Concorde	17.01	0.00	2.4 min	40.43	0.42	3.0 min	109.33	1.07	3.0 min
POMO (no aug.)	25.91	52.34	0.6 s	117.39	191.57	6.5 min	OOM
POMO ( $\times 8$ aug.)	24.75	45.48	3.1 s	OOM			OOM
LEHD (greedy)	17.91	5.32	4.1 s	53.09	31.88	8.0 min	OOM

Appendix

Table 8: TSP results on explosion distributions (16 instances per size). Bold marks the lowest gap and solve time at each size, excluding Concorde; gray highlights Ours.

Method	1K			10K			100K
	Obj. $\downarrow$	Gap (%)	Time	Obj. $\downarrow$	Gap (%)	Time	Obj. $\downarrow$	Gap (%)	Time
LKH-3 (2.0 h)	20.29	–	–	63.25	–	–	189.57	–	–
Concorde	20.29	0.00	1.7 min	63.53	0.44	3.0 min	191.64	1.10	3.0 min
POMO (no aug.)	28.85	42.20	0.6 s	119.39	88.76	6.5 min	OOM
POMO ( $\times 8$ aug.)	28.39	39.94	3.1 s	OOM			OOM
LEHD (greedy)	21.05	3.75	4.2 s	81.98	29.61	8.0 min	OOM

Appendix

Table 9: TSP results on implosion distributions (16 instances per size). Bold marks the lowest gap and solve time at each size, excluding Concorde; gray highlights Ours.

Instance	Scale	LEHD	TTPL	H-TSP	UDC	GLOP	JI+Refine (Ours)
pr1002	1,002	4.43%	0.73%	7.19%	2.62%	5.21%	4.41%
u1060	1,060	10.01%	2.54%	10.84%	3.55%	4.82%	2.08 %
vm1084	1,084	5.42%	1.44%	12.70%	3.95%	5.61%	3.29%
pcb1173	1,173	7.95%	1.72%	8.51%	5.23%	7.48%	4.36%
d1291	1,291	13.46%	6.22%	16.11%	8.32%	9.59%	2.47%
rl1304	1,304	8.14%	4.16%	14.67%	6.94%	10.00%	2.82%

Appendix

Table 10: Relative gaps (%) on TSPLIB95 instances. Bold marks the lowest reported gap in each row; gray highlights Ours. OOM marks out-of-memory on a 24 GB GPU.

Instance	Scale	HGS	OR-Tools	LEHD	L2C	TTPL	UDC	GLOP	Ours
X-n1001-k43	1,000	3.01%	9.59%	7.55%	7.53%	6.01%	6.49%	88.26%	6.10%
Leuven1	3,000	5.42%	5.42%	16.36%	7.07%	6.48%	9.64%	105.31%	5.35%
Leuven2	4,000	9.00%	12.36%	33.12%	25.76%	24.06%	44.00%	45.29%	12.52%
Antwerp1	6,000	5.49%	7.25%	15.17%	6.23%	6.69%	9.59%	130.39%	4.47%
Antwerp2	7,000	11.27%	12.41%	21.36%	20.00%	13.54%	21.08%	63.61%	9.56%
Ghent1	10,000	6.74%	7.11%	27.64%	11.15%	10.64%	12.36%	146.15%	3.96%

Appendix

Table 11: Relative gaps (%) on CVRPLIB instances. Bold marks the lowest reported gap in each row; gray highlights Ours.

Point	1	2	3	4	5	6	7	8	9	10	11	12
$x$	0.00	5.13	23.47	24.95	27.88	44.78	48.84	51.61	51.76	71.21	74.72	76.97
GAP (%)	3.684	3.684	3.674	3.671	3.683	3.662	3.653	3.645	3.657	3.661	3.643	3.646
Point	13	14	15	16	17	18	19	20	21	22	23	24
$x$	91.20	93.77	101.18	102.97	103.52	104.91	107.66	111.03	123.94	146.85	151.44	162.71
GAP (%)	3.631	3.641	3.648	3.634	3.647	3.657	3.652	3.638	3.616	3.597	3.585	3.564

Appendix

Table 12: Intermediate solve states on the 100K uniform TSP instance.

x

denotes cumulative compact-space 2-opt evaluations (millions), and GAP is measured after recovery and refinement.

	Final relative gap (%)				Search time (s)
Scale	JI	RNN	Hilbert	MST	JI	RNN	Hilbert	MST
1K	8.6338	10.7757	12.3769	10.5459	0.016	0.015	0.024	0.022
5K	9.2353	11.3989	13.4103	11.0869	0.156	0.150	0.194	0.198
10K	9.2395	11.2762	13.4725	11.1091	0.092	0.092	0.180	0.169
20K	9.2093	11.3263	13.6263	11.1296	0.224	0.211	0.441	0.409
50K	9.2136	11.1755	13.5666	11.1678	0.792	0.836	1.843	1.394

Appendix

Table 13: Final GAP and refinement time under matched initializations.

Scale	Greedy		JI
Scale	GAP(%)	Time(s)	GAP(%)	Time(s)
1K	8.4431	0.012	7.5405	0.012
5K	8.0722	0.072	7.7279	0.069
10K	8.2994	0.161	7.6362	0.145
20K	7.9563	0.373	7.6374	0.330
50K	7.9596	1.068	7.6603	0.785

Appendix

Table 14: Final GAP and 2-opt refinement time using greedy and JI initializations across different TSP scales.

Explore similar work

COMPASS: Ordered Clustered Routing at 100K Scale
Sep 17, 2026Ido Greenberg, Hugo Linsenmaier, Piotr Sielski +4Salesman Problem Order Matters
NVIDIA
Compute Time Scaling with Recursive Models for Combinatorial Optimization
Sep 28, 2026Zhengxi Zhang, Paul SwobodaCombinatorial Optimization Neural Solvers
COAgents: Multi-Agent Framework to Learn and Navigate Routing Problems Search Space
May 20, 2026Oleksandr Yakovenko, Mahdi Mostajabdaveh, Cheikh Ahmed +4Vehicle Routing Problem Multi-Agent Path Finding
Huawei Technologies Canada, 4321 Still Creek Dr, Burnaby, BC, Canada V5C 6S7 · Huawei Technologies, China

Sep 17, 2026, cs.LGJ/K move · Enter open · S save

COMPASS: Ordered Clustered Routing at 100K Scale

Ido Greenberg, Hugo Linsenmaier, Piotr Sielski, Shie Mannor+3

NVIDIA

Salesman Problem Order Matters

Open paper AskPDF arXiv

Large-scale routing often requires visiting clusters of nodes in a prescribed order, giving rise to the Ordered Clustered Traveling Salesman Problem (OCTSP). Optimizing each cluster independently seems natural, but misses non-local dependencies. We introduce the COMPASS algorithm for OCTSP, which combines search with learning-accelerated routing by orchestrating parallel sub-solvers. COMPASS has no quality ceiling and its solutions keep improving with compute. It exploits the clustered structure, and can reach exact solutions in time exponential in cluster size rather than instance size. Empirically, COMPASS consistently outperforms alternative methods. Unlike common large-scale routing solvers, COMPASS consumes general distance matrices and is not limited to coordinate inputs. We demonstrate scaling to 100K synthetic nodes and to 28.5K real e-commerce nodes. To our knowledge, the latter is the largest reported routing solution over asymmetric distances, 9x beyond established ATSP benchmarks.

Abstract

Explore similar work

COMPASS: Ordered Clustered Routing at 100K Scale

Compute Time Scaling with Recursive Models for Combinatorial Optimization

COAgents: Multi-Agent Framework to Learn and Navigate Routing Problems Search Space