The p-next center problem with capacity and coverage radius constraints: model and heuristics

Abstract

This paper introduces a novel problem of facility location, called the p-next center problem with capacity and coverage radius constraints. We formulate a mixed integer programming model for this problem, and compare the results found by CPLEX with three Biased Random-Key Genetic Algorithms variants. We also propose several instances for this problem, based on existing ones for the p-next center problem. Additionally, we analyze the effect of the radius and demand on instance difficulty. We also observe the performance gains with a relaxed capacity and demand constraint, i.e., permitting demand to be unmet by the model. Results point that the BRKGA variants had significantly better performance than CPLEX, and similar performances among themselves. Of those, BRKGA-FI was shown to have slightly better results than the other variants.

Publication
Proceedings of the 14th Metaheuristics International Conference