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

Xiang Li

College of Computer Science, Yangtze University, Jingzhou, China

arXiv: https://arxiv.org/abs/2606.22776

---

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.

Key Results

Setting	NAR4TSP-R Gap	GeoRouteNet Gap	Reduction
TSP50 (Beam-1000)	0.42%	0.32%	22.2%
TSP100 (Beam-1000)	2.73%	1.26%	53.8%
TSPLIB (Beam-1000)	17.12%	3.60%	79.0%

Repository Structure

GeoRouteNet/
├── README.md                   # This file
├── LICENSE                     # MIT License
├── requirements.txt            # Python dependencies
├── train.py                    # Training entry point
├── evaluate.py                 # Single-method evaluation
├── benchmark.py                # Batch benchmark (generates paper tables)
├── utils.py                    # Core TSP utilities (distance matrix, tour decoding)
│
├── modules/                    # Model architectures
│   ├── nar4tsp.py              # NAR4TSP baseline (0.912M params)
│   └── georoutenet.py          # GeoRouteNet architecture (2.024M params)
│
├── training_methods/           # Training strategies
│   ├── pg.py                   # Single-candidate policy gradient
│   └── mcs_rl.py               # MCS-RL (multi-candidate self-comparison RL)
│
├── framework/                  # Training framework
│   ├── config.py               # Experiment configuration
│   ├── runner.py               # Training loop, checkpointing
│   ├── registry.py             # Plugin registry
│   └── utils.py                # Framework utilities
│
├── benchmark/                  # Evaluation framework
│   ├── decode/                 # Greedy & beam search decoders
│   ├── solvers/                # Concorde & LKH3 integration
│   ├── runner.py               # Benchmark orchestrator
│   └── report.py               # Results table generation (CSV + Markdown)
│
├── checkpoint/                 # Pre-trained weights (4 ablation variants)
│   ├── nar4tsp-pg-n50-*/       # NAR4TSP-R: nar4tsp + pg
│   ├── nar4tsp-mcs_rl-n50-*/   # NAR4TSP-MCS: nar4tsp + mcs_rl
│   ├── grn-pg-n50-*/           # GRN-PG: georoutenet + pg
│   └── georoutenet-n50-*/      # GeoRouteNet: georoutenet + mcs_rl
│
├── data/                       # Evaluation datasets
│   ├── tsp50_val.pt            # 10,000 fixed TSP50 instances
│   ├── tsp100_val.pt           # 10,000 fixed TSP100 instances
│   └── tsplib/                 # 27 TSPLIB EUC_2D instances
│
├── train_config/               # Training experiment configs
├── module_config/              # Model hyperparameter configs
├── benchmark_config/           # Benchmark evaluation configs
└── scripts/                    # Utility scripts (dataset generation)

Installation

Requirements

• Python 3.10+
• PyTorch 2.7+ (CUDA recommended for GPU inference)
• numpy, matplotlib, tqdm

Setup

# Create conda environment
conda create -n georoutenet python=3.12
conda activate georoutenet

# Install PyTorch (adjust CUDA version as needed)
pip install torch --index-url https://download.pytorch.org/whl/cu128

# Install other dependencies
pip install -r requirements.txt

Quick Start

1. Verify available models and training strategies

python train.py --list-models
# Expected: nar4tsp, georoutenet

python train.py --list-training-strategies
# Expected: pg, mcs_rl

2. Generate evaluation datasets

python scripts/generate_dataset.py --output data/tsp50_val.pt --num-samples 10000 --num-nodes 50 --seed 1234
python scripts/generate_dataset.py --output data/tsp100_val.pt --num-samples 10000 --num-nodes 100 --seed 1234

3. Smoke test (CPU, minimal training)

python train.py \
  --train-config train_config/georoutenet.json \
  --epochs 1 \
  --steps-per-epoch 1 \
  --batch-size 2 \
  --device cpu

Reproducing Paper Results

Training from scratch

