GeoRouteNet: Geometry-Enhanced Non-Autoregressive Neural Solver for the Traveling Salesman Problem

• URL: http://arxiv.org/abs/2606.22776v1
• Date: Mon, 22 Jun 2026 02:31:22 GMT
• Title: GeoRouteNet: Geometry-Enhanced Non-Autoregressive Neural Solver for the Traveling Salesman Problem
• Abstract summary: GeoRouteNet is a geometry-enhanced neural solver for Euclidean traveling salesman problem (TSP)<n>On the model side, GeoRouteNet incorporates centered node features, learnable radial distance basis functions, distance-aware graph attention, LayerNorm-SwiGLU feed-forward blocks, and cross-layer attentive residual encoder mixing.<n>On the training side, we design multi-candidate self-comparison reinforcement learning (MCS-RL), which samples multiple candidate tours per instance.
• Score: 5.202950948929751
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The traveling salesman problem (TSP) is a canonical NP-hard combinatorial optimization benchmark that tests the representational capacity and generalization of neural solvers. While non-autoregressive (NAR) approaches offer parallel inference, they often lack sufficient geometric inductive bias and stable training signals, leading to degraded performance under cross-scale and cross-distribution shifts. We propose GeoRouteNet, a geometry-enhanced NAR neural solver for Euclidean TSP. On the model side, GeoRouteNet incorporates centered node features, learnable radial distance basis functions, distance-aware graph attention with explicit edge messaging, LayerNorm-SwiGLU feed-forward blocks, and cross-layer attentive residual mixing. On the training side, we design multi-candidate self-comparison reinforcement learning (MCS-RL), which samples multiple candidate tours per instance, constructs adaptive baselines from greedy and peer candidates, and adds winner-candidate guidance with annealed entropy regularization. On 10,000 random TSP50 instances, GeoRouteNet achieves a 0.32% optimality gap under Beam-1000 decoding. On TSP100, the gap is 1.26%. On 27 stratified TSPLIB EUC_2D instances, the overall gap drops from 17.12% (NAR4TSP reproduction) to 3.60%, while batch inference throughput substantially exceeds that of Concorde and LKH3. Ablation studies confirm that geometric structure enhancement and multi-candidate training are complementary: structure improvements dominate cross-distribution gains, while MCS-RL further stabilizes solution quality when paired with a strong geometric encoder.

Related papers

• GeoSPRINT: Geometric Redundancy-Aware Step Pruning for Inference in Diffusion Trajectories [0.0]
  Diffusion models achieve high sample quality but remain expensive at inference time because sampling requires many neural function evaluations (NFEs)<n>We introduce GeoPRINT, a training-free framework for constructing non-uniform sampling schedules from the geometry of denoising trajectories.<n>GeoSPRINT consistently improves over uniform DDIM (Denoising Diffusion Implicit Models) schedules at matched NFE budgets.
  arXiv  Detail & Related papers  (2026-09-02T06:22:04Z)
• Geometric Self-Supervised Pre-training for Neural Combinatorial Optimization [40.74618635552097]
  We propose a geometric self-supervised pre-training framework for routing graphs.<n>The framework learns robust structural representations prior to the policy optimization phase.<n>The proposed model exhibits remarkable computational efficiency, delivering speedups of up to two orders of magnitude over the exact solver Concorde.
  arXiv  Detail & Related papers  (2026-07-31T20:23:21Z)
• AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network [50.69521065962045]
  We present the Anisotropic Graph Diffusion Network (AGDN), a new Graph Neural Network framework designed to solve the Traveling Salesman Problem (TSP)<n>Our method tackles two central difficulties: (1) the lack of informative topological prior in fully connected TSP graphs, and (2) losing connected nodes in the optimal solution after the commonly used graph sparsification techniques.<n>AGDN consistently outperforms existing methods while keeping time competitive.
  arXiv  Detail & Related papers  (2026-06-17T15:24:37Z)
