logo móvil
Contáctanos

Resolviendo el problema del centro de vértice K con capacidad a través del problema del conjunto dominante de capacidad mínima

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

Idioma: Inglés

Editor: MDPI

Año: 2020

Descargar PDF

Acceso abierto

Artículo científico


Categoría

Matemáticas

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 15

Citaciones: Sin citaciones


Descripción
El problema del centro k con vértice capacitado recibe como entrada un grafo completo ponderado y un conjunto de restricciones de capacidad. Su objetivo es encontrar un conjunto de centros y una asignación de vértices que no viole las restricciones de capacidad. Además, la distancia desde el vértice más lejano a su centro asignado debe minimizarse. El problema del centro k con vértice capacitado modela situaciones reales donde un número máximo de clientes debe ser asignado a centros y el tiempo de viaje o la distancia desde los clientes hasta su centro asignado debe minimizarse. Estos centros pueden ser hospitales, escuelas, comisarías, entre otros. El objetivo de este documento es declarar explícitamente cómo están relacionados el problema del centro k con vértice capacitado y el problema del conjunto dominante capacitado mínimo. Presentamos un algoritmo exacto que consiste en resolver una serie de formulaciones de programación entera equivalentes al problema del conjunto dominante capacitado mínimo sobre el grafo de entrada del cuello de botella. Por último, presentamos una evaluación empírica del algoritmo propuesto utilizando software de optimización listo para usar.

Documentos Relacionados

Temas Virtualpro