Al final del módulo 5 dijimos que dejábamos de afilar herramientas para salir al mundo. Esta lección es la primera salida: vamos a ver dónde vive la optimización en la industria real —logística, manufactura, energía, planificación de personal— y, sobre todo, vamos a resolver de principio a fin "un día en la operativa de Rutalia" encadenando piezas que ya construiste: el clustering de 05-05, el algoritmo húngaro de 03-06 y el TSP del módulo 2, al que añadiremos una técnica nueva y ligera (la mejora 2-opt). El objetivo ya no es entender un algoritmo, sino algo más difícil y más valioso: modelar — traducir un problema de negocio a los algoritmos correctos, elegir entre alternativas y medir la mejora en cada paso.

1. El mapa de la optimización industrial
2. El caso central: un día en la operativa de Rutalia
3. Paso 1 — Agrupar pedidos en zonas de reparto (clustering)
4. Paso 2 — Asignar repartidores a zonas (algoritmo húngaro)
5. Paso 3 — Ordenar las paradas dentro de cada zona (TSP + 2-opt)
6. Medir la mejora: el pipeline completo con métricas
7. Más allá del caso: turnos como PL, y el VRP como generalización real
8. La lección de ingeniería: "suficientemente bueno hoy"

La optimización industrial no es un algoritmo: es una disciplina de modelado. En cada sector el problema de negocio suena distinto, pero debajo casi siempre hay un problema canónico que ya conoces de este curso:

Fíjate en el patrón: la columna difícil no es la última (los algoritmos ya los tienes), sino la tercera. Reconocer el problema canónico dentro del problema de negocio es el 80 % del trabajo. Un especialista en optimización pasa más tiempo preguntando "¿qué restricciones son de verdad duras y cuáles negociables?" que programando.

Ese bucle de vuelta (medir → remodelar) es lo que distingue la optimización real de los ejercicios de libro: el primer modelo casi nunca captura todas las restricciones que el negocio daba por obvias.

Situación: son las 7:00 y Rutalia tiene 60 pedidos pendientes para hoy, repartidos por la ciudad, y 4 repartidores disponibles, cada uno con distinto conocimiento de cada parte de la ciudad. La operativa actual —la que queremos batir— es artesanal: un coordinador reparte los pedidos "a ojo" por orden de llegada y cada repartidor improvisa su ruta.

El plan algorítmico encadena tres decisiones, cada una con su algoritmo:

1. ¿Qué pedidos van juntos? → clustering k-means (05-05) con k = 4 zonas.
2. ¿Qué repartidor lleva cada zona? → asignación óptima con el algoritmo húngaro (03-06).
3. ¿En qué orden visita cada repartidor sus paradas? → TSP heurístico: vecino más cercano (02-02) + mejora 2-opt (nueva en esta lección).

Cada paso reduce el coste total y lo mediremos. Primero, los datos ficticios (coordenadas en km sobre la cuadrícula de la ciudad que usamos desde 01-03):

La métrica de negocio será kilómetros totales recorridos (todos los repartidores: salida del depósito, todas sus paradas y vuelta). Menos kilómetros = menos combustible, menos horas y más entregas por jornada.

La línea base. Para saber si mejoramos necesitamos un punto de comparación honesto: simulamos la operativa "a ojo" repartiendo los pedidos en 4 bloques por orden de llegada (sin criterio geográfico) y visitándolos en ese mismo orden.

Con la semilla fija, la línea base ronda los 330 km. Todo lo que hagamos a partir de aquí se compara contra ese número.

En 05-05 implementaste k-means y k-means++ desde cero; aquí lo usamos como pieza, sin re-explicar su mecánica. La decisión de modelado es otra: ¿por qué clustering y no, por ejemplo, un reparto equitativo de 15 pedidos por cabeza?

• Porque el coste dominante del reparto son los desplazamientos entre pedidos: pedidos cercanos deben ir juntos.
• Porque k-means minimiza exactamente eso: la dispersión intra-grupo.
• El precio: los grupos pueden quedar desequilibrados (18 pedidos en una zona, 11 en otra). En Rutalia lo aceptamos hoy; si fuera inaceptable, haría falta un modelo con restricción de capacidad (lo retomamos al hablar del VRP).

Solo con agrupar bien —sin haber ordenado todavía ninguna ruta— el total baja típicamente a unos 210 km: cada repartidor ya no cruza la ciudad entera. Primera lección de modelado: la decisión de nivel superior (qué va con qué) suele mover más la aguja que la optimización fina posterior.

Tenemos 4 zonas y 4 repartidores, pero no son intercambiables: cada repartidor conoce mejor unas partes de la ciudad (menos tiempo perdido, menos incidencias). Modelamos ese conocimiento como una matriz de coste repartidor × zona (minutos extra estimados por jornada) y resolvemos la asignación óptima con el método húngaro que ya usaste vía scipy en 03-06.

