About the journal

• Home page
• Contact information
• Aims and scope
• Indexing information
• Editorial policies
• ComSIS consortium
• Journal boards
• Managing board

For authors

• Information for contributors
• Paper submission
• Article submission through OJS
• Copyright transfer form
• Download section

For readers

• Forthcoming articles
• Current issue
• Archive

For reviewers

• View and review submissions

News

• Journal's Facebook page
• Calls for special issues
• New issue notification

Solving the P-Second Center Problem with Variable Neighborhood Search

Dalibor Ristic¹, Dragan Urosevic^{1, 2}, Nenad Mladenovic³ and Raca Todosijevic⁴

1. School of Computing, Union University
   Knez Mihailova 6, 11000 Belgrade, Serbia
   dalibor.ristic@outlook.com
2. Mathematical Institute of the Serbian Academy of Sciences and Arts
   Knez Mihailova 36, 11000 Belgrade, Serbia
   durosevic@raf.rs
3. Khalifa University, PO Box 127788
   Abu Dhabi, United Arab Emirates
   nenadmladenovic12@gmail.com
4. Polytechnic University of Hauts-de-France, Cedex 9
   Valenciennes, France
   racatodosijevic@gmail.com

Abstract

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)

https://doi.org/10.2298/CSIS210804049R

Publication information

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

Full text

Available 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), https://doi.org/10.2298/CSIS210804049R