Click here to Skip to main content
14,241,236 members

Simulated Annealing - Solving the Travelling Salesman Problem (TSP)

Rate this:
4.70 (29 votes)
Please Sign up or sign in to vote.
4.70 (29 votes)
7 Jun 2008CPOL
This articles solves the Travelling Salesman Problem (TSP) using the Simulated Annealing Metaheuristic algorithm.


Combinatorial optimization is the process of finding an optimal solution for problems with a large discrete set of possible solutions. Such optimizations can be used to solve problems in resources management, operations management, and quality control, such as routing, scheduling, packing, production management, and resources assignment. Meta-heuristic algorithms have proved to be good solvers for combinatorial optimization problems, in a way that they provide good optimal solutions in a bounded (usually short) time.

Examples of meta-heuristics are: simulated annealing, tabu search, harmony search, scatter search, genetic algorithms, ant colony optimization, and many others. In this article, we will be discussing Simulated Annealing and its implementation in solving the Travelling Salesman Problem (TSP).


Simulated Annealing was given this name in analogy to the “Annealing Process” in thermodynamics, specifically with the way metal is heated and then is gradually cooled so that its particles will attain the minimum energy state (annealing). Then, the aim for a Simulated Annealing algorithm is to randomly search for an objective function (that mainly characterizes the combinatorial optimization problem).

Simulated Annealing's advantage over other methods is the ability to obviate being trapped in local minima. In here, we mean that the algorithm does not always reject changes that decrease the objective function but also changes that increase the objective function according to its probability function:

P = exp (-∆f/T)

Where T is the control parameter (analogy to temperature) and ∆f is the variation in the objective function.

The probability function is definitely a derivative of the Boltzmann probability distribution function.

Travelling Salesman Problem

A salesman wants to travel t o N cities (he should pass by each city). How can we order the cities so that the salesman’s journey will be the shortest? The objective function to minimize here is the length of the journey (the sum of the distances between all the cities in a specified order).

To start solving this problem; we need:

  1. Configuration setting: This is the permutation of the cities from 1 to N, given in all orders. Selecting an optimal one between these permutations is our aim.
  2. Rearrangement strategy: The strategy that we will follow here is replacing sections of the path, and replacing them with random ones to retest if this modified one is optimal or not.
  3. The objective function (which is the aim of the minimization): This is the sum of the distances between all the cities for a specific order.

Using the code

The class TravellingSalesmanProblem.cs does the job. Just instantiate a new object, and assign to it your adjacency matrix (which is a text file), then call the Anneal() method. The Anneal() method will return the shortest path (order of the cities).

TravellingSalesmanProblem problem = new TravellingSalesmanProblem();
problem.FilePath = "Cities.txt";

Below is the code for the Simulated Annealing algorithm:

/// <span class="code-SummaryComment"><summary></span>
/// Annealing Process
/// <span class="code-SummaryComment"></summary></span>
public void Anneal()
    int iteration = -1;

    double temperature = 10000.0;
    double deltaDistance = 0;
    double coolingRate = 0.9999;
    double absoluteTemperature = 0.00001;


    double distance = GetTotalDistance(currentOrder);

    while (temperature > absoluteTemperature)
        nextOrder = GetNextArrangement(currentOrder);

        deltaDistance = GetTotalDistance(nextOrder) - distance;

        //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) || (distance > 0 && 
             Math.Exp(-deltaDistance / temperature) > random.NextDouble()))
            for (int i = 0; i < nextOrder.Count; i++)
                currentOrder[i] = nextOrder[i];

            distance = deltaDistance + distance;

        //cool down the temperature
        temperature *= coolingRate;


    shortestDistance = distance;


  • Optimization by Simulated Annealing – S. Kirkpatrick
  • Simulated Annealing Overview - Franco Busetti
  • Metaheuristics Progress as Real Problem Solvers – Springer
  • Numerical Recipes in C: The Art of Scientific Computing


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Ali Hamdar
Software Developer (Senior) Integrated Digital Systems - IDS
Lebanon Lebanon
Been programming since 2001 interested in finance, security, workflows, SharePoint and algorithms. He is an MCSD, MCDBA, MCAD, MCSD, (again), MCTS, MCPD and MCT.
My Blog:

