Efficient Neural Combinatorial Optimization Solver for the Min-max Heterogeneous Capacitated Vehicle Routing Problem

• URL: http://arxiv.org/abs/2507.21386v1
• Date: Mon, 28 Jul 2025 23:38:33 GMT
• Title: Efficient Neural Combinatorial Optimization Solver for the Min-max Heterogeneous Capacitated Vehicle Routing Problem
• Authors: Xuan Wu, Di Wang, Chunguo Wu, Kaifang Qi, Chunyan Miao, Yubin Xiao, Jian Zhang, You Zhou,
• Abstract summary: Existing NCO solvers typically select a vehicle and its next node to visit at each decoding step, but often make myopic decoding decisions and overlook key properties of MMHCVRP.<n>To better address these limitations, we propose ECHO, an efficient NCO solver.<n>ECHO outperforms state-of-the-art NCO solvers across varying numbers of vehicles and nodes, and exhibits well-performing generalization across both scales and distribution patterns.
• Score: 44.53289422887474
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Numerous Neural Combinatorial Optimization (NCO) solvers have been proposed to address Vehicle Routing Problems (VRPs). However, most of these solvers focus exclusively on single-vehicle VRP variants, overlooking the more realistic min-max Heterogeneous Capacitated Vehicle Routing Problem (MMHCVRP), which involves multiple vehicles. Existing MMHCVRP solvers typically select a vehicle and its next node to visit at each decoding step, but often make myopic decoding decisions and overlook key properties of MMHCVRP, including local topological relationships, vehicle permutation invariance, and node symmetry, resulting in suboptimal performance. To better address these limitations, we propose ECHO, an efficient NCO solver. First, ECHO exploits the proposed dual-modality node encoder to capture local topological relationships among nodes. Subsequently, to mitigate myopic decisions, ECHO employs the proposed Parameter-Free Cross-Attention mechanism to prioritize the vehicle selected in the preceding decoding step. Finally, leveraging vehicle permutation invariance and node symmetry, we introduce a tailored data augment strategy for MMHCVRP to stabilize the Reinforcement Learning training process. To assess the performance of ECHO, we conduct extensive experiments. The experimental results demonstrate that ECHO outperforms state-of-the-art NCO solvers across varying numbers of vehicles and nodes, and exhibits well-performing generalization across both scales and distribution patterns. Finally, ablation studies validate the effectiveness of all proposed methods.

Related papers

• 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)
• Multiobjective Vehicle Routing Optimization with Time Windows: A Hybrid Approach Using Deep Reinforcement Learning and NSGA-II [52.083337333478674]
  This paper proposes a weight-aware deep reinforcement learning (WADRL) approach designed to address the multiobjective vehicle routing problem with time windows (MOVRPTW) The Non-dominated sorting genetic algorithm-II (NSGA-II) method is then employed to optimize the outcomes produced by the WADRL.
  arXiv  Detail & Related papers  (2024-07-18T02:46:06Z)
• DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems [26.48767051423456]
  We present a novel attention-based Partition-and-Navigation encoder (P&N) that learns distinct embeddings for partition and navigation. We develop an effective agent-permutation-symmetric (APS) loss function.
  arXiv  Detail & Related papers  (2024-05-27T15:33:16Z)
• 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)
• A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical Computation Offloading [62.34538208323411]
  We propose a multi-head ensemble multi-task learning (MEMTL) approach with a shared backbone and multiple prediction heads (PHs) MEMTL outperforms benchmark methods in both the inference accuracy and mean square error without requiring additional training data.
  arXiv  Detail & Related papers  (2023-09-02T11:01:16Z)
• A Feasibility-Preserved Quantum Approximate Solver for the Capacitated Vehicle Routing Problem [3.0567007573383678]
  The Capacitated Vehicle Routing Problem (CVRP) is an NP-optimization problem (NPO) that arises in various fields including transportation and logistics. We present a new binary encoding for the CVRP, with an objective function of minimizing the shortest path that bypasses the vehicle capacity constraint of the CVRP. We discuss the effectiveness of the proposed encoding under the framework of the variant of the Quantum Alternating Operator Ansatz.
  arXiv  Detail & Related papers  (2023-08-17T05:14:43Z)
• Greedy based Value Representation for Optimal Coordination in Multi-agent Reinforcement Learning [64.05646120624287]
  We derive the expression of the joint Q value function of LVD and MVD. To ensure optimal consistency, the optimal node is required to be the unique STN. Our method outperforms state-of-the-art baselines in experiments on various benchmarks.
  arXiv  Detail & Related papers  (2022-11-22T08:14:50Z)
• 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)
• RoMA: Robust Model Adaptation for Offline Model-based Optimization [115.02677045518692]
  We consider the problem of searching an input maximizing a black-box objective function given a static dataset of input-output queries. A popular approach to solving this problem is maintaining a proxy model that approximates the true objective function. Here, the main challenge is how to avoid adversarially optimized inputs during the search.
  arXiv  Detail & Related papers  (2021-10-27T05:37:12Z)
• Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem [13.389057146418056]
  Vehicles in real-world scenarios are likely to be heterogeneous with different characteristics that affect their capacity (or travel speed) We propose a DRL method based on the attention mechanism with a vehicle selection decoder accounting for the heterogeneous fleet constraint and a node selection decoder accounting for the route construction, which learns to construct a solution by automatically selecting both a vehicle and a node for this vehicle at each step.
  arXiv  Detail & Related papers  (2021-10-06T10:05:19Z)

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.