GELD: A Unified Neural Model for Efficiently Solving Traveling Salesman Problems Across Different Scales

• URL: http://arxiv.org/abs/2506.06634v1
• Date: Sat, 07 Jun 2025 03:00:05 GMT
• Title: GELD: A Unified Neural Model for Efficiently Solving Traveling Salesman Problems Across Different Scales
• Authors: Yubin Xiao, Di Wang, Rui Cao, Xuan Wu, Boyang Li, You Zhou,
• Abstract summary: We introduce a novel neural network-based solver named GELD to solve the Traveling Salesman Problem.<n>GELD integrates a lightweight Global-view inference (GE) with a heavyweight Local-view Decoder (LD) to enrich embedding representation.<n>Extensive experiments conducted on both synthetic and real-world datasets demonstrate that GELD outperforms seven state-of-the-art models.
• Score: 16.177833864654172
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Traveling Salesman Problem (TSP) is a well-known combinatorial optimization problem with broad real-world applications. Recent advancements in neural network-based TSP solvers have shown promising results. Nonetheless, these models often struggle to efficiently solve both small- and large-scale TSPs using the same set of pre-trained model parameters, limiting their practical utility. To address this issue, we introduce a novel neural TSP solver named GELD, built upon our proposed broad global assessment and refined local selection framework. Specifically, GELD integrates a lightweight Global-view Encoder (GE) with a heavyweight Local-view Decoder (LD) to enrich embedding representation while accelerating the decision-making process. Moreover, GE incorporates a novel low-complexity attention mechanism, allowing GELD to achieve low inference latency and scalability to larger-scale TSPs. Additionally, we propose a two-stage training strategy that utilizes training instances of different sizes to bolster GELD's generalization ability. Extensive experiments conducted on both synthetic and real-world datasets demonstrate that GELD outperforms seven state-of-the-art models considering both solution quality and inference speed. Furthermore, GELD can be employed as a post-processing method to significantly elevate the quality of the solutions derived by existing neural TSP solvers via spending affordable additional computing time. Notably, GELD is shown as capable of solving TSPs with up to 744,710 nodes, first-of-its-kind to solve this large size TSP without relying on divide-and-conquer strategies to the best of our knowledge.

Related papers

• LocalEscaper: A Weakly-supervised Framework with Regional Reconstruction for Scalable Neural TSP Solvers [14.238953745477193]
  LocalEscaper is a weakly-supervised learning framework for large-scale Traveling Salesman Problem (TSP)<n>It effectively combines the advantages of both SL and RL, enabling effective training on datasets with low-quality labels.<n>It sets a new benchmark for scalability and efficiency, solving TSP instances with up to 50,000 cities.
  arXiv  Detail & Related papers  (2025-02-18T03:10:27Z)
• Cascaded Large-Scale TSP Solving with Unified Neural Guidance: Bridging Local and Population-based Search [23.528483405321975]
  UNiCS is a novel unified neural-guided cascaded solver for the traveling salesman problem.<n>It consistently outperforms state-of-the-art methods, with its runtime advantage consistent across various budgets.
  arXiv  Detail & Related papers  (2025-01-24T06:56:27Z)
• 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)
• 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)
• GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time [17.450373393248984]
  GLOP is a unified hierarchical framework that efficiently scales toward large-scale routing problems. For the first time, we hybridize non-autoregressive neurals for coarse-grained problem partitions and autoregressive neurals for fine-grained route constructions. Experiments show that GLOP achieves competitive and state-of-the-art real-time performance on large-scale routing problems.
  arXiv  Detail & Related papers  (2023-12-13T15:46:58Z)
• LD-GAN: Low-Dimensional Generative Adversarial Network for Spectral Image Generation with Variance Regularization [72.4394510913927]
  Deep learning methods are state-of-the-art for spectral image (SI) computational tasks. GANs enable diverse augmentation by learning and sampling from the data distribution. GAN-based SI generation is challenging since the high-dimensionality nature of this kind of data hinders the convergence of the GAN training yielding to suboptimal generation. We propose a statistical regularization to control the low-dimensional representation variance for the autoencoder training and to achieve high diversity of samples generated with the GAN.
  arXiv  Detail & Related papers  (2023-04-29T00:25:02Z)
• Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem [67.32731657297377]
  Traveling Salesman Problem (TSP) is a classic routing optimization problem originally arising in the domain of transportation and logistics. Recently, Deep Reinforcement Learning has been increasingly employed to solve TSP due to its high inference efficiency. We propose a novel end-to-end DRL approach, referred to as Pointerformer, based on multi-pointer Transformer.
  arXiv  Detail & Related papers  (2023-04-19T03:48:32Z)
• Iterative Soft Shrinkage Learning for Efficient Image Super-Resolution [91.3781512926942]
  Image super-resolution (SR) has witnessed extensive neural network designs from CNN to transformer architectures. This work investigates the potential of network pruning for super-resolution iteration to take advantage of off-the-shelf network designs and reduce the underlying computational overhead. We propose a novel Iterative Soft Shrinkage-Percentage (ISS-P) method by optimizing the sparse structure of a randomly network at each and tweaking unimportant weights with a small amount proportional to the magnitude scale on-the-fly.
  arXiv  Detail & Related papers  (2023-03-16T21:06:13Z)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  We propose a novel Reinforcement Learning (RL) approach to design generic Congestion Control (CC) algorithms. Our solution, MARLIN, uses the Soft Actor-Critic algorithm to maximize both entropy and return. We trained MARLIN on a real network with varying background traffic patterns to overcome the sim-to-real mismatch.
  arXiv  Detail & Related papers  (2023-02-02T18:27:20Z)
• Resource Allocation via Model-Free Deep Learning in Free Space Optical Communications [119.81868223344173]
  The paper investigates the general problem of resource allocation for mitigating channel fading effects in Free Space Optical (FSO) communications. Under this framework, we propose two algorithms that solve FSO resource allocation problems.
  arXiv  Detail & Related papers  (2020-07-27T17:38:51Z)
• Model-Driven Beamforming Neural Networks [47.754731555563836]
  This article introduces general data- and model-driven beamforming neural networks (BNNs) It presents various possible learning strategies, and also discusses complexity reduction for the DL-based BNNs. We also offer enhancement methods such as training-set augmentation and transfer learning in order to improve the generality of BNNs.
  arXiv  Detail & Related papers  (2020-01-15T12:50:09Z)

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.