5. Choice of Short Term Memory Structure

Short term memory structures are used in tabu search to prevent the search from re-visiting solutions that it has visited in the immediate past. They are normally stored as a collection of forbidden moves in a list called the tabu list. Each move in the tabu list remains in the list for a pre-specified number of tabu search iterations. This number is called its tabu tenure. Tabu search implementations either keep the tabu tenure as a fixed number or one that changes deterministically with algorithm parameters (e.g., the number of tabu search iterations already executed) or problem parameters (e.g., problem size) or generate the tenure randomly within a pre-specified range. We refer to the first two kinds of tabu tenure as static tabu tenures, and the second one as random tabu tenure.

5.1. Static Tabu Tenure

47 of the instances in papers that we surveyed dealt with non-random tabu tenures. Of those, 26 dealt with tabu tenures that were fixed, and the other 21 instances dealt with tabu tenures that varied with the number of iterations already performed by tabu search, or with the instance size. While varying with number of iterations, search procedure actually sees the change in solution quality to determine the updated tabu tenure values. Table 4 provides a list of the papers that dealt with fixed tabu tenures. Table 5 presents a group of papers by the

parameter that they use to determine the tabu tenure.

From Table 4 we see that the range of values for the tabu tenure lies mostly in between 5 to 25 across years. Further, nearly 60% of these papers use tabu tenures between 5 and 14. In papers like [26,43,70], the authors conducted experiments to see the effect of different tenure values on solution quality. In [26], the authors showed that static tenure outperforms all other kinds of tabu tenures in tabu search applied to TSPs. Of the different non-random tabu tenures used, a tabu tenure of 15 emerges as the best choice in [26]. In [70], the authors attempted to find out optimal tabu tenures for different sets of problems but were unable to generate any universal recommendation.

From Table 5, we observe that most of the papers that do not fix tabu tenure irrespective of the problem instance vary the tabu tenure based on the problem size. Only one of the papers that we surveyed ([37] for VRPs), describes an elaborate mechanism for determining the tabu tenure. In that paper describing tabu search implementation in VRP context by Osman, the tenure value depends on four problem parameters; a customer identification number, a vehicle identification number, a capacity ratio of the demand to the available vehicle capacities, and the type of moves considered. It was shown through computational experiments that results obtained by using this strategy gave a better solution than simulated annealing results, although the paper did not compare its strategy with other variants of tabu search.

There is also a more formalized approach called the functional approach (see e.g., [8,9]) to determine tabu tenures. In this approach the tabu tenure is determined using a function of problem specific parameters. The form of the function is pre-specified. The coefficients of the function are derived by regressing tenure value over other problem parameters for the best solutions found. In some papers like [5,35,44,58,71], the functional approach is followed to determine static tabu tenures. In [5,58], the form of the function is logarithmic, while in [35], both logarithmic and linear functions are used. The size of the TSP instance is taken as the only independent variable during regression in these papers. A detailed comparison of such static tabu tenures over different problem sizes appears in [29]. In this paper, tabu tenures ranging from n/32 to 3n/2 (where n is the size of the TSP) were tested for TSPs with sizes varying between 20 and 100 nodes. The paper concludes that the tabu tenure should be within n/8 and n/4 for 2-opt moves, and between n/16 and n/8 for 3-opt moves.

5.2. Random Tabu Tenure

The change of tabu tenure from deterministic to random was initiated in [74] for the quadratic assignment problem. Among the papers we surveyed, in 23 instances authors used random tabu tenures. In all of these papers, tabu tenures are picked randomly from a uniform distribution with fixed lower and upper bounds. In $10$ papers, the limits of the distributions from which the tabu tenure is drawn varied with the problem size or number of iterations. Table 6 summarizes the range of tabu tenures in papers where the support of the distribution from which tabu tenures did not depend on the problem being solved. It shows that the support of the distribution from which tabu tenure values were drawn was [5,10] in a majority of the papers. This support was first used in [36] and was motivated by a suggestion in [75].

Reference [38] influenced the trend of making tabu tenures depend on problem and search characteristics. In

this paper, the authors modified the tabu tenure based on solution values in previous iterations. After this, 10 papers have appeared in the literature in which the support of the distribution from which the tabu tenure is chosen is based on the problem being solved. All of them (except [52] and [53]), considered instances with between 50 and 150 nodes. Reference [53] considered instances with 400 nodes.