Comments and Discussions

QuestionGreat Pin
Member 1097635428-Jul-14 5:30
memberMember 1097635428-Jul-14 5:30 
Bugwrong implementation? Pin
Member 105815058-Feb-14 8:47
memberMember 105815058-Feb-14 8:47 
GeneralRe: wrong implementation? Pin
Member 1436409716-May-19 9:28
memberMember 1436409716-May-19 9:28 
QuestionWhat is the purpose of distance > 0 clause in if ((deltaDistance < 0) || (distance > 0 && Math.Exp(-deltaDistance / temperature) > random.NextDouble()))? Pin
Terry7608-Dec-13 16:23
memberTerry7608-Dec-13 16:23 
QuestionGreat example Pin
Petey Boy14-Sep-13 1:23
memberPetey Boy14-Sep-13 1:23 
Questionhi. i want to request Pin
masoum1239-Dec-12 8:00
membermasoum1239-Dec-12 8:00 
AnswerRe: hi. i want to request Pin
Petey Boy14-Sep-13 1:22
memberPetey Boy14-Sep-13 1:22 
Questionneed a job scheduling algoriothm Pin
523sahi7-Jan-12 23:36
member523sahi7-Jan-12 23:36 
AnswerRe: need a job scheduling algoriothm Pin
Petey Boy14-Sep-13 1:24
memberPetey Boy14-Sep-13 1:24 
Questionwhat are used value for SA parameters? Pin
aliebrahimi9845-Nov-11 1:19
memberaliebrahimi9845-Nov-11 1:19 
GeneralA few basic questions on the algorithm Pin
MikeChristensen1-Aug-10 21:17
memberMikeChristensen1-Aug-10 21:17 
QuestionWhat is "int iteration" used for? Pin
MikeChristensen1-Aug-10 20:34
memberMikeChristensen1-Aug-10 20:34 
Generalshortes path routing using non dominated sorting genetic algorithm Pin
rehvathi4-Nov-09 8:38
memberrehvathi4-Nov-09 8:38 
GeneralLet me give you a challenge Pin
William SerGio18-Sep-08 2:52
professionalWilliam SerGio18-Sep-08 2:52 
GeneralInteresting Pin
Saurabh.Garg11-Jun-08 15:43
subeditorSaurabh.Garg11-Jun-08 15:43 
GeneralRe: Interesting Pin
Ali Hamdar17-Jun-08 12:27
memberAli Hamdar17-Jun-08 12:27 
GeneralRe: Interesting Pin
Saurabh.Garg17-Jun-08 19:00
subeditorSaurabh.Garg17-Jun-08 19:00 
GeneralRe: Interesting Pin
Ali Hamdar18-Jun-08 1:52
memberAli Hamdar18-Jun-08 1:52 
GeneralRe: Interesting Pin
Saurabh.Garg18-Jun-08 2:17
subeditorSaurabh.Garg18-Jun-08 2:17 
GeneralRe: Interesting Pin
Naii24-Jun-12 2:15
memberNaii24-Jun-12 2:15 
GeneralInput string was not in a correct format. Pin
mashiharu10-Jun-08 11:58
membermashiharu10-Jun-08 11:58 
GeneralRe: Input string was not in a correct format. Pin
Ali Hamdar17-Jun-08 12:25
memberAli Hamdar17-Jun-08 12:25 
GeneralInteresting Pin
merlin9819-Jun-08 4:14
professionalmerlin9819-Jun-08 4:14 
GeneralHave to note Pin
User of Users Group7-Jun-08 12:31
memberUser of Users Group7-Jun-08 12:31 
GeneralRe: Have to note Pin
Ali Hamdar17-Jun-08 12:31
memberAli Hamdar17-Jun-08 12:31 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Posted 7 Jun 2008

Tagged as


61 bookmarked