PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2609.35443v3cs.AI

TL;DR

Large-scale routing is difficult because existing solvers face growing computational costs, while learning-based approaches still struggle to scale. Just Initialize compresses instances to identify global routing structures and recovers them as starting points for refinement. Across four routing benchmarks, it reports competitive or superior quality at substantially lower cost, with an average speedup of approximately 70×.

  • Problem

    Large-scale routing is computationally expensive, and learning-based methods remain challenging to scale to large routing problems.

    Source: §1 · pp. 1–2

  • Method

    Just Initialize is a training-free, solver-agnostic component that compresses routing instances to find global structures and recovers them as optimization-friendly starting points.

    Source: §1 · p. 2

  • Results

    Across four routing benchmarks, JI+Refine achieves competitive or superior solution quality while reducing computational cost, with an average speedup of approximately 70× over existing approaches.

    Source: §5.2 · p. 8

  • Takeaways & Limitations

    Experiments show initialization can help navigate large combinatorial search spaces as a complement to improving optimization algorithms.

    Source: §6 · p. 10

Abstract

from arXiv · show

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.

1 INTRODUCTION

Large-scale routing remains costly because exact methods scale poorly, iterative heuristics require search, and scaling learning-based methods is challenging. Just Initialize addresses this by finding optimization-friendly starting points through compression, then leaving fine-grained decisions to downstream refinement; experiments report competitive or superior quality with reduced cost across four routing problems and 1K–100K-node instances.

1 INTRODUCTION

  • Exact methods become prohibitively costly at scale, while heuristics and metaheuristics rely on iterative evolution and evaluation.These constraints hinder their use in large-scale real-world scenarios requiring efficient decisions.Source: §1 · p. 1
  • Recent learning-based approaches address scaling through solver, decomposition, search-space, and neural-guidance improvements, but focus on the solving process rather than its starting point.Scaling neural combinatorial optimization to large routing problems remains challenging.Source: §1 · p. 2
  • Prior compression approaches that expect recovery to yield a high-quality solution directly must preserve global structure and local detail, limiting compression.Source: §1 · p. 2
  • Just Initialize compresses an instance, identifies promising global structures in a compact surrogate space, and recovers them as optimization-friendly starting points for downstream refinement.The approach treats initialization quality as refinement potential, not just immediate objective value.Source: §1 · p. 2
  • Across TSPs, CVRPs, VRPTWs, and PCTSPs, Just Initialize achieves competitive or superior solution quality while reducing computational cost on instances from 1K to 100K nodes.The approach is training-free and solver-agnostic.Source: §1 · p. 2

2 RELATED WORKS

Prior work tackles routing scalability through traditional search, neural combinatorial optimization, and problem reduction. Just Initialize differs from recovery-oriented reduction by using compression to find optimization-friendly starting points while leaving detailed routing decisions to later optimization.

2.1 TRADITIONAL OPTIMIZATION METHODS

  • High-quality solutions from exact methods become increasingly expensive with problem size, while large-scale heuristics and metaheuristics rely on designed neighborhoods and iterative search.Examples include Lin–Kernighan–Helsgaun, adaptive large neighborhood search, and hybrid genetic search.Source: §2.1 · p. 3

2.2 NEURAL COMBINATORIAL OPTIMIZATION

  • Neural combinatorial optimization learns construction or improvement strategies, and large-scale variants alter architectures, decompose problems, change representations, or combine neural predictions with classical optimization.These methods primarily target how solutions are constructed, represented, or optimized during search.Source: §2.2 · p. 3

2.3 PROBLEM REDUCTION AND COMPRESSION

  • Unlike reduction methods that preserve information for solution recovery, Just Initialize compresses to identify optimization-friendly starting points and leaves detailed routing decisions to subsequent optimization.Earlier reduction approaches include clustering, explicit reduction, restricted neighborhoods, subproblem optimization, and graph coarsening.Source: §2.3 · p. 3

3 PRELIMINARIES

The preliminaries represent routing solutions with a shared sequence-and-boundary form, map original solutions into a compact space that preserves coarse structure, and evaluate initializations by their downstream objective under a fixed solver and budget.

3.1 ROUTING PROBLEMS AND SOLUTION SPACES

  • A multi-route solution is represented as one visiting sequence plus breakpoints that divide it into routes, with the representation shared across routing variants.TSP and PCTSP use a single segment, while CVRP and VRPTW impose additional route-segment and visitation constraints.Source: §3.1 · pp. 3–4