Most of the work on the dependence of tabu tenure on instance size is due to Cordeau, Gendreau and their coauthors. They developed a functional relation for the ranges of distribution based on the instance size. There are however two distinct trends in the modeling of the dependence. In [11,13,47], the support of the distribution from which tabu tenures are chosen were directly proportional to the problem size, while in [34,58], the dependence is logarithmic. There is no empirical evidence to show that one of these forms is better than the other.

6. Choice of Intermediate Term Memory Structure

Intermediate term memory structures are used in tabu search to intensify the search by restricting it to promising regions of the solution space. We found 24 instances in the papers reviewed implemented intermediate term memory structures. We classify the strategies used into the following broad four categories:

Strategy IT1: Edges that occur frequently in low cost tours are forced into candidate tours for next few iterations.

Strategy IT2: The search is re-started with a tour that was one of the lower cost tours found in previous iterations.

Strategy IT3: Higher probabilities are assigned to include the edges common to previously encountered low cost tours in a probabilistic tabu search.

Strategy IT4: Changing tabu tenure (in comparison to existing tenure value) whenever a local optimum is reached.

As mentioned in the previous sections, we ignored minor deviations from the categories identified for grouping convenience. Table 8 presents information about the use of the four strategies. We see that the first two strategies have been used in two-third of the papers cited. Strategy IT1 has a wide acceptability because it restricts the solution space. In Strategy IT2, the search is re-initiated from a promising region without any particular restriction in the search process. The scarcity of papers involving Strategy IT3 is expected, because it works for probabilistic tabu search, which itself is not frequently used. In some papers (see e.g., [24,38,57]), more than one of these strategies are used together.

7. Choice of Long Term Memory Structure

Tabu search uses long term memory structures to diversify the search to new regions in the solution space. We found 34 instances in papers that used long term memory structures to achieve diversification. We list the broad strategies used below.

Strategy LT1 is a frequency based diversification scheme implemented by adding a penalty value to the cost of each edge. The penalty is proportional to the number of times the edge appeared in previously visited tours. The objective here is to create a disincentive for including edges that were often encountered previously.

Strategy LT2 is a modification of strategy LT1, in which the penalty value also includes terms that are not dependent on frequency measures.

Strategy LT3 attains diversification by changing the way in which tours are evaluated in order to move the search to new parts of the search space. It may also involve changing the move being used in the search.

Strategy LT4 creates a diversification mechanism by changing the stopping criterion to allow more non-improving moves.

Strategy LT5 is a diversification scheme which restarts tabu search iteration from different initial solutions. It helps to change the initial search space and creates a chance to reach to a different solution region.

Strategy LT6 is used in some papers for diversification if no improvement is seen in the best tour cost for certain number of iterations, diversification is attained by adding a parameter called influence measure to the tour costs for neighboring solutions. The influence measure measures the degree of similarity between two consecutive solutions.

This list of diversification strategies is not exhaustive and we clubbed minor variations of some strategies into broad categories defined above.

Table 9 presents the usage of long term memory structures in the tabu search literature on TSP and VRP. It is

clear from the table that Strategy LT1 is the most commonly used strategy for using long term memory structures. Reference [36] used Strategy LT2 for the first time in their tabu search implementation. In their implementation, the penalty value was dependent on a factor equal to absolute difference between two successive values of objective function, the square root of the neighborhood size for a particular move, and a scaling factor to control the intensity of diversification to be achieved. The concept of a scaling factor was also used in [5,34, 35,58], among others. Reference [24] used Strategy LT3 in their tabu search implementation. They modified the cost of tours to facilitate the inclusion of non-frequent moves. In the tabu search implementation in [33], edges do not enter the tabu list if the cost of the tour is within 10% of the cheapest tour up to that iteration. In reference [20], Or-opt moves were used instead of 2-opt move when it could not improve the best tour for a specific number of iterations. References [60,62] used influence measures to diversify their tabu search. By inserting this expression in the objective function, they restricted moves to visit similar kinds of tours.

8. Aspiration Criteria

Aspiration criteria are a set of conditions which if satisfied, permits tabu search to make use of tabu moves to reach neighboring solutions. 40 of the papers that we reviewed used aspiration criteria. Although the design of aspiration criteria can be finely tuned, all the papers except [58] chose to overrule the tabu status of moves if they allowed the search to find a tour that was better than the best found until that iteration. [58] developed attribute specific adaptive aspiration level functions instead of taking solution values.

9. Conclusion and Future Directions

