A Two-Stage Iterated Local Search Algorithm for the Capacitated p-Center Problem
- Resource Type
- Conference
- Authors
- Zhang, Qingyun; Lu, Zhipeng; Su, Zhouxing
- Source
- 2023 IEEE International Conference on Systems, Man, and Cybernetics (SMC) Systems, Man, and Cybernetics (SMC), 2023 IEEE International Conference on. :5070-5075 Oct, 2023
- Subject
- Aerospace
Bioengineering
Communication, Networking and Broadcast Technologies
Computing and Processing
General Topics for Engineers
Power, Energy and Industry Applications
Robotics and Control Systems
Signal Processing and Analysis
Transportation
Metaheuristics
Benchmark testing
Search problems
Cybernetics
capacitated p-center problem
metaheuristic search
variable neighborhood search
ejection chain
- Language
- ISSN
- 2577-1655
The capacitated p-center problem $(\mathrm{C}p\text{CP})$ is an extension of the classical p-center problem. It consists of choosing $p$ centers from a set of candidate centers and assigning each client to a center such that the total client demand assigned to each center does not exceed its given capacity. The objective of the $\mathrm{C}p\text{CP}$ is to minimize the maximum distance between each client and its assigned center. In this paper, we propose a two-stage iterated local search algorithm called TS-ILS to solve the $\mathbf{C}p\mathbf{CP}$. The first stage uses a tabu search procedure to select centers and greedily assign clients to centers, while the second stage adopts a variable neighborhood search procedure to perform the fine-grained assignment of clients. Tested on 39 commonly studied instances in the literature, TS-ILS improves the best known results of the state-of-the-art metaheuristic algorithms on 18 instances and matches the records for the remaining ones within less run time.