Traveling Salesperson Problem on TSP N=200 (Generalization (128 instances))
0Optimality GapConcorde
Evaluation Results
| Method | Links | |||
|---|---|---|---|---|
| Concorde2023.01 | 0 | 2 | — | |
| Concorde2023.11 | 0 | — | 10.687 | |
| LKH32023.11 | 0 | — | 10.687 | |
| BQ-transformer bs16decoding=beam search, beam size=16, backbone=Transformer2023.01 | 0.09 | 3 | — | |
| MoH-KGLSHeuristic Category=Improvement Heuristic, Local Search Strategy=KGLS2025.05 | 0.177 | — | 10.699 | |
| MCTS-AHD-KGLSHeuristic Category=Improvement Heuristic, Local Search Strategy=KGLS2025.05 | 0.204 | — | 10.702 | |
| ReEvo-KGLSHeuristic Category=Improvement Heuristic, Local Search Strategy=KGLS2025.05 | 0.221 | — | 10.704 | |
| HSEvo-KGLSHeuristic Category=Improvement Heuristic, Local Search Strategy=KGLS2025.05 | 0.221 | — | 10.704 | |
| MoH-GLSHeuristic Category=Improvement Heuristic, Local Search Strategy=GLS2025.05 | 0.291 | — | 10.711 | |
| HSEvo-GLSHeuristic Category=Improvement Heuristic, Local Search Strategy=GLS2025.05 | 0.328 | — | 10.715 | |
| ReEvo-GLSHeuristic Category=Improvement Heuristic, Local Search Strategy=GLS2025.05 | 0.331 | — | 10.715 | |
| EoH-GLSHeuristic Category=Improvement Heuristic, Local Search Strategy=GLS2025.05 | 0.342 | — | 10.716 | |
| COMPASS2023.11 | 0.348 | — | 10.724 | |
| BQ-transformer Gdecoding=greedy, backbone=Transformer2023.01 | 0.54 | 9 | — | |
| SGBS (10,10)search parameters=(10,10)2023.01 | 0.67 | 1 | — | |
| EAS2023.11 | 0.672 | — | 10.759 | |
| Att-GCN+MCTS*2023.01 | 0.88 | 2 | — | |
| Poppynum_samples=162023.11 | 1.007 | — | 10.795 | |
| POMO augx8augmentation=x82023.01 | 1.57 | 5 | — | |
| MDAM bs50beam size=502023.01 | 2.04 | 3 | — | |
| BQ-perceiver Gdecoding=greedy, backbone=Perceiver2023.01 | 2.09 | 2 | — | |
| Sym-NCO s100samples=1002023.01 | 2.28 | 2 | — | |
| POMOsearch_mode=greedy2023.11 | 2.3 | — | 10.933 | |
| OR-ToolsHeuristic Category=Baseline2025.05 | 2.478 | — | 10.944 | |
| POMOsearch_mode=sampling2023.11 | 2.513 | — | 10.956 | |
| OR-Tools2023.01 | 4.52 | 4 | — | |
| TransTSP bs1024beam size=10242023.01 | 5.12 | 1 | — | |
| AM bs1024beam size=10242023.01 | 6.18 | 1 | — | |
| MoHHeuristic Category=Constructive Heuristic2025.05 | 13.307 | — | 12.1 | |
| MCTS-AHDHeuristic Category=Constructive Heuristic2025.05 | 13.921 | — | 12.165 | |
| HSEvoHeuristic Category=Constructive Heuristic2025.05 | 14.32 | — | 12.208 | |
| ReEvoHeuristic Category=Constructive Heuristic2025.05 | 14.403 | — | 12.217 | |
| EoHHeuristic Category=Constructive Heuristic2025.05 | 14.548 | — | 12.233 | |
| FunsearchHeuristic Category=Constructive Heuristic2025.05 | 18.143 | — | 12.615 | |
| Nearest NeighborHeuristic Category=Baseline2025.05 | 25.228 | — | 13.374 | |
| ConcordeHeuristic Category=Baseline2025.05 | — | — | 10.679 |