Neural Combinatorial Optimization for Real-World Routing

• URL: http://arxiv.org/abs/2503.16159v1
• Date: Thu, 20 Mar 2025 13:57:33 GMT
• Title: Neural Combinatorial Optimization for Real-World Routing
• Authors: Jiwoo Son, Zhikai Zhao, Federico Berto, Chuanbo Hua, Changhyun Kwon, Jinkyoo Park,
• Abstract summary: Vehicle Routing Problems (VRPs) are a class of NP-hard problems ubiquitous in several real-world logistics scenarios.<n>NCO has emerged as a promising alternative to classical approaches to solve VRPs.<n>This work introduces RRNCO (Real Routing NCO) to bridge the gap of NCO between synthetic and real-world VRPs.
• Score: 15.136899433821894
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Vehicle Routing Problems (VRPs) are a class of NP-hard problems ubiquitous in several real-world logistics scenarios that pose significant challenges for optimization. Neural Combinatorial Optimization (NCO) has emerged as a promising alternative to classical approaches, as it can learn fast heuristics to solve VRPs. However, most research works in NCO for VRPs focus on simplified settings, which do not account for asymmetric distances and travel durations that cannot be derived by simple Euclidean distances and unrealistic data distributions, hindering real-world deployment. This work introduces RRNCO (Real Routing NCO) to bridge the gap of NCO between synthetic and real-world VRPs in the critical aspects of both data and modeling. First, we introduce a new, openly available dataset with real-world data containing a diverse dataset of locations, distances, and duration matrices from 100 cities, considering realistic settings with actual routing distances and durations obtained from Open Source Routing Machine (OSRM). Second, we propose a novel approach that efficiently processes both node and edge features through contextual gating, enabling the construction of more informed node embedding, and we finally incorporate an Adaptation Attention Free Module (AAFM) with neural adaptive bias mechanisms that effectively integrates not only distance matrices but also angular relationships between nodes, allowing our model to capture rich structural information. RRNCO achieves state-of-the-art results in real-world VRPs among NCO methods. We make our dataset and code publicly available at https://github.com/ai4co/real-routing-nco.

Related papers

• Dataless Neural Networks for Resource-Constrained Project Scheduling [0.0]
  This paper presents the first dataless neural network approach for the Resource-Constrained Project Scheduling Problem (RCPSP)<n>We provide a complete mathematical framework that transforms discrete scheduling constraints into differentiable objectives suitable for gradient-based optimization.<n>We detail the mathematical formulation for both precedence and renewable resource constraints, including a memory-efficient dense time-grid representation.
  arXiv  Detail & Related papers  (2025-07-07T15:59:57Z)
• Private Training & Data Generation by Clustering Embeddings [74.00687214400021]
  Differential privacy (DP) provides a robust framework for protecting individual data.<n>We introduce a novel principled method for DP synthetic image embedding generation.<n> Empirically, a simple two-layer neural network trained on synthetically generated embeddings achieves state-of-the-art (SOTA) classification accuracy.
  arXiv  Detail & Related papers  (2025-06-20T00:17:14Z)
• EFormer: An Effective Edge-based Transformer for Vehicle Routing Problems [25.234292937274212]
  We introduce EFormer, an Edge-based Transformer model that uses edge as the sole input for VRPs.<n>Our approach employs a precoder module with a mixed-score attention mechanism to convert edge information into temporary node embeddings.<n>EFormer outperforms established baselines on synthetic datasets.
  arXiv  Detail & Related papers  (2025-06-19T16:07:11Z)
• OCMG-Net: Neural Oriented Normal Refinement for Unstructured Point Clouds [18.234146052486054]
  We present a robust refinement method for estimating oriented normals from unstructured point clouds. Our framework incorporates sign orientation and data augmentation in the feature space to refine the initial oriented normals. To address the issue of noise-caused direction inconsistency existing in previous approaches, we introduce a new metric called the Chamfer Normal Distance.
  arXiv  Detail & Related papers  (2024-09-02T09:30:02Z)
• A simple algorithm for output range analysis for deep neural networks [0.0]
  This paper presents a novel approach for the output range estimation problem in Deep Neural Networks (DNNs) by integrating a Simulated Annealing (SA) algorithm.<n>The method effectively addresses the challenges by the lack of geometric information and non-linearity inherent inResNets.
  arXiv  Detail & Related papers  (2024-07-02T22:47:40Z)
