A Greedy Randomized Adaptive Search Procedure with Fast Vertex Substitution for the α-Neighbor k-Supplier Problem

Abstract: The α-neighbor k-supplier problem, an extension of the classical k-supplier problem, seeks to select a set of k suppliers or facilities that minimizes the maximum distance between any customer and its α-th nearest open facility. The problem is relevant to the location of emergency facilities, where service coverage must be maintained despite unforeseen incidents, such as natural disasters, labor strikes, or accidents, that may cause facility failures. This multiple-coverage requirement significantly increases the complexity of evaluating neighborhood moves, making the design of efficient solution methods particularly challenging. This work proposes a GRASP-based metaheuristic for the discrete α-neighbor k-supplier prob- lem in which the local search phase is driven by a facility swap neighborhood. The resulting algorithm, called α-Fast Vertex Substitution, exploits specialized auxiliary data structures that cap- ture the behavior of customer-to-facility assignments under facility substitutions. By intelligently reusing this information, the method avoids repeatedly performing costly assignment computations during neighborhood exploration, leading to a substantial reduction in the computational effort required to evaluate candidate moves. The proposed heuristic is assessed through extensive computational experiments on benchmark instances and is compared with an exact integer programming solver. The results demonstrate that the α-Fast Vertex Substitution heuristic consistently produces high-quality solutions in very short computational times and that the proposed GRASP is highly effective, frequently outperforming the exact method within the prescribed time limit. These findings show that exploiting the properties of the objective function through dedicated data structures constitutes an effective strategy for solving the α-neighbor k-supplier problem and other large-scale location problems based on vertex interchange neighborhoods.