Train all four ablation variants:

# NAR4TSP-R (baseline)
python train.py --train-config train_config/nar4tsp_pg.json

# NAR4TSP-MCS (training-only ablation)
python train.py --train-config train_config/nar4tsp_mcs_rl.json

# GRN-PG (structure-only ablation)
python train.py --train-config train_config/grn_pg.json

# GeoRouteNet (full method)
python train.py --train-config train_config/georoutenet.json

Each training run produces a directory under checkpoint/ containing best.ckpt, train_history.csv, and resolved_config.json.

Evaluate a single checkpoint

python evaluate.py \
  --name GeoRouteNet \
  --train-config train_config/georoutenet.json \
  --decode greedy \
  --decode beam100 \
  --decode beam1000 \
  --reference-solver Concorde

Generate benchmark tables (TSP50, TSP100, TSPLIB)

First-time run will automatically download and compile Concorde and LKH3 solvers.

# Main TSP50 results (Table 1 in paper)
python benchmark.py --config benchmark_config/main_results_tsp50.json

# TSP100 generalization (Table 2 in paper)
python benchmark.py --config benchmark_config/generalization_tsp100.json

# TSPLIB stratified evaluation (Tables 3-4 in paper)
python benchmark.py --config benchmark_config/tsplib_classic.json

Output: results/<benchmark_name>/results_summary.csv and results_summary.md

Using pre-trained weights

The checkpoint/ directory contains pre-trained weights for all four variants. To use them directly for evaluation:

python evaluate.py \
  --name GeoRouteNet \
  --checkpoint checkpoint/georoutenet-n50-*/best.ckpt \
  --decode greedy \
  --decode beam100 \
  --decode beam1000

Ablation Variants

The paper isolates contributions through four variants (2x2: model × training):

Variant	Model	Training	Role
NAR4TSP-R	nar4tsp	pg	Reproduction baseline
NAR4TSP-MCS	nar4tsp	mcs_rl	Training-only ablation
GRN-PG	georoutenet	pg	Structure-only ablation
GeoRouteNet	georoutenet	mcs_rl	Full method

Model Architecture

GeoRouteNet introduces five geometric inductive biases:

1. Centered node coordinates — translation invariance
2. Learnable RBF distance features — nonlinear distance encoding (K=16 Gaussian bases)
3. Distance-aware graph attention — edge bias + learnable distance penalty in attention logits
4. LayerNorm + SwiGLU FFN — stable, expressive feed-forward blocks
5. Cross-layer attentive residual mixing — multi-scale representation fusion

MCS-RL Training

Multi-Candidate Self-Comparison RL (MCS-RL) improves training signal quality through:

• K=3 candidate tours sampled per instance
• Adaptive baseline: min(greedy, best_peer_candidate)
• Winner-candidate guidance: reinforce the shortest sampled tour proportional to quality gap
• Annealed entropy regularization: η: 0.0125 → 0 (linear decay)

Training overhead vs. single-candidate PG: ~3% (training only; inference unchanged).

Hardware & Environment

Paper experiments used:

• Intel Xeon Silver 4214R CPU
• NVIDIA GeForce RTX 3080 Ti GPU
• Python 3.12.3, PyTorch 2.7.0, CUDA 12.8

Solver (Concorde / LKH3) evaluation uses CPU only. Neural model evaluation uses GPU; batch_size is halved automatically on OOM.

Citation

If you use this code or the GeoRouteNet method in your research, please cite:

@article{li2026georoutenet,
  title={GeoRouteNet: Geometry-Enhanced Non-Autoregressive Neural Solver
         for the Traveling Salesman Problem},
  author={Li, Xiang},
  journal={arXiv preprint arXiv:2606.22776},
  year={2026},
  note={arXiv:2606.22776}
}

License

MIT License — see LICENSE for details.

The external solvers (Concorde, LKH3, QSopt) are downloaded and compiled automatically during first benchmark run. Each has its own license; see their respective distributions.