A Good Route Is Not Always a Good Starting Route

TL;DR for operators

A dispatch system preparing routes for thousands of destinations has limited time to produce a workable plan. Improving the optimization algorithm is one option; improving the routes supplied to that algorithm is another. The second approach may deliver substantial gains without replacing the existing solver.

Zhao and colleagues introduce Just Initialize (JI), a training-free method that constructs starting solutions according to how well they can be improved by subsequent optimization.¹ It groups geographically related destinations, searches for promising arrangements of those groups, and reconstructs feasible routes for local refinement.

In controlled experiments, starting routes with nearly identical initial costs produced materially different final solutions under the same refinement procedure. On 100,000-node traveling-salesman instances, JI initialization achieved a 9.10% final gap, against approximately 11.02%–13.55% for three alternative initializations.

For logistics operators and routing-software providers, the practical opportunity is to treat initialization as a separately optimizable component. The benchmark results are substantial, but the reported speedups do not establish equivalent gains for deployed routing systems.

The starting route affects what a solver can achieve

Consider a delivery operation that must organize thousands of destinations before vehicles depart. Its routing system already contains a local-search optimizer, but the planning window permits only a limited number of improvements.

A conventional objective is to supply that optimizer with the lowest-cost feasible starting route available. The assumption is that a better starting cost should produce a better final route.

That assumption overlooks how local search operates. A solver explores modifications to its current arrangement, and different arrangements can expose different opportunities for improvement. Two routes with similar travel distances may therefore respond differently to the same optimization procedure.

The paper tests this distinction directly.

In Appendix E.5, Table 13, the authors compare JI initialization against randomized nearest-neighbor, Hilbert-order, and minimum-spanning-tree approaches. Starting objective gaps are matched within 0.05 percentage points, and every method uses the same 64-neighbor 2-opt refinement procedure.

The difference between JI and randomized nearest-neighbor is approximately 1.91 percentage points. Relative to Hilbert-order initialization, it is approximately 4.45 percentage points.

These results matter because the experiment controls the most direct alternative explanation: that JI simply begins with a shorter route. Under approximately matched initial costs, the resulting solutions still differ substantially.

The evidence supports a more discriminating definition of initialization quality: the cost achievable after a specified solver has operated for a specified computational budget.

The paper formalizes this using:

Here, $\pi_0$ is the feasible starting solution, $\mathcal{R}$ is the downstream solver, $B$ is its refinement budget, and $C_I$ measures routing cost. A smaller value indicates a more effective initialization.

This definition is conditional. A route that responds well to 2-opt under one computational budget is not necessarily the best starting point for another solver or a different budget.

Finding useful global structure without solving every detail

JI attempts to construct refinement-friendly routes without carrying out expensive full-resolution optimization from the beginning.

Its pipeline separates four activities.

Geometry-guided compression. Nearby destinations are grouped into compact units. Each unit retains geometric summaries, boundary information, local node sequences, and relevant routing constraints. The algorithm can initially consider relationships among groups rather than every individual destination.

Compact-space search. The method constructs and improves the ordering of these units using spatially restricted candidate searches and feasibility checks. Candidate structures are assessed according to the quality obtainable after recovery and bounded refinement, rather than only their compact-space objective.

Structural recovery. A selected compact arrangement must become a feasible original-space route. JI uses stored geometry, boundary configurations, and local sequences to favor compatible reconstructions. A temperature-controlled weighting mechanism gives higher probability to candidates with stronger structural consistency.

Micro-refinement. Local optimization then improves the recovered route while preserving feasibility.

This design deliberately leaves some fine-grained decisions for later. Unlike reduction methods that aim to reconstruct a near-final answer directly, JI seeks a starting arrangement that makes subsequent improvement productive.

The theoretical argument is also specific. If $n$ original destinations are compressed into $m=n/b$ units, the approximate ratio of candidate decisions examined per sweep is:

Here, $b$ is the average number of original nodes per compact unit, while $K_c$ and $K$ are the respective candidate-neighborhood widths.

With comparable widths and constant-size compact summaries, increasing the compression factor reduces the number of candidate decisions approximately proportionally.

This is a conditional reduction in search work, not a guarantee of proportional end-to-end runtime savings. Compression, feasibility checks, recovery, and refinement still consume computation.

JI is training-free, but it is not optimization-free.

The benchmark advantage extends beyond initialization quality

The main experiments cover 272 selected instances across traveling-salesman problems (TSP), capacitated vehicle routing (CVRP), vehicle routing with time windows (VRPTW), and prize-collecting TSP (PCTSP). Additional evaluations examine non-uniform spatial distributions and public benchmark libraries.

The principal comparisons report objective gaps against reference solutions, together with computation times. Those references are not universally certified global optima.

Selected large-scale results illustrate the differences:

Source: Section 5, Tables 1–2. Each row uses its problem-specific reference objective and reported solver configuration. These are selected comparisons, not hardware-normalized universal rankings.

