13,344,508 members (48,714 online)
Add your own
alternative version

#### Stats

133.4K views
7.4K downloads
60 bookmarked
Posted 7 Jun 2008

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

## About the Author

 Software Developer (Senior) Integrated Digital Systems - IDS 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

 First Prev Next
 Great Member 1097635428-Jul-14 6:30 Member 10976354 28-Jul-14 6:30
 wrong implementation? Member 105815058-Feb-14 9:47 Member 10581505 8-Feb-14 9:47
 What is the purpose of distance > 0 clause in if ((deltaDistance < 0) || (distance > 0 && Math.Exp(-deltaDistance / temperature) > random.NextDouble()))? Terry7608-Dec-13 17:23 Terry760 8-Dec-13 17:23
 Great example Petey Boy14-Sep-13 2:23 Petey Boy 14-Sep-13 2:23
 hi. i want to request masoum1239-Dec-12 9:00 masoum123 9-Dec-12 9:00
 Re: hi. i want to request Petey Boy14-Sep-13 2:22 Petey Boy 14-Sep-13 2:22
 need a job scheduling algoriothm 523sahi8-Jan-12 0:36 523sahi 8-Jan-12 0:36
 Re: need a job scheduling algoriothm Petey Boy14-Sep-13 2:24 Petey Boy 14-Sep-13 2:24
 what are used value for SA parameters? aliebrahimi9845-Nov-11 2:19 aliebrahimi984 5-Nov-11 2:19
 A few basic questions on the algorithm MikeChristensen1-Aug-10 22:17 MikeChristensen 1-Aug-10 22:17
 What is "int iteration" used for? imaudi@comcast.net1-Aug-10 21:34 imaudi@comcast.net 1-Aug-10 21:34
 shortes path routing using non dominated sorting genetic algorithm rehvathi4-Nov-09 9:38 rehvathi 4-Nov-09 9:38
 Let me give you a challenge GUI Developer18-Sep-08 3:52 GUI Developer 18-Sep-08 3:52
 Interesting Saurabh.Garg11-Jun-08 16:43 Saurabh.Garg 11-Jun-08 16:43
 Re: Interesting Ali Hamdar17-Jun-08 13:27 Ali Hamdar 17-Jun-08 13:27
 Re: Interesting Saurabh.Garg17-Jun-08 20:00 Saurabh.Garg 17-Jun-08 20:00
 Re: Interesting Ali Hamdar18-Jun-08 2:52 Ali Hamdar 18-Jun-08 2:52
 Re: Interesting Saurabh.Garg18-Jun-08 3:17 Saurabh.Garg 18-Jun-08 3:17
 Re: Interesting Naii24-Jun-12 3:15 Naii 24-Jun-12 3:15
 Input string was not in a correct format. mashiharu10-Jun-08 12:58 mashiharu 10-Jun-08 12:58
 Re: Input string was not in a correct format. Ali Hamdar17-Jun-08 13:25 Ali Hamdar 17-Jun-08 13:25
 Interesting merlin9819-Jun-08 5:14 merlin981 9-Jun-08 5:14
 Have to note User of Users Group7-Jun-08 13:31 User of Users Group 7-Jun-08 13:31
 Re: Have to note Ali Hamdar17-Jun-08 13:31 Ali Hamdar 17-Jun-08 13:31
 Last Visit: 31-Dec-99 19:00     Last Update: 16-Jan-18 18:33 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

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

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.180111.1 | Last Updated 7 Jun 2008
Article Copyright 2008 by Ali Hamdar
Everything else Copyright © CodeProject, 1999-2018
Layout: fixed | fluid