Traveling Salesman Problem on TSP-500 (test)
0GapGUROBI
Evaluation results
| Method | Links | |||||
|---|---|---|---|---|---|---|
| GUROBIType=EXACT2023.02 | 0 | 16.55 | 45.63 | — | — | |
| LKH-3 (DEFAULT)Type=HEURISTICS2023.02 | 0 | 16.55 | 46.28 | — | — | |
| LKH-3 (LESS TRAILS)Type=HEURISTICS2023.02 | 0 | 16.55 | 3.03 | — | — | |
| ConcordeTYPE=Exact2025.02 | 0 | 16.55 | 37.66 | — | — | |
| GurobiTYPE=Exact2025.02 | 0 | 16.55 | 45.63 | — | — | |
| LKH-3TYPE=Heuristics2025.02 | 0 | 16.55 | 46.28 | — | — | |
| ConcordeInference Time=37m39s, Training Time=-2026.01 | 0 | 16.55 | — | — | — | |
| LKH-3Inference Time=46m40s, Training Time=-2026.01 | 0 | 16.55 | — | — | — | |
| LKH-3Type=Heuristic2026.01 | 0 | 16.55 | — | 21.69 | — | |
| ConcordeTYPE=OR, TIME=37.66m2026.05 | 0 | 16.55 | — | — | — | |
| LKH-3TYPE=OR, TIME=46.88m2026.05 | 0 | 16.55 | — | — | — | |
| CONCORDEType=EXACT2026.06 | 0 | 16.6 | — | 37.7 | — | |
| LKH-3Type=HEURISTICS2026.06 | 0 | 16.6 | — | 11.4 | — | |
| HEATACOBackbone=DIFUSCO, Post-processing=2opt2026.01 | 0.11 | 16.56 | — | — | — | |
| HEATACOBackbone=DIMES, Post-processing=2opt2026.01 | 0.14 | 16.57 | — | — | — | |
| MMASType=Heuristic, Post-processing=2opt2026.01 | 0.16 | 16.57 | — | 2.49 | — | |
| HEATACOBackbone=UTSP, Post-processing=2opt2026.01 | 0.16 | 16.57 | — | — | — | |
| LEHDType=AR+Greedy, Partial Re-Constriction=10002026.01 | 0.17 | 16.58 | — | 33.75 | — | |
| HEATACOBackbone=AttGCN, Post-processing=2opt2026.01 | 0.17 | 16.57 | — | — | — | |
| Fast T2TTYPE=SL+S+2Opt, Steps=T=5, Tg=52025.02 | 0.21 | 16.58 | 651 | — | — | |
| MMASType=Heuristic+3opt2026.01 | 0.3 | — | — | 7.5 | — | |
| Fast T2TTYPE=SL+G+2Opt, Steps=T=5, Tg=52025.02 | 0.39 | 16.61 | 210 | — | — | |
| HEATACOHeatmap source=DIMES, Refinement=3-opt2026.01 | 0.4 | — | — | 8.05 | — | |
| SoftDistType=Heuristic+MCTS2026.01 | 0.43 | 16.62 | — | 50 | — | |
| DIFUSCOType=SL+MCTS2023.02 | 0.46 | 16.63 | 10.13 | — | — | |
| DIFUSCOType=SL+MCTS2026.06 | 0.46 | 16.6 | — | 10.1 | — | |
| HEATACOHeatmap source=UTSP, Refinement=3-opt2026.01 | 0.5 | — | — | 6.97 | — | |
| MCTSBackbone=DIFUSCO2026.01 | 0.51 | 16.63 | — | — | — | |
| DIFUSCOType=SL+S+2-OPT2023.02 | 0.57 | 16.65 | 11.46 | — | — | |
| HEATACOHeatmap source=AttGCN, Refinement=3-opt2026.01 | 0.6 | — | — | 6.84 | — | |
| HEATACOHeatmap source=DIFUSCO, Refinement=3-opt2026.01 | 0.6 | — | — | 6.51 | — | |
| AGDNType=UL+MCTS2026.06 | 0.64 | 16.7 | — | 0.64 | — | |
| MCTSType=MCTS2026.01 | 0.66 | 16.66 | — | 50 | — | |
| MCTSBackbone=AttGCN2026.01 | 0.69 | 16.66 | — | — | — | |
| MCTSBackbone=DIMES2026.01 | 0.69 | 16.66 | — | — | — | |
| AGDNType=SL+MCTS2026.06 | 0.74 | 16.7 | — | 2.3 | — | |
| HEATACOBackbone=DIFUSCO2026.01 | 0.8 | 16.68 | — | — | — | |
| UTSPType=UL+MCTS2026.06 | 0.84 | 16.7 | — | 0.85 | — | |
| MCTSBackbone=UTSP2026.01 | 0.9 | 16.69 | — | — | — | |
| FastT2TInference Time=6m29s, Training Time=260h, Multi-step Sampling (MS)=true, Gradient Search (GS)=true2026.01 | 0.97 | 16.71 | — | — | — | |
| GatedGCNType=SL+MCTS2026.06 | 1.28 | 16.8 | — | 1.46 | — | |
| PositionType=SoftDist+MCTS2026.06 | 1.44 | 16.8 | — | 0 | — | |
| DIFUSCOType=SL+G+2-OPT2023.02 | 1.49 | 16.8 | 3.65 | — | — | |
| LEHDType=AR+Greedy2026.01 | 1.56 | 16.81 | — | 0.14 | — | |
| FMIPTYPE=SL, TIME=11.95m2026.05 | 1.69 | 16.83 | — | — | — | |
| DIMESType=RL+AS+MCTS2023.02 | 1.76 | 16.84 | 2.15 | — | — | |
| DIFUSCOTYPE=SL, TIME=11.95m2026.05 | 1.81 | 16.85 | — | — | — | |
| DeepACOType=NAR+ACO2026.01 | 1.84 | 16.86 | — | 10 | — | |
| DIMESType=RL+MCTS2023.02 | 1.93 | 16.87 | 2.92 | — | — | |
| GLOPType=NAR+AR2026.01 | 1.99 | 16.91 | — | 0.7 | — | |
| CAMTYPE=UL, TIME=11.95m2026.05 | 2.18 | 16.91 | — | — | — | |
| Fast T2TTYPE=SL+G, Steps=T=5, Tg=52025.02 | 2.33 | 16.93 | 212 | — | — | |
| ATT-GCNType=SL+MCTS2023.02 | 2.54 | 16.97 | 2.2 | — | — | |
| Att-GCNType=SL+MCTS2026.06 | 2.54 | 17 | — | 2.2 | — | |
| SDDSTYPE=UL, TIME=11.95m2026.05 | 2.6 | 16.98 | — | — | — | |
| HEATACOBackbone=AttGCN2026.01 | 3.53 | 17.13 | — | — | — | |
| PointerformerInference Time=53s, Training Time=547h47m2026.01 | 3.56 | 17.14 | — | — | — | |
| HEATACOBackbone=DIMES2026.01 | 3.98 | 17.2 | — | — | — | |
| DIFUSCOType=SL+S2023.02 | 4.08 | 17.23 | 11.02 | — | — | |
| TSP-MDFInference Time=1m6s, Training Time=1m55s, T=30, Base Heuristic Constructor=Farthest Insertion2026.01 | 4.29 | 17.26 | — | — | — | |
| HEATACOBackbone=UTSP2026.01 | 4.39 | 17.27 | — | — | — | |
| T2TTYPE=SL+G, Steps=T=50, Tg=302025.02 | 5.61 | 17.48 | 623 | — | — | |
| MMASType=Heuristic2026.01 | 6.13 | 17.56 | — | 1.88 | — | |
| DIFUSCOInference Time=10m46s, Training Time=129h10m2026.01 | 6.34 | 17.6 | — | — | — | |
| FastT2TInference Time=25s, Training Time=260h2026.01 | 6.82 | 17.68 | — | — | — | |
| DIMESInference Time=37m10s, Training Time=17m20s, Active Search (AS)=true2026.01 | 7.37 | 17.77 | — | — | — | |
| DIMESType=RL+AS+S2023.02 | 7.55 | 17.8 | 2.11 | — | — | |
| DIMESTYPE=UL, TIME=2.11h2026.05 | 7.55 | 17.8 | — | — | — | |
| Fast T2TTYPE=SL+G, Steps=T=12025.02 | 7.57 | 17.8 | 17 | — | — | |
| DIMESType=RL+AS+G2023.02 | 7.61 | 17.81 | 2.1 | — | — | |
| DIMESType=RL+AS+G2026.06 | 7.61 | 17.8 | — | 2.1 | — | |
| TSP-MDFInference Time=3s, Training Time=1m55s, T=1, Base Heuristic Constructor=Farthest Insertion2026.01 | 9 | 18.04 | — | — | — | |
| DIFUSCOTYPE=SL+G, Steps=T=1002025.02 | 9.82 | 18.17 | 431 | — | — | |
| Farthest InsertionInference Time=0.17s, Training Time=-2026.01 | 10.51 | 18.29 | — | — | — | |
| FARTHEST INSERTIONType=HEURISTICS2023.02 | 10.57 | 18.3 | 0 | — | — | |
| Farthest InsertionTYPE=Heuristics2025.02 | 10.57 | 18.3 | 0 | — | — | |
| Farthest InsertionType=Heuristic2026.01 | 10.57 | 18.3 | — | 0 | — | |
| DIFUSCOType=SL+G2023.02 | 10.85 | 18.35 | 3.61 | — | — | |
| DIFUSCODecoding Strategy=NAR+Greedy2026.01 | 10.85 | 18.35 | — | 1.69 | — | |
| Random InsertionType=Heuristic2026.01 | 12.21 | 18.57 | — | 0 | — | |
| DIMESType=RL+S2023.02 | 13.84 | 18.84 | 1.06 | — | — | |
| DIMESType=RL+G2023.02 | 14.38 | 18.93 | 0.97 | — | — | |
| DIMES*TYPE=RL+G2025.02 | 14.38 | 18.93 | 0.97 | — | — | |
| DeepACOInference Time=16m25s, Training Time=6m17s2026.01 | 14.38 | 18.93 | — | — | — | |
| DIMESType=RL+G2026.06 | 14.4 | 18.9 | — | 0.97 | — | |
| TSP-MDFInference Time=1m11s, Training Time=2m01s, T=30, Base Heuristic Constructor=Nearest Insertion2026.01 | 14.44 | 18.94 | — | — | — | |
| DIMESInference Time=22s, Training Time=17m20s2026.01 | 15.41 | 19.1 | — | — | — | |
| POMO+EAS-EMBType=RL+AS+G2023.02 | 16.25 | 19.24 | 12.8 | — | — | |
| POMOTYPE=UL, TIME=12.80h2026.05 | 16.25 | 19.24 | — | — | — | |
| POMO+EAS-EmbType=RL+AS+G2026.06 | 16.3 | 19.2 | — | 12.8 | — | |
| AMType=RL+BS2023.02 | 18.03 | 19.53 | 21.99 | — | — | |
| AMTYPE=UL, TIME=21.99m2026.05 | 18.03 | 19.53 | — | — | — | |
| AMType=RL+G2023.02 | 20.99 | 20.02 | 1.51 | — | — | |
| AM*TYPE=RL+G2025.02 | 20.99 | 20.02 | 1.51 | — | — | |
| AMType=RL+G2026.06 | 21 | 20 | — | 1.51 | — | |
| TSP-MDFInference Time=3s, Training Time=2m01s, T=1, Base Heuristic Constructor=Nearest Insertion2026.01 | 23.32 | 20.41 | — | — | — | |
| Nearest InsertionInference Time=0.19s, Training Time=-2026.01 | 24.59 | 20.62 | — | — | — | |
| Nearest InsertionType=Heuristic2026.01 | 24.59 | 20.62 | — | 0 | — | |
| AMType=AR+Greedy2026.01 | 29.71 | 21.46 | — | 0.55 | — | |
| UTSPDecoding Strategy=NAR+Greedy2026.01 | 32.28 | 21.89 | — | 0.64 | — |