AI TSP Problem

An end-to-end project around the fixed-start / fixed-end Euclidean TSP path problem:

• Rust exact solvers and dataset generation
• Python model training and evaluation
• AI-only route prediction for fast approximation
• AI + exact algorithm hybrid search for provably optimal answers

The core question is simple:

Can a learned model make route search meaningfully faster, while still keeping exact search available when you need proof of optimality?

In this repository, the answer is:

• yes for larger instances, when AI is used as a guide
• no for very small instances, where exact search is already cheap
• also yes if you only need a very strong approximation instead of the absolute best route

Project links:

• GitHub repository: https://github.com/cochon123/AI-TSP-Problem
• Hugging Face model: https://huggingface.co/Cochon123/ai-tsp-problem-v2

What We Built

The project went through two major phases:

• V1 was the first prototype and is kept only as a legacy checkpoint
• V2 is the current system, with harder data, richer labels, a geometry-aware model, and exact-hybrid search

The current V2 pipeline does three things well:

• it predicts very strong approximate routes
• it generates high-quality warm starts for exact search
• it cuts the number of explored exact-search states on the hard n=17..20 bucket

Interactive Demo

If you just want to try the project in a browser, open:

• demo.html

The demo lets you:

• place cities manually
• generate random instances
• toggle AI mode
• compare Exact best, Exact mean, Exact worst, AI, and AI + algorithm
• compare route quality and solving speed

For large node counts, the page intentionally skips brute force and shows a popup explaining:

• why exact brute force was disabled
• how long brute force would roughly have taken
• why only AI and AI + algorithm are shown

Note:

• the browser demo uses lightweight in-browser heuristics so it stays easy to run
• the trained V2 model and the full hybrid benchmark live in the Rust/Python pipeline

Demo screenshots:

The first view shows the live canvas while the exact solver is still exploring paths and the route display can be switched between Exact best, AI, and AI + algorithm.

The second view shows the analysis panels: histogram, distance comparison, and speed comparison for the same instance.

The Problem

The problem is a small but expensive combinatorial optimization task:

• the start node is fixed
• the end node is fixed
• all intermediate nodes must be visited exactly once
• the objective is the shortest possible Euclidean path

Brute force is exact, but it becomes expensive very quickly as n grows. That is the tension this project explores:

• exact search gives certainty
• AI gives speed
• hybrid search tries to get both

The Solution

The final V2 system is a hybrid:

1. Rust generates exact labeled data with a classical solver.
2. Python trains a pointer-style Transformer on that data.
3. The model predicts a strong route and step scores.
4. The exact branch-and-bound solver uses those scores to search fewer states.

The important point is that exactness still comes from the classical solver. The model is only a guide.

That gives three useful operating modes:

1. Exact only Best when the instance is small and brute force or branch-and-bound is already fast.
2. AI only Best when you need a route immediately and a tiny optimality gap is acceptable.
3. Hybrid AI + exact search Best when you still want a provably optimal answer, but you want the solver to search less.

Results

Training curves

The final training run is stable, with clean loss and accuracy curves.

There is a visible disturbance in the middle of the training curves because one long run was interrupted by a machine suspend and had to be resumed. The final checkpoint and the final benchmark numbers are still the ones that matter.

Speed benchmark

The default speed benchmark compares:

• BnB without AI
• Hybrid AI
• Beam AI

It was run on three ranges:

• n=7..10
• n=11..16
• n=17..20

AI-only benchmark

The graphs below focus on the AI only method.

• the black line is the exact baseline latency
• the blue line is the AI latency
• the green line shows exact-route accuracy
• the red line shows the mean gap to the optimal route

This is the cleanest way to read the approximation tradeoff:

• if the blue line stays far below the black line, AI is much faster
• if the red line stays close to zero, AI remains near-optimal
• if the green line stays high, AI often predicts the exact best route directly

These plots show the practical story very clearly:

• for small n, exact search is so cheap that AI latency is not an advantage
• in the middle range, AI becomes competitive
• by n=17..20, AI is dramatically faster than exact search while still staying very close to the optimum

Example from the saved benchmark JSON:

• at n=16, exact baseline latency is about 700.44 ms, while AI-only latency is about 40.65 ms
• at n=20, exact baseline latency is about 23087.18 ms, while AI-only latency is about 49.73 ms
• even at n=20, the mean AI-only gap stays around 0.41%

To regenerate the AI-only benchmark:

PYTHONPATH=python/src python -m aifindpath.benchmark --mode greedy --checkpoint artifacts/checkpoints/v2/best_score.pt --data data/pilot_v2 --split test --samples-per-size 16 --output-dir artifacts/benchmarks/v2

This produces:

• artifacts/benchmarks/v2/greedy_speed_benchmark.json
• artifacts/benchmarks/v2/greedy_node_speed_vs_accuracy.png
• artifacts/benchmarks/v2/greedy_node_speed_vs_gap.png

Key numbers

From the final benchmark:

Range	BnB baseline mean latency	Hybrid mean latency	Speedup
n=7..10	1.59 ms	49.65 ms	0.03x
n=17..20	2626.86 ms	1639.05 ms	1.60x

