Previous versions of this page
Table of Contents
The travelling salesman problem (TSP) or travelling salesperson problem asks the following question:
Given a list of cities and the distances between each pair of cities, which is the shortest possible route that visits each city exactly once and returns to the origin city?
A discussion about the work of Hamilton & Kirkman can be found in the book Graph Theory (Biggs et al. 1976).
It is believed that the general form of the TSP have been first studied by Kalr Menger in Vienna and Harvard. The problem was later promoted by Hassler, Whitney & Merrill at Princeton. A detailed description about the connection between Menger & Whitney, and the development of the TSP can be found in On the history of combinatorial optimization (till 1960)
The simulated annealing algorithm was originally inspired from the process of annealing in metal work.
Annealing involves heating and cooling a material to alter its physical properties due to the changes in its internal structure. As the metal cools its new structure becomes fixed, consequently causing the metal to retain its newly obtained properties.
Pseudocode
Given an initial solution, the simulated annealing process, will start with a high temperature and gradually cool down until the desired temperature is reached.
For each temperature, a neighbouring new solution newSolution is calculated. The higher the temperature the higher the probability of accepting the new solution as a possible bester solution.
Once the desired temperature is reached, the best solution found is returned
Solution = initial_solution;
temperature = initial_temperature;
while (temperature > final_temperature) {
do tries_per_temperature times {
newSolution = neighbour(solution);
If P(E(solution), E(newSolution), T) >= random(0, 1)
solution = newSolution;
}
temperature = temperature * cooling factor;
}
Output: the best solution
pgRouting’s implementation adds some extra parameters to allow some exit controls within the simulated annealing process.
max_changes_per_temperature
:max_consecutive_non_changes
:max_processing_time
:Solution = initial_solution;
temperature = initial_temperature;
WHILE (temperature > final_temperature) {
DO tries_per_temperature times {
newSolution = neighbour(solution);
If Probability(E(solution), E(newSolution), T) >= random(0, 1)
solution = newSolution;
BREAK DO WHEN:
max_changes_per_temperature is reached
OR max_consecutive_non_changes is reached
}
temperature = temperature * cooling factor;
BREAK WHILE WHEN:
no changes were done in the current temperature
OR max_processing_time has being reached
}
Output: the best solution found
There is no exact rule on how the parameters have to be chose, it will depend on the special characteristics of the problem.
A recommendation is to play with the values and see what fits to the particular data.
The control parameters are optional, and have a default value.
Parameter  Type  Default  Description 

start_vid  BIGINT 
0  The greedy part of the implementation will use this identifier. 
end_vid  BIGINT 
0  Last visiting vertex before returning to start_vid. 
max_processing_time  FLOAT 
+infinity  Stop the annealing processing when the value is reached. 
tries_per_temperature  INTEGER 
500  Maximum number of times a neighbor(s) is searched in each temperature. 
max_changes_per_temperature  INTEGER 
60  Maximum number of times the solution is changed in each temperature. 
max_consecutive_non_changes  INTEGER 
100  Maximum number of consecutive times the solution is not changed in each temperature. 
initial_temperature  FLOAT 
100  Starting temperature. 
final_temperature  FLOAT 
0.1  Ending temperature. 
cooling_factor  FLOAT 
0.9  Value between between 0 and 1 (not including) used to calculate the next temperature. 
randomize  BOOLEAN 
true  Choose the random seed

Returns SET OF (seq, node, cost, agg_cost)
Column  Type  Description 

seq  INTEGER 
Row sequence. 
node  BIGINT 
Identifier of the node/coordinate/point. 
cost  FLOAT 

agg_cost  FLOAT 