3.2 COMPACT REPRESENTATIONS AND SOLUTION SPACE MAPPING

  • Instance compression groups original nodes into compact units, and projection preserves coarse structure while omitting fine-grained decisions; multiple original solutions can map to one compact solution.The compact instance induces a lower-dimensional solution space.Source: §3.2 · p. 4

3.3 INITIALIZATION QUALITY MEASUREMENT

  • Initialization quality is measured by the expected objective after applying a downstream solver to the starting solution under a computational budget.The budget may be runtime, search iterations, or objective evaluations; lower cost indicates a more effective initialization when comparing under a fixed solver and budget.Source: §3.3 · p. 4

4 METHODOLOGY

Just Initialize separates solution discovery from optimization: it searches compact routing structures, recovers an optimization-friendly starting point, and leaves local decisions to downstream refinement.

4.1 OVERVIEW OF JUST INITIALIZE

  • Just Initialize separates global structure discovery in a compact space from optimization in the original space, where downstream refinement improves the recovered starting point.The method has three stages: compression, compact-space optimization, and solution recovery.Source: §4.1 · p. 5

4.2 GEOMETRY-GUIDED INSTANCE COMPRESSION FOR SOLUTION SPACE REDUCTION

  • Compression groups original nodes into compact units, preserving coarse geometry and boundary information while leaving fine-grained decisions for later refinement.The compact representation maps multiple original solutions to the same compact structure.Source: §4.2 · p. 5

4.3 SOLVING IN THE COMPACT SPACE

  • Compact-space search minimizes estimated initialization quality by iteratively modifying compact-unit order while preserving feasibility.The exact downstream expectation is unavailable and is estimated with Monte Carlo sampling; the final compact solution is then recovered.Source: §4.3 · pp. 5–6

4.4 RECOVERING OPTIMIZATION-FRIENDLY INITIALIZATIONS

  • Recovery selects an original-space initialization compatible with the compact ordering, geometry, and boundary configuration, balancing compatibility with diversity.The selected initialization is passed to downstream refinement.Source: §4.4 · p. 6

4.5 MICRO REFINEMENT

  • Micro refinement repeatedly selects the best improving neighbor and stops when none improves the objective, correcting local decisions without rebuilding the global structure.The recovered initialization is treated as a starting point rather than a final solution.Source: §4.5 · p. 7

5 EXPERIMENT

Across four routing benchmarks, Just Initialize paired with refinement achieves competitive or superior solution quality at substantially lower computational cost. Tests also find benefits across initializations and refinement procedures, with compression and recovery contributing strongly in ablations.

5.1 EXPERIMENT SETTINGS

  • The evaluation covers TSP, CVRP, VRPTW, and PCTSP, including large-scale instances from 1K to 100K nodes, and reports objectives, relative gaps, and time cost.JI runtimes include compression, compact-space optimization, recovery, and downstream refinement.Source: §5.1 · p. 7

5.2 COMPARATIVE STUDY

  • Approximately 70× average speedup accompanies comparable solution quality; 10K-node instances finish within seconds and 100K-node instances within tens of seconds.Across TSP, CVRP, VRPTW, and PCTSP, JI+Refine remains competitive or superior while reducing computational cost.Source: §5.2 · p. 8, Table 2 · p. 8

5.3 EFFECTIVENESS AS A SOLVER INITIALIZATION

  • Across refinement procedures and problem scales, JI initialization yields lower final gaps and shorter overall runtimes than the original solvers.With the same JI-generated initialization, the proposed refinement also achieves better solution quality than existing refinement procedures.Source: §5.3 · pp. 8–9, Table 3 · p. 9

5.4 ABLATION STUDY

  • On uniform TSP instances, removing compression or recovery increases final gaps by over 1% at large scales, while removing compact-space solving causes smaller changes.The ablations compare component removals with the full model.Source: §5.4 · p. 9, Table 4 · p. 9

6 CONCLUSION

The conclusion presents Just Initialize as a training-free, solver-independent way to improve where optimization starts, using compact-space global structures to guide refinement. Its experiments span four routing problems and scales from 1K to 100K nodes, while the appendix groups baseline methods by approach and trade-off.

