acceptodds
Under review as a conference paper at ICLR 2027

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

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, sub-second runtimes on 10K-node instances, and runtimes within tens of seconds on 100K-node instances.

Primary area:
optimization
Keywords:
Large-Scale Routing Optimization, Combinatorial Optimization, Training-Free Initialization, Solution Space Compression, Optimization Initialization.

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 2 reviews, above 27% of the others.
Reviewer_ihw7OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes a method for solving large-scale vehicle routing problems (VRPs). The proposed approach is to transform the problem into a compact space, optimize in that compact space, transform back, and then refine the result. This results in an orders of magnitude improvement in solve time in variety of VRPs.

Critical strengths
  1. The numerical benchmark results are amazing.
  2. The selection of baselines is solid, and the benchmark instances and metrics are standard.
Critical weaknesses
  1. There are almost no details about the proposed method, for example: how is the compact representation obtained? Is it learned? If so, there are no training details given in the main paper or appendix. If it isn't learned, then what is the relevance to ICLR?
  2. Same for the solving in the compact space, recovery from the compact space, and micro refinement.
Questions for authors
  1. Address the weaknesses
5 comments
AuthorsOpenReview ↗

Official Comment by Authors

Thank you for pointing out these limitations. We have further clarified the implementation details of each stage in the revised manuscript, with all modifications highlighted in blue. We provide the corresponding explanations and implementation references below.

Q1. How is the compact representation obtained? Is it learned?

JI is entirely training-free. The compact representation is constructed directly from the input instance using geometry-guided compression. For TSP, we construct candidate neighborhoods for each node, grow path fragments with a target size of 32 by examining eight candidate neighbors at each extension, and retain 16 portal neighbors for each fragment. For other routing problems, we use problem-specific compression procedures that preserve the corresponding constraints, such as aggregated demand for CVRP and prize and penalty information for PCTSP.

These procedures are described in Section 4.2, Algorithm 1, Appendix B.1, Appendix B.3, and Appendix D. Their concrete implementations are provided in src/JI_solver.py: tsp_c_compress (Lines 78–249), cvrp_compress (Lines 901–1120), pctsp_compress (Lines 1268–1354), and vrptw_compress (Lines 2251–2606), respectively.

Q2. How is optimization performed in the compact space?

The compact solution is first constructed by selecting feasible compact units and their orientations according to their connection costs. We then improve the resulting plan through compact-level local search, including exchange, relocation, and reversal operations. The feasibility checks and objective evaluation account for the constraints of each routing problem. For CVRP, an additional route-merging procedure is used to improve the compact plan.

The overall optimization procedure is described in Section 4.3, Algorithm 2, and Appendix B.1. In the source code, the corresponding implementations are Oracle (Lines 3128–3320), _construct_plan (Lines 3335–3388), _merge_plan (Lines 3390–3438), and _improve_plan (Lines 3440–3498), with solve coordinating these procedures (Lines 3320–3333).

Q3. How is the solution recovered from the compact space?

Recovery uses the original node sequences retained during compression. Given the optimized compact ordering, each fragment is expanded according to its selected orientation, and the resulting sequences are concatenated to construct the original-space solution. The paper further defines a structural consistency criterion based on geometric and intra-fragment sequence consistency to describe the compatibility between the recovered solution and the compact structure.

The recovery formulation is described in Section 4.4 and Appendix B.2, particularly Eqs. (43)–(48). The actual sequence reconstruction in the released source code is implemented by restore in src/JI_solver.py (Lines 3500–3505).

Q4. How is micro-refinement performed?

After recovery, the solution is further optimized in the original solution space. We apply problem-specific local-search operators and accept improving solutions according to the original objective and feasibility constraints. For TSP, this includes 2-opt, 3-opt, Or-opt, and iterated local search with Lin–Kernighan improvement.

