Auxiliary data structures and techniques to speed up solving of the p-next center problem: A VNS heuristic

Abstract

In this paper we study the p-next center problem and propose an adequate solution approach. The p-next center problem aims to minimizing the maximum distance from a user to the nearest center plus the distance between the center and its closest center. In this paper we propose a new Variable Neighborhood Search based algorithm to solve the p-next center problem. It uses refined local search and shaking procedures as well as auxiliary data structures. The implementation consists in filtering out the candidate centers to enter a solution by considering only ones that potentially decrease the objective function value. The same approach has been applied to the classical p-center problem. Here we show that known properties of an efficient implementation of VNS heuristic developed for the p-center problem, hold for the new problem as well. More precisely, all the proposals in this work are inspired by other analogous ones used in the literature for similar problems. Hence, the novelty is the adaptation of the known properties that hold for the p-center problem to the p-next center problem. The performance of the proposed heuristic is assessed on the benchmark instances from the literature as well as newly generated larger instances with 1000, 1500, 2000 and 2500 vertices and instances defined over graphs up to 1000 vertices with different densities. The obtained results clearly demonstrate the effectiveness and efficiency of the proposed algorithm. Hence, the paper shows that the same observations used to solve p-center problem may be used to efficiently solve the p-next center problem.