"The memory structures used in tabu search can be divided into three categories:

Short-term: The list of solutions recently considered. If a potential solution appears on this list, it cannot be revisited until it reaches an expiration point.

Intermediate-term: A list of rules intended to bias the search towards promising areas of the search space.

Long-term: Rules that promote diversity in the search process (i.e. regarding resets when the search becomes stuck in a plateau or a suboptimal dead-end)."

I have quoted this from wikipedia. just go thru the references related to it and implement it. by the way why ur using this age old technique for TSP?? Lot of other approaches also there and u can think some new one which people not yet have tried.

It depends on the way you will use the Long Term Memory (LTM). Basically, it can be use to explore regions of the solution space that have not been considered. For instance, you can build a frequency table for the arcs used in the solutions. Then you can use this table to bias your exploration (penalties). However, I don't think this will help you reach all the optimal solutions for the TSP. I suggest strategic oscillation. It's a good way to alternate between intensification and diversification. Otherwise, you can try ejection chains, but it is a bit more tricky to implement. Another way to improve is to perform K tabu searches from different initial solutions, keep the K incumbent solutions then use them to perform a scatter search step. Glover and Laguna wrote a very good book on TS. Even it is a bit old, I suggest you read it:

- Glover, F. and M. Laguna (1997) Tabu Search, Kluwer Academic Publishers, Boston

All in one, TS is a good way to quickly reach good solutions. If you wish to get better solutions, then you have to consider strategies in which TS is a component. Combination of metaheuristics (hybridization) is another possible way.

Anindya and Duhamel have given valid explanation about long and short term memory in TS. I also suggest to read the book of Glover and Laguna.

Nevertheless, dislike Anindya says, I do not consider TS an "old"

technique. In fact, TS is an useful meta-heuristic in many real

applications, because in some of these optimization problems, other meta-heuristics (even the "new" ones) are not able to avoid cycles in the search process.

My previous experience when solving several NP-hard problems (graph partitioning, etc.) says that TS works well, especiallly if it is combined with Simulated Annealing (SA). In the following references, you can find information about the combination of SA and TS in the single- and multi-objective context, respectively:

C Gil, J Ortega, MG Montoya, R Baños (2002), A mixed heuristic for

circuit partitioning, Computational Optimization and Applications 23

(3), 321-340

R Baños, C Gil, B Paechter, J Ortega (2007) A hybrid meta-heuristic

for multi-objective optimization: MOSATS, Journal of Mathematical

Modelling and Algorithms 6 (2), 213-230.

Short-term memory acts as a filter and temporary storage. Your short-term memory works like your computer’s RAM, which provides working space for short computations.

In our use of TS (in forestry) it works as well as other s-metaheuristics (SA, TA), when 2-opt or 3-opt choices are available. Basic TS uses 1-opt choices (select the best change to make, check tabu status, decide what to do ...). "Exchange" 2-opt choices involve the switching of assignments to two different decision variables. When attempted, twice the amount of constraints may need to be assessed (for the two variables involved), but the process does a nice job of refining and improving solution values. However, using 2-opt or 3-opt moves slows down the processing, and requires a lot of coding. Some have even suggested that a 2-opt move involves randomly changing the assignments to two decision variables (not swapping the assignments) at one time. Glover once wrote a paper on the use of 4-opt moves.