Tabu Search Modern Heuristic Techniques for Combinatorial Problems

Tabu Search I 49
Woodruff and Speannan (1992) present a highly innovative TS procedure for production scheduling, addressing a general sequencing problem that includes two classes of jobs with setup times, setup costs, holding costs and deadlines. A TS method is used with insertion moves to transform one trial solution into another. Due to the presence of deadline constraints, not every sequence is feasible. However, the search path is allowed to visit infeasible solutions by a form of strategic oscillation. A candidate list is also used as a means of reducing the computational effort involved in evaluating a given neighborhood. Diversification is achieved by introducing a parameter d into the cost function. Low values of d result in the selection of the best available move (with reference to the objective function value) as customarily done in a deterministic tabu search, while high values result in a randomized move selection which resembles a variant of probabilistic tabu search.

The tabu list designed for this approach is based on the concept of hashing functions. The list is composed of two entries for each visited sequence, the cost and the value of a simple hashing function (i.e., a value that represents the ordering of jobs in the sequence). Computational experiments were conducted on simulated data that captured the characteristics of the demand and production environment in a large circuit board plant. For a set of twenty test problems, the average deviation from optimality was 3% and optimal solutions were achieved in seventeen cases. The best solutions were found during searches using d values other than zero, which supports the contention that long term memory considerations become important in complex problem settings. This study also marks the fIrst application of TS where hashing functions are used to control the tabu structures. A more detailed study on these kinds of functions and their use within the TS framework is given in Woodruff and Zemel (1993).

The fIrSt parallel implementation of tabu search to appear in the literature is due to Malek, et ai. (1989). In this implementation, each child process runs a copy of a serial TS method with different parameter settings (i.e., tabu list size and tabu restrictions). After specified intervals, the child processes are halted and the main process compares their results. The main process then selects the "best" solution found and gives it as the initial solution to all the child processes. The "best" solution is generally the one with the least tour cost, but an alternative solution is passed if the tour has been used before. The tabu data structures are blanked every time that the child process are temporarily stopped. This scheme requires little overhead due to interprocessor communication, and implements an intensification phase around "good" solutions that is not easily reproduced in a serial environment. This research shows the importance of parallel computing in solving large combinatorial optimization problems, and also it illustrates one possibility for exploiting the flexibility of tabu search in this kind of environment Joining such an approach with the use of stronger move neighborhoods, such as those of Gendreau, Hertz, and Laporte (1991) or of Glover (1991a), may be expected to yield additional improvements.

Chakrapani and Skorin-Kapov (1993) present a parallel implementation on the Connection Machine CM-2 of a TS method for the quadratic assignment problem. The implementation uses n2 processors, where n is the size of the problem. A moving gap strategy is used to dynamically

50 I GLOVER and LAGUNA
vary the tabu tenure. Additional intensification and diversification are achieved via frequency based memory. The procedure proves to be very effective in term of solution quality. The largest problems that can be currently solved by exact methods are of size n = 20. The authors' method easily matches all known optimal solutions and also matches best known solutions for additional problems of size up to n = 80. (These solutions were obtained by a TS procedure due to Taillard (1991).) In addition the study by Chakrapani and Skorin-Kapov repons new best solutions to a set of published problems of size n = 100. A careful implementation on the Connecti.on Machine, a massively parallel system, proves to be extremely suitable in this context. The increase in time per iteration appears to be a logarithmic function of n. This study also offers directions for alternative implementations that may be more efficient when solving very large quadratic

assignment problems. Vehicle routing constitutes another important area with many practical applications. Several TS variants and a hybrid simulated annealing I TS approach for the vehicle routing problem under capacity and distance constraints are presented by Osman (1993). The neighborhoods are defined using a so called A-interchange. The hybrid simulated annealing approach, which uses a nonmonotonic TS strategy for adjusting temperatures, improves significantly over a standard SA. The hybrid approach produces new best solutions for 7 instances in a set of 14 previously published problems. However, this approach exhibits a large variance with regard to solution quality and computational time. The pure TS methods also find 7 new best solutions to problems in the same set, and in addition they maintain a good average solution quality without excessive computational effort. The procedures developed by Osman are easily adapted to the vehicle routing problem with different vehicle sizes.

Gendreau, Henz, and Laporte (1991) also develop a TS procedure for vehicle routing, using a somewhat different move neighborhood than used by Osman (1993). Their' approach is tested against the previously reigning best solution approaches in the literature, and outperforms all of them in most problems. Interestingly, in spite of the different choice of move neighborhoods, their results are quite closely comparable to those of Osman.

Semet and Taillard (1993) address a difficult version of the vehicle routing problem with many complicating side conditions, including different vehicle types and sizes, different regions, and restricted delivery windows. Their outcomes improve significantly over those previously obtained for those problems, and again demonstrate the ability of tabu search to be adapted to handle diverse real world features.

One of the first TS methods to use more than one tabu list is due to Gendreau, Soriano, and Salvail (1991), which is designed to solve the maximum clique problem in graphs. The method uses add-delete moves to define neighborhoods for the current solutions and a tabu list to store the indexes of the vertices most recently deleted. A second list is used to record the solutions visited during a specified number of most recent iterations. The second list is always active while the first one is only consulted when "augmenting" moves are considered (i.e., moves that increase the size of the current clique). Storing previously visited solutions as part of the tabu structure is unusual