- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes a multi-segment merging strategy for the Capacitated Vehicle Routing Problem (CVRP). Starting from single-customer segments, the approach iteratively selects pairs of endpoints—from among all capacity-feasible options—to merge, based on the current state of the segments and Clarke–Wright (CW) savings values. Each segment is treated as a complete route implicitly connected to the depot, eliminating the need for explicit decisions regarding when to return to the depot. The authors employ a combination of staged supervised learning and reinforcement learning, utilizing the same strategy for both initial construction and the reconstruction phase following a "destruction" step. Experiments cover various problem scales and capacities; the method achieves strong results in greedy inference for CVRP100–500 and demonstrates cross-capacity generalization on CVRP100, though its greedy performance on CVRP1000 still lags behind that of LEHD.
Critical strengths
- The same strategy can be applied both to initial construction (starting from single-customer segments) and to reconstruction (starting from existing segments), offering practical reusability.
- The reconstruction results (Table 2) and cross-capacity generalization results (Table 5) support the overall effectiveness of the method—notably, the model remains adaptable to different test settings even when trained exclusively on CVRP100 instances with a capacity of 50.
Critical weaknesses
- The experiments are limited to CVRP, and the performance advantage under matched computational budgets remains unclear.
- While the traditional CW comparison in Table 5 and the early-training ablation in Table 4 provide relevant evidence, they do not isolate the independent contributions of "freely selecting segment pairs" and "CW signals" to the final model. A controlled comparison is still missing: conducted within the same neural framework and using an identical, complete training pipeline.
Questions for authors
- In NLNS, reinforcement learning is used to determine where a designated endpoint should be connected, based on current segment endpoints and total demand. While this paper differs mainly by allowing the free selection of endpoint pairs and employing implicit depot closure, it does not discuss or compare against this directly related work.
- Is it possible to compare the performance of "extending one segment at a time" versus "freely selecting segment pairs," while keeping the backbone architecture, training data, CW signals, and training budget constant?
- Following full S0–S3 training, could you compare the results across three scenarios: (a) retaining the CW signals, (b) excluding the CW signals during training, and (c) removing the CW signals only during inference?
[1]: Hottung, A., & Tierney, K. Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem. ECAI 2020.