A Comparative Analysis of Traveling Salesman Solutions from Geographic Information Systems. Issue 2 (9th June 2013)

• Record Type: Journal Article
• Authors: Curtin, Kevin M.; Voicu, Gabriela; Rice, Matthew T.; Stefanidis, Anthony
• Is Part Of: Transactions in GIS. Volume 18:Issue 2(2014:Apr.)
• Page Start: 286
• Page End: 301
• Publication Date: 2013-06-09
• Subjects: Geographic information systems -- Periodicals; 910.285
• DOI: 10.1111/tgis.12045
• Languages: English
• ISSNs: 1361-1682

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>The Traveling Salesman Problem is one of the most prominent problems in combinatorial optimization, and is regularly employed in a wide variety of applications. The objective of this article is to demonstrate the extent of sub‐optimality produced by Traveling Salesman solution procedures implemented in the context of Geographic Information Systems and to discuss the consequences that such solutions have for practice. Toward that end, an analysis is made of Traveling Salesman solutions from implementations in four Geographic Information System packages. These implementations are tested against the optimal solution for a range of problem sizes. Computational results are presented in the context of a school bus routing application. This analysis concludes that no Traveling Salesman implementation in GIS is likely to find the optimal solution when problems exceed 10 stops. In contrast, optimal solutions can be generated with desktop linear programming software for up to 25 cities. Moreover, one GIS implementation consistently found solutions that were closer to optimal than its competitors. This research strongly suggests that for applications with fewer than 25 stops, the use of an optimal solution procedure is advised, and that GIS implementations can benefit from the integration of more robust optimization techniques.</p> </abstract>