25-08-2017, 09:32 PM
A Comparative Study of Tabu Search and Simulated Annealing for Traveling Salesman Problem
tsp using ts.pdf (Size: 105.32 KB / Downloads: 489)
Introduction
A Classical Traveling Salesman Problem (TSP) can be defined as a problem where starting from a node it is required to visit every other node only once in a way that the total distance covered is minimized. This can be mathematically stated as follows [2]:
Tabu Search for TSP
Tabu Search is a heuristic that, if used effectively, can promise an efficient near-optimal solution to the TSP. The basic steps as applied to the TSP in this paper are presented below:
Simulated Annealing for TSP
The basic steps of Simulated Annealing (SA) applied to the TSP are described below. The solution representation and the algorithm for initial solution for the SA are same as that for Tabu Search described above.
1. Neighborhood: At each step, a neighborhood solution is selected by an exchange of a randomly selected pair of nodes. The randomly generated neighbor solution is selected if it improves the solution else it is selected with a probability that depends on the extent to which it deteriorates from the current solution.
2. Termination criteria: The algorithm terminates if it meets any one of the following criteria:
a. It reaches a pre-specified number of iterations.
b. There is no improvement in the solution for last pre-specified number of iterations.
c. Fraction of neighbor solutions tried that is accepted at any temperature reaches a pre-specified minimum.
The maximum number of iterations is kept large enough to allow the process to terminate either using criterion b or c.