Aquí la matriz es amigable y el óptimo (42 min) se ve a simple vista, pero ese es justo el punto: con 4×4 lo ves a ojo; con 40 repartidores y 40 zonas ya no, y el húngaro sigue dándote el óptimo exacto en O(n³). Fíjate también en de dónde salen los números de la matriz: de estimaciones sobre el histórico — la optimización de este módulo consume las predicciones del módulo 5. Los módulos no eran compartimentos: eran capas.

Cada zona tiene ~15 paradas más el depósito. En 02-02 viste que el TSP exacto por PD (Held-Karp) es O(2ⁿ·n²): con 15 paradas aún es viable pero lento, y con 25 imposible. La receta industrial estándar para tamaños medios es más humilde y muy eficaz: construir una ruta rápida con el vecino más cercano (el voraz de 02-02, contraejemplo incluido) y mejorarla con 2-opt.

2-opt, la técnica nueva de esta lección. La idea cabe en una frase: si la ruta se cruza sobre sí misma, descruzarla siempre la acorta. Formalmente: toma dos aristas de la ruta, (a→b) y (c→d), elimínalas y reconecta como (a→c) y (b→d), invirtiendo el tramo entre b y c. Si la suma de las dos aristas nuevas es menor que la de las viejas, la ruta mejora. Se repite hasta que ningún intercambio mejore (óptimo local).

Detalles que importan al leer el código:

• La condición despues < antes - 1e-9 evita bucles infinitos por errores de redondeo en coma flotante: solo aceptamos mejoras estrictas.
• Cada pasada evalúa O(n²) intercambios; con 15 paradas es instantáneo. Con cientos de paradas, 2-opt sigue sirviendo pero conviene acelerarlo (listas de vecinos cercanos) o escalar a metaheurísticas: los genéticos (02-04) y la colonia de hormigas (02-05) son exactamente la evolución natural cuando 2-opt se estanca en un óptimo local pobre o la instancia crece.
• 2-opt da un óptimo local, no global — la misma limitación que viste en k-means (05-05) y en el descenso de gradiente (05-03). Es un tema recurrente del curso: casi toda la optimización práctica es "mejora local + saber cuándo conformarse".

Recapitulemos el día de Rutalia con números (los tuyos variarán algo con otra semilla; el orden de magnitud es lo estable):

Tres observaciones de ingeniería:

• Cada capa se mide por separado. Si mañana el negocio pregunta "¿qué pasa si quito el 2-opt para simplificar?", la respuesta es un número (~13 km/día), no una opinión.
• La ganancia marginal decrece. El clustering ahorró ~120 km; el 2-opt, ~13. Esa curva te dice dónde invertir el siguiente esfuerzo.
• La línea base honesta es sagrada. Compararse contra una línea base artificialmente mala infla la mejora y destruye la credibilidad del proyecto. Es el equivalente operativo de la trampa de la exactitud de 05-02.

Planificación de turnos. El otro gran clásico industrial se modela con la programación lineal de 02-01. Ejemplo mínimo: Rutalia necesita cubrir una demanda de repartidores por franja (mañana 6, mediodía 10, tarde 8, noche 3) con turnos de 8 horas que cubren dos franjas consecutivas (el turno de noche enlaza con la mañana). Variables: cuántas personas empiezan en cada franja; objetivo: minimizar plantilla; restricciones: cada franja cubierta.

El parámetro integrality pide soluciones enteras (no puedes contratar 2,5 repartidores): es la PL entera que en 02-01 vimos que dispara la complejidad teórica, pero que los solvers modernos manejan sin despeinarse a estos tamaños.

El VRP. Nuestro pipeline (clustering + TSP por zona) es en realidad una heurística clásica —cluster first, route second— para el Vehicle Routing Problem, la generalización industrial del TSP. El VRP añade lo que el TSP ignora: capacidad de cada vehículo (kilos, volumen), ventanas de tiempo de entrega ("entre 9:00 y 11:00"), flotas heterogéneas, varias pasadas por el depósito. Es NP-duro con agravantes, y en la práctica casi nadie lo resuelve desde cero: se usan solvers especializados como Google OR-Tools (gratuito y omnipresente en logística), que combinan por dentro construcción voraz, búsqueda local tipo 2-opt/3-opt y metaheurísticas — exactamente las familias que has aprendido. Conocer lo que hay dentro de la caja es lo que te permite configurarla bien y detectar cuándo su respuesta no tiene sentido.

En 02-02 calculamos el óptimo exacto del TSP de 9 paradas (35,22 km) porque el tamaño lo permitía. Hoy, con 60 pedidos y las furgonetas saliendo a las 8:00, la pregunta correcta no es "¿cuál es el óptimo?" sino "¿cuánta mejora me cabe antes de las 8:00?". La regla de oro de la optimización industrial:

Una solución un 5 % peor que el óptimo, disponible a tiempo, vale infinitamente más que el óptimo que llega tarde. El óptimo es el patrón de medida, no siempre el objetivo.

