A Parallel Heuristic for the Uniform Capacitated Vertex k-Center Problem

Abstract: The uniform capacitated vertex k-center problem is an NP-Hard combinatorial optimization problem that receives as input a complete weighted graph G = (V, E) with edge weights that follow a metric and two integers k, L. The goal is to find a set C in V with at most k vertices and an assignment function f such that the distance from the farhest vertex v in V to its asssigned center c in C is minimum and the number of vertices assigned to every center is at ost L. This problem models real situations where k centers can only attend a maximum number of clients, and the travel time or distance from the clients to their assigned center has to be minimized. This paper introduces a polynomial-time parallel constructive heuristic for the uniform capacitated vertex k-center problem. This heuristic exploits the relationship between the capacitated vertex k-center problem and the minimum capacitated dominating set problem. Besides, the proposed heuristic is based on the one-hop farthest-first heuristic that has proven effective for the uncapacitated version of the problem. We performed different empirical evaluations of the proposed algorithm, including an analysis on the effect of parallel computing, which significantly improved the running time for relatively large instances. Finally, we present a discussion on the advantages and disadvantages of our proposed heuristic.