Effective metaheuristic algorithms for the minimum differential dispersion problem

This paper presents tabu search and memetic search algorithms for solving the minimum differential dispersion problem. The tabu search algorithm employs a neighborhood decomposition candidate list strategy and a rarely used solution-based tabu memory. Unlike the typical attribute-based tabu list, the solution-based tabu strategy leads to a more highly focused intensification process and avoids tuning the tabu tenure, while employing coordinated hash functions that accelerate the determination of tabu status. The memetic search algorithm incorporates the tabu search procedure within it and makes use of a crossover operator that generates solution assignments by an evaluation mechanism that includes both quality and distance criteria. Experimental results on a benchmark testbed of 250 problems reveal that our tabu search algorithm is capable of discovering better solutions for 179 (71.6%) of the problem instances, while our memetic search algorithm finds better solutions for 157 (62.8%) of the instances, collectively yielding better solutions for 181 (72.4%) of the test problems than recently reported state-of-the-art algorithms.