Traveling Salesperson Problem on TSP N=1000 Generalization (128 instances)
0Optimality GapConcorde
Evaluation results
| Method | Links | |||
|---|---|---|---|---|
| Concorde2023.01 | 0 | 2.5 | — | |
| MoH-KGLSHeuristic Category=Improvement Heuristic, Local Search Strategy=KGLS2025.05 | 1.363 | — | 23.419 | |
| BQ-transformer bs16decoding=beam search, beam size=16, backbone=Transformer2023.01 | 1.38 | 38 | — | |
| MCTS-AHD-KGLSHeuristic Category=Improvement Heuristic, Local Search Strategy=KGLS2025.05 | 1.389 | — | 23.425 | |
| MoH-GLSHeuristic Category=Improvement Heuristic, Local Search Strategy=GLS2025.05 | 1.476 | — | 23.445 | |
| ReEvo-KGLSHeuristic Category=Improvement Heuristic, Local Search Strategy=KGLS2025.05 | 1.595 | — | 23.473 | |
| HSEvo-KGLSHeuristic Category=Improvement Heuristic, Local Search Strategy=KGLS2025.05 | 1.615 | — | 23.478 | |
| BQ-transformer Gdecoding=greedy, backbone=Transformer2023.01 | 2.29 | 2 | — | |
| HSEvo-GLSHeuristic Category=Improvement Heuristic, Local Search Strategy=GLS2025.05 | 2.66 | — | 23.719 | |
| ReEvo-GLSHeuristic Category=Improvement Heuristic, Local Search Strategy=GLS2025.05 | 2.715 | — | 23.731 | |
| EoH-GLSHeuristic Category=Improvement Heuristic, Local Search Strategy=GLS2025.05 | 2.781 | — | 23.747 | |
| Att-GCN+MCTS*2023.01 | 3.22 | 13 | — | |
| DIFUSCO G+2opt*decoding=greedy2023.01 | 3.4 | 12 | — | |
| OR-ToolsHeuristic Category=Baseline2025.05 | 5.011 | — | 24.262 | |
| OR-Tools2023.01 | 5.02 | 2.4 | — | |
| BQ-perceiver Gdecoding=greedy, backbone=Perceiver2023.01 | 8.97 | 22 | — | |
| MoHHeuristic Category=Constructive Heuristic2025.05 | 15.049 | — | 26.581 | |
| MCTS-AHDHeuristic Category=Constructive Heuristic2025.05 | 16.06 | — | 26.814 | |
| ReEvoHeuristic Category=Constructive Heuristic2025.05 | 16.076 | — | 26.818 | |
| EoHHeuristic Category=Constructive Heuristic2025.05 | 16.39 | — | 26.89 | |
| DIMES RL+S*search=true2023.01 | 17.69 | 2 | — | |
| HSEvoHeuristic Category=Constructive Heuristic2025.05 | 18.727 | — | 27.431 | |
| FunsearchHeuristic Category=Constructive Heuristic2025.05 | 19.332 | — | 27.571 | |
| MDAM bs50beam size=502023.01 | 19.96 | 1.1 | — | |
| SGBS (10,10)search parameters=(10,10)2023.01 | 25.25 | 2.9 | — | |
| Nearest NeighborHeuristic Category=Baseline2025.05 | 25.474 | — | 28.99 | |
| AM bs1024beam size=10242023.01 | 29.75 | 31 | — | |
| Sym-NCO s100samples=1002023.01 | 37.51 | 2 | — | |
| POMO augx8augmentation=x82023.01 | 40.6 | 10 | — | |
| TransTSP bs1024beam size=10242023.01 | 76.21 | 37 | — | |
| ConcordeHeuristic Category=Baseline2025.05 | — | — | 23.104 |