/simulated-annealing-tsp

Simulated Annealing algorithm to solve Travelling Salesmen Problem in Python

Primary LanguagePythonMIT LicenseMIT

FASTER Simulated Annealing algorithm to solve Travelling Salesman Problem in Python

⚠ What's different about my version vs original is that it doesn't recalculate whole length every time and instead considers the difference. However, would be faster still if reversing was to be done only when actually needed. Also, for an even more optimal solution in case of a large number of nodes, one could store links from nodes to nodes instead of a direct array path.

Using simulated annealing metaheuristic to solve the travelling salesman problem, and visualizing the results.

Starts by using a greedy algorithm (nearest neighbour) to build an initial solution.

A simple implementation which provides decent results.

An example of the resulting route on a TSP with 100 nodes.

Route Graph

The fitness (objective value) through iterations.

Learning Plot

References Kirkpatrick et al. 1983: "Optimization by Simulated Annealing"

http://www.blog.pyoung.net/2013/07/26/visualizing-the-traveling-salesman-problem-using-matplotlib-in-python/