map-optimization-patterns

# Optimización Combinatoria sobre Mapas ## Cuándo cargar esta skill Cuando el usuario pida: optimización de ubicación de instalaciones, p-median, p-center, TSP (viajante), problema de transporte/supply-demand, rutas óptimas que visitan múltiples puntos, ubicación óptima de almacenes/centros, logística de distribución. ## Contexto Inspirado en un proyecto R Shiny ("組合せ最適化 on Map — ompr版") que resuelve 4 problemas clásicos de investigación operativa sobre un mapa Leaflet interactivo. Extraemos los patrones para implementarlos en nuestro stack (Node.js + Vanilla JS + Leaflet). --- ## Los 4 Problemas Clásicos ### 1. Facility Location — Ubicación de Instalaciones **Pregunta:** ¿Dónde poner *p* instalaciones para minimizar la distancia a los usuarios? #### p-median - **Objetivo:** Minimizar la **distancia total ponderada** entre cada punto de demanda y su instalación más cercana - **Uso:** Hospitales, centros de salud, almacenes, estaciones de bomberos - **Input:** Puntos de demanda (lat, lng, peso) + número *p* de instalaciones - **Output:** Ubicaciones óptimas + asignación demanda→instalación ```javascript // p-median: minimizar distancia total ponderada // min Σ_i Σ_j w_i * d_ij * x_ij // s.t. Σ_j x_ij = 1 (cada demanda asignada a 1 instalación) // Σ_j y_j = p (exactamente p instalaciones) // x_ij ≤ y_j (solo se asigna a instalaciones abiertas) ``` #### p-center - **Objetivo:** Minimizar la **distancia máxima** (el peor caso) - **Uso:** Emergencias, cobertura garantizada, SLA de servicio - **Input:** Igual que p-median - **Output:** Ubicaciones que minimizan la distancia del punto más desfavorecido ```javascript // p-center: minimizar la peor distancia // min D // s.t. d_ij * x_ij ≤ D para todo i,j // Σ_j x_ij = 1 // Σ_j y_j = p ``` **Diferencia clave:** p-median optimiza el promedio, p-center optimiza el peor caso. Un hospital usa p-center (nadie debe quedar lejos). Un almacén usa p-median (coste total mínimo). ### 2. TSP — Traveling Salesman Problem (Problema del Viajante) **Pregunta:** ¿Cuál es el circuito más corto que visita todas las ciudades exactamente una vez? - **Uso:** Rutas de reparto, logística de última milla, planificación de visitas - **Input:** Lista de ciudades (lat, lng) - **Output:** Orden óptimo de visita + distancia total **Complejidad:** NP-hard. Exacto viable ≤ 12 ciudades (branch & bound / MTZ). Para más → heurísticas. ### 3. Transportation Problem — Problema de Transporte (Supply-Demand) **Pregunta:** ¿Cómo mover mercancía de orígenes (oferta) a destinos (demanda) minimizando coste? - **Uso:** Distribución logística, suministro, planificación de rutas multi-origen - **Input:** Orígenes con capacidad + Destinos con demanda + Matriz de costes (distancia/tiempo) - **Output:** Flujos óptimos (cuánto enviar de cada origen a cada destino) ```javascript // min Σ_i Σ_j c_ij * x_ij (coste total de transporte) // s.t. Σ_j x_ij ≤ supply_i (no enviar más de lo que hay) // Σ_i x_ij ≥ demand_j (cubrir toda la demanda) // x_ij ≥ 0 ``` --- ## Heurísticas JS (sin solver LP/MIP) Para tamaños < 50 puntos, las heurísticas dan resultados ≈ óptimos en milisegundos. No necesitamos GLPK, ompr, ni ningún solver externo. ### p-median — Greedy Interchange ```javascript // Algoritmo: Greedy + intercambio 1-opt function solvePMedian(demandPoints, p, distanceFn) { const n = demandPoints.length; if (p >= n) return demandPoints.map((_, i) => i); // 1. Greedy: añadir instalación que más reduce la distancia total let facilities = []; let assignments = new Array(n).fill(-1); for (let iter = 0; iter < p; iter++) { let bestIdx = -1, bestCost = Infinity; for (let c = 0; c < n; c++) { if (facilities.includes(c)) continue; // Calcular coste total si c fuera la nueva instalación let totalCost = 0; const testFacilities = [...facilities, c]; for (let d = 0; d < n; d++) { const minDist = Math.min(...testFacilities.map(f => distanceFn(demandPoints[d], demandPoints[f]) )); totalCost += (demandPoints[d].weight || 1) * minDist; } if (totalCost < bestCost) { bestCost = totalCost; bestIdx = c; } } facilities.push(bestIdx); } // 2. Intercambio 1-opt: intentar swap facility↔non-facility let improved = true; while (improved) { improved = false; for (let i = 0; i < facilities.length; i++) { for (let c = 0; c < n; c++) { if (facilities.includes(c)) continue; const testFacilities = facilities.map((f, idx) => idx === i ? c : f); const newCost = totalCostPMedian(demandPoints, testFacilities, distanceFn); const oldCost = totalCostPMedian(demandPoints, facilities, distanceFn); if (newCost < oldCost - 0.01) { facilities[i] = c; improved = true; } } } } // Asignar cada demanda a su instalación más cercana for (let d = 0; d < n; d++) { let minD = Infinity, bestF = 0; for (const f of facilities) { const dist = distanceFn(demandPoints[d], demandPoints[f]); if (dist < minD) { minD = dist; bestF = f; } } assignments[d] = bestF; } return { facilities, assignments }; } function totalCostPMedian(points, facilities, distFn) { return points.reduce((sum, p, i) => { const minDist = Math.min(...facilities.map(f => distFn(p, points[f]))); return sum + (p.weight || 1) * minDist; }, 0); } ``` ### p-center — Minimax Greedy ```javascript // Igual que p-median pero minimizando el MÁXIMO en vez del total function solvePCenter(demandPoints, p, distanceFn) { // Misma estructura greedy, pero evaluando Math.max en vez de Math.sum // El intercambio busca reducir la distancia del punto MÁS LEJANO // (ver implementación completa en references/tsp-heuristics.md) } ``` ### TSP — Nearest Neighbor + 2-opt ```javascript // Nearest Neighbor: heurística greedy (rapida, ~25% óptimo) function tspNearestNeighbor(points, distFn) { const n = points.length; const visited = new Array(n).fill(false); const tour = [0]; visited[0] = true; for (let step = 1; step < n; step++) { const last = tour[tour.length - 1]; let bestNext = -1, bestDist = Infinity; for (let j = 0; j < n; j++) { if (visited[j]) continue; const d = distFn(points[last], points[j]); if (d < bestDist) { bestDist = d; bestNext = j; } } tour.push(bestNext); visited[bestNext] = true; } return tour; } // 2-opt: mejora local intercambiando 2 aristas function tsp2Opt(tour, points, distFn) { let improved = true; while (improved) { improved = false; for (let i = 1; i < tour.length - 1; i++) { for (let j = i + 1; j < tour.length; j++) { // Calcular coste antes y después del intercambio const d1 = distFn(points[tour[i-1]], points[tour[i]]) + distFn(points[tour[j]], points[tour[(j+1) % tour.length]]); const d2 = distFn(points[tour[i-1]], points[tour[j]]) + distFn(points[tour[i]], points[tour[(j+1) % tour.length]]); if (d2 < d1 - 0.01) { // Reversar el segmento tour[i..j] tour.splice(i, j - i + 1, ...tour.slice(i, j + 1).reverse()); improved = true; } } } } return tour; } // Combinación: Nearest Neighbor → 2-opt function solveTSP(points, distFn) { const tour = tspNearestNeighbor(points, distFn); return tsp2Opt(tour, points, distFn); } ``` **Límite práctico:** 2-opt funciona bien hasta ~30-50 puntos. Para más, usar 3-opt o Lin-Kernighan (complejidad mayor). ### Transportation Problem — Simplex de Transporte ```javascript // Implementación simple del método de transporte (Vogel's Approximation + MODI) function solveTransportation(supply, demand, costMatrix) { // supply: [cap1, cap2, ...] (origenes) // demand: [dem1, dem2, ...] (destinos) // costMatrix: [[c11, c12, ...], [c21, c22, ...]] (coste unitario) const m = supply.length, n = demand.length; const flows = Array.from({length: m}, () => new Array(n).fill(0)); // Vogel's Approximation Method (VAM) const sup = [...supply], dem = [...demand]; for (let iter = 0; iter < m * n; iter++) { // Calcular penalizaciones (diferencia entre 2 menores costos) // Seleccionar celda con mayor penalización // Asignar el máximo posible // Actualizar supply/demand restante // (implementación completa en references/transport-simplex.md) } return flows; // flows[i][j] = cuánto enviar del origen i al destino j } ``` --- ## Distancia: Euclidiana vs Real ### Euclidiana (rápida, sin API) ```javascript function haversine(lat1, lon1, lat2, lon2) { const R = 6371000; // metros const dLat = (lat2 - lat1) * Math.PI / 180; const dLon = (lon2 - lon1) * Math.PI / 180; const a = Math.sin(dLat/2)**2 + Math.cos(lat1*Math.PI/180) * Math.cos(lat2*Math.PI/180) * Math.sin(dLon/2)**2; return R * 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); } // Para TSP y p-median, usar matriz de distancias precalculada function buildDistanceMatrix(points, distFn) { const n = points.length; const matrix = Array.from({length: n}, () => new Array(n).fill(0)); for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { const d = distFn(points[i], points[j]); matrix[i][j] = d; matrix[j][i] = d; } } return matrix; } ``` ### Real por carretera (ORS/OSRM) **CRÍTICO:** No usar API de routing para calcular la matriz de distancias completa — sería O(n²) llamadas y se agota el rate limit. **Solución:** Precalcular la matriz con euclidiana para resolver la optimización, y luego usar ORS/OSRM solo para dibujar la ruta final en el mapa. ```javascript // Patrón: optimizar con euclidiana, visualizar con routing real async function solveAndVisualize(points, p, distanceMode) { // 1. Resolver con euclidiana (instantáneo) const solution = solvePMedian(points, p, haversine); // 2. Si el usuario quiere ruta real, resolver solo las rutas necesarias if (distanceMode === 'road') { for (const d of solution.demandPoints) { const facility = points[solution.assignments[d.id]]; const route = await fetchRoute(d, facility, 'car'); // ORS/OSRM renderRoute(route); // dibujar en mapa } } return solution; } ``` ### Matrices precalculadas (para matrices grandes) ```javascript // Para 50+ puntos, precalcular en worker // y cachear en localStorage const cacheKey = `dist-matrix-${points.length}-${hash}`; const cached = localStorage.getItem(cacheKey); if (cached) return JSON.parse(cached); const matrix = buildDistanceMatrix(points, haversine); localStorage.setItem(cacheKey, JSON.stringify(matrix)); return matrix; ``` --- ## UI Pattern: Mapa + Optimización ### Layout estándar ``` ┌─────────────────────────────────────────────┐ │ Header oscuro (#1a1a2e) │ ├──────────┬──────────────────────────────────┤ │ Sidebar │ Mapa Leaflet Canvas │ │ (280px) │ │ │ │ [click → añadir punto] │ │ Problema │ │ │ (select) │ [resultado → polígonos/rutas] │ │ │ │ │ Params │ │ │ (p, modo)│ │ │ │ │ │ Input │ │ │ (click/ │ │ │ CSV) │ │ │ │ │ │ Solucionar│ │ │ │ │ │ Resultado│ │ │ (KPIs) │ │ │ │ │ │ Fórmula │ │ │ (math) │ │ └──────────┴──────────────────────────────────┘ ``` ### Entrada de datos: Click + CSV ```javascript // Patrón: dual input (click en mapa o subir CSV) let points = []; // Click en mapa map.on('click', (e) => { points.push({ lat: e.latlng.lat, lng: e.latlng.lng, name: `Punto ${points.length + 1}`, weight: 1 }); renderPoints(points); }); // CSV upload function parseOptimizationCSV(text) { const lines = text.trim().split('\n'); const headers = lines[0].toLowerCase().split(',').map(h => h.trim()); return lines.slice(1).map(line => { const vals = line.split(',').map(v => v.trim()); const obj = {}; headers.forEach((h, i) => obj[h] = vals[i]);