GRASP and VNS for solving the p-next center problem

• Published in: Computers & operations research 2019-04, Vol.104, p.295-303
• Main Authors: López-Sánchez, A.D., Sánchez-Oro, J., Hernández-Díaz, A.G.
• Format: Article
• Language: English
• Subjects: Adaptive search techniques; Discrete location; GRASP; Heuristic methods; Operations research; p-center problem; p-next center problem; Search algorithms; VNS
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2018.12.017

•A discrete location problem is addressed motivated by very common situations in humanitarian logistics, the p-next center problem (pNCP).•Two metaheuristic methods are designed and compared to solve the pNCP: (a) A Greedy Randomized Adaptive Search Procedure and (b) a Variable Neighborhood Search algorithm.•The two methodologies above, the proposed GRASP and VNS algorithms, are then hybridized in order to attain even better results.•A wide set of instances with different sizes is solved and the algorithms are able to obtain optimal or near-optimal solutions in short computing times. This paper presents two metaheuristic algorithms for the solution of the p-next center problem: a Greedy Randomized Adaptive Search Procedure and a Variable Neighborhood Search algorithm, that will be subsequently hybridized. The p-next center problem is a variation of the p-center problem, which consists of locating p out of n centers and assigning them to users in order to minimize the maximum, over all users, of the distance of each user to its corresponding center plus the distance between this center to its closest alternative center. This problem emerges from the need to reach a secondary help center in the case of a natural disaster, when the closest center may become unavailable.