The traveling salesman problem (TSP) asks for the shortest route that visits every specified city once and returns to the starting city. The number of possible routes grows exponentially with the number of cities, making large instances computationally infeasible; researchers therefore often use heuristics that seek good, not necessarily optimal, routes. section 5.4.1
As a test of learned optimization, a Ptr-Net trained on optimal solutions for small instances generalized to larger ones, finding near-optimal tours for problems with up to about 30 cities. Its performance was compared with traditional heuristics. section 5.4.1
Table 5.3 Performance of heuristics (A1 and A3) and Ptr-Net on the TSP
|
Problem size
|
Optimal
|
A1
|
A3
|
Ptr-Net
|
|---|---|---|---|---|
|
5
|
2.12
|
2.18
|
2.12
|
2.12
|
|
10
|
2.87
|
3.07
|
2.87
|
2.88
|
|
25
|
N/A
|
4.71
|
4.24
|
4.30
|
|
50 (A1 Trained)
|
N/A
|
6.46
|
5.79
|
6.42
|
|
50 (5–20 Trained)
|
N/A
|
6.46
|
5.79
|
7.66
|
Compare heuristic and Ptr-Net tour results across problem sizes, including instances with 50 cities. section 5.4.1
