The symmetric traveling salesman problem (STSP) asks for the shortest round trip through every city exactly once. Cities are points in a Euclidean plane, and distance is identical in either direction, so the route forms an undirected graph. section 2.1.1 section 11.5
A regional delivery loop
For 13 major cities in the Greater Toronto Area, a planner must choose one complete loop and optimize distance, time, or another cost. The permutation search space grows factorially, making naive enumeration impractical. section 2.1.1
Figure 2.2 TSP in the Greater Toronto Area (GTA). The traveling salesman must visit all 13 cities and wishes to select the “best” path, whether that be based on distance, time, or some other criterion.
Use the regional map to visualize cities as points and compare candidate round trips against the chosen cost criterion. section 2.1.1
Common solution directions include:
- Dynamic programming reduces the search burden by solving smaller subproblems; Bellman–Held–Karp has O(2^n × n²) complexity. section 2.1.1
- Exact and approximate alternatives include Concorde, branch and bound, Christofides, 2-opt, and 3-opt. section 2.1.1
- Machine learning can generate tours directly, configure optimization parameters, or repeatedly guide decisions during optimization. section 11.5