• RouteFinder: Towards Foundation Models for Vehicle Routing Problems [21.3310292139361]
  RouteFinder is a comprehensive foundation model framework to tackle different Vehicle Routing Problem (VRP) variants.<n>We propose a unified VRP environment capable of efficiently handling any attribute combination.<n>Experiments on 48 VRP variants show RouteFinder outperforms recent state-of-the-art learning methods.
  arXiv  Detail & Related papers  (2024-06-21T09:34:26Z)
• Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalization [18.298695520665348]
  Vehicle routing problems (VRPs) can be found in numerous real-world applications. In this work, we make the first attempt to tackle the crucial challenge of cross-problem generalization. Our proposed model can successfully solve VRPs with unseen attribute combinations in a zero-shot generalization manner.
  arXiv  Detail & Related papers  (2024-02-23T13:25:23Z)
• Universal Neural Optimal Transport [0.0]
  UNOT (Universal Neural Optimal Transport) is a novel framework capable of accurately predicting (entropic) OT distances and plans. We show that our network not only accurately predicts optimal transport distances and plans across a wide range of datasets, but also captures the geometry of the Wasserstein space correctly.
  arXiv  Detail & Related papers  (2022-11-30T21:56:09Z)
• On the Effective Usage of Priors in RSS-based Localization [56.68864078417909]
  We propose a Received Signal Strength (RSS) fingerprint and convolutional neural network-based algorithm, LocUNet. In this paper, we study the localization problem in dense urban settings. We first recognize LocUNet's ability to learn the underlying prior distribution of the Rx position or Rx and transmitter (Tx) association preferences from the training data, and attribute its high performance to these.
  arXiv  Detail & Related papers  (2022-11-28T00:31:02Z)
• Neural Attentive Circuits [93.95502541529115]
  We introduce a general purpose, yet modular neural architecture called Neural Attentive Circuits (NACs) NACs learn the parameterization and a sparse connectivity of neural modules without using domain knowledge. NACs achieve an 8x speedup at inference time while losing less than 3% performance.
  arXiv  Detail & Related papers  (2022-10-14T18:00:07Z)
• An optimised deep spiking neural network architecture without gradients [7.183775638408429]
  We present an end-to-end trainable modular event-driven neural architecture that uses local synaptic and threshold adaptation rules. The architecture represents a highly abstracted model of existing Spiking Neural Network (SNN) architectures.
  arXiv  Detail & Related papers  (2021-09-27T05:59:12Z)
• Clustered Federated Learning via Generalized Total Variation Minimization [83.26141667853057]
  We study optimization methods to train local (or personalized) models for local datasets with a decentralized network structure. Our main conceptual contribution is to formulate federated learning as total variation minimization (GTV) Our main algorithmic contribution is a fully decentralized federated learning algorithm.
  arXiv  Detail & Related papers  (2021-05-26T18:07:19Z)
• Learning to Continuously Optimize Wireless Resource in a Dynamic Environment: A Bilevel Optimization Perspective [52.497514255040514]
  This work develops a new approach that enables data-driven methods to continuously learn and optimize resource allocation strategies in a dynamic environment. We propose to build the notion of continual learning into wireless system design, so that the learning model can incrementally adapt to the new episodes. Our design is based on a novel bilevel optimization formulation which ensures certain fairness" across different data samples.
  arXiv  Detail & Related papers  (2021-05-03T07:23:39Z)
• ePointDA: An End-to-End Simulation-to-Real Domain Adaptation Framework for LiDAR Point Cloud Segmentation [111.56730703473411]
  Training deep neural networks (DNNs) on LiDAR data requires large-scale point-wise annotations. Simulation-to-real domain adaptation (SRDA) trains a DNN using unlimited synthetic data with automatically generated labels. ePointDA consists of three modules: self-supervised dropout noise rendering, statistics-invariant and spatially-adaptive feature alignment, and transferable segmentation learning.
  arXiv  Detail & Related papers  (2020-09-07T23:46:08Z)
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data [59.50904660420082]
  Federated Learning (FL) has become a popular paradigm for learning from distributed data. To effectively utilize data at different devices without moving them to the cloud, algorithms such as the Federated Averaging (FedAvg) have adopted a "computation then aggregation" (CTA) model.
  arXiv  Detail & Related papers  (2020-05-22T23:07:42Z)

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.