A Maximal Client Coverage Algorithm for the p-Center Problem

Sittipong Dantrakul, Chulin Likasiri

Abstract

In this work, we propose a maximal client coverage algorithm for solving the p-center problem. The algorithm is created to locate p facilities and assign clients to them in order to minimize the maximum distance between clients and the facilities. We consider both uncapacitated and capacitated cases where demands of clients and capacities of facilities are taken into account. The simulations to test the proposed algorithm are also given and compared with method given by Albareda-Sambola et al. in 2010. Optimal solutions of the test problems are found using branch and bound algorithm to compare the optimality gaps of the proposed heuristics. The proposed
heuristics solutions are found to be statistically faster than the reference algorithm at the significance level $\alpha= 0.01$ in both uncapacitated and capacitated cases.