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/
Hi! I am a robot. I just upvoted you! I found similar content that readers might be interested in:
https://blog.algorithmia.com/traveling-salesman-by-api/
Congratulations @akadal! You have completed some achievement on Steemit and have been rewarded with new badge(s) :
Click on any badge to view your own Board of Honor on SteemitBoard.
For more information about SteemitBoard, click here
If you no longer want to receive notifications, reply to this comment with the word
STOPCongratulations @akadal! You have completed some achievement on Steemit and have been rewarded with new badge(s) :
Click on any badge to view your own Board of Honor on SteemitBoard.
For more information about SteemitBoard, click here
If you no longer want to receive notifications, reply to this comment with the word
STOPA good post. Correct me if I am wrong, but shouldn't there be a breeding/mating part included, which helps improving the fitness with every new generation? I could see an improved version of this algorithm where instead of selecting cities on a purely random basis, it features a weighted random selection based on the positions of cities within two or three winning "parents" from the previous generation. It's just an idea, but I might be working on it to see the results.