使用说明
🚑 Maximal Covering Location Problem - Aguascalientes
📋 Descripción del Proyecto
Solución integral para el Maximal Covering Location Problem (MCP) de la competencia de Optimización del ITAM. El objetivo es determinar las ubicaciones óptimas para ambulancias en Aguascalientes, maximizando la cobertura de accidentes de tráfico dentro de radios de servicio predefinidos.
🎯 Objetivos y Resultados
| Categoría | Meta | Estado | Cobertura Clave (Manhattan) |
|---|---|---|---|
| Obligatorio | Generar 100 soluciones (Métrica Manhattan) | ✅ Completado | $\mathbf{86.33%}$ (Máx.) y $\mathbf{4.53%}$ (Mín.) |
| Bonus (+1 punto) | Generar 100 soluciones (Métrica Alternativa) | ✅ Completado | Euclidiana fue elegida como la métrica ganadora. |
⚙️ Metodología y Estrategia Óptima
La estrategia se centró en la precisión del modelo matemático y la eficiencia algorítmica.
1. Calibración Crítica del Factor de Conversión
Mediante ingeniería inversa y validación empírica con soluciones conocidas, se determinó el factor de conversión exacto utilizado por el evaluador, eliminando el error de escala del problema:
- Factor de Conversión: $\mathbf{107.5 \text{ km/grado}}$
- Validación: Este factor replica exactamente la cobertura del $17.98%$ reportada por el evaluador oficial.
2. Algoritmo Híbrido Superior
Se implementó un Algoritmo Greedy híbrido para balancear la velocidad y la calidad de la solución:
- Heurística Base (Greedy): Selecciona iterativamente los candidatos (generados inteligentemente) que maximizan la cobertura marginal.
- Refinamiento (Grid Search Local): Aplica una búsqueda intensiva ($\pm 0.002^{\circ}$, 30 iteraciones) sobre las ubicaciones Greedy para asegurar que la solución sea un máximo local. Esta fase fue la responsable de la mejora consistente de $\mathbf{+0.1% \text{ a } +0.5%}$ por instancia.
3. Elección del Bono: Euclidiana vs. Haversine
Se probó la complejidad de Haversine contra la simplicidad de Euclidiana para el bono.
| Métrica | Algoritmo | Desempeño Clave (4 Casos Testeados) | Decisión Final |
|---|---|---|---|
| Euclidiana ($L_2$) | Greedy + Grid Search | Ganó a Haversine en la mayoría de los escenarios. | GANADORA (Robusta y precisa) |
| Haversine (Geodésica) | Look-Ahead + Búsqueda Intensiva | Complejidad alta, pero rendimiento final inferior. | Descartada |
Conclusión: La métrica Euclidiana demostró ser la más eficiente para el concurso, proporcionando la mayor ganancia ($\mathbf{+1.16}$ puntos en el caso $R=1.0 \text{ km}, N=10$) sobre el Manhattan base.
📊 Resultados Clave de la Solución Final
| Configuración | Cobertura Lograda (Manhattan) | Cobertura Ganadora (Euclidiana) |
|---|---|---|
| 0.5 km, 5 amb | $7.46%$ | $\mathbf{11.67%}$ |
| 1.0 km, 10 amb | $37.11%$ | $\mathbf{48.12%}$ |
| 2.5 km, 10 amb | $91.83%$ | $\mathbf{97.46%}$ |
🏗️ Estructura del Proyecto
El repositorio incluye el código fuente de las tres métricas utilizadas para el análisis:
| Directorio | Archivo Generador | Métrica Generada | Propósito |
|---|---|---|---|
output/ |
mcp_generator_manhattan_fixed.py |
Manhattan ($L_1$) | Soluciones Obligatorias (Calibración). |
output_euclidean/ |
mcp_generator_euclidean_fixed.py |
Euclidiana ($L_2$) | Soluciones para el Bono Opcional. |
output_haversine/ |
mcp_generator_ultimate_fixed.py |
Haversine (Geodésica) | Implementación del Máximo Esfuerzo (Validación). |
data/ |
Contiene los 5 archivos CSV de datos de accidentes. | N/A | Datos de entrada. |
🚀 Instalación y Uso
Requisitos
pip install pandas numpy scipy scikit-learn
Este proyecto fue desarrollado con fines académicos para la competencia MCP del ITAM.