6 CONCLUSION

  • The method separates solution discovery from optimization, recovering coarse global structures from compact space as starting points for existing solvers.This lets solvers focus on refining promising regions rather than searching the entire solution space.Source: §6 · p. 9
  • Across TSP, CVRP, VRPTW, and PCTSP, Just Initialize scales from 1K to 100K nodes with competitive solution quality and substantially reduced computational cost.The conclusion frames initialization as a complementary direction to improving optimization algorithms.Source: §6 · p. 10

A.1 BASELINES

  • The appendix organizes baselines as classical solvers, neural construction and diffusion methods, and decomposition or learned-search methods, describing each approach’s trade-offs.Examples include LKH-3, POMO, and GLOP.Source: §A.1 · pp. 14–15

A.2 BENCHMARKS

The appendix specifies routing formulations and benchmark conventions for four problem types. It also describes instance scales, objective scaling, and relative-gap calculation.

A.2 BENCHMARKS

  • Synthetic objectives are divided by 10^6 after scaling distance-related quantities, and reported relative gap is 100(C − Cref)/Cref percent.Public TSP instances use their source distance rules and unscaled objectives.Source: §A.2 · p. 15
  • The main CVRP comparison uses 80 instances at five scales from 5K to 100K customers, with one additional depot in each instance.The synthetic TSP benchmarks contain 96 uniform and 144 extended-distribution instances; the additional 42 public instances retain their original distance definitions.Source: §A.2 · pp. 15–16
  • VRPTW adds service durations and service-start windows to capacitated routing, and its benchmark has 72 instances from 1K to 20K customers, each with one depot.The formulation represents departures and returns with start and end depot copies.Source: §A.2 · p. 16
  • PCTSP minimizes travel plus penalties for omitted customers while requiring a collected-prize quota; its benchmark has 72 instances from 1K to 20K optional customers.The synthetic benchmark uses P = 1 before integer export.Source: §A.2 · pp. 16–17

B IMPLEMENTATION DETAILS OF JUST INITIALIZE

Just Initialize searches compact routing units, recovers an optimization-friendly solution, and applies bounded refinement; the analysis characterizes its decision cost and compact-objective estimates.

B.1 ALGORITHMIC IMPLEMENTATION

  • Compact search, recovery, and bounded original-space refinement form the implementation; each unit retains its ordered node sequence for recovery.Problem-specific feasibility checks use the resources relevant to that routing class.Source: §B.1 · p. 17

B.2 STRUCTURAL CONSISTENCY SCORE FOR RECOVERY

  • The recovery score favors solutions that preserve compact-route boundary geometry, inter-unit connections, and stored local node structure.Its normalized discrepancy terms receive equal weights, and more consistent candidates receive higher recovery probability.Source: §B.2 · pp. 19–20

B.3 PARAMETER SETTINGS

  • TSP units contain about 32 nodes, PCTSP units 8, CVRP units target 0.8Q demand, and VRPTW fragments contain at most 16 nodes.These problem-specific settings are fixed within each class rather than tuned per instance.Source: §B.3 · p. 20

C THEORETICAL ANALYSIS

  • The analysis assumes candidate-restricted neighborhoods, constant-size unit summaries, and strictly decreasing accepted refinement moves that stop at a local endpoint or budget limit.It models n nodes grouped into m units, with average unit size b=n/m>1.Source: C THEORETICAL ANALYSIS · pp. 20–21

C.1 DECISION COUNT AND COST OF THE COMPACT STAGE

  • With Kc=Θ(K), compact search reduces decisions per sweep by factor b; its construction cost is O(mKc), versus O(nK) for full-instance placements.A compact decision is O(1) when connection costs use constant-size unit summaries; total initialization cost is a bounded multiple of an original-space sweep under fixed configuration.Source: §C.1 · p. 21

C.2 VALIDITY OF THE COMPACT-SPACE OBJECTIVE

  • The compact objective averages S independent refinement trials, yielding an unbiased estimate whose variance is σ²/S; bounded trials also admit a Hoeffding deviation bound.For a finite evaluated candidate set, the selected candidate is within 2ε of the best initialization quality with probability at least 1−α; deterministic refinement with concentrated recovery gives ε=0.Source: §C.2 · p. 22

C.3 DECOMPOSITION OF THE RESIDUAL ERROR

The residual error separates structural selection from recovery fidelity, assigning compression and compact search responsibility for the former and local refinement for the latter.

