The fascinating Traveling Salesman Problem (TSP)

Understanding TSP algorithm with real-examples

TSP — optimal route to visit all the countries in the world (image by author)

Have you ever wondered about the optimal route to visit all the countries in the world? The answer lies in a fascinating data science problem called the Traveling Salesman Problem (TSP). This algorithm seeks to find the shortest route for a salesman who needs to visit a set of cities, with the constraint that each city must be visited exactly once. In this blog post, we’ll delve into the world of TSP, exploring how it can help us plan our travels efficiently and showcasing some intriguing applications.

Understanding the Earth’s Surface

Before we embark on our journey, it’s essential to understand how TSP takes into account the actual distance on the Earth’s surface, known as the haversine distance. This is crucial because the Earth is round, and traditional Euclidean distance (straight line) is not suitable for measuring distances on a spherical object.

Source Photo by NASA on Unsplash + Author

Paris: A Touristic Example:

Let’s begin our exploration by examining the shortest route to visit touristic locations in Paris…