Solving Traveling Salesman Problem with Genetic Algorithm on Real World Map!

Traveling Salesman is one of the classic NP-Hard problems: finding the optimal solution can take a long time. It is easy to see the solution for a small number of cities: you just look at all the possible routes and add up the distances (or travel times) for each possible solution.

Unfortunately, as the number of cities grows, the number of comparisons you have to make increases very rapidly. Traveling to 3 cities requires 3 comparisons, but traveling to 4 cities requires 12, 5 cities require 60 comparisons, and so on. Now, we can see that solving this problem for a large number of cities is very computationally expensive, to the point of being impossible for very large trips.

When you can’t get a perfect solution before the heat-death of the universe, you have to approximate. There are lots of ways to do so, but Genetic Algorithms offer a particularly clever and useful approach. In a nutshell, we start by randomly selecting a few possible solutions. In this case, we several initial travel routes: each one contains all the cities we want to go to, but their order is randomly selected. We calculate the total travel distance for each one, and pick the top few, discarding the rest. These “round one” winners move on to the second round, during which a few of the cities’ orders are swapped around. Then, we add more randomly-generated routes, and do it again. We repeat this whole process for many rounds, permuting the winners each time, and adding random new routes as well.

After enough repetitions, good solutions arise, and we pick the best one. It may not be perfect… the algorithm does the best it can within some reasonable time constraints, but we can’t be 100% certain that a better one doesn’t exist. But most of the time, the route that emerges is only a few percentage points longer than the truly optimal route (and, sometimes, we happen to get the perfect one)!

You can try and use this algorithm on https://algorithmia.com/algorithms/akadal/TSP

References

Akadal, E., Saylan, S., 2016, Gerçek dünya haritası üzerinde genetik algoritmalarla gezgin satıcı problemi uygulaması, R ile Veri Madenciliği Uygulamaları, Çağlayan Kitabevi, Istanbul Turkey, 183-205.

Peck, J., 2017, Traveling Salesman by API, Retrieved from: https://blog.algorithmia.com/traveling-salesman-by-api/