C.3 DECOMPOSITION OF THE RESIDUAL ERROR

  • Descent refinement cannot increase objective value, so the refined solution’s residual error is bounded by the recovery error of its starting initialization.The decomposition’s two terms are nonnegative.Source: §C.3 · p. 22
  • Structural error reflects the selected structure, while recovery error reflects how faithfully recovery instantiates it; local refinement can absorb the latter, not the former.This separation permits aggressive compression when global structure is retained, without requiring local detail to be accurate during compression.Source: §C.3 · p. 23
  • Immediate objective value alone does not determine initialization quality: equal-cost starts can reach different local minima under a fixed descent budget.The paper therefore compares starts by expected refined objective for a fixed solver and budget.Source: §C.3 · p. 23

D.1 DATASETS

The datasets cover synthetic and public TSP benchmarks and uniform CVRP, VRPTW, and PCTSP instances; generation and solver settings specify their scales and constraints.

D.1 DATASETS

  • The TSP collection has 282 instances across uniform, clustered, explosion, implosion, and public benchmark groups; CVRP has 96 uniform instances, while VRPTW and PCTSP each have 72.Main uniform comparisons use 80 TSP and 80 CVRP instances from 5K to 100K; VRPTW’s 20K set retains eight selected instances.Source: §D.1 · p. 23

D.2 PARAMETERS

  • Generation settings define task-specific spatial distributions, capacities, time windows, and seeds; frozen solver settings fix parameters such as candidate counts and search budgets.For example, CVRP capacity remains 2000 at 50K and 100K customers, while VRPTW instances are resampled until every customer permits a feasible depot round trip.Source: §D.2 · pp. 23–24, Table 6 · p. 24

E.1 NON-UNIFORM TSP INSTANCES

Just Initialize remains efficient across non-uniform synthetic TSP distributions and performs competitively on TSPLIB95, including large instances, without training or instance-specific adaptation.

E.1 NON-UNIFORM TSP INSTANCES

  • On clustered, explosion, and implosion TSP instances, JI maintains competitive quality at substantially lower computational cost, taking a few seconds at 10K nodes and tens of seconds at 100K.The evaluation covers 16 instances per distribution at 1K, 10K, and 100K nodes.Source: §E.1 · pp. 24–25, Table 7 · p. 25, Table 8 · p. 25

E.2 TSPLIB95 INSTANCES

  • The TSPLIB95 evaluation applies JI without additional training or instance-specific adaptation, supporting its use on unseen real-world routing instances.The analysis attributes its performance to extracting each instance’s geometric structure through compression.Source: §E.2 · p. 26
  • On 32 TSPLIB95 instances, JI achieves the lowest average relative optimality gap among compared methods at 3.54%, has the best-reported gap on 19 instances, and successfully solves all instances.Source: §E.2 · p. 26

E.3 CVRPLIB INSTANCES

Across CVRPLIB and TSP studies, Just Initialize (JI) produced strong refined solutions across routing scales and formulations. Matched-start and greedy-start comparisons indicate that its initializations can improve downstream refinement, including reducing the evaluations needed to reach a target GAP.

E.3 CVRPLIB INSTANCES

  • JI achieved a 7.77% average gap on all 11 CVRPLIB instances and the best-reported gap on 8, across instances with up to 30K customers.The authors report the lowest average gap among compared methods.Source: §E.3 · p. 27, Table 11 · p. 28

E.4 CASE STUDY

  • On a 100K-node uniform TSP, refined GAP decreased from 3.684% to 3.564% across compact-space solve checkpoints, with small intermediate fluctuations.Each sampled compact-space state was recovered and refined using the same procedure and budget.Source: Table 12 · p. 28, §E.4 · p. 29, Figure 3 · p. 29

E.5 CONVERGENCE FROM MATCHED STARTING GAPS

  • Under matched initial GAPs, JI consistently achieved lower final GAPs than alternative initializations across all six TSP scales, with convergence trajectories showing faster improvement during optimization and better final solutions.Source: §E.5 · p. 30, Figure 4 · p. 30

E.6 GREEDY STARTS AND SEARCH EFFICIENCY

  • Across different TSP scales, JI reached the 10% GAP target with 29–41% fewer candidate evaluations than greedy initialization and achieved lower final GAPs across all scales.JI also used comparable or lower refinement time and improved more rapidly during early optimization.Source: §E.6 · p. 31

Related papers

Loading 2609.35443v3…