Chain-interchange heuristic method

Abstract

This paper describes a new Tabu search-like technique for solving combinatorial optimization problems. The chain-interchange move is introduced., which is an extension of the well-known 1-interchange move. Instead of interchanging one solution attribute that is in the solution with one that is not, four attributes are interchanged. In that way the Tabu search recency-based memory is easily obtained, i.e., the possibility of getting out of the local optimum trap can be achieved without additional efforts. Some location-allocation problems that could be solved by the same chain-interchange algorithm by only changing the objective function are listed. Moreover, most of the problems listed are suggested for the first time to be solved by Tabu search method (TS). Computer results are reported.