Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning

• URL: http://arxiv.org/abs/2506.02392v1
• Date: Tue, 03 Jun 2025 03:15:22 GMT
• Title: Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning
• Authors: Yuanyao Chen, Rongsheng Chen, Fu Luo, Zhenkun Wang,
• Abstract summary: We introduce a novel learning framework driven by Large Language Models (LLMs)<n>Unlike prevailing techniques that necessitate joint training with the neural network, our approach operates exclusively during the inference phase.<n>Our method enables a backbone model (trained on 100-node instances) to achieve superior performance on large-scale Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) of up to 100K nodes from diverse distributions.
• Score: 3.0711362702464684
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Neural Combinatorial Optimization (NCO) has emerged as a promising learning-based paradigm for addressing Vehicle Routing Problems (VRPs) by minimizing the need for extensive manual engineering. While existing NCO methods, trained on small-scale instances (e.g., 100 nodes), have demonstrated considerable success on problems of similar scale, their performance significantly degrades when applied to large-scale scenarios. This degradation arises from the distributional shift between training and testing data, rendering policies learned on small instances ineffective for larger problems. To overcome this limitation, we introduce a novel learning framework driven by Large Language Models (LLMs). This framework learns a projection between the training and testing distributions, which is then deployed to enhance the scalability of the NCO model. Notably, unlike prevailing techniques that necessitate joint training with the neural network, our approach operates exclusively during the inference phase, obviating the need for model retraining. Extensive experiments demonstrate that our method enables a backbone model (trained on 100-node instances) to achieve superior performance on large-scale Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) of up to 100K nodes from diverse distributions.

Related papers

• Learning to Reduce Search Space for Generalizable Neural Routing Solver [12.396576646539252]
  Constructive neural optimization (NCO) has attracted growing research attention due to its ability to solve complex routing problems without relying on handcrafted rules.<n>Existing NCO methods face challenges in generalizing to large-scale problems due to high computational complexity and inefficient capture of structural patterns.<n>We propose a novel learning-based search space reduction method that adaptively selects a small set of promising candidate nodes at each step of the constructive NCO process.
  arXiv  Detail & Related papers  (2025-03-05T03:25:09Z)
• Preventing Local Pitfalls in Vector Quantization via Optimal Transport [77.15924044466976]
  We introduce OptVQ, a novel vector quantization method that employs the Sinkhorn algorithm to optimize the optimal transport problem.<n>Our experiments on image reconstruction tasks demonstrate that OptVQ achieves 100% codebook utilization and surpasses current state-of-the-art VQNs in reconstruction quality.
  arXiv  Detail & Related papers  (2024-12-19T18:58:14Z)
• Prompt Learning for Generalized Vehicle Routing [17.424910810870273]
  This work investigates an efficient prompt learning approach in Neural optimization for cross-distribution adaptation. The proposed model learns a set of prompts among various distributions and then selects the best-matched one to prompt a pre-trained attention model for each problem instance. It also outperforms existing generalized models on both in-distribution prediction and zero-shot generalization to a diverse set of new tasks.
  arXiv  Detail & Related papers  (2024-05-20T15:42:23Z)
• Instance-Conditioned Adaptation for Large-scale Generalization of Neural Routing Solver [15.842155380912002]
  We propose a novel Instance-Conditioned Adaptation Model (ICAM) for better large-scale generalization of neural routing solvers.<n>We show that our proposed method is capable of obtaining promising results with a very fast inference time.
  arXiv  Detail & Related papers  (2024-05-03T08:00:19Z)
• Self-Improved Learning for Scalable Neural Combinatorial Optimization [15.842155380912002]
  This work proposes a novel Self-Improved Learning (SIL) method for better scalability of neural optimization. We develop an efficient self-improved mechanism that enables direct model training on large-scale problem instances without any labeled data. In addition, we design a linear attention complexity mechanism for the computation model to efficiently handle large-scale problem instances with low overhead.
  arXiv  Detail & Related papers  (2024-03-28T16:46:53Z)
• Auto-Train-Once: Controller Network Guided Automatic Network Pruning from Scratch [72.26822499434446]
  Auto-Train-Once (ATO) is an innovative network pruning algorithm designed to automatically reduce the computational and storage costs of DNNs. We provide a comprehensive convergence analysis as well as extensive experiments, and the results show that our approach achieves state-of-the-art performance across various model architectures.
  arXiv  Detail & Related papers  (2024-03-21T02:33:37Z)
• Towards a Better Theoretical Understanding of Independent Subnetwork Training [56.24689348875711]
  We take a closer theoretical look at Independent Subnetwork Training (IST) IST is a recently proposed and highly effective technique for solving the aforementioned problems. We identify fundamental differences between IST and alternative approaches, such as distributed methods with compressed communication.
  arXiv  Detail & Related papers  (2023-06-28T18:14:22Z)
• Solving Large-scale Spatial Problems with Convolutional Neural Networks [88.31876586547848]
  We employ transfer learning to improve training efficiency for large-scale spatial problems. We propose that a convolutional neural network (CNN) can be trained on small windows of signals, but evaluated on arbitrarily large signals with little to no performance degradation.
  arXiv  Detail & Related papers  (2023-06-14T01:24:42Z)
• Towards Omni-generalizable Neural Methods for Vehicle Routing Problems [14.210085924625705]
  This paper studies a challenging yet realistic setting, which considers generalization across both size and distribution in VRPs. We propose a generic meta-learning framework, which enables effective training of an model with the capability of fast adaptation to new tasks during inference.
  arXiv  Detail & Related papers  (2023-05-31T06:14:34Z)
• Unifying Synergies between Self-supervised Learning and Dynamic Computation [53.66628188936682]
  We present a novel perspective on the interplay between SSL and DC paradigms. We show that it is feasible to simultaneously learn a dense and gated sub-network from scratch in a SSL setting. The co-evolution during pre-training of both dense and gated encoder offers a good accuracy-efficiency trade-off.
  arXiv  Detail & Related papers  (2023-01-22T17:12:58Z)
• Extrapolation for Large-batch Training in Deep Learning [72.61259487233214]
  We show that a host of variations can be covered in a unified framework that we propose. We prove the convergence of this novel scheme and rigorously evaluate its empirical performance on ResNet, LSTM, and Transformer.
  arXiv  Detail & Related papers  (2020-06-10T08:22:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.