A Comparative Test of Traveling Salesman Solutions from GIS Software Packages
Date
2015-08-06
Authors
Nies, Brandi
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The Traveling Salesman Problem (TSP) has long been studied and remains a challenge in the realm of combinatorial optimization across many disciplines. This research investigates the extent to which heuristic solutions for symmetric TSPs generated within geographic information systems (GIS) applications are sub-optimal, compared to exact solution procedures. The TSP is addressed in this research through multiple real-world street networks and a range of problem instances, for which a path must be generated that visits each city only once, and returns to the original point of departure, while minimizing the distance traveled. Two GIS applications were used to generate heuristic solutions for the symmetric TSP for each network dataset. These results were compared against the optimal solutions generated from an exact solution procedure for the same networks. The cumulative cost of each TSP route for all network problem instances was examined to determine the performance and level of sub-optimality where applicable. This research concludes that the heuristic solutions generated sub-optimal results averaging a combined performance measure of 17.36% above optimal, however the software that employs the tabu search (TS) heuristic significantly outperformed the software that used the genetic algorithm (GA) by consistently producing solutions nearer to the known optimum as generated by the exact solution procedure. Given the wide range in the extent of sub-optimal results from the heuristic-based GIS applications, this research suggests that careful consideration should be made prior to the use of these implementations for spatial analysis. Additionally, GIS packages could benefit from integrating additional, or more efficient heuristic or exact solution procedures within the application, and allowing the user more control of the search parameters to accommodate various network optimization problems. Keywords: network analysis; traveling salesman; TSP, route optimization; GIS; heuristic; genetic algorithm; tabu search
Description
This work was embargoed by the author and will not be publicly available until January 2020.
Keywords
Network analysis, Traveling salesman, Route optimization, GIS, Heuristic, Exact algorithm