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
Acceso abierto
Artículo científico
Categoría
Matemáticas
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 15
Citaciones: Sin citaciones
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.
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.