NCO4CVRP: Neural Combinatorial Optimization for the Capacitated Vehicle Routing Problem

• URL: http://arxiv.org/abs/2604.16581v1
• Date: Fri, 17 Apr 2026 14:28:50 GMT
• Title: NCO4CVRP: Neural Combinatorial Optimization for the Capacitated Vehicle Routing Problem
• Abstract summary: This work focuses on improving existing inference techniques to enhance solution quality and generalization.<n>By refining inference techniques and leveraging enhanced search strategies, our work contributes to the broader applicability of NCO models in real-world optimization tasks.
• Score: 0.23560550919269374
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Neural Combinatorial Optimization (NCO) has emerged as a powerful framework for solving combinatorial optimization problems by integrating deep learning-based models. This work focuses on improving existing inference techniques to enhance solution quality and generalization. Specifically, we modify the Random Re-Construct (RRC) approach of the Light Encoder Heavy Decoder (LEHD) model by incorporating Simulated Annealing (SA). Unlike the conventional RRC, which greedily replaces suboptimal segments, our SA-based modification introduces a probabilistic acceptance mechanism that allows the model to escape local optima and explore a more diverse solution space. Additionally, we enhance the Policy Optimization with Multiple Optima (POMO) approach by integrating Beam Search, enabling systematic exploration of multiple promising solutions while maintaining diversity in the search space. We further investigate different inference strategies, including Softmax Sampling, Greedy, Gumbel-Softmax, and Epsilon-Greedy, analyzing their impact on solution quality. Furthermore, we explore instance augmentation techniques, such as horizontal and vertical flipping and rotation-based augmentations, to improve model generalization across different CVRP instances. Our extensive experiments demonstrate that these modifications significantly reduce the optimality gap across various Capacitated Vehicle Routing Problem (CVRP) benchmarks, with Beam Search and SA-based RRC consistently yielding superior performance. By refining inference techniques and leveraging enhanced search strategies, our work contributes to the broader applicability of NCO models in real-world combinatorial optimization tasks.

Related papers

• New Hybrid Fine-Tuning Paradigm for LLMs: Algorithm Design and Convergence Analysis Framework [52.69678300445233]
  Fine-tuning Large Language Models (LLMs) typically involves either full fine-tuning, which updates all model parameters, or.<n>Efficient Fine-Tuning (PEFT) adjusts a small subset of parameters.<n>We propose a novel hybrid fine-tuning approach that jointly updates both LLMs and PEFT modules using a combination of zeroth-order and first-order optimization methods.
  arXiv  Detail & Related papers  (2026-04-10T22:39:38Z)
• Hybrid Node-Destroyer Model with Large Neighborhood Search for Solving the Capacitated Vehicle Routing Problem [1.9573380763700716]
  We propose an iterative learning hybrid optimization solver to strengthen the performance of metaheuristic algorithms.<n>The proposed approach reduces operational complexity and scales down the search space involved in the optimization process.
  arXiv  Detail & Related papers  (2025-08-12T05:56:13Z)
• Preference-Driven Multi-Objective Combinatorial Optimization with Conditional Computation [10.153136816705542]
  POCCO is a novel plug-and-play framework that enables adaptive selection of model structures for subproblems.<n>We propose a preference-driven optimization algorithm that learns pairwise preferences between winning and losing solutions.
  arXiv  Detail & Related papers  (2025-06-10T15:25:06Z)
• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  Reinforcement Learning (RL) has emerged as a powerful tool for neural optimization, enabling models learns that solve complex problems without requiring expert knowledge.<n>Despite significant progress, existing RL approaches face challenges such as diminishing reward signals and inefficient exploration in vast action spaces.<n>We propose Preference Optimization, a novel method that transforms quantitative reward signals into qualitative preference signals via statistical comparison modeling.
  arXiv  Detail & Related papers  (2025-05-13T16:47:00Z)
• RL-finetuning LLMs from on- and off-policy data with a single algorithm [53.70731390624718]
  We introduce a novel reinforcement learning algorithm (AGRO) for fine-tuning large-language models.<n>AGRO leverages the concept of generation consistency, which states that the optimal policy satisfies the notion of consistency across any possible generation of the model.<n>We derive algorithms that find optimal solutions via the sample-based policy gradient and provide theoretical guarantees on their convergence.
  arXiv  Detail & Related papers  (2025-03-25T12:52:38Z)
• Diversity Optimization for Travelling Salesman Problem via Deep Reinforcement Learning [29.551883712536295]
  Existing neural methods for the Travelling Salesman Problem (TSP) mostly aim at finding a single optimal solution.<n>We propose a novel deep reinforcement learning based neural solver, which is primarily featured by an encoder-decoder structured policy.
  arXiv  Detail & Related papers  (2025-01-01T16:08:40Z)
• 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)
• Ensemble Kalman Filtering Meets Gaussian Process SSM for Non-Mean-Field and Online Inference [47.460898983429374]
  We introduce an ensemble Kalman filter (EnKF) into the non-mean-field (NMF) variational inference framework to approximate the posterior distribution of the latent states. This novel marriage between EnKF and GPSSM not only eliminates the need for extensive parameterization in learning variational distributions, but also enables an interpretable, closed-form approximation of the evidence lower bound (ELBO) We demonstrate that the resulting EnKF-aided online algorithm embodies a principled objective function by ensuring data-fitting accuracy while incorporating model regularizations to mitigate overfitting.
  arXiv  Detail & Related papers  (2023-12-10T15:22:30Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver. This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
  arXiv  Detail & Related papers  (2023-01-28T01:50:42Z)
• An Empirical Evaluation of Zeroth-Order Optimization Methods on AI-driven Molecule Optimization [78.36413169647408]
  We study the effectiveness of various ZO optimization methods for optimizing molecular objectives. We show the advantages of ZO sign-based gradient descent (ZO-signGD) We demonstrate the potential effectiveness of ZO optimization methods on widely used benchmark tasks from the Guacamol suite.
  arXiv  Detail & Related papers  (2022-10-27T01:58:10Z)
• Multi-Agent Deep Reinforcement Learning in Vehicular OCC [14.685237010856953]
  We introduce a spectral efficiency optimization approach in vehicular OCC. We model the optimization problem as a Markov decision process (MDP) to enable the use of solutions that can be applied online. We verify the performance of our proposed scheme through extensive simulations and compare it with various variants of our approach and a random method.
  arXiv  Detail & Related papers  (2022-05-05T14:25:54Z)
• Optimization-Inspired Learning with Architecture Augmentations and Control Mechanisms for Low-Level Vision [74.9260745577362]
  This paper proposes a unified optimization-inspired learning framework to aggregate Generative, Discriminative, and Corrective (GDC) principles. We construct three propagative modules to effectively solve the optimization models with flexible combinations. Experiments across varied low-level vision tasks validate the efficacy and adaptability of GDC.
  arXiv  Detail & Related papers  (2020-12-10T03:24:53Z)

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.