Solving the Capacitated Vertex K-Center Problem through the Minimum Capacitated Dominating Set Problem

José Alejandro Cornejo Acosta, Jesús García Díaz, Ricardo Menchaca-Méndez, Rolando Menchaca-Méndez

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva

4 Citas (Scopus)

Resumen

The capacitated vertex k-center problem receives as input a complete weighted graph and a set of capacity constraints. Its goal is to find a set of k centers and an assignment of vertices that does not violate the capacity constraints. Furthermore, the distance from the farthest vertex to its assigned center has to be minimized. The capacitated vertex k-center problem models real situations where a maximum number of clients must be assigned to centers and the travel time or distance from the clients to their assigned center has to be minimized. These centers might be hospitals, schools, police stations, among many others. The goal of this paper is to explicitly state how the capacitated vertex k-center problem and the minimum capacitated dominating set problem are related. We present an exact algorithm that consists of solving a series of integer programming formulations equivalent to the minimum capacitated dominating set problem over the bottleneck input graph. Lastly, we present an empirical evaluation of the proposed algorithm using off-the-shelf optimization software.

Idioma originalInglés
Número de artículo1551
PublicaciónMathematics
Volumen8
N.º9
DOI
EstadoPublicada - sep 2020

Huella

Profundice en los temas de investigación de 'Solving the Capacitated Vertex K-Center Problem through the Minimum Capacitated Dominating Set Problem'. En conjunto forman una huella única.

Citar esto