HRC: A Hybrid Reconstruction Framework for Neural Combinatorial Optimization Solvers

Recent studies have proposed post-processing strategies that iteratively reconstruct a partial segment of current solutions using Neural Combinatorial Optimization (NCO) solvers, thereby improving their performance on large-scale Vehicle Routing Problem (VRP) instances. However, the reconstruction subproblem is essentially a Shortest Hamiltonian Path Problem (SHPP) instance, which differs fundamentally from the original VRP variant on which the solver is trained. Consequently, the NCO solver may suffer from performance degradation during reconstruction due to limited generalization across problem variants. Moreover, relying solely on the solver may be insufficient to effectively identify and correct complex intersections or suboptimal topological structures. To address these limitations, we propose a post-processing strategy termed Hybrid Reconstruction Framework (HRC). Specifically, HRC first fine-tunes the NCO solver on SHPP instances and then exploits the enhanced solver to perform large-neighborhood random reconstruction. Subsequently, HRC conducts small-neighborhood reconstruction using 2-opt and kNN-DGR. The experimental results on both synthetic and real-world Traveling Salesman Problem and Capacitated Vehicle Routing Problem instances demonstrate that HRC substantially improves the performance of two representative NCO solvers on large-scale instances and achieves better overall performance than the state-of-the-art reconstruction strategy. Finally, ablation studies further validate the effectiveness of all proposed designs.