5,693,062 members and growing! (17,436 online)
Email Password   helpLost your password?
General Programming » Algorithms & Recipes » Algorithms     Advanced License: The Code Project Open License (CPOL)

Simulated Annealing - Solving the Travelling Salesman Problem (TSP)

By Ali Hamdar

This articles solves the Travelling Salesman Problem (TSP) using the Simulated Annealing Metaheuristic algorithm.
C# (C# 1.0, C# 2.0, C# 3.0, C#), .NET, Dev

Posted: 7 Jun 2008
Updated: 7 Jun 2008
Views: 8,953
Bookmarked: 24 times
Announcements
Loading...



Search    
Advanced Search
Sitemap
14 votes for this Article.
Popularity: 5.06 Rating: 4.42 out of 5
1 vote, 7.1%
1
0 votes, 0.0%
2
1 vote, 7.1%
3
2 votes, 14.3%
4
10 votes, 71.4%
5

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:

/// <summary>
/// Annealing Process
/// </summary>
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)

About the Author

Ali Hamdar


Been programming since 2001 while pretending to be a mind reader, psychologist, defense intelligence researcher, financial analyst, portfolio manager and at last a developer. He is an MCSD, MCDBA, MCAD, MCSD (again) and MCT.
http://www.ids.com.lb
Occupation: Web Developer
Company: Integrated Digital Systems - IDS
Location: Lebanon Lebanon

Other popular Algorithms & Recipes articles:

Article Top
Sign Up to vote for this article
You must Sign In to use this message board.
FAQ FAQ Noise ToleranceSearch Search Messages 
 Layout  Per page   
 Msgs 1 to 11 of 11 (Total in Forum: 11) (Refresh)FirstPrevNext
GeneralLet me give you a challengememberGUI Developer3:52 18 Sep '08  
GeneralInterestingmemberSaurabh.Garg16:43 11 Jun '08  
GeneralRe: InterestingmemberAli Hamdar13:27 17 Jun '08  
GeneralRe: InterestingmemberSaurabh.Garg20:00 17 Jun '08  
GeneralRe: InterestingmemberAli Hamdar2:52 18 Jun '08  
GeneralRe: InterestingmemberSaurabh.Garg3:17 18 Jun '08  
GeneralInput string was not in a correct format.membermashiharu12:58 10 Jun '08  
GeneralRe: Input string was not in a correct format.memberAli Hamdar13:25 17 Jun '08  
GeneralInterestingmembermerlin9815:14 9 Jun '08  
GeneralHave to notememberUser of Users Group13:31 7 Jun '08  
GeneralRe: Have to notememberAli Hamdar13:31 17 Jun '08  

General General    News News    Question Question    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

PermaLink | Privacy | Terms of Use
Last Updated: 7 Jun 2008
Editor: Smitha Vijayan
Copyright 2008 by Ali Hamdar
Everything else Copyright © CodeProject, 1999-2008
Web18 | Advertise on the Code Project