2025-11-11
El problema de cobertura (Set Covering Problem, SCP) es un modelo de optimización combinatoria de tipo discreto, cuya finalidad es determinar un subconjunto mínimo de elementos que cubran completamente un conjunto universal de requerimientos o entidades.
El objetivo principal es determinar la ubicación óptima de instalaciones o recursos que permitan cubrir un conjunto de puntos de demanda, garantizando el servicio requerido con el menor número posible de instalaciones o al mínimo costo total.
| Elemento | Descripción |
|---|---|
| Formulación | Modelo entero binario para ubicar instalaciones con menor costo total. |
| Conjuntos | Puntos posibles de instalación y de demanda. |
| Parámetros | Costos y relaciones de cobertura entre sitios y demandas. |
| Variables de decisión | Binarias: 1 si se instala, 0 en caso contrario. |
| Función objetivo | Minimizar costos o número de instalaciones con cobertura total. |
| Restricciones | Toda demanda debe estar cubierta y las variables son binarias. |
| Interpretación general | Busca la solución más eficiente con mínima inversión y cobertura completa. |
| Ventajas | Desventajas |
|---|---|
| Optimiza recursos y reduce costos. | Problema NP-difícil. |
| Aplicable en logística, redes y servicios. | Requiere alto poder computacional. |
| Formulación matemática clara. | A veces necesita heurísticas. |
| Mejora decisiones de planificación. | Sensible a datos o cambios en costos. |
| Área | Aplicación típica |
|---|---|
| Logística | Ubicación de almacenes o centros. |
| Transporte | Asignación de rutas o vehículos. |
| Telecomunicaciones | Ubicación de antenas o repetidores. |
| Seguridad | Estaciones de policía o bomberos. |
| Salud | Ubicación de hospitales o clínicas. |
| Aviación | Asignación de tripulaciones a vuelos. |
La empresa Southwestern Airways necesita asignar tres tripulaciones con base en San Francisco (SF) para cubrir una serie de vuelos programados entre distintas ciudades: Los Ángeles (LA), Denver (DE), Chicago (CH) y Seattle (SE).
Cada tripulación puede seguir una secuencia factible de vuelos, es decir, una combinación de trayectos que forma un itinerario posible dentro de las restricciones de horarios y logística operativa.
En total existen 12 secuencias de vuelos factibles, cada una con un costo asociado (expresado en miles de dólares).
Objetivo del Problema
El propósito de la empresa es asignar tres de esas secuencias —una por cada tripulación— de manera que se cumplan las siguientes condiciones:
| Vuelo | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1. SF → LA | 1 | 1 | 1 | 1 | 1 | |||||||
| 2. SF → Denver | 1 | 1 | 2 | 3 | ||||||||
| 3. SF → Seattle | 1 | 1 | ||||||||||
| 4. LA → Chicago | 2 | 3 | ||||||||||
| 5. LA → SF | 2 | 3 | 5 | |||||||||
| 6. Chicago → Denver | 3 | 3 | 4 | |||||||||
| 7. Chicago → Seattle | 3 | |||||||||||
| 8. Denver → SF | 2 | 3 | ||||||||||
| 9. Denver → Chicago | 4 | 2 | ||||||||||
| 10. Seattle → SF | 4 | 5 | ||||||||||
| 11. Seattle → LA | 4 | 4 | 2 | |||||||||
| Costo (miles de $) | 2 | 3 | 4 | 6 | 7 | 5 | 7 | 8 | 9 | 9 | 8 | 9 |
\[ a_{ij} = \begin{cases} 1, & \text{si la secuencia } j \text{ incluye (cubre) el vuelo } i, \\[4pt] 0, & \text{en caso contrario.} \end{cases} \]
\[ x_j = \begin{cases} 1, & \text{si se selecciona la secuencia } j, \\[4pt] 0, & \text{en caso contrario.} \end{cases} \]
El objetivo es minimizar el costo total de asignar tripulaciones a las secuencias de vuelos, asegurando que todos los vuelos sean cubiertos y que se asignen exactamente tres tripulaciones.
\[ \min Z = \sum_{j \in J} c_j x_j \tag{1} \]
\[\begin{align}
\sum_{j \in J} a_{ij} x_j &\ge 1 && \forall i \in I \tag{2} \\
\sum_{j \in J} x_j &= p && \tag{3} \\
x_j &\in \{0,1\} && \forall j \in J \tag{4}
\end{align}\]
Southwestern Airways debe asignar tres tripulaciones con base en San Francisco para cubrir todos sus vuelos programados, eligiendo las secuencias más eficientes que aseguren la cobertura completa con el menor costo operativo posible. El modelo fue implementado mediante funciones de R.
La solución óptima selecciona las secuencias 1, 3 y 11 para asignar las tres tripulaciones.
Cada vuelo es cubierto al menos una vez, garantizando la cobertura total con el costo mínimo posible.
El Problema de Cobertura permitió comprender cómo optimizar recursos y reducir costos operativos.
En el caso de Southwestern Airways, el modelo facilitó la asignación eficiente de tripulaciones, asegurando la cobertura total de los vuelos con menor uso de recursos y mayor eficiencia operativa.
¡GRACIAS!