This stage is described in Section 4.5 and Appendix D. Its implementation is dispatched through optimize in src/JI_solver.py (Lines 3536–3590), with the TSP implementation in tsp_ils_ils_optimize (Lines 812–845), CVRP implementation in cvrp_optimize_exchange (Lines 1179–1205), PCTSP implementation in pctsp_optimize (Lines 1578–1623), and VRPTW implementation in vrptw_optimize (Lines 2860–3000).

Verification and reproducibility.

We also provide the complete source code, instance-generation scripts, experimental configurations, and evaluation procedures. In particular, test/evaluate.py independently checks solution feasibility and recomputes objective values from the original instances (Lines 221–380). The evaluation protocol and commands for reproducing the experiments are documented in README.md (Lines 31–82). These resources allow the implementation and reported experimental results to be independently examined and reproduced.

We hope these additional references clarify where the methodological details are presented in the paper and how the corresponding procedures can be located and verified in the released implementation.

Thank you for providing the pointers to the source code. If there is no training and no machine learning components, can the authors explain the suitability of the work to ICLR?

AuthorsOpenReview ↗

Official Comment by Authors

Thank you for raising this concern. We acknowledge that Just Initialize does not introduce a trainable model or a new learning procedure. However, we believe its relevance to ICLR lies in its contribution to scalable learning-based combinatorial optimization.

Existing neural combinatorial optimization (NCO) methods primarily focus on learning how to construct or improve solutions. Our work investigates a complementary but important question: how can we identify optimization-friendly initializations that enable downstream solvers, including learning-based ones, to achieve better solutions under a fixed computational budget?

To this end, we formulate initialization quality in terms of expected downstream optimization performance, rather than immediate solution quality, and develop a geometry-guided compression, search, and recovery framework to identify such initializations. Importantly, Just Initialize is training-free and solver-agnostic, making it complementary to existing learning-based and classical optimization methods rather than another competing solver.

We believe this perspective provides a useful algorithmic contribution to the broader study of scalable combinatorial optimization, particularly NCO, by shifting attention from learning increasingly sophisticated search policies to improving where optimization begins. We will further clarify this connection and the intended positioning of our work in the revised manuscript.

Reviewer_tVEJOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents Just Initialize, a training-free initialization method for large-scale routing optimization. It groups nodes into compact units, searches for a promising route structure in the compressed space, and expands the result into an initial solution for further refinement. The aim is to find starting points that lead to good solutions after limited optimization, rather than simply minimizing the initial route cost. The method is evaluated with several downstream search procedures. Experiments cover TSP, CVRP, VRPTW, and PCTSP, including TSP and CVRP instances with up to 100K nodes, and report competitive solution quality with shorter runtimes than many tested baselines.

Critical strengths
  1. The paper highlights the importance of initialization for local search-based methods. It provides a practical way to build useful starting points from compact global structures, rather than relying only on random or simple greedy initialization.

  2. The empirical results show that the proposed method achieves superior performance than heavily-trained neural methods while preserves better efficiency.

Critical weaknesses
  1. The compression and recovery procedures rely strongly on the geometry and spatial locality of Euclidean routing. Although the experiments cover four routing problems, they do not establish how broadly this approach applies beyond this shared setting. The paper should clarify which parts of the method depend on Euclidean structure and which could extend to other routing settings or combinatorial optimization problems.

  2. The method uses post-search performance to select candidates, but the generation mechanism itself is not clearly designed around downstream search. If the good initial points can not be generated, the search-aware selection would not contribute enough gains. Therefore, designing a search-aware generation mechanism is more critical.

Questions for authors

How sensitive is the method to the compression strategy and granularity? For example, how do the target fragment size in TSP and the demand threshold in CVRP affect final solution quality and total runtime?

3 comments
AuthorsOpenReview ↗

Official Comment by Authors

We sincerely thank the reviewer for the positive assessment. It encourages us a lot. We hope our responses below address your concerns and questions.

All revisions made during the rebuttal are highlighted in blue in the revised PDF.

Weakness 1. Compression and recovery rely on Euclidean locality. Please clarify which components require it and how the method could extend to non-Euclidean routing or other combinatorial optimization problems.

