List your company
ResearchFormerly WizWand

Traveling Salesperson Problem on TSP N=200 (Generalization (128 instances))

0Optimality GapConcorde
-1.009125.8024412.61419.42556Jan 9, 2023Jun 2, 2023Oct 25, 2023Mar 18, 2024Aug 10, 2024Jan 2, 2025May 27, 2025
Updated 7mo ago

Evaluation results

MethodLinks
Concorde2023.0102—
Concorde2023.110—10.687
LKH32023.110—10.687
BQ-transformer bs16decoding=beam search, beam size=16, backbone=Transformer2023.010.093—
MoH-KGLSHeuristic Category=Improvement Heuristic, Local Search Strategy=KGLS2025.050.177—10.699
MCTS-AHD-KGLSHeuristic Category=Improvement Heuristic, Local Search Strategy=KGLS2025.050.204—10.702
ReEvo-KGLSHeuristic Category=Improvement Heuristic, Local Search Strategy=KGLS2025.050.221—10.704
HSEvo-KGLSHeuristic Category=Improvement Heuristic, Local Search Strategy=KGLS2025.050.221—10.704
MoH-GLSHeuristic Category=Improvement Heuristic, Local Search Strategy=GLS2025.050.291—10.711
HSEvo-GLSHeuristic Category=Improvement Heuristic, Local Search Strategy=GLS2025.050.328—10.715
ReEvo-GLSHeuristic Category=Improvement Heuristic, Local Search Strategy=GLS2025.050.331—10.715
EoH-GLSHeuristic Category=Improvement Heuristic, Local Search Strategy=GLS2025.050.342—10.716
COMPASS2023.110.348—10.724
BQ-transformer Gdecoding=greedy, backbone=Transformer2023.010.549—
SGBS (10,10)search parameters=(10,10)2023.010.671—
EAS2023.110.672—10.759
Att-GCN+MCTS*2023.010.882—
Poppynum_samples=162023.111.007—10.795
POMO augx8augmentation=x82023.011.575—
MDAM bs50beam size=502023.012.043—
BQ-perceiver Gdecoding=greedy, backbone=Perceiver2023.012.092—
Sym-NCO s100samples=1002023.012.282—
POMOsearch_mode=greedy2023.112.3—10.933
OR-ToolsHeuristic Category=Baseline2025.052.478—10.944
POMOsearch_mode=sampling2023.112.513—10.956
OR-Tools2023.014.524—
TransTSP bs1024beam size=10242023.015.121—
AM bs1024beam size=10242023.016.181—
MoHHeuristic Category=Constructive Heuristic2025.0513.307—12.1
MCTS-AHDHeuristic Category=Constructive Heuristic2025.0513.921—12.165
HSEvoHeuristic Category=Constructive Heuristic2025.0514.32—12.208
ReEvoHeuristic Category=Constructive Heuristic2025.0514.403—12.217
EoHHeuristic Category=Constructive Heuristic2025.0514.548—12.233
FunsearchHeuristic Category=Constructive Heuristic2025.0518.143—12.615
Nearest NeighborHeuristic Category=Baseline2025.0525.228—13.374
ConcordeHeuristic Category=Baseline2025.05——10.679