Prize-Collecting Traveling Salesperson Problem on PCTSP-50 (Metrics: Cost, Gap)
0Optimality GapILS
Evaluation Results
| Method | Links | ||
|---|---|---|---|
| ILSInference Time=18.30s, Implementation Language=C++2025.02 | 0 | — | |
| DIFU-AdaZero-shot=true, TSP-trained=true, Decoding=Greedy, Time=1.99s2025.02 | 3.57 | 4.63 | |
| OR-ToolsInference Time=2.02m2025.02 | 4.85 | — | |
| DIFU-AdaInference Time=1.92s, Training-free=true, Training Time=0 day2025.02 | 8.43 | — | |
| T2TZero-shot=true, TSP-trained=true, Decoding=Greedy, Time=2.18s2025.02 | 9.38 | 4.9 | |
| ASPInference Time=0.08s, Training-free=false, Training Time=4.6 days, Data Source=reported from [11]2025.02 | 10.34 | — | |
| AM-FTInference Time=8.02s, Search Strategy=Sampling, Training-free=false, Training Time=4.9 days2025.02 | 14.11 | — | |
| AMInference Time=7.08s, Search Strategy=Sampling, Training-free=false, Training Time=3.5 days2025.02 | 14.58 | — | |
| DIFUSCOZero-shot=true, TSP-trained=true, Decoding=Greedy, Time=1.35s2025.02 | 15.97 | 5.2 | |
| AM-FTInference Time=0.07s, Search Strategy=greedy, Training-free=false, Training Time=4.9 days2025.02 | 16.58 | — | |
| AMInference Time=0.07s, Search Strategy=Greedy, Training-free=false, Training Time=3.5 days2025.02 | 18.2 | — | |
| MDAMInference Time=4.77m, Search Strategy=Beam Search, Training-free=false, Training Time=4.3 days, Data Source=reported from [11]2025.02 | 18.81 | — | |
| MDAMInference Time=1.31m, Search Strategy=Greedy, Training-free=false, Training Time=4.3 days, Data Source=reported from [11]2025.02 | 24.73 | — | |
| ILS (Python 10x)Inference Time=4.70s, Implementation Language=Python, Data Source=reported from [11]2025.02 | 148.05 | — |