Solving the P-Second Center Problem with Variable Neighborhood Search

Dalibor Ristic1, Dragan Urosevic1, 2, Nenad Mladenovic3 and Raca Todosijevic4

  1. School of Computing, Union University
    Knez Mihailova 6, 11000 Belgrade, Serbia
  2. Mathematical Institute of the Serbian Academy of Sciences and Arts
    Knez Mihailova 36, 11000 Belgrade, Serbia
  3. Khalifa University, PO Box 127788
    Abu Dhabi, United Arab Emirates
  4. Polytechnic University of Hauts-de-France, Cedex 9
    Valenciennes, France


The p-center problem is a well-known and highly studied problem pertaining to the identification of p of the potential n center locations in such a way as to minimize the maximum distance between the users and the closest center. As opposed to the p-center, the p-second center problem minimizes the maximum sum of the distances from the users to the closest and the second closest centers. In this paper, we propose a new Variable Neighborhood Search based algorithm for solving the p-second center problem. Its performance is assessed on the benchmark instances from the literature. Moreover, to further evaluate the algorithm’s performance, we generated larger instances with 1000, 1500, 2000, and 2500 nodes and instances defined over graphs up to 1000 nodes with different densities. The obtained results clearly demonstrate the effectiveness and efficiency of the proposed algorithm.

Key words

variable neighborhood method, heuristic algorithms, p-second center problem, combinatorial optimization

Digital Object Identifier (DOI)

Publication information

Volume 20, Issue 1 (January 2023)
Year of Publication: 2023
ISSN: 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

DownloadAvailable in PDF
Portable Document Format

How to cite

Ristic, D., Urosevic, D., Mladenovic, N., Todosijevic, R.: Solving the P-Second Center Problem with Variable Neighborhood Search. Computer Science and Information Systems, Vol. 20, No. 1, 95–115. (2023),