Abstract

An extension of the $p$-center problem, called the $p$-next center problem, is considered in this paper. In practice, it has been shown that centers can close suddenly due to a problem (accident, staff shortage, technical problem, etc.). In this case, customers should proceed to the backup center - the one closest to the closed center. Both the $p$-center problem and the $p$-next center problem are NP-hard, so approximation methods are suitable for solving them. In this paper, an efficient solution approach based on Skewed Variable Neighborhood Search (SVNS) is proposed for the $p$-next center problem. The performance of the proposed SVNS method is evaluated on a set of pmed instances with up to 900 nodes. The obtained computational results are presented and compared with the best results from the literature, confirming the efficiency and stability of the proposed method in solving the $p$-next center problem.

Keywords: Combinatorial optimization; $p$-next center problem; variable neighborhood search; fast interchange heuristic.

MSC: 90C27, 90C59, 90B80

DOI: 10.57016/MV-RBJS4362

Pages:  66--83     

Volume  76 ,  Issue  1-2 ,  2024