A Spatially Informed Solving Approach for the Traveling Salesman Problem.
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 sol...
| Publicado en: | Professional Geographer Vol. 77; no. 6; pp. 690 - 704 |
|---|---|
| Autores principales: | , , |
| Formato: | Artículo |
| Publicado: |
Taylor & Francis Ltd
2025
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=ssf&AN=189877074&site=ehost-live header: @attributes: shortDbName: ssf uiTerm: 189877074 longDbName: Social Sciences Full Text (H.W. Wilson) uiTag: AN controlInfo: bkinfo: jinfo: jid: 00330124 PGG jtl: Professional Geographer issn: 00330124 maglogo: Y pubinfo: dt: 2025 vid: 77 iid: 6 pid: 377 pub: Taylor & Francis Ltd artinfo: ui: 189877074 10.1080/00330124.2025.2565474 ppf: 690 ppct: 14 formats: tig: atl: A Spatially Informed Solving Approach for the Traveling Salesman Problem. aug: au: Kim, Wanhee Kim, Hyun Chun, Yongwan affil: University of Tennessee, Knoxville, USA The University of Texas at Dallas, USA su: Heuristic Traveling salesman problem Combinatorial optimization Routing systems Mixed integer linear programming Constraint programming Route choice Geospatial data sug: subj: Heuristic Traveling salesman problem Combinatorial optimization Routing systems Mixed integer linear programming Constraint programming Route choice Geospatial data ab: 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. pubtype: Academic Journal doctype: Article src: R language: English refInfo: copyright: @attributes: flag: N holdings: @attributes: islocal: N |
|---|