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:
“I believe the alphabet is no longer considered an essential piece of equipment for traveling through life. In my day it was the keystone to knowledge. You learned the alphabet as you learned to count to ten, as you learned “Now I lay me” and the Lord’s Prayer and your father’s and mother’s name and address and telephone number, all in case you were lost.”
—Eudora Welty (b. 1909)
“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)
“Give a scientist a problem and he will probably provide a solution; historians and sociologists, by contrast, can offer only opinions. Ask a dozen chemists the composition of an organic compound such as methane, and within a short time all twelve will have come up with the same solution of CH4. Ask, however, a dozen economists or sociologists to provide policies to reduce unemployment or the level of crime and twelve widely differing opinions are likely to be offered.”
—Derek Gjertsen, British scientist, author. Science and Philosophy: Past and Present, ch. 3, Penguin (1989)