Y una advertencia que no es retórica: los resultados de estos modelos son recomendaciones. Antes de aplicarlos a una operativa real (rutas, turnos, asignaciones de personas) deben validarlos quienes conocen el terreno y las obligaciones del negocio —normativa laboral, restricciones de tráfico, compromisos con clientes—, porque el modelo solo optimiza lo que se le puso en la función objetivo, y la realidad siempre tiene restricciones que nadie escribió. La decisión final es humana.

• Optimizar sin línea base. Si no mides la situación actual con la misma métrica, no puedes afirmar que mejoraste. Es el error número uno en proyectos reales.
• Confundir el óptimo del modelo con el óptimo del negocio. El modelo minimiza kilómetros; el negocio quizá valora más la puntualidad. Pregunta qué se optimiza de verdad antes de escribir la función objetivo.
• Aplicar 2-opt sin tolerancia numérica. Aceptar "mejoras" de tamaño 1e-15 provoca bucles infinitos por redondeo. Usa siempre despues < antes - epsilon.
• Encadenar etapas sin revisar el acople. Cluster first, route second es una heurística: un clustering óptimo puede inducir rutas mediocres. Si el resultado global decepciona, prueba a variar k o a mover pedidos frontera entre zonas y re-rutar.
• Reinventar el VRP. Para problemas con capacidades y ventanas de tiempo, evalúa OR-Tools u otro solver antes de escribir el tuyo: tu valor está en el modelado y la validación, no en reimplementar búsqueda local madura.
• Consejo: fija las semillas aleatorias (random.seed) en los experimentos. Sin reproducibilidad no hay comparación justa entre variantes.

1. Sensibilidad al número de zonas. Ejecuta el pipeline completo con k = 3, 4, 5 y 6 zonas (con su correspondiente número de repartidores) y construye la tabla k → km totales tras 2-opt. ¿Sigue bajando el total al subir k? ¿Qué coste oculto tiene subir k que los kilómetros no reflejan?
2. El voraz engañado, revisitado. Construye una zona de 12 paradas donde el vecino más cercano produzca una ruta al menos un 15 % peor que la que se obtiene tras aplicar 2-opt (pista: recuerda el contraejemplo del voraz de 02-02 — paradas casi en línea con una trampa cerca del origen). Verifícalo con coste_ruta.
3. Turnos con techo. Amplía el modelo de turnos a 6 franjas de 4 horas con demanda [4, 6, 10, 9, 7, 3], turnos que cubren dos franjas consecutivas (el de la franja 5 enlaza con la 0) y la restricción adicional de que en ninguna franja puede haber más de 12 personas activas. Resuélvelo con linprog e integrality.

1. Con los focos del ejemplo, k=4 coincide con la estructura real de la demanda y da el mejor equilibrio; k=5 y k=6 apenas reducen kilómetros (a veces incluso los suben, porque más zonas implican más viajes depósito↔zona) y añaden el coste oculto de un repartidor y un vehículo más por zona. La curva km-vs-k tiene forma de codo — exactamente el método del codo que usaste para elegir k en 05-05: el mismo criterio estadístico resulta ser un criterio de negocio.
2. Un patrón que funciona: depósito en (0,0), una parada "cebo" en (0.5, 0.1) y el resto casi colineales en x = 1..10 (y≈0), con una parada final en (10, 3). El vecino más cercano muerde el cebo, recorre la línea y el retorno cruza toda la ciudad; también suele zigzaguear entre paradas casi equidistantes. 2-opt descruza esos retornos. Midiendo con coste_ruta, la mejora supera con holgura el 15 %. La moraleja de 02-02 se mantiene: el voraz es un buen constructor, no un buen terminador.
3. Con cobertura circular, la restricción de demanda de la franja f es x[(f-1) % 6] + x[f] >= demanda[f] (filas con -1 en esas dos posiciones y b_ub = -demanda[f]), y la de techo es la misma pareja con signo positivo y b_ub = 12. Son 12 filas en total. Con la demanda dada, el mínimo entero factible ronda las 20 personas; comprueba en la solución que la franja de demanda 10 queda cubierta casi exacta y que ninguna supera 12 — cuando una restricción de techo y una de demanda aprietan a la vez, el solver "desplaza" inicios de turno hacia franjas valle.

Has visto el catálogo de la optimización industrial y has resuelto un día completo de Rutalia encadenando tres algoritmos de tres módulos distintos: clustering (05-05) para decidir qué va junto, el húngaro (03-06) para decidir quién hace qué, y vecino más cercano + 2-opt (02-02 y esta lección) para decidir en qué orden — con una métrica midiendo cada eslabón y una mejora total cercana al 70 % sobre la operativa artesanal. Las ideas que debes llevarte: reconocer el problema canónico es el 80 % del trabajo, las decisiones de nivel alto mueven más la aguja que el pulido fino, y "suficientemente bueno a tiempo" gana al óptimo tardío. En la próxima lección cambiamos de dominio pero no de método: las redes sociales como grafos, donde el BFS, las componentes y el clustering que ya dominas se convierten en detección de comunidades, medición de influencia —con PageRank como caso estrella— y recomendación de amistades.