Click here to Skip to main content
Click here to Skip to main content

Simulated Annealing - Solving the Travelling Salesman Problem (TSP)

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

Introduction

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).

Background

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";
problem.Anneal();

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;

    LoadCities();

    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;

        iteration++;
    }

    shortestDistance = distance;
}

References

  • 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

License

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

Share

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: www.alihamdar.com

Comments and Discussions

 
QuestionGreat PinmemberMember 1097635428-Jul-14 5:30 
Bugwrong implementation? PinmemberMember 105815058-Feb-14 8:47 
QuestionWhat is the purpose of distance > 0 clause in if ((deltaDistance < 0) || (distance > 0 && Math.Exp(-deltaDistance / temperature) > random.NextDouble()))? PinmemberTerry7608-Dec-13 16:23 
QuestionGreat example PinmemberPetey Boy14-Sep-13 1:23 
Questionhi. i want to request Pinmembermasoum1239-Dec-12 8:00 
AnswerRe: hi. i want to request PinmemberPetey Boy14-Sep-13 1:22 
Questionneed a job scheduling algoriothm Pinmember523sahi7-Jan-12 23:36 
Blush | :O
AnswerRe: need a job scheduling algoriothm PinmemberPetey Boy14-Sep-13 1:24 
Questionwhat are used value for SA parameters? Pinmemberaliebrahimi9845-Nov-11 1:19 
GeneralA few basic questions on the algorithm PinmemberMikeChristensen1-Aug-10 21:17 
QuestionWhat is "int iteration" used for? Pinmemberimaudi@comcast.net1-Aug-10 20:34 
Generalshortes path routing using non dominated sorting genetic algorithm Pinmemberrehvathi4-Nov-09 8:38 
GeneralLet me give you a challenge PinmemberGUI Developer18-Sep-08 2:52 
GeneralInteresting PinmemberSaurabh.Garg11-Jun-08 15:43 
GeneralRe: Interesting PinmemberAli Hamdar17-Jun-08 12:27 
GeneralRe: Interesting PinmemberSaurabh.Garg17-Jun-08 19:00 
GeneralRe: Interesting PinmemberAli Hamdar18-Jun-08 1:52 
GeneralRe: Interesting PinmemberSaurabh.Garg18-Jun-08 2:17 
GeneralRe: Interesting PinmemberNaii24-Jun-12 2:15 
GeneralInput string was not in a correct format. Pinmembermashiharu10-Jun-08 11:58 
GeneralRe: Input string was not in a correct format. PinmemberAli Hamdar17-Jun-08 12:25 
GeneralInteresting Pinmembermerlin9819-Jun-08 4:14 
GeneralHave to note PinmemberUser of Users Group7-Jun-08 12:31 
GeneralRe: Have to note PinmemberAli Hamdar17-Jun-08 12:31 

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

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

| Advertise | Privacy | Mobile
Web03 | 2.8.140821.2 | Last Updated 7 Jun 2008
Article Copyright 2008 by Ali Hamdar
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid