Editing Tabu search (section)

==Example: the traveling salesman problem==

The [[traveling salesman problem]] (TSP) is sometimes used to show the functionality of tabu search.<ref name="malek89"/> This problem poses a straightforward question: given a list of cities, what is the shortest route that visits every city? For example, if city&nbsp;A and city&nbsp;B are next to each other, while city&nbsp;C is farther away, the total distance traveled will be shorter if cities A and&nbsp;B are visited one after the other before visiting city&nbsp;C. Since finding an optimal solution is [[NP-hard]], heuristic-based approximation methods (such as local searches) are useful for devising close-to-optimal solutions. To obtain good TSP solutions, it is essential to exploit the graph structure. The value of exploiting problem structure is a recurring theme in metaheuristic methods, and tabu search is well-suited to this. A class of strategies associated with tabu search called ejection chain methods has made it possible to obtain high-quality TSP solutions efficiently <ref name="gamboa2005">{{cite journal
 |author1=D. Gamboa, C. Rego  |author2=F. Glover
  |name-list-style=amp | year = 2005
 | title = Data Structures and Ejection Chains for Solving Large Scale Traveling Salesman Problems
 | journal = European Journal of Operational Research
 | volume = 160
 | issue = 1
 | pages = 154–171
 | doi=10.1016/j.ejor.2004.04.023|citeseerx=10.1.1.417.9789
  }}
</ref>

On the other hand, a simple tabu search can be used to find a [[satisficing]] solution for the traveling salesman problem (that is, a solution that satisfies an adequacy criterion, although not with the high quality obtained by exploiting the graph structure). The 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 – i.e., repeatedly visiting a particular set of solutions – and to avoid becoming stuck in [[local optima]], a solution is added to the tabu list if it is accepted into the solution neighborhood, <math>N^*(x)</math>.

New solutions are created until some stopping criterion, such as an arbitrary number of iterations, is met. Once the simple tabu search stops, it returns the best solution found during its execution.