Traveling Salesman Problem on TSP-1000 (test)
0Optimality GapLKH-3 (DEFAULT)
Evaluation results
| Method | Links | ||||
|---|---|---|---|---|---|
| LKH-3 (DEFAULT)Type=HEURISTICS2023.02 | 0 | 23.12 | 2.57 | — | |
| LKH-3 (LESS TRAILS)Type=HEURISTICS2023.02 | 0 | 23.12 | 7.73 | — | |
| ConcordeTYPE=Exact2025.02 | 0 | 23.12 | 6.65 | — | |
| GurobiTYPE=Exact2025.02 | 0 | 23.12 | 2.57 | — | |
| LKH-3TYPE=Heuristics2025.02 | 0 | 23.12 | 1.25 | — | |
| ConcordeTYPE=OR, TIME=6.65h2026.05 | 0 | 23.12 | — | — | |
| LKH-3TYPE=OR, TIME=2.57h2026.05 | 0 | 23.12 | — | — | |
| CONCORDEType=EXACT2026.06 | 0 | 23.1 | — | 6.65 | |
| LKH-3Type=HEURISTICS2026.06 | 0 | 23.1 | — | 38.1 | |
| SPO+ lossLearning Rate=0.12026.05 | 0.31 | — | — | 3,790 | |
| Fast T2TTYPE=SL+S+2Opt, Steps=T=5, Tg=52025.02 | 0.42 | 23.22 | 1,817 | — | |
| SPO+ lossRelaxation=true2026.05 | 0.46 | — | — | 3,699 | |
| Fast T2TTYPE=SL+G+2Opt, Steps=T=5, Tg=52025.02 | 0.58 | 23.25 | 837 | — | |
| MAE lossComponents=O,S2026.05 | 0.58 | — | — | 280 | |
| SPO+ loss2026.05 | 0.83 | — | — | 4,442 | |
| AGDNType=UL+MCTS2026.06 | 0.96 | 23.3 | — | 0.97 | |
| SPO+ lossCache=0%2026.05 | 0.98 | — | — | 266 | |
| MSE loss2026.05 | 1 | — | — | 108 | |
| SPO+ lossCache=5%2026.05 | 1 | — | — | 1,348 | |
| MAP lossCache=0%2026.05 | 1 | — | — | 212 | |
| MAP lossCache=5%2026.05 | 1.01 | — | — | 947 | |
| DIFUSCOType=SL+MCTS2023.02 | 1.17 | 23.39 | 24.47 | — | |
| DIFUSCOType=SL+MCTS2026.06 | 1.17 | 23.4 | — | 24.5 | |
| UTSPType=UL+MCTS2026.06 | 1.18 | 23.4 | — | 1.82 | |
| AGDNType=SL+MCTS2026.06 | 1.28 | 23.4 | — | 2.4 | |
| DIFUSCOType=SL+S+2-OPT2023.02 | 1.43 | 23.45 | 48.09 | — | |
| DIFUSCOTYPE=SL+G+2Opt, Steps=T=1002025.02 | 1.89 | 23.55 | 1,425 | — | |
| DIFUSCOType=SL+G+2-OPT2023.02 | 1.9 | 23.56 | 12.06 | — | |
| PositionType=SoftDist+MCTS2026.06 | 2.2 | 23.6 | — | 0 | |
| DIMESType=RL+AS+MCTS2023.02 | 2.46 | 23.69 | 4.62 | — | |
| CAMTYPE=UL, TIME=47.01m2026.05 | 2.51 | 23.7 | — | — | |
| DIMESType=RL+MCTS2023.02 | 2.64 | 23.73 | 6.87 | — | |
| FMIPTYPE=SL, TIME=47.01m2026.05 | 2.98 | 23.81 | — | — | |
| DIFUSCOTYPE=SL, TIME=47.01m2026.05 | 3.16 | 23.85 | — | — | |
| ATT-GCNType=SL+MCTS2023.02 | 3.22 | 23.86 | 4.1 | — | |
| Att-GCNType=SL+MCTS2026.06 | 3.22 | 23.9 | — | 4.1 | |
| SDDSTYPE=UL, TIME=47.01m2026.05 | 3.37 | 23.9 | — | — | |
| Fast T2TTYPE=SL+G, Steps=T=5, Tg=52025.02 | 3.64 | 23.96 | 912 | — | |
| MSE lossComponents=O,S2026.05 | 3.79 | — | — | 270 | |
| HEATACOHeatmap source=DIFUSCO, Refinement=3-opt2026.01 | 5 | — | — | 15.63 | |
| MMASType=Heuristic+3opt2026.01 | 6 | — | — | 5.79 | |
| HEATACOHeatmap source=DIMES, Refinement=3-opt2026.01 | 6 | — | — | 15.08 | |
| HEATACOHeatmap source=UTSP, Refinement=3-opt2026.01 | 6 | — | — | 15.06 | |
| HEATACOHeatmap source=AttGCN, Refinement=3-opt2026.01 | 7 | — | — | 14.6 | |
| GatedGCNType=SL+MCTS2026.06 | 7.26 | 24.8 | — | 4.96 | |
| DIMESType=RL+AS+S2023.02 | 7.7 | 24.89 | 4.53 | — | |
| MSE lossComponents=OS2026.05 | 7.7 | — | — | 2,774 | |
| DIMESTYPE=UL, TIME=4.53h2026.05 | 7.7 | 24.89 | — | — | |
| DIMESType=RL+AS+G2023.02 | 7.74 | 24.91 | 4.49 | — | |
| DIMESType=RL+AS+G2026.06 | 7.74 | 24.9 | — | 4.49 | |
| DIFUSCOType=SL+S2023.02 | 8.95 | 25.19 | 46.08 | — | |
| Fast T2TTYPE=SL+G, Steps=T=12025.02 | 9.13 | 25.23 | 55 | — | |
| FARTHEST INSERTIONType=HEURISTICS2023.02 | 11.25 | 25.72 | 0 | — | |
| DIFUSCOTYPE=SL+G, Steps=T=1002025.02 | 11.36 | 25.74 | 1,420 | — | |
| DIFUSCOType=SL+G2023.02 | 13.06 | 26.14 | 11.86 | — | |
| DIMESType=RL+S2023.02 | 14.01 | 26.36 | 2.38 | — | |
| DIMESType=RL+G2023.02 | 14.97 | 26.58 | 2.08 | — | |
| DIMES*TYPE=RL+G2025.02 | 14.97 | 26.58 | 2.08 | — | |
| DIMESType=RL+G2026.06 | 15 | 26.6 | — | 2.08 | |
| AMType=RL+BS2023.02 | 29.23 | 29.9 | 1.64 | — | |
| AMTYPE=UL, TIME=1.64m2026.05 | 29.23 | 29.9 | — | — | |
| AMType=RL+G2023.02 | 34.75 | 31.15 | 3.18 | — | |
| AMType=RL+G2026.06 | 34.8 | 31.2 | — | 3.18 | |
| EANType=RL+S+2-OPT2023.02 | 106.46 | 47.73 | 5.39 | — | |
| GCNType=SL+G2023.02 | 110.29 | 48.62 | 28.52 | — | |
| POMO+EAS-TabType=RL+AS+G2026.06 | 114 | 49.6 | — | 63.5 | |
| POMO+EAS-TABType=RL+AS+G2023.02 | 114.36 | 49.56 | 63.45 | — | |
| POMOTYPE=UL, TIME=63.45h2026.05 | 114.36 | 49.56 | — | — | |
| GatedGCNType=SL+BS2026.06 | 121 | 51.3 | — | 51.7 | |
| GCNType=SL+BS2023.02 | 121.73 | 51.26 | 51.67 | — | |
| GCNTYPE=SL, TIME=51.67m2026.05 | 121.73 | 51.26 | — | — | |
| CONCORDEType=EXACT2023.02 | — | 23.12 | 6.65 | — |