The authors report approximately 70-fold average acceleration over existing approaches. That aggregate describes the evaluated comparisons and their runtime aggregation, not an expected multiplier for every routing workload.

More directly relevant to integration, Section 5.3, Table 3 tests whether JI benefits existing local-search procedures.

At 100,000 TSP nodes, conventional 2-opt obtains an 11.67% gap in 42.9 seconds. JI+2-opt obtains a 9.10% gap in 3.3 seconds, including the initialization pipeline. Improvements in both reported final gaps and total runtimes also appear for variable-neighborhood descent, iterated local search, and guided local search across the six tested TSP scales.

This supports treating initialization as a complementary solver component rather than requiring a replacement optimizer.

Component tests explain where the improvements originate

The study’s ablation experiments investigate whether the pipeline’s individual stages contribute to its performance.

On 100K-node uniform TSP instances, the complete method has a 3.78% gap in the ablation setting. Removing geometry-guided compression raises the gap to 5.00%; removing structural restoration raises it to 5.08%. Removing compact-space solving produces a smaller increase, to 4.34% (Section 5.4, Table 4).

These tests support the importance of both compressing the problem and reconstructing an effective route. They also suggest that the benefit cannot be attributed entirely to sophisticated search inside the compact representation.

A separate greedy-start experiment provides another view of efficiency. Under the specified 2-opt setup, JI requires approximately 29%–41% fewer candidate evaluations than greedy initialization to reach a 10% relative gap across six TSP scales (Appendix E.6, Table 15).

That result concerns candidate evaluations during a common refinement procedure. It should not be substituted for an end-to-end runtime comparison, because generating the starting solutions introduces its own costs.

The distinction is essential when translating experimental search efficiency into operational savings.

When better initialization becomes a business advantage

For a logistics operator, the immediate application is a routing system that already works but faces restrictive computation windows.

If initialization produces routes that respond more effectively to the existing optimizer, the operator may obtain lower-cost feasible routes without extending the planning period. Alternatively, the same quality threshold may be reached with less computation.

For an optimization-software provider, this suggests a modular design: retain the downstream solver while experimenting with alternative initialization components.

Cognaptus infers that a practical evaluation should compare initialization strategies on the same operational instances, using the same downstream optimization procedure and defined computational budgets. The measurements should include final route cost, feasibility, complete initialization and refinement time, and integration overhead.

The relevant business metric is not simply how quickly an initial route is generated. It is how much computation the entire pipeline requires to reach an acceptable feasible solution.

This distinction also affects systems with frequently changing destinations, capacities, or time windows. The benchmark results establish advantages on tested instances, but they do not determine the cost of rebuilding compressed representations or adapting recovered routes when operational inputs change.

Compression can exclude solutions that refinement cannot recover

JI’s speed advantage rests partly on restricting which global structures are considered. That restriction creates a corresponding risk.

The theoretical analysis separates approximation error into two components: structural error from choosing a restricted global arrangement, and recovery error from reconstructing a particular original-space route within that arrangement (Appendix C.3, Equation 60).

If the compact structure excludes the globally optimal original-space route, refinement constrained to that structure cannot recover it. Better reconstruction alone cannot eliminate such structural error.

The empirical results also show that JI does not dominate every comparison. On 2K-customer VRPTW instances, its 8.25% gap is worse than VROOM’s 1.83% and OR-Tools’ 5.03%, although JI is considerably faster. On 2K PCTSP instances, its 13.62% gap exceeds OR-Tools PCTSP’s 9.88%.

These cases show that quality-versus-runtime tradeoffs change with problem type and scale.

Other boundaries remain. The benchmark implementation uses a single trial for estimating downstream initialization quality, so general concentration guarantees for stochastic evaluation should not be inferred from repeated sampling that was not performed. The method also relies on problem-specific feasibility handling despite its training-free design.

Most importantly, the study does not establish production reliability, ongoing integration costs, or performance under continuously changing real-world routing workloads.

Initialization belongs in the optimization budget

The central contribution of Just Initialize is a change in what counts as a good starting solution.

Its matched-starting-gap experiments establish that immediate route cost cannot fully characterize the outcome of subsequent local search. Its compression and recovery pipeline offers a concrete way to construct routes with favorable downstream behavior, and its benchmark results show substantial computational gains under the evaluated conditions.

For organizations operating routing systems, this creates a credible engineering option: improve how solutions enter the optimizer before investing exclusively in more expensive optimization algorithms.

The value of that option ultimately depends on whether improved final routes or shorter computation times justify the complete cost of generating, integrating, and maintaining those initializations.

The best starting route is the one that allows the available solver to achieve the best feasible result within the actual planning budget.

Reference

Research implementation: https://github.com/BeihangAILab/Just-Initialize

Cognaptus: Automate the Present, Incubate the Future.