Traveling Salesperson Problem on TSP N=500 Generalization (128 instances)
0Optimality GapConcorde
Evaluation results
| Method | Links | |||
|---|---|---|---|---|
| Concorde2023.01 | 0 | 40 | — | |
| BQ-transformer bs16decoding=beam search, beam size=16, backbone=Transformer2023.01 | 0.55 | 15 | — | |
| MoH-KGLSHeuristic Category=Improvement Heuristic, Local Search Strategy=KGLS2025.05 | 0.805 | — | 16.652 | |
| HMACEGPT-5.4 Evaluation=true2026.05 | 0.809 | — | 16.653 | |
| MCTS-AHD-KGLSHeuristic Category=Improvement Heuristic, Local Search Strategy=KGLS2025.05 | 0.867 | — | 16.662 | |
| CORALGPT-5.4 Evaluation=true2026.05 | 0.882 | — | 16.665 | |
| MoH-GLSHeuristic Category=Improvement Heuristic, Local Search Strategy=GLS2025.05 | 0.936 | — | 16.674 | |
| EoHGPT-5.4 Evaluation=true2026.05 | 0.956 | — | 16.677 | |
| HSEvo-KGLSHeuristic Category=Improvement Heuristic, Local Search Strategy=KGLS2025.05 | 0.958 | — | 16.678 | |
| ReEvo-KGLSHeuristic Category=Improvement Heuristic, Local Search Strategy=KGLS2025.05 | 0.976 | — | 16.681 | |
| EoH-GLSHeuristic Category=Improvement Heuristic, Local Search Strategy=GLS2025.05 | 1.176 | — | 16.714 | |
| BQ-transformer Gdecoding=greedy, backbone=Transformer2023.01 | 1.18 | 55 | — | |
| HSEvo-GLSHeuristic Category=Improvement Heuristic, Local Search Strategy=GLS2025.05 | 1.266 | — | 16.729 | |
| ReEvo-GLSHeuristic Category=Improvement Heuristic, Local Search Strategy=GLS2025.05 | 1.344 | — | 16.741 | |
| DIFUSCO G+2opt*decoding=greedy2023.01 | 2.4 | 4 | — | |
| Att-GCN+MCTS*2023.01 | 2.54 | 6 | — | |
| OR-ToolsHeuristic Category=Baseline2025.05 | 4.479 | — | 17.259 | |
| OR-ToolsGPT-5.4 Evaluation=false2026.05 | 4.479 | — | 17.259 | |
| OR-Tools2023.01 | 4.89 | 31 | — | |
| BQ-perceiver Gdecoding=greedy, backbone=Perceiver2023.01 | 5.22 | 8 | — | |
| MDAM bs50beam size=502023.01 | 9.88 | 13 | — | |
| SGBS (10,10)search parameters=(10,10)2023.01 | 11.42 | 20 | — | |
| MoHHeuristic Category=Constructive Heuristic2025.05 | 14.224 | — | 18.869 | |
| MoHGPT-5.4 Evaluation=false2026.05 | 14.224 | — | 18.869 | |
| EoHHeuristic Category=Constructive Heuristic2025.05 | 15.196 | — | 19.029 | |
| EoHGPT-5.4 Evaluation=false2026.05 | 15.196 | — | 19.029 | |
| ReEvoHeuristic Category=Constructive Heuristic2025.05 | 15.232 | — | 19.035 | |
| ReEvoGPT-5.4 Evaluation=false2026.05 | 15.232 | — | 19.035 | |
| MCTS-AHDHeuristic Category=Constructive Heuristic2025.05 | 15.24 | — | 19.036 | |
| MCTS-AHDGPT-5.4 Evaluation=false2026.05 | 15.24 | — | 19.036 | |
| DIMES RL+S*search=true2023.01 | 16.07 | 1 | — | |
| AM bs1024beam size=10242023.01 | 17.98 | 8 | — | |
| FunsearchHeuristic Category=Constructive Heuristic2025.05 | 18.242 | — | 19.531 | |
| FunsearchGPT-5.4 Evaluation=false2026.05 | 18.242 | — | 19.531 | |
| HSEvoHeuristic Category=Constructive Heuristic2025.05 | 18.349 | — | 19.55 | |
| HSEvoGPT-5.4 Evaluation=false2026.05 | 18.349 | — | 19.55 | |
| POMO augx8augmentation=x82023.01 | 20.18 | 1 | — | |
| Sym-NCO s100samples=1002023.01 | 21.64 | 13 | — | |
| Nearest NeighborHeuristic Category=Baseline2025.05 | 25.252 | — | 20.691 | |
| Nearest NeighborGPT-5.4 Evaluation=false2026.05 | 25.252 | — | 20.691 | |
| TransTSP bs1024beam size=10242023.01 | 36.14 | 9 | — | |
| ConcordeHeuristic Category=Baseline2025.05 | — | — | 16.519 | |
| ConcordeGPT-5.4 Evaluation=false2026.05 | — | — | 16.519 |