Interpretation:

• on small instances, the model is not worth the overhead
• on n=17..20, the hybrid method is meaningfully faster
• the model also keeps high route quality on both uniform and hard test sets
• if you do not need the absolute best route, AI only is already a valid operating mode because its gap stays very small

Additional quality results from the final V2 checkpoint:

• uniform test beam exact route accuracy: 91.63%
• uniform test beam mean optimality gap: 0.0496%
• hard test beam exact route accuracy: 93.55%
• hard test beam mean optimality gap: 0.0240%

Similar Work

This project is not trying to claim that “AI for routing” is new. It is much closer to a focused engineering/research build inspired by several lines of prior work:

• Pointer Networks Vinyals et al. showed that neural models can emit permutations directly, which is one of the key ideas behind learned TSP-style solvers.
• Neural Combinatorial Optimization with Reinforcement Learning Bello et al. pushed the idea of learning routing policies directly for combinatorial optimization problems.
• Attention, Learn to Solve Routing Problems! Kool et al. is one of the clearest references for attention-based neural routing models.
• Exact Combinatorial Optimization with Graph Convolutional Neural Networks Gasse et al. is especially relevant to the hybrid side of this repository: using learned guidance to improve exact search.

The angle of this repository is narrower and more practical:

• fixed-start / fixed-end Euclidean TSP path
• exact Rust labeling
• a trained Python model
• direct side-by-side benchmarks between exact, AI-only, and AI-guided exact search

Repository Layout

rust/
  crates/
    tsp_core/   exact solvers and shared types
    tsp_gen/    exact data generation
    tsp_bench/  solve and benchmark CLI
python/
  configs/
  src/aifindpath/
docs/
  images/       committed plots used by this README
explication/
  V2.md        French documentation for the V2 system

Getting Started

1. Install dependencies

Python:

cd python
python3 -m venv .venv
source .venv/bin/activate
python -m pip install --upgrade pip
python -m pip install -e .

Rust:

cd rust
cargo test

1.5. Try the browser demo

If you only want the interactive visualization, open:

xdg-open demo.html

or just double-click demo.html in your file explorer.

2. Generate the V2 dataset

cd rust
cargo run --release -p tsp_gen -- generate-manifest --manifest manifests/pilot_v2.yaml

This creates the V2 data under data/pilot_v2/.

3. Train the model

From the repo root:

PYTHONPATH=python/src python -m aifindpath.train --config python/configs/pilot.yaml

Training writes checkpoints and plots under artifacts/.

4. Evaluate the model

Approximate route quality:

PYTHONPATH=python/src python -m aifindpath.eval --checkpoint artifacts/checkpoints/v2/best_score.pt --data data/pilot_v2 --split test --beam 32

Exact hybrid evaluation:

PYTHONPATH=python/src python -m aifindpath.eval --checkpoint artifacts/checkpoints/v2/best_score.pt --data data/pilot_v2 --split test --beam 32 --run-hybrid

Hard split evaluation:

PYTHONPATH=python/src python -m aifindpath.eval --checkpoint artifacts/checkpoints/v2/best_score.pt --data data/pilot_v2 --split test_hard --beam 32

5. Run the speed benchmark

PYTHONPATH=python/src python -m aifindpath.benchmark --checkpoint artifacts/checkpoints/v2/best_score.pt --data data/pilot_v2 --split test --beam 32 --samples-per-size 16 --output-dir artifacts/benchmarks/v2

This generates:

• artifacts/benchmarks/v2/speed_benchmark.json
• artifacts/benchmarks/v2/speed_benchmark_overview.png
• artifacts/benchmarks/v2/speed_benchmark_quality.png

6. Run the AI-only benchmark

PYTHONPATH=python/src python -m aifindpath.benchmark --mode greedy --checkpoint artifacts/checkpoints/v2/best_score.pt --data data/pilot_v2 --split test --samples-per-size 16 --output-dir artifacts/benchmarks/v2

This generates:

• artifacts/benchmarks/v2/greedy_speed_benchmark.json
• artifacts/benchmarks/v2/greedy_node_speed_vs_accuracy.png
• artifacts/benchmarks/v2/greedy_node_speed_vs_gap.png

Checkpoints

The model weights are organized by version:

• artifacts/checkpoints/v1/best.pt for the legacy V1 model
• artifacts/checkpoints/v2/best_score.pt for the best V2 checkpoint
• artifacts/checkpoints/v2/best_hybrid.pt for the best hybrid-guidance checkpoint
• artifacts/checkpoints/v2/last.pt for the latest training state

Documentation

For a French explanation of the project and the V2 design, see:

• explication/README.md
• explication/V2.md

Why This Matters

The main takeaway is not that AI replaces exact algorithms. The main takeaway is that different methods are best for different goals:

• use exact when correctness is cheap enough
• use AI only when you want a fast route and a tiny gap is acceptable
• use hybrid AI + exact search when you want proof of optimality without paying the full search cost everywhere

That is the useful line in this repository:

• classical solver for correctness
• AI for strong approximations
• hybrid search for speed on the hard cases