The Traveling Salesman Problem is arguably the most prominent problem in combinatorial optimization, and is regularly employed in a wide variety of applications. In this presentation, an analysis is made of Traveling Salesman implementations in Geographic Information Systems (GIS). An investigation into the solution procedures used in four software packages is presented, and 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 12 cities. 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 suggests that for some applications, the use of an optimal solution procedure is advised, and GIS implementations can benefit from the integration of more robust optimization techniques.

The Geography Seminar Series is organized by the Geographical Honors Society Gamma Theta Upsilon Eta Omicron Chapter.