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:

    You don’t want a general houseworker, do you? Or a traveling companion, quiet, refined, speaks fluent French entirely in the present tense? Or an assistant billiard-maker? Or a private librarian? Or a lady car-washer? Because if you do, I should appreciate your giving me a trial at the job. Any minute now, I am going to become one of the Great Unemployed. I am about to leave literature flat on its face. I don’t want to review books any more. It cuts in too much on my reading.
    Dorothy Parker (1893–1967)

    [Oliver North is a] document-shredding, Constitution-trashing, Commander in Chief-bashing, Congress-thrashing, uniform-shaming, Ayatollah-loving, arms-dealing, criminal-protecting, résumé-enhancing, Noriega-coddling, Social
    Security-threatening, public school-denigrating, Swiss-banking-law-breaking, letter-faking, self-serving, election-losing, snake-oil salesman who can’t tell the difference between the truth and a lie.
    Charles S. Robb (b. 1939)

    The problem with marriage is that it ends every night after making love, and it must be rebuilt every morning before breakfast.
    —Gabriel García Márquez (b. 1928)