Combining simulated annealing with tabu mechanism for the simple plant location problem

This paper presents a hybrid method that combines the simulated annealing with tabu mechanism for the simple (or uncapacitated) plant location problem. Two modified heuristic procedures are applied for the generation mechanism in simulated annealing. In some cases, the moves guided by the heuristic procedures may cause the search stuck at a local optimum. To avoid this problem, the tabu list is incorporated with the move generation procedures to prohibit the strongly biased moves inherent in heuristics. Therefore, the search diversity is maintained and the most promising space may be explored at the earliest. In addition, a large perturbation scheme is introduced to leap over the barriers during a search and to explore another region of the search space. The control temperature is reheated whenever the large perturbation scheme is activated. The proposed algorithm was tested on a well-known data set taken from QAPLIB, with up to 100 potential locations and 1000 customers. Our experimental results show that the performance of simulated annealing is significantly improved by the incorporation of these two modified heuristics, the tabu list and the large perturbation scheme. The proposed algorithm is effective and outperforms the traditional simulated annealing and genetic algorithm both on the solution quality and the computation time.