Authors: Ristić, Dalibor
Mladenović, Nenad 
Ratli, Mustapha
Todosijević, Raca 
Urošević, Dragan 
Affiliations: Computer Science 
Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Auxiliary data structures and techniques to speed up solving of the p-next center problem: A VNS heuristic
Journal: Applied Soft Computing
Volume: 140
First page: 110276
Issue Date: 2023
Rank: ~M21a
ISSN: 1568-4946
DOI: 10.1016/j.asoc.2023.110276
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.
Keywords: Heuristics | Location | p-center | p-next center | Variable neighborhood search
Publisher: Elsevier

Show full item record


checked on May 23, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.