In this literature, we examine various aspects of tabu search implementation in the context of TSP and allied problems. We reviewed this literature from implementation as well as from methodological point of view. While seeing the implementation aspect, we find from Table 1 that most of the papers do not address a practically sized large problem size. More than 40% of the papers chose a problem size of 100 nodes or less. Also most authors consider symmetric TSPs (STSP) described on complete graphs for tabu search implementation. If we look into ATSP, success of tabu search is rather limited if compared with the success in the context of STSP. As mentioned in [3], one reason for this could be the absence of particular instance type in ATSP which enables specific heuristics to reduce computational time by exploiting problem characteristics. Contrary to STSP, where two dimensional geometric instances dominate, there is no single instance type which dominates in the field of ATSP. A particular ATSP instance can be represented by a list of n(n – 1) inter-city distances, where n is the problem size. This creates a large space requirement and makes it difficult to handle large problem instances. An attempt to address ATSP instances is more practically motivated because of two reasons; most practical networks are asymmetric, and the STSP is a special case of the ATSP. If we take any distribution and logistics problem to see the nature of underlying graph, it is likely to be asymmetric and typically problem size is large. We believe these two important aspects of problem context, i.e. size and asymmetry, are missing in existing literature.

While generating initial solutions for tabu search, authors do not use very sophisticated methods for tabu search implementations (Table 2). It is not clear whether they do this because the neighborhoods of good initial solutions do not provide other good solutions, or whether tabu search is found to be powerful enough to generate good quality solutions regardless of the initial solution. Computational effort will surely be less to generate initial solutions using Random Insertion or Nearest Neighborhood method.

To generate neighboring solutions from an initial solution, authors prefer moves that are simple to implement and which give rise to small neighborhoods. In the last few years, they have primarily considered vertex insertion, vertex exchange,and 2-opt moves. It seems that they find running more tabu search iterations with less improvement per iteration to be a better option than running few tabu search iterations each of which could provide potentially much larger improvement. Reduction on computational time becomes specifically important for increasing problem size (with asymmetry).

The intensification and diversification within the search process are achieved by three different memory structures: short term, intermediate term and long term. Most authors prefer to use short term memory structures in their tabu search implementations. The issue of deciding tabu tenures has not received adequate attention in the literature. In aggregate more authors have preferred fixed tabu tenures over random tabu tenures. This preference seems to have increased in recent years. The problem comes while implementing tabu search on large problem sizes because commonly used fixed tenure values tend to fail since the neighborhood size is large. Among authors who have chosen to use fixed tabu tenures, more authors are beginning to tailor the tabu tenures. First, papers have looked at only linear and logarithmic dependences of the tabu tenure on problem size. We did not find any justification for restricting themselves to only these functional forms. It would also be interesting to experiment with other functional forms of dependence of the tabu tenure on problem size. Second, papers that have modified tabu tenures based on the problems being solved look at the size of the problem as the only problem specific criterion. It would be interesting to see if the length of the tabu tenure could be made dependent on other problem characteristics to yield better results.

Intermediate term memory structure is used mostly for intensification to focus the search process into a specific region. Strategy IT1 has its advantage of reduction of neighborhood size and hence reduction in computational time. In strategy IT4, typically the tabu tenure is reduced to intensify the search process to a specific region. In case of functional tenure values, the process of changing the tenure values is not explained very clearly in the literature. Changes in the functional form is also necessary. Detailed study of using a particular type of intermediate term memory based on the neighborhood structure is required to draw some meaningful conclusion over the usefulness of this memory structure. Some composite strategy for intensification can also be experimented.

Long term memory structure leads to the diversification of the search process. From the published literature, strategy LT1 and LT2 are the two strategies which are used over the years to implement this structure in tabu search. Following in similar line as suggested in intermediate term memory structure, composite strategies can be developed for diversification as well.

None of the papers that we reviewed used all of the features of tabu search in their tabu search implementations. Although in recent years, more number of published papers address tabu search implementation with more than two or three features. Components like strategic oscillation were ignored in past due to its difficulty in implementation. A shift in this area is also observed as more infrequent features of tabu search are included in recent papers.

10. Acknowledgements

I thank Prof. Diptesh Ghosh and Dr. G. S. Ravindra for their valuable inputs and suggestions in various phases of this work. I am also thankful to the anonymous referees for their helpful suggestions and comments to improve the quality and clarity of the paper.

REFERENCES