Exploiting flat subspaces in local search for p-Center problem and two fault-tolerant variants

被引:5
作者
Mousavi, Seyed R. [1 ]
机构
[1] Coventry Univ, Coventry, England
关键词
Flat subspace; Heuristic function; Local search; Metaheuristic; Move operation; p -Center problem; Search space; ALGORITHM; NEIGHBOR; METAHEURISTICS; NETWORK; SERVICE; GRASP;
D O I
10.1016/j.cor.2022.106023
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
In this paper, local search algorithms are proposed for the p-Center, alpha-Neighbour p-Center and p-Next Center facility location problems. The alpha-Neighbour p-Center and p-Next Center problems may be viewed as two fault -tolerant variants of the p-Center problem. The algorithm proposed for p-Center outperforms the most recent state-of-the-art metaheuristic for this problem using standard datasets. The proposed algorithm for p-Next Center also outperforms an existing, more complex, state-of-the-art metaheuristic for this problem. The algorithm proposed for alpha-Neighbour p-Center is the first metaheuristic for this problem, to the best of the author's knowledge. The proposed algorithms share a common design, which is the integration of the first-improvement local search with strategies to exploit flat subspaces in the search space. The overall success of this design paradigm motivates further investigation about its properties and applications to similar NP-hard optimisation problems.
引用
收藏
页数:22
相关论文
共 58 条
[1]   When centers can fail: A close second opportunity [J].
Albareda-Sambola, Maria ;
Hinojosa, Yolanda ;
Marin, Alfredo ;
Puerto, Justo .
COMPUTERS & OPERATIONS RESEARCH, 2015, 62 :145-156
[2]  
[Anonymous], 2005, J MATH MODELL ALGORI
[3]  
[Anonymous], 2022, CPU BENCHMARKS
[4]  
BEASLEY JE, 1990, J OPER RES SOC, V41, P1069, DOI 10.2307/2582903
[5]  
Beasly JE, OR LIB
[6]   Metaheuristics in combinatorial optimization: Overview and conceptual comparison [J].
Blum, C ;
Roli, A .
ACM COMPUTING SURVEYS, 2003, 35 (03) :268-308
[7]   Hyper-heuristics: a survey of the state of the art [J].
Burke, Edmund K. ;
Gendreau, Michel ;
Hyde, Matthew ;
Kendall, Graham ;
Ochoa, Gabriela ;
Oezcan, Ender ;
Qu, Rong .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2013, 64 (12) :1695-1724
[8]  
Calik H, 2019, LOCATION SCI, P51, DOI DOI 10.1007/978-3-030-32177-2
[9]   Double bound method for solving the p-center location problem [J].
Calik, Hatice ;
Tansel, Barbaros C. .
COMPUTERS & OPERATIONS RESEARCH, 2013, 40 (12) :2991-2999
[10]   Optimal solutions for the continuous p-centre problem and related -neighbour and conditional problems: A relaxation-based algorithm [J].
Callaghan, Becky ;
Salhi, Said ;
Brimberg, Jack .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2019, 70 (02) :192-211