Parallel iterative solution-based tabu search for the obnoxious p-median problem
Parallel iterative solution-based tabu search for the obnoxious p-median problem
复制标题
DOI：
10.1016/j.cor.2020.105155
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
Jian Chang;Lifang Wang;Jin‐Kao Hao;Yang Wang
中科院分区：
文献类型：
--
作者：
Jian Chang;Lifang Wang;Jin‐Kao Hao;Yang Wang
The obnoxiousp-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 beNP-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 PISTS algorithm is publicly available to facilitate future comparative studies.
