The travelling salesman problem (TSP) is defined as follows, “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?”. Increasing the number of cities increases the number of possible routes enormously which makes this a tricky problem to solve or at least get within a small percentage of the optimal solution.
I picked 10 major cities from around the world for which Excel had the latitude and longitude in its geography data type and calculated the distance between each pair of cities using a VBA function detailed at the bottom of this post.
The cities were then randomly sorted, starting and finishing in London, and the total distance for the salesman’s journey calculated.
I wrote a very simplistic genetic algorithm in VBA to take the route and rearranged it a little before testing to see if the new route was longer or shorter than the previous route. The rearrangement swaps the position along the route of ten sets of two randomly selected cities before the length of the new route is tested.
A macro (findTheShortest) when called runs this process (processing) for 100,000 iterations keeping track of the shortest route found so far, at which iteration is was found, and the number of iterations so far completed. The VBA code for this is given below.
For the 10 cities chosen to visit during the roundtrip to London, the shortest route distance found was 56,541km. The 100,000 iterations were run a further five times, each time starting with the cities randomly ordered, and no shorter result was found.
Excel Solver found the same result (sometimes in the reverse order) in just a few seconds repeatedly starting with the route randomly shuffled, so it appears that the shortest possible route was most likely found.
Calculate the Distance Between Two Locations from their Latitudes and Longitudes
The distances between two location on Earth for which we know the latitude and longitude were calculated using the function below which takes into account the effect of the curvature of the Earth on the distance.
