Setup
Each size has ten seeded Euclidean instances and ten solver seeds. The reference for every instance, including 15 and 20 cities, is the proven Held-Karp optimum. All methods get the same budget of attempted operations.
Results
- Bit-flip QUBO annealing reaches an 86.65% mean gap at 20 cities: one-hot penalty landscapes are hard to search.
- A permutation-preserving swap move brings the gap down to 3.69%, still 3.32 points above multi-start 2-opt at 0.37%.
- At 10 cities swap annealing is slightly ahead of 2-opt (0.27% vs 0.41%), a small difference in these runs.
What is inside
- QUBO builder and simulated annealing solver
- TSP, capacitated VRP and VRP with time windows, with independent feasibility checks
- OR-Tools reference solvers
- Interactive route visualization demo