Rutas de última milla
VRP con ventanas de tiempo, capacidades y tráfico en tiempo real: cientos de vehículos, miles de paradas, minutos para decidir cada mañana.
TSP · VRP · colonias de hormigasLaboratorio de optimización combinatoria · SSA
Cuando el espacio de soluciones crece más rápido que cualquier computador, la eurística toma el mando: reglas de búsqueda inspiradas en la naturaleza que encuentran soluciones muy buenas en tiempo razonable. Esta página lo demuestra en vivo — empezando por el clásico entre clásicos.
§ 01 · el problema
Un problema combinatorio pide elegir la mejor configuración entre un conjunto finito pero astronómico de posibilidades: un orden, una asignación, un subconjunto. La enumeración exhaustiva es el método exacto… y es impracticable casi siempre.
| n | permutaciones n! | tiempo exacto* |
|---|
* evaluando 10⁹ soluciones por segundo — más de las que caben en un parpadeo.
Aquí nace la eurística. Del griego heurískō (εὑρίσκω): descubrir, encontrar. En lugar de garantías absolutas, ofrece un pacto honesto: una solución de alta calidad, un coste de cómputo acotado y la posibilidad de seguir mejorando si le das más tiempo.
La optimización combinatoria formaliza ese pacto con cuatro piezas — y casi todos los problemas industriales pueden escribirse con ellas.
El conjunto de todas las configuraciones factibles: permutaciones, subconjuntos, asignaciones. En un TSP de 30 ciudades, 𝒮 tiene ~2,6 × 10³⁰ elementos.
La medida de calidad que se quiere minimizar (coste, distancia, tiempo) o maximizar (beneficio, fiabilidad). Es el paisaje que exploran los algoritmos.
Lo que convierte una combinación cualquiera en una solución factible: capacidades, plazos, exclusividad, conectividad. Definen la frontera de 𝒮.
Las soluciones «cercanas» a s bajo un movimiento simple: intercambiar dos elementos, invertir un tramo, añadir o quitar un ítem. El motor de la búsqueda local.
§ 03 · el algoritmo
Publicado en 2020, el SSA modela el forrajeo de una bandada de gorriones: unos pocos descubren la comida, el resto sigue al que más tiene, y un grupo vigila a los depredadores. La metáfora se traduce en tres operadores matemáticos.
Los individuos con mejor fitness guían a la bandada. Su paso se ensancha al inicio y se estrecha al final de la búsqueda: exploración que madura en explotación.
Monitorizan a los productores y se desplazan hacia el mejor filón descubierto; los más hambrientos se dispersan aleatoriamente en busca de comida nueva.
Vigilan el peligro (un óptimo local, un depredador). Al detectarlo, parte de la bandada se teletransporta: diversidad inyectada justo cuando más hace falta.
¿Y en problemas combinatorios? Las posiciones se codifican como permutaciones o subconjuntos y las ecuaciones se reescriben con swaps, inversiones y máscaras binarias — la lógica de roles (producir, seguir, alarmarse) se conserva intacta. Así se aplica SSA a TSP, mochila o scheduling.
§ 04 · laboratorio en vivo
El mismo terreno de fitness (minimizar), tres estrategias. Observa quién cae en el óptimo local, quién salta fuera y quién converge con la bandada.
terreno #7 · el valle más oscuro es el óptimo global · los algoritmos minimizan f(x,y)
§ 05 · resultados
Con instancias de referencia de óptimo conocido (TSPLIB) y una mérica honesta: el gap — cuánto nos quedamos por encima de la solución perfecta.
SSA binario con operador 2-opt de reparación · presupuesto fijo de evaluaciones · resultados ilustrativos
| instancia | n | óptimo TSPLIB | mejor SSA | gap % | gap visual |
|---|---|---|---|---|---|
| berlin52 | 52 | 7.542 | 7.612 | 0,93 | |
| eil51 | 51 | 426 | 431 | 1,17 | |
| eil76 | 76 | 538 | 549 | 2,04 | |
| kroA100 | 100 | 21.282 | 21.604 | 1,51 | |
| kroA150 | 150 | 26.524 | 27.118 | 2,24 | |
| pcb442 | 442 | 50.778 | 52.350 | 3,09 |
nada es gratis: el teorema No-Free-Lunch recuerda que ninguna metaheurística domina en todos los problemas — el diseño está en casar algoritmo y estructura.
§ 06 · en el mundo real
VRP con ventanas de tiempo, capacidades y tráfico en tiempo real: cientos de vehículos, miles de paradas, minutos para decidir cada mañana.
TSP · VRP · colonias de hormigasTurnos hospitalarios, puertas de aeropuerto, órdenes de fabricación en job-shop: asignar recursos escasos a tareas con fechas y precedencias.
job-shop · recocido simulado · tabúColocar y enrutar millones de celdas minimizando longitud de cable y consumo.
placement · QAPDónde situar antenas, hubs logísticos o centros de datos para cubrir más con menos.
set cover · steinerSeleccionar activos con cardinalidad limitada y correlaciones: un knapsack cuadrático.
knapsack · SSA binarioPlegamiento de proteínas, diseño de experimentos, búsqueda de hiperparámetros: espacios discretos gigantes donde cada evaluación es cara y la eurística es la única vía.
optimización negra · enjambresAulas a exámenes, jueces a partidos, donantes a receptores: restricciones duras que convierten cualquier asignación «casi válida» en un laberinto combinatorio.
matching · graph coloring§ 07 · vocabulario