TSP Simulator based on Simulated Annealing Technique

Traveling Salesman Problem is one of the very interesting topics among algorithm enthusiast. The problem definition is very simple. 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? It is an NP hard problem with no polynomial time algorithm known till date. It finds several important real life application such as routing and floor planning of Integrated Circuits, Mechanical Arm sequencing etc.
More regarding this interesting problem can by found on Wikipedia(TSP).
Simulated Annealing algorithm is a generic probabilistic metaheuristic technique for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. Simulated Annealing can be used for solving several optimization problems. TSP is one of them.



In this post I am showcasing the application of Simulated Annealing technique for solving TSP. The pseudo code for mapping TSP on simulated annealing is as shown below.

TSPSimulatedAnnealing(GRAPH G)
    Temperature = <Initial Value> //Eg 1000
    DeltaDistance = 0
    CoolingRate  = <CoolingRate> //EG 0.999
    FinalTemperature =  <Final Value> //Eg 0.01
    CurrentCost = GetTotalDistance(CurrentOrder,G);
    Repeat While (Temperature  > FinalTemperature)
        Begin
            NextOrder = GetNextArrangement(CurrentOrder,G);
            DeltaDistance = GetTotalDistance(NextOrder,G) - CurrentCost;
            //if the new order has a smaller distance or if the new order has a larger distance 

            //but satisfies Boltzman condition then accept the arrangement
            If ((DeltaDistance < 0) || (CurrentCost > 0 && Exp(-DeltaDistance / Temperature) > RANDOM.NextDouble(0,1)))
            BEGIN        
                CurrentOrder = NextOrder ;
                CurrentCost = DeltaDistance + CurrentCost;
            END
            //cool down the temperature
            Temperature =  Temperature  * CoolingRate;
        End
    ShortestDistance =  CurrentCost;
    ShortedOrder     =  CurrentOrder;

There are several variations possible for running the SA algorithm such as changing the Initial and Final Temperature, changing the cooling rate. I have built a generic simulator using C# language to showcase the working of SA algorithm to solve TSP. Following is the snapshot of TSP simulator with 15 cities picked randomly.

I captured the simulation in the video that shows how the algorithm searches through the node and tries to converge at a solution. There is an option available to run the search multiple times after altering the Temperatures and Cooling rate.

I am sharing the source code of the console application written in C++. The snapshot and videos posted above are from a Windows App I developed using C#.  If anyone needs the complete windows application then please get back to me or leave you email ID in the comment section.


Console Application Source Code: tsp_console_app

Enjoy reading..