×

Tabu search. (English) Zbl 0932.90031

Aarts, Emile (ed.) et al., Local search in combinatorial optimization. Chichester: Wiley. 121-136 (1997).
The method of tabu search is known since 1970s. The paper gives a short summary of its progress and modifies it for applying to some combinatorial problems. The authors suggest to enlarge a domain of search at each step and to apply a learning procedure to decrease the number of iteration. These improvements are realised for the quadratic assignment problem. A solution procedure for it is described in detail.
Then the proposed procedure is applied to the graph coloring problem. The course scheduling problem is formulated as graph coloring, that is the courses correspond to the vertices, an edge connects two vertices if the courses cannot be assigned at the same time, and the periods correspond to the colors. So this problem is equivalent to the graph coloring problem and tabu search can solve it in proposed manner.
The vehicle routing problem is similar to the well known travelling salesman problem but has some specialities. Initially \(m\) identical vehicles all are in some node of a graph, every node is visited exactly once. The problem is to find a summarized least-cost route. The length of any route and the capacity of a vehicle to serve nodes may be restricted. As the authors report this problem may be successfully solved by tabu search as well.
For the entire collection see [Zbl 0869.00019].

MSC:

90C27 Combinatorial optimization
90C05 Linear programming
PDFBibTeX XMLCite