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.

Read more about this topic:  Tabu Search

Famous quotes containing the words traveling, salesman and/or problem:

    We joined long wagon trains moving south; we met hundreds of wagons going north; the roads east and west were crawling lines of families traveling under canvas, looking for work, for another foothold somewhere on the land.... The country was ruined, the whole world was ruined; nothing like this had ever happened before. There was no hope, but everyone felt the courage of despair.
    Rose Wilder Lane (1886–1968)

    Nobody dast blame this man.... For a salesman, there is no rock bottom to the life. He don’t put a bolt to a nut, he don’t tell you the law or give you medicine. He’s a man way out there in the blue, riding on a smile and a shoeshine. And when they start not smiling back—that’s an earthquake. And then you get yourself a couple of spots on your hat, and you’re finished. Nobody dast blame this man. A salesman is got to dream, boy. It comes with the territory.
    Arthur Miller (b. 1915)

    Involuntary mental hospitalization is like slavery. Refining the standards for commitment is like prettifying the slave plantations. The problem is not how to improve commitment, but how to abolish it.
    Thomas Szasz (b. 1920)