A new category of Tabu search, Chain-interchange heuristic method is proposed in this paper. It can be viewed as a Tabu search method adopted for a large class of problems, as well as extended interchange heuristic method. Instead of interchanging two solution attributes in order to generate a set of neighbourhood of a current solution, we interchange positions of four attributes. This simple extension of the well known descent local search 1-interchange method allows us to obtain an efficient descent-ascent local search heuristic. Thus, our move could be easily augmented in any problem where Interchange heuristic has been used, now with property of escaping from local optima trap. Some location-allocation problems that could be solved by the same chain-interchange algorithm only by changing objective function are listed. Moreover, most of the problems listed are for the first time suggested to be solved by Tabu Search. Computer results are reported.
Paru en septembre 1995 , 20 pages