Traveling Salesman Problem: A Comprehensive Review and Computational Implementation in Python

Abstract

The Traveling Salesman Problem (TSP) is a well-known problem in combinatorial optimization, in which a salesperson who wishes to sell goods in a specific set of cities is seeking for the shortest possible course that would take him or her to all the cities before returning to the original point where he or she is based. Looking at what we have come up with, it becomes evident that we want to find the shortest distance possible. Even though Algorithm TSP is a well-researched problem, the fact that it is NP-resistant has encouraged a lot of work in various solutions. As such, the aim of this paper is to present a brief discussion of TSP, its history, and various approaches developed throughout the years. Thus, when considering the brute force approach implemented in Python we examine its flaws in terms of the methodological approach and possible computational performance. Using the notion of visualization, we also offer a means for an intuitive understanding of the solution space with particular focus placed on the interdependence between data, computations, and graphics.