A Spatially Informed Solving Approach for the Traveling Salesman Problem. - Kim, Wanhee; Kim, Hyun; Chun, Yongwan (Professional Geographer, 2025)
The traveling salesman problem (TSP) is a combinatorial optimization problem that seeks to determine the optimal route that minimizes the travel cost among a given set of nodes. Because solving the TSP inherently requires an exhaustive search, examining all possible routes to achieve the optimal solution, it becomes computationally challenging, particularly with an increase of problem size. Ensuring optimality while making the problem effectively tractable for large-scale instances has been a critical issue, which is also a key concern in many heuristic approaches with TSP. Despite various efforts to improve computational performance, limited research has explored the potential of incorporating spatial information to systematically reduce the problem size while maintaining solution quality. To address this issue, this research proposes an effective spatially informed approach, named SI-TSP, which incorporates skeleton Voronoi polygons method within a mixed integer programming framework. The SI-TSP leverages the critical spatial information extracted from the proximate neighborhoods of given nodes to distinguish essential and nonessential decision variables in determining the optimal route. The numerical experiments demonstrate that the SI-TSP is an effective and promising approach for solving that can be applied to similar network-routing problems when finding the optimal solution is a primary concern.