Parallel iterative solution-based tabu search for the obnoxious p-median problem

摘要

The obnoxious p-median problem (OpM) is to determine a set of opened facilities such that the sum of distances between each client and the opened facilities is maximized. OpM is a general model that has a wide range of practical applications. However the problem is computationally challenging because it is known to be NP-hard. In this work, we propose an effective parallel iterative solution-based tabu search algorithm to solve OpM. The proposed algorithm combines a delete-add compound move instead of a typical time-consuming swap move to improve neighborhood exploration, a solution-based tabu search procedure to strictly prevent visited solutions from being revisited, a perturbation scheme similar to the shaking phase of variable neighborhood search for diversification, and a parallel strategy of leveraging multiple processors of a computer. Experimental results on 144 benchmark instances demonstrate that the proposed algorithm is able to find new lower bounds for 7 instances and match the best known results for the other instances. Further experimental analysis sheds light on the key ingredients to the performance of the proposed algorithm. The code of our FISTS algorithm is publicly available to facilitate future comparative studies. (C) 2020 Elsevier Ltd. All rights reserved.