Skip to main navigation Skip to search Skip to main content

A vertex weighting-based double-tabu search algorithm for the classical p-center problem

  • Qingyun Zhang
  • , Zhipeng Lü
  • , Zhouxing Su*
  • , Chumin Li
  • *Corresponding author for this work

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

Abstract

The p-center problem, which is NP-hard, aims to select p centers from a set of candidates to serve all clients while minimizing the maximum distance between each client and its assigned center. To solve this challenging optimization problem, we transform the p-center problem into a series of decision subproblems, and propose a vertex weighting-based double-tabu search (VWDT) algorithm. It integrates a vertex weighting strategy and a double-tabu search which combines both solution-based and attribute-based tabu strategies to help the search to escape from the local optima trap. Computational experiments on totally 510 public instances in the literature show that VWDT is highly competitive comparing to the state-of-the-art algorithms. Specifically, VWDT improves the previous best known results for 84 large instances and matches the best results for all the remaining ones. Apart from the improvements in solution quality, VWDT is much faster than other state-of-the-art algorithms in the literature, especially on some large instances. Furthermore, we perform additional experiments to analyze the impact of the key components to VWDT, such as the vertex weighting and the double-tabu search strategy. © 2023 Elsevier Ltd
Original languageEnglish
Article number106373
JournalComputers and Operations Research
Volume160
Online published9 Aug 2023
DOIs
Publication statusPublished - Dec 2023
Externally publishedYes

Funding

This work was supported in part by the National Natural Science Foundation of China (NSFC) under Grant 72101094 and the Special Project for Knowledge Innovation of Hubei Province under Grant 2022013301015175 .

Research Keywords

  • Location problem
  • p-Center problem
  • Solution-based tabu strategy
  • Tabu search
  • Vertex weighting

Fingerprint

Dive into the research topics of 'A vertex weighting-based double-tabu search algorithm for the classical p-center problem'. Together they form a unique fingerprint.

Cite this