Improving the quality of heuristic solutions for the capacitated vertex p-center problem through iterated greedy local search with variable neighborhood descent |
| |
Affiliation: | 1. Centro de Informática, Universidade Federal da Paraíba (UFPB), João Pessoa, PB, Brazil;2. Computer Engineering Department, École Polytechnique de Montréal, Montreal, Canada;1. Department of Gynecological Oncology, Fudan University, Shanghai Cancer Center, Shanghai 200032, China;2. Department of Pathology, Fudan University Shanghai Cancer Center, Shanghai 200032, China;3. Department of Oncology, Shanghai Medical College, Fudan University, Shanghai 200032, China |
| |
Abstract: | The capacitated vertex p-center problem is a location problem that consists of placing p facilities and assigning customers to each of these facilities so as to minimize the largest distance between any customer and its assigned facility, subject to demand capacity constraints for each facility. In this work, a metaheuristic for this location problem that integrates several components such as greedy randomized construction with adaptive probabilistic sampling and iterated greedy local search with variable neighborhood descent is presented. Empirical evidence over a widely used set of benchmark data sets on location literature reveals the positive impact of each of the developed components. Furthermore, it is found empirically that the proposed heuristic outperforms the best existing heuristic for this problem in terms of solution quality, running time, and reliability on finding feasible solutions for hard instances. |
| |
Keywords: | Combinatorial optimization Discrete location Metaheuristics Iterated greedy local search Variable neighborhood descent |
本文献已被 ScienceDirect 等数据库收录! |
|