Tabu Search - Example: Traveling Salesman Problem

Example: Traveling Salesman Problem

The traveling salesman problem (TSP) is often used to show the functionality of tabu search. This problem poses a straightforward question - given a list of cities, is there a way to order that list to minimize the distance travelled while still visiting every city. For example, if city A and city B are next to each other, while city C is farther away, the total distance traveled will be shorter if cities A and B are visited one after the other before visiting city C. Since finding an optimal solution to the TSP is an NP-hard task, heuristic-based approximation methods (such as local searches) are useful for devising close-to-optimal solutions.

Tabu search can be used to find a satisficing solution for the traveling salesman problem (that is, a solution that satisfies an adequacy criterion, rather than the absolutely optimal solution). First, the tabu search starts with an initial solution, which can be generated randomly or according to some sort of nearest neighbor algorithm. To create new solutions, the order that two cities are visited in a potential solution is swapped. The total traveling distance between all the cities is used to judge how ideal one solution is compared to another. To prevent cycles and to avoid becoming stuck in local optima, a solution is added to the tabu list if it is accepted into the solution neighborhood, .

New solutions continue to be created until some stopping criteria, such as an arbitrary number of iterations, is met. Once the tabu search stops, the best solution returned is the solution with the shortest distance traveled while visiting all cities.