We use Euclidean distances to grow local fragments, identify nearby fragments during compact search, and estimate the cost of reconnecting them during recovery. JI can extend to routing and other planning problems that admit a weighted-graph abstraction, provided that edge costs capture meaningful locality and the abstraction preserves the information needed to estimate connection costs and recover feasible solutions.

Weakness 2. Downstream search guides candidate selection. Please clarify how it also guides the generation of candidates that are easy to refine.

Thank you for raising this point. We agree that the ability to discover promising initializations is essential. We would like to clarify that downstream performance guides the iterative generation process in our solve stage, rather than only a final selection among independently generated candidates. As defined in the compact-space update equation, the next solution is selected according to its estimated post-refinement objective, and subsequent candidates are generated from the neighborhood of this updated solution. Thus, downstream feedback changes the search state and consequently the region explored in subsequent iterations.

While the neighborhood operators themselves are not adapted to a particular downstream solver, the overall initialization-generation process is guided by downstream performance. Designing adaptive proposal operators could further improve search efficiency, but is not required for this feedback mechanism.

Question 1. How sensitive is the method to the compression strategy and granularity? For example, how do the target fragment size in TSP and the demand threshold in CVRP affect final solution quality and total runtime?

To assess sensitivity to compression granularity, we jointly vary the fragment length cap bb and the extension neighborhood size KK in TSP because both constrain fragment growth. We report mean final gap to BKS (%) and mean total runtime (s) over 16 uniform instances per scale, with three runs per instance.

(b,K)5K Gap5K Time10K Gap10K Time20K Gap20K Time50K Gap50K Time100K Gap100K Time
(8, 2)3.7550.683.8341.503.9123.353.9479.724.13834.98
(16, 4)3.4230.483.4771.063.6142.403.6667.423.64327.78
(32, 8)3.3100.463.4421.023.5092.343.6298.083.64728.95
(64, 16)3.3620.583.4211.343.5153.203.65110.483.63637.12
(128, 32)3.4400.943.4342.093.5105.083.59716.203.66954.51

Intermediate settings are fastest at every scale because granularity shifts work between two stages. Coarser fragments leave fewer units for Solve, while the wider neighborhood makes Optimize more expensive. Once the finest setting is avoided, further coarsening yields no consistent improvement in final gap. The default (32,8)(32,8) offers a robust trade-off across all five scales, staying within 0.04 percentage points of the lowest mean gap and within 9% of the fastest mean runtime.

Thank you for your detailed response. I will maintain my positive score.

Dear Reviewer,

Thank you for taking the time to review our rebuttal and for your continued support. We sincerely appreciate your time and effort throughout the review process.

Best regards, The Authors

Comments on the paper

4 comments
AuthorsOpenReview ↗

Official Comment by Authors

Thank you for your comments and constructive suggestions. We address your concerns and questions below.

W1:My main concern is that the methodological novelty relative to established heuristics, and its contribution to the headline efficiency results, are insufficiently established. Coarsening followed by recovery and refinement has substantial precedent, including Walshaw (2002), A Multilevel Approach to the Travelling Salesman Problem, and the more recent Nałęcz-Charkiewicz et al. (2025), Graph Coarsening Approach to the Vehicle Routing Problem: An Approximation Strategy. The latter is already cited by the submission. Thank you for raising this important concern. We agree that the general paradigm of coarsening followed by recovery and refinement has been extensively studied, and we do not claim this high-level pipeline itself as our methodological novelty. Our contribution lies in a different objective for coarsening-based search: identifying initializations according to their downstream refinement potential, rather than directly solving the reduced problem or preserving a solution throughout a multilevel optimization process.

1. Difference from existing coarsening methods.

Walshaw (2002) adopts a multilevel optimization strategy, progressively coarsening the TSP instance and refining the tour across different levels. Nałęcz-Charkiewicz et al. (2025) reduce CVRP graph size through vertex merging, solve the reduced problem, and recover the solution through inflation. Both primarily use coarsening to facilitate solving the original problem.

