Source-linked AI summary
Depot-Closed Multi-Component Construction for Neural Vehicle Routing
Shinichiro Hamada, Hisashi Kashima
TL;DR
Route-by-route neural construction commits route membership early, limiting coordination across routes. The paper builds multiple components and uses depot-closed interpretation with Clarke–Wright savings to guide merges; its CVRP100-trained policy reports strong performance across size and capacity shifts, with stated limitations at CVRP1000 and in objective scope.
Problem
Route-by-route construction commits customer assignments before other routes form, limiting global coordination across routes.
Source: §1 · p. 1Method
The method grows multiple route components and uses the depot-closed interpretation and exact Clarke–Wright merge savings with component state to learn which merges to make and when.
Source: §1 · pp. 1–2Results
A single CVRP100-trained policy outperforms reported representative neural solvers on CVRP100–500 with greedy inference, performs strongly up to CVRP1000 when reused for reconstruction, and beats reported neural solvers across C = 10 to 500.
Source: §1 · p. 2Takeaways & Limitations
The results support multi-component construction as an alternative neural route-construction paradigm, with controls identifying learned route closing as a plausible contributor to tight-regime failures.
Source: §5 · p. 9Greedy inference on CVRP1000 falls short of LEHD, and the study focuses on additive total-distance CVRP with variable route counts rather than prescribed counts or non-additive objectives.
Source: §5 · p. 9
Abstract
from arXiv · showhide
Most neural constructive solvers for the vehicle routing problem (VRP) use route-by-route construction, extending one route until completion before starting the next. This commits route membership early and hinders global coordination across routes. We propose multi-component construction, which maintains many route components simultaneously and merges them in an arbitrary order. This removes the depot-return cue that route-by-route construction obtains from the remaining capacity; to compensate, we introduce an interpretation in which every component is treated as an implicitly depot-closed route. Under this depot-closed interpretation, every intermediate state of standard CVRP construction is a complete feasible solution, and the exact cost reduction of a merge is the Clarke-Wright saving. The neural policy combines this CW-saving signal with the evolving component state to learn what to connect and when to connect. A policy trained only on CVRP100 outperforms the reported results of representative neural solvers on CVRP100-500 with greedy inference and, reused for ruin-and-reconstruct, performs strongly at all evaluated sizes up to CVRP1000. In a zero-shot Constraint Tightness evaluation with capacities from $C=10$ to $500$, it outperforms the reported neural solvers at every capacity. Controlled analyses show that robustness persists without CW grounding and point to learned route-closing behavior as a plausible contributor to the tight-regime degradation of learned route-by-route solvers.
1 INTRODUCTION
Neural constructive solvers commonly build one route at a time, which commits customer assignments before other routes form and limits coordination. The paper instead grows multiple components, grounding their merges in depot-closed routes and Clarke–Wright savings; a CVRP100-trained policy reports strong size and capacity generalization.
1 INTRODUCTION
- Route-by-route construction commits customers before other routes form, limiting global coordination despite using remaining capacity as a feasibility and route-progress cue.The cue helps the policy judge when to return to the depot.Source: §1 · p. 1
- Multi-component construction grows many route components simultaneously, allowing assignment decisions across routes to be committed in an arbitrary order.The whole component configuration is visible as the route partition forms.Source: §1 · p. 1
- Preliminary experiments found that a multi-component policy without depot-related grounding formed some petal-like geometry but closed routes to the depot poorly.This motivated grounding merges in depot-related information.Source: §1 · p. 2
- The depot-closed interpretation treats each component as a closed route, making every intermediate state feasible and each merge’s exact cost reduction its Clarke–Wright saving.The policy combines that saving signal with component state to select what to connect and when.Source: §1 · p. 2
- A CVRP100-trained policy outperforms reported representative neural solvers on CVRP100–500 with greedy inference and performs strongly up to CVRP1000 when reused for reconstruction.A single C = 50 model also outperforms reported neural solvers at every evaluated capacity from C = 10 to 500.Source: §1 · p. 2
2 RELATED WORK
Prior neural routing work largely uses autoregressive, route-by-route construction, while some methods construct or modify multiple routes or fragments. This paper distinguishes its approach by selecting sequential merges from an evolving component state and grounding action scores in exact Clarke–Wright savings.
2 RELATED WORK
- Unlike DIFUSCO’s static heatmap for joining path fragments, this policy recomputes merge actions from the evolving route-component state.JAMPR and L2C-Insert also revisit construction, but use route–customer pair actions or insertions at valid positions.Source: §2 · p. 2
- Ruin-and-reconstruct is used for large-scale generalization and inference-time refinement, and this method shares its depot-closed component representation between construction and reconstruction.The same policy serves both settings.Source: §2 · p. 3
- Classical Clarke–Wright greedily merges feasible depot-closed singleton routes by saving, whereas this method uses saving as an exact action-local signal in a dynamic multi-component policy.Learning-based CW enhancements instead adjust the priority order within the saving list.Source: §2 · p. 3
- Prior generalization studies emphasize size and coordinate-distribution shifts, while Constraint Tightness varies capacity and can change route structure and solving strategy.The cited analysis places CVRP100 with C = 10 near OVRP and C = 500 near TSP.Source: §2 · p. 3
3 DEPOT-CLOSED MULTI-COMPONENT CONSTRUCTION
The section replaces sequential single-route growth with asynchronous merging of feasible route components, then assigns each component depot-closed semantics to keep merges tied to routing cost.
3.1 MULTI-COMPONENT DECISION PROCESS
- Each step merges endpoints of different capacity-feasible components; route partition and route count emerge jointly when no feasible merge remains.Source: §3.1 · p. 4
3.2 GIVING ROUTE SEMANTICS TO EACH COMPONENT
- Treating each path as implicitly depot-closed makes every intermediate construction state a complete feasible CVRP solution with an evaluable routing cost.Source: §3.2 · p. 4
3.3 GROUNDING EACH MERGE IN THE ROUTING OBJECTIVE
- A merge's exact objective reduction is the Clarke–Wright saving, while a learned state-conditioned score accounts for future options beyond immediate savings.Source: §3.3 · p. 4
3.4 GLOBAL NEURAL REASONING OVER UNORDERED MERGES
- The light encoder handles static customer features; each step's heavy decoder re-encodes the depot and active endpoints with loads, and pair scores combine symmetrized pointer logits with CW bias.Source: Figure 2 · p. 5, §3.4 · p. 5
3.5 LEARNING WHAT TO CONNECT AND WHEN TO CONNECT
- Training expands decision freedom from what to connect toward when, and states from ordinary construction toward repair; supervised learning treats all reference-compatible feasible merges as correct without imposing a teacher order.Source: §3.5 · pp. 5–6
3.6 THE SAME POLICY FOR CONSTRUCTION AND RECONSTRUCTION
- The same policy handles construction and ruin-and-reconstruct by treating remaining route fragments and singletons as components, with only the initial state changing.Source: §3.6 · p. 6
4 EXPERIMENTS
Experiments test a C=50-trained policy across sizes and capacities using greedy and reconstruction inference, alongside controlled analyses. Results show strong cross-size and zero-shot capacity performance, while analyses examine route-subset sampling, CW grounding, and possible causes of tight-regime degradation.
4.1 EXPERIMENTAL SETUP
- The experiments train all main models on uniform Euclidean CVRP100 with C = 50 and apply the same policy to larger sizes without additional training.Training uses 1,000,000 CVRP100 instances solved by HGS; test sets include CVRP100 and 128 instances each of CVRP200/500/1000.Source: §4.1 · p. 6
4.2 STANDARD SIZE GENERALIZATION
- With greedy inference, S3 outperforms reported results on CVRP100–500 but falls short of LEHD on CVRP1000.Its gap is larger than S3's at every size for Classical CW, and learned state-dependent merge selection provides an additional gain.Source: §4.2 · pp. 6–7, Table 1 · p. 7
4.2 STANDARD SIZE GENERALIZATION; 4.5 GENERALIZATION ACROSS CONSTRAINT TIGHTNESS
- S3 beats LEHD RRC1000 at all four sizes and reported neural solvers at every capacity (mean gap 3.00% versus BQ's 7.22% and LEHD's 9.62%).The capacity sweep is zero-shot, with neural models trained at C = 50.Source: §4.2 · p. 7, Table 2 · p. 7, Table 5 · p. 8
4.3 ANALYSIS OF SIZE GENERALIZATION
- Route-subset sampling sacrifices about 0.1–0.2 pp on CVRP100 but improves extrapolation; on CVRP500, S3's gap falls from 2.746% to 1.407%.The analysis suggests experiencing different effective problem sizes during training is important for size generalization.Source: §4.3 · p. 7, Table 3 · p. 8
- Fixing α at its CVRP100-selected value changes S3's mean gap only from 2.700% to 2.725%, so target-size calibration is not essential.The saving coefficient is a scalar hyperparameter that can be calibrated without retraining.Source: §4.3 · p. 8
4.4 DISENTANGLING NEURAL REASONING AND CLARKE–WRIGHT GROUNDING
- Adding CW saving post hoc improves the gap from 5.822% to 3.883%, and fine-tuning on CW-grounded logits further improves it to 3.787%.The analysis attributes gains both to making each candidate merge's objective change explicit and to adapting the learned score to the CW-grounded action space.Source: §4.4 · p. 8, Table 4 · p. 8
4.5 GENERALIZATION ACROSS CONSTRAINT TIGHTNESS
- At C = 10, learned route-by-route solvers have gaps of at least 7.47%, while non-learned CW controls and multi-component policies are at most 5.91%.Controls do not isolate the cause; learned route closing is hypothesized as a contributor, while sequential CW is only 1.28 points worse than parallel CW at C = 10.Source: §4.5 · p. 9
5 CONCLUSION
Multi-component construction pairs flexible route growth with depot-closed components and Clarke–Wright savings; experiments support its promise while identifying scope and correction limits. The paper also records AI-use and reproducibility information.
5 CONCLUSION
- Depot-closed components make every intermediate CVRP state a complete feasible solution, with merge improvement equal to the Clarke–Wright saving combined with component state.The policy learns which components to connect and when; controls point to learned route closing as a plausible contributor to tight-regime failures.Source: §5 · p. 9
- Edges fixed inside a component cannot be changed directly during ordinary construction, so major corrections require ruin-and-reconstruct.The work focuses on additive total-distance CVRP with a variable number of routes; prescribed route counts and non-additive objectives such as min-max routing remain future work.Source: §5 · p. 9
AI USE STATEMENT / REPRODUCIBILITY STATEMENT
- Generative AI tools assisted with technical discussion, literature search, implementation, experimental analysis, and manuscript preparation; authors reviewed outputs and take responsibility for the final content.The paper says its method, protocol, and settings are specified in Sections 3–4 and Appendix A, including architecture, training, seeds, inference, and runtime measurement details.Source: AI USE STATEMENT · p. 10, REPRODUCIBILITY STATEMENT · p. 10
A.1 MODEL AND TRAINING CONFIGURATION
The appendix identifies the shared-policy curriculum and specifies training-stage, reconstruction, and inference settings, including how the saving coefficient is chosen.
A.1 MODEL AND TRAINING CONFIGURATION
- All curriculum stages train the same policy, each starting from the preceding stage’s checkpoint.Training progresses from supervised learning in S0–S2 to REINFORCE in S3, with a rollout baseline initialized from S2 and updated on challenge-set improvement.Source: Table 6 · p. 13, §A.1 · p. 13
- The appendix identifies the model-configuration and stage-specific training-settings tables, with the latter defining “constr. prefix” and S3 micro-batching.The S3 batch of 512 is processed in micro-batches of 256.Source: Table 7 · p. 13, Table 8 · p. 14
- Polar ruin selects a random customer as center, samples a destroy size from 4 to min(100, n), and removes customers with closest polar angles.Greedy inference uses one construction pass; RRC1000 uses the same policy for 1,000 reconstruction iterations, with destroy sizes from 4 to n.Source: §A.1 · p. 13
- For size generalization, the final S3 saving coefficient is selected separately by target size; the fixed-α ablation uses α = 100 at every size.Constraint Tightness uses one coefficient selected at C = 50 and fixed across target capacities.Source: §A.1 · p. 14
A.2 INFERENCE RUNTIME
The runtime appendix reports same-system inference measurements and an S3 anytime quality–compute trajectory. It cautions that LEHD RRC1000 timing was not valid for strict comparison.
A.2 INFERENCE RUNTIME
- Same-environment measurements use one RTX PRO 6000 system, with evaluation batch sizes of 1,000 for CVRP100 and 128 for CVRP200/500/1000.Timing is measured over each evaluation driver’s inference region after loading and before serialization, divided by evaluated instances.Source: §A.2 · p. 14
- S3 greedy inference is slower than LEHD on CVRP100 and CVRP200, nearly identical on CVRP500, and faster on CVRP1000.RRC1000 costs substantially more because it performs 1,000 destroy–repair iterations; the table reports absolute inference cost rather than a compute-matched comparison.Source: §A.2 · p. 14, Table 9 · p. 14
- LEHD RRC1000’s same-environment rerun did not reproduce published quality, so its timing is not used as a valid runtime comparison.Published LEHD RRC runtimes used different hardware and implementation conditions.Source: §A.2 · p. 14
- Figure 3 shows diminishing returns overall: substantial improvements arrive in the first 10–100 reconstruction iterations, while CVRP1000 continues improving markedly through 1,000.The trajectory uses ratio-of-means gap to LKH3 from saved incumbent costs; its x-axis is wall-clock time per instance on a logarithmic scale.Source: §A.2 · p. 15, Figure 3 · p. 15
B ADDITIONAL RESULTS
The additional results cover S3 target-size calibration and enhanced-inference results on standard CVRP.
B ADDITIONAL RESULTS
- Table 10 evaluates S3 target-size calibration with greedy inference using mean per-instance gap to LKH3 (%).Source: Table 10 · p. 15
- The calibration ablation compares sizes using the CVRP100-selected fixed α = 100.Source: Table 10 · p. 15
- Table 11 reports full enhanced-inference results on standard CVRP, including all reported RRC budgets for LEHD and MnLP, by mean per-instance gap to LKH3 (%).Source: Table 11 · p. 16