• Closed-Form Spectral Regularization for Multi-Task Model Merging [96.82449201305234]
  Model merging combines several independently fine-tuned experts into a single multi-task model without any training data.<n>State-of-the-art merging methods formulate merging as a layer-wise interference problem.<n>We propose SWUDI, a closed-form method that combines a soft exponential filter, which matches the gradient-flow trajectory of iterative descent.
  arXiv  Detail & Related papers  (2026-06-05T14:00:47Z)
• R2G: A Multi-View Circuit Graph Benchmark Suite from RTL to GDSII [14.790942679912595]
  R2G is a multi-view circuit-graph benchmark suite that standardizes five stage-aware views with information parity.<n>R2G provides an end-to-end DEF-to-graph pipeline spanning synthesis, placement, and routing stages.
  arXiv  Detail & Related papers  (2026-04-09T22:59:27Z)
• RsGCN: Subgraph-Based Rescaling Enhances Generalization of GCNs for Solving Traveling Salesman Problems [10.605940576092507]
  GCN-based traveling salesman problem (TSP) solvers face two critical challenges: poor cross-scale generalization for TSPs and high training costs.<n>We propose a Subgraph-Based Rescaling Graph Convolutional Network (RsGCN)<n>Under a unified subgraph perspective, RsGCN can efficiently learn scale-generalizable representations from small-scale TSPs at low cost.<n>Based on a combined architecture of RsGCN and RBS, our solver achieves remarkable generalization and low training cost.
  arXiv  Detail & Related papers  (2025-05-31T12:40:02Z)
• FusionLLM: A Decentralized LLM Training System on Geo-distributed GPUs with Adaptive Compression [55.992528247880685]
  Decentralized training faces significant challenges regarding system design and efficiency. We present FusionLLM, a decentralized training system designed and implemented for training large deep neural networks (DNNs) We show that our system and method can achieve 1.45 - 9.39x speedup compared to baseline methods while ensuring convergence.
  arXiv  Detail & Related papers  (2024-10-16T16:13:19Z)
• A GREAT Architecture for Edge-Based Graph Problems Like TSP [10.48061333321108]
  We propose a novel GNN-based and edge-focused neural model called Graph Edge Attention Network (GREAT)<n>Using GREAT as an encoder to capture the properties of a routing problem instance, we build a reinforcement learning framework.<n>Our framework is among the first to tackle non-Euclidean variants of these problems and competitive results among learning-based benchmarks.
  arXiv  Detail & Related papers  (2024-08-29T17:07:43Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining. Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• SVNet: Where SO(3) Equivariance Meets Binarization on Point Cloud Representation [65.4396959244269]
  The paper tackles the challenge by designing a general framework to construct 3D learning architectures. The proposed approach can be applied to general backbones like PointNet and DGCNN. Experiments on ModelNet40, ShapeNet, and the real-world dataset ScanObjectNN, demonstrated that the method achieves a great trade-off between efficiency, rotation, and accuracy.
  arXiv  Detail & Related papers  (2022-09-13T12:12:19Z)
• Solve routing problems with a residual edge-graph attention neural network [10.42872026679616]
  In this paper, an end-to-end deep reinforcement learning framework is proposed to solve NP-hard optimization problems. The proposed framework is aiming to improve the models in literacy in terms of the neural network model and the training algorithm. Specifically, the average optimality gap is reduced from 4.53% (reported best citeR22) to 3.67% for TSP with 100 nodes and from 7.34% (reported best citeR22) to 6.68% for CVRP with 100 nodes when using the greedy decoding strategy.
  arXiv  Detail & Related papers  (2021-05-06T14:47:47Z)
• Distributed Multi-agent Meta Learning for Trajectory Design in Wireless Drone Networks [151.27147513363502]
  This paper studies the problem of the trajectory design for a group of energyconstrained drones operating in dynamic wireless network environments. A value based reinforcement learning (VDRL) solution and a metatraining mechanism is proposed.
  arXiv  Detail & Related papers  (2020-12-06T01:30:12Z)

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.