Study on Incorporating Tabu Search Strategies into A Multi-start Metaheuristic

摘要

Meta-RaPS (Meta-heuristic for Randomized Priority Search) is a typical multi-start local search meta-heuristic, which iteratively constructs feasible initial solutions and improves them by applying local search heuristics. It can be viewed as a generalized form of several other multi-start heuristics such as the classic random restart and the GRASP procedure. These heuristics are memoryless in the sense that they do not make use of the information in the previous iterations to build new solutions. The adaptive memory in Tabu Search (TS) has been extensively studied in application with transition neighborhoods in local search, however, the little work done to incorporate adaptive memory in muti-start heuristics has been restricted to the construction phases. This paper investigates the incorporation of the Tabu adaptive memory into Meta-RaPS and analyzes its collaboration with systematic randomness in the construction phase and the intensified local search in the improvement phase. This paper discovers several efficient algorithms that maintain a good balance between randomness and memory and can find the optimal solutions for the 45 Set-covering Problem (SCP) test instances from OR-library, while only one other heuristic from the literature can achieve the optimality for these benchmark problems.