🚚 Optimizador de Rutas de Reparto — Recocido Simulado en Vivo

El recocido simulado es una técnica de optimización probabilística inspirada en el proceso metalúrgico de calentar un metal y enfriarlo lentamente para que sus átomos se asienten en una estructura cristalina de baja energía. Aplicado al problema del viajante / enrutamiento de vehículos, la "energía" es la distancia total del recorrido. A alta temperatura el algoritmo acepta muchos movimientos que empeoran la solución, permitiéndole explorar ampliamente y escapar de disposiciones locales pobres; a medida que la temperatura baja se vuelve cada vez más codicioso, refinando el recorrido hasta converger cerca de una ruta corta. Es popular para el enrutamiento porque el espacio de búsqueda de posibles órdenes de paradas es de tamaño factorial, demasiado grande para buscar exhaustivamente, aunque los entornos 2-opt combinados con el recocido encuentran de forma fiable recorridos a pocos puntos porcentuales del óptimo.

Un movimiento 2-opt elimina dos aristas del recorrido y reconecta los cuatro extremos de la única otra forma que mantiene un único bucle cerrado, lo que equivale a invertir el orden de las paradas entre los dos puntos de corte. Es el movimiento de búsqueda local más simple capaz de deshacer un cruce en el recorrido: siempre que dos segmentos de ruta se cruzan en el mapa, exactamente un movimiento 2-opt los endereza y acorta la distancia total. Como solo cambian dos aristas, el cambio en la longitud del recorrido (Δ) puede calcularse comparando solo esas dos aristas antiguas y las dos nuevas, sin volver a sumar toda la ruta.

Una vez calculado el delta de coste de un movimiento candidato, el algoritmo siempre acepta los movimientos que acortan el recorrido (Δ < 0). Para los movimientos que lo alargan, se aceptan con probabilidad e^(−Δ/T), donde T es la temperatura actual. Esto significa que un movimiento que empeora mucho rara vez se acepta, pero los movimientos que empeoran poco siguen siendo bastante probables al principio, cuando T es alta. A medida que T decae hacia cero, e^(−Δ/T) colapsa hacia cero para cualquier Δ positivo, de modo que el algoritmo se convierte en la práctica en un descenso puramente codicioso — no se permite subir colinas y solo sobreviven los movimientos que mejoran.

Esta simulación usa enfriamiento geométrico: T se multiplica por una tasa de enfriamiento α (cercana a 1 pero por debajo) tras cada movimiento propuesto, de modo que T decae exponencialmente con el número de iteraciones. Una tasa de enfriamiento muy cercana a 1 (por ejemplo, 0.9995) enfría lentamente, dando a la búsqueda muchas iteraciones a temperaturas más altas para explorar ampliamente antes de comprometerse a refinar una solución — esto suele encontrar recorridos más cortos, pero tarda más en estabilizarse. Una tasa de enfriamiento más baja (por ejemplo, 0.985) enfría rápido y se comporta casi como una búsqueda local 2-opt codiciosa, convergiendo rápidamente pero con más probabilidad de quedar atrapada en un mínimo local mediocre.

Ese es precisamente el objetivo del recocido: a alta temperatura, el criterio de Metrópolis acepta deliberadamente algunos movimientos que aumentan la longitud. Un recorrido puede parecer localmente óptimo (ningún movimiento 2-opt individual lo mejora) y sin embargo estar lejos del recorrido más corto posible — esto es un mínimo local. Al aceptar ocasionalmente un movimiento peor, la búsqueda puede salir de la cuenca de ese mínimo local y caer más tarde en otro distinto y más corto. Observando el gráfico de distancia, normalmente lo verás caer rápido al principio, subir de forma puntual mientras T sigue alta, y luego asentarse en un descenso monótono y suave a medida que T se aproxima a cero.

Las empresas de logística reales resuelven problemas de enrutamiento de vehículos (VRP) con cientos o miles de paradas, múltiples vehículos, ventanas horarias y límites de capacidad — un problema combinatorio NP-difícil donde las soluciones exactas son computacionalmente inviables más allá de unas pocas decenas de paradas. Metaheurísticas como el recocido simulado, junto con los algoritmos genéticos, la optimización por colonia de hormigas y la búsqueda tabú, son herramientas estándar en la industria para encontrar rutas muy buenas (aunque no demostrablemente óptimas) en segundos o minutos. Esta simulación modela el núcleo de un solo vehículo de ese problema — el clásico problema del viajante — que es el mismo motor combinatorio que hay en el corazón del software de enrutamiento en producción.