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

Abstract: May May α-neighbor k-supplier problem (αNkSP), an extension of the classical k-supplier problem, seeks to select a set of k suppliers or facilities to minimize the maximum distance between any customer and its α-th nearest open facility. The additional coverage requirement significantly increases the complexity of evaluating neighborhood moves, making the design of efficient solution methods particularly challenging. This paper proposes a GRASP-based metaheuristic for the discrete αNkSP in which the local search phase is driven by a facility swap neighborhood. The resulting algorithm, called α-Fast Vertex Substitution (α-FVS), exploits specialized auxiliary data structures that capture 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 formulation solved by CPLEX. The results demonstrate that α-FVS consistently produces solutions of very high quality extremely fast, and that over all GRASP approach is very effective outperforming exact methods. These findings show that exploiting the structure of the objective function through dedicated data structures constitutes an effective strategy for solving the αNkSP and other large-scale location problems based on vertex interchange neighborhoods.