In contrast, JI treats compression as a means of discovering optimization-friendly initializations. Specifically, Section 3.3 formulates initialization quality in terms of the expected objective after downstream optimization under a fixed budget, and Section 4.3 incorporates this criterion into compact-space search through J^B\widehat J_B. Thus, our goal is not simply to obtain a good solution in the compact space, but to identify a compact structure that leads to better downstream optimization.

2. Evidence of efficiency and effectiveness.

Our runtime comparisons include the complete pipeline, including compression, compact-space optimization, recovery, and refinement (Section 5.1). Table 3 further shows that JI improves both solution quality and search efficiency under the same refinement procedure. For example, on 100K TSP, JI+2-opt achieves a 9.10% gap in 3.3 seconds, compared with 11.67% in 42.9 seconds for conventional 2-opt.

Moreover, the ablation study in Table 4 demonstrates the contributions of individual components: removing compression or recovery increases both the final gap and runtime, while removing compact-space optimization primarily degrades solution quality. These results support the role of the proposed initialization mechanism in improving the efficiency of downstream optimization.

We will further clarify these distinctions and the corresponding experimental evidence in the revised manuscript.

Q1(part 1)&W4:How sensitive is the final quality–runtime trade-off to both fragment grouping and the internal visiting sequences? For example, at a representative TSP scale, could you vary the internal path construction or local improvement effort while holding group membership, endpoints, and coarse order fixed? Please use the same downstream refiner, match total runtime budgets including internal path construction, and report costs before and after refinement together with stage runtimes. This would test whether leaving internal paths only partially optimized is compensated by inexpensive downstream repair.

Thank you for raising this important concern.We compared three ways of constructing internal paths on 16 uniform TSP-50K instances with three seeds each. Fragment membership, endpoints, fragment order, and the downstream refiner were fixed. At about 5 s end to end, the initial advantage of stronger internal 2-opt largely disappeared after refinement. Judging by the initial gap alone would therefore overstate the benefit of extra 2-opt in this setting. Random ordering still yielded poor final solutions after a longer run.

MethodPre-Refine GAP (%) ↓Post-Refine GAP (%) ↓Internal Time (s)Refine Time (s)Total Time (s)
Full JI21.69593.67690.08172.60955.0347
Random Order338.1654326.86020.08564.26236.6962
Stronger Internal Optimization20.84133.69170.18512.47845.0250
AuthorsOpenReview ↗

Official Comment by Authors

Q4(part 1)&W6:Are the VRPTW service times, depot horizon, demand bounds, and capacities reported correctly? If so, is there evidence for settings where both capacity and time-window constraints can be active?

Thank you for catching this. The reported parameters are correct, and we overlooked that capacity is redundant at every tested scale. The depot horizon is fixed at 3, and each customer requires 0.2 units of service time. Therefore, a route can serve at most 15 customers and carry at most 135 units of demand, well below the minimum vehicle capacity of 250. The original experiments therefore do not test the interaction between binding capacity and time-window constraints.

To assess the effect of vehicle capacity, we set the capacity limit (Q) to 40, as this is equivalent to the combined average demand of eight customers at the mean demand of 5, well within the theoretical limit of 15 customers imposed by service time alone. The route checks confirmed that capacity and customer time windows could each independently rule out a route extension in every tested instance. We report the paired change in total distance to quantify the effect on the solutions, and end-to-end runtime to measure its computational impact.

2K5K10K20K
Mean distance increase5.13%6.60%9.03%10.41%
Default Time0.58 s1.80 s2.80 s5.85 s
Q=40Q=40 Time0.51 s1.66 s2.85 s6.21 s

As the number of customers increases within the same area, the default solutions consolidate more stops within the fixed depot horizon, from 7.2 customers per route at 2K to 8.6 at 20K. With Q=40Q=40, the share of fully loaded routes rises from 23% to 39%, and the increase in route count relative to the default grows from 8.3% to 17.5%. The additional distance on depot departure and return legs accounts for 74–88% of the total distance increase across scales, with the largest share at 20K.

Q4(part 2)&W6:For the 20K collection, could you explain the lowest-reference-cost selection rule and report results or solver-status information for all sixteen originally generated instances? Proven optima are not necessary for this clarification; available feasible reference costs and explicit reference-search status would already help assess the selection's effect.

Thank you for raising this concern about potential selection bias.We ran HGS-PyVRP on all 16 originally generated 20K instances with a four-hour search budget per instance. For five instances, the final feasible solution still used one vehicle per customer, so We excluded these five from the selection pool. We ranked the remaining 11 instances by total distance, the optimization objective, and retained the eight with the lowest final feasible HGS costs. As a cross-check, the same eight instances had the largest percentage reductions in total distance relative to their respective one-customer-per-vehicle baselines.

IDCostReduction ratioIDCostReduction ratio
013,359.0784.95%0925,616.730.00%
022,574.2386.68%102,195.1087.52%
0322,891.690.00%112,736.7386.29%
042,778.5786.16%1229,129.450.00%
053,136.3185.41%131,952.1988.13%
061,940.5288.17%143,044.4985.67%
072,615.5886.56%1524,376.930.00%
083,353.8584.99%1627,514.640.00%

Q4(part 3)&W6:Two reporting details also need clarification. JI+VND on TSP-100K is 5.74%/2.7 minutes in Table 1 versus 6.08%/1.1 minutes in Table 3. Table 3's total JI+2-opt times match the rounded refinement-only times in Table 13. Since Section 5.1 states that all stages are included, please reconcile the configurations and timing definitions; this is not an assertion that initialization was omitted.

We apologize for the inconsistencies in our reported results and appreciate the reviewer's careful examination.The discrepancies between Tables 1 and 3 arise from selecting different checkpoints from the same search trajectories. We will standardize the checkpoint selection protocol and reconcile the reported results across both tables in the revised manuscript.

Q4(part 4)&W6:Exact solver versions and paired per-instance variability would also help assess the comparisons.

We appreciate the reviewer's emphasis on reproducibility and provide additional per-instance comparisons and exact solver versions. With the same reference costs, JI’s average gap across reruns was lower than UDC’s on every TSP-10K and TSP-20K instance. The margin varied by instance. We used UDC from CIAM-Group/NCO_code (commit 505742e). The reference solvers were LKH 3.0.9 (ProvideQ mirror) for TSP and PCTSP, PyVRP 0.11.3 for VRPTW, and FILO2 (commit 17b8f84) for CVRP.

AuthorsOpenReview ↗

Official Comment by Authors

Q2:Appendix B.1 mentions a shortlist: how is it formed, how many candidates receive downstream refinement, and what is the evaluation budget?

Thank you for pointing out this ambiguity. The shortlist is formed from the restricted compact-space neighborhood rather than the entire compact solution space. Specifically, we generate candidate solutions through exchange, relocation, and reversal operations, and retain only feasible candidates. The resulting feasible neighborhood, together with the current solution, constitutes the candidates considered for downstream evaluation. The candidate width for compact-space local search is Klocal=min⁡(24,m)K_{\mathrm{local}}=\min(24,m), where mm is the number of compact units.

Each candidate is evaluated using one downstream refinement trajectory (S=1S=1). The refinement is bounded by BB steps and terminates early when no improving move is available. This evaluation budget is separate from BμB_\mu, which controls the final post-recovery refinement.

We acknowledge that the original description does not explicitly report the resulting shortlist cardinality or the numerical value of BB for each problem class. We will clarify these implementation details and make the shortlist construction explicit in Appendix B.1 and Algorithm 2.

AuthorsOpenReview ↗

Gentle Reminder

Dear Reviewer,

As the rebuttal discussion period is coming to an end, we'd really appreciate it if you could take a look at our response when you have time. Please let us know if you have any further questions or concerns.

Thank you very much for your time and consideration!

Best regards, The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.