Si reparte a 15, 30 o 100 clientes al día, ya ha estado haciendo TSP sin saberlo: el Traveling Salesman Problem, o problema del viajante. Es uno de los problemas más estudiados de la informática, y es exactamente el que resuelve OptiRoad cada vez que pulsa "Optimizar". Esta guía explica en lenguaje claro qué es, por qué es más difícil de lo que parece y cómo se resuelve en la práctica.
El problema, en una frase
Tiene un punto de partida (su almacén, su casa) y una lista de direcciones que visitar en el día. ¿Cuál es el orden de paso que minimiza la distancia total recorrida? Eso es el TSP.
Trivial de plantear, brutalmente difícil de resolver cuando se pasan de una decena de direcciones. Y es precisamente ahí donde la intuición humana se queda corta: el ojo detecta con facilidad una buena ruta de 5 paradas, pero mucho peor una de 40.
Un ejemplo concreto
Imagine 5 entregas en Madrid:
- A: Sol
- B: Atocha
- C: Chamartín
- D: Moncloa
- E: Retiro
Si parte del almacén y pasa por orden alfabético A → B → C → D → E, probablemente hará zigzag por la ciudad. En concreto, esa ruta alfabética le hace cruzar Madrid de un extremo a otro y volver: cuente unos 13 km. Reorganizando inteligentemente las mismas 5 direcciones (por ejemplo agrupando las paradas cercanas entre sí), el orden optimizado baja a unos 9 km, aproximadamente un 30 % menos para exactamente las mismas entregas. Sobre 200 días laborables al año, ese ahorro por ruta son miles de kilómetros: horas de conducción y un presupuesto de combustible nada despreciable.
Por qué el TSP es difícil
Con 5 direcciones hay 5! = 120 órdenes posibles. Un humano puede probarlos a mano. Con 10 direcciones, sube a 3,6 millones de órdenes. Con 20, son 2,4 trillones. Ninguna máquina del mundo puede probar todas las combinaciones de una ruta de 30 entregas en un tiempo razonable.
El TSP es lo que se llama un problema NP-difícil: ningún algoritmo conocido puede garantizar la solución perfecta en un tiempo que escale razonablemente con el número de paradas. Cada dirección añadida multiplica el espacio de soluciones, no solo lo suma.
Para recordar: para 10 direcciones o menos, aún se pueden probar todas las combinaciones y garantizar el óptimo absoluto. Más allá, se usan heurísticas, estrategias que dan una solución muy buena sin garantizar la perfección matemática.
Un poco de historia
El TSP no es ninguna novedad. Los matemáticos lo estudian desde los años 1930: el matemático austríaco Karl Menger lo planteó en Viena dentro de su círculo científico, y el problema pronto se difundió por las universidades estadounidenses. El punto de inflexión llegó en los años 1950 en la RAND Corporation, donde George Dantzig, Delbert Ray Fulkerson y Selmer Johnson publicaron en 1954 la resolución exacta de una instancia célebre: una ruta óptima que enlazaba 49 ciudades de Estados Unidos (una por estado, más Washington). Fue una hazaña para la época, lograda con métodos de programación lineal y mucho cálculo a mano. Aún hoy, el TSP sigue siendo un banco de pruebas de referencia en investigación de operaciones y logística: los nuevos algoritmos se miden a menudo sobre estas instancias históricas.
Los enfoques en la práctica
1. Fuerza bruta (≤ 10 paradas)
Se prueban todas las permutaciones posibles y se guarda la mejor. Garantiza el óptimo absoluto, pero deja de ser práctico más allá de 10 paradas.
2. Vecino más cercano (heurística simple)
En cada paso, se va a la parada más cercana de la anterior. Rápido, pero a menudo lejos del óptimo: se puede acabar atrapado lejos del resto de paradas.
3. 2-opt (mejora local)
Se parte de una solución inicial (a menudo de vecino más cercano), luego se intentan "deshacer" los cruces invirtiendo segmentos de la ruta. Iterativo, normalmente da resultados a menos del 5 % del óptimo teórico.
4. Algoritmos más avanzados
Lin-Kernighan, recocido simulado, algoritmos genéticos, programación por restricciones: existen muchos enfoques en investigación de operaciones. Para un uso de negocio como el reparto, vecino más cercano + 2-opt ofrece el mejor compromiso de simplicidad, calidad y velocidad.
¿Óptimo perfecto o muy bueno al instante?
Esta es la verdadera pregunta cuando se diseña una herramienta de reparto. Un solver puede aspirar a la solución matemáticamente perfecta, pero esta puede requerir horas de cálculo en una ruta grande. Sobre el terreno, sin embargo, nadie espera horas para salir a repartir. Una solución a un pequeño porcentaje del óptimo, calculada en segundos, gana de calle a una solución perfecta que llega demasiado tarde.
¿Por qué? Porque los últimos puntos porcentuales de distancia recortados casi nunca compensan la espera: entre una ruta de 9,0 km y una de 8,8 km, la diferencia a lo largo de su jornada es insignificante, mientras que el tiempo de cálculo puede dispararse. Por eso las heurísticas como vecino más cercano + 2-opt son la decisión de ingeniería acertada: aportan lo esencial de la ganancia, de inmediato y de forma fiable. La perfección teórica es cosa de los investigadores; la rentabilidad diaria, de los repartidores.
Las variantes que importan para el reparto
El TSP "puro" supone que se vuelve al punto de partida al final. En la práctica, sus restricciones son más ricas:
- TSP open-loop: sin vuelta al almacén (termina en el último cliente).
- VRPTW (Vehicle Routing Problem with Time Windows): cada dirección tiene una franja horaria de apertura (ej. 9 a 12). Es lo que usa para las franjas de entrega.
- VRP multi-vehículo: varios repartidores, así que ¿cómo repartir las paradas entre vehículos para minimizar el tiempo total?
- VRP con capacidades: cada vehículo tiene una carga útil máxima.
OptiRoad gestiona estas variantes: VRPTW para franjas horarias (planes Pro y Business) y VRP multi-vehículo con algoritmo Clarke-Wright Savings (plan Business, hasta 10 vehículos).
Cómo resuelve OptiRoad su TSP
Cada vez que pulsa Optimizar en el panel, OptiRoad aplica la siguiente estrategia:
- Geocodifica sus direcciones (las transforma en coordenadas GPS) si no lo están.
- Construye la matriz de distancias entre todos los puntos vía OpenRouteService (o Google Routes como fallback).
- Si ≤ 10 paradas: fuerza bruta, todas las permutaciones probadas, óptimo absoluto garantizado.
- Si no: vecino más cercano para construir la ruta inicial, luego 2-opt para afinar por iteraciones sucesivas.
- Si VRPTW activado: el solver respeta las franjas vía un enfoque Earliest Deadline First, señalando todo retraso previsible.
- Si multi-vehículo: Clarke-Wright Savings para repartir paradas, luego TSP local en cada ruta.
Todo en pocos segundos (3 segundos para 15 paradas, hasta 20 segundos para 150 paradas con timeout adaptativo).
En la práctica: lo que cambia para usted
Sobre una ruta típica de 30 entregas en zona urbana:
- Sin optimización: unos 120 km, unas 5h de ruta
- Con OptiRoad: unos 85 a 90 km, unas 3h30 a 4h de ruta
- Ganancia típica: 25 a 30 % de distancia, 20 a 30 % de tiempo
Sobre 200 días laborables al año, eso son miles de kilómetros y cientos de horas ahorradas. Y todo viene de resolver un problema que se llama "el TSP" desde 1930.
Preguntas frecuentes
¿Cuántas direcciones puede optimizar OptiRoad?
Hasta 150 paradas por ruta. Hasta 10 paradas, la fuerza bruta prueba todas las combinaciones y garantiza el óptimo absoluto. Más allá, OptiRoad pasa a las heurísticas (vecino más cercano y luego 2-opt), que siguen siendo excelentes incluso en rutas grandes.
¿La ruta es siempre la más corta posible?
Sí, y está garantizado matemáticamente hasta 10 paradas. Más allá, el resultado se sitúa normalmente a menos de un 5 % del óptimo teórico gracias al 2-opt: una diferencia imperceptible sobre el terreno, con un cálculo casi instantáneo.
¿Necesito un punto de partida?
Sí. Hace falta un punto de partida: un almacén o una dirección de domicilio. El punto de llegada, en cambio, es opcional: si no indica ninguno, OptiRoad asume que vuelve a su punto de partida (ruta en bucle).
¿Cuánto tarda el cálculo?
Unos segundos. OptiRoad usa un timeout adaptativo: unos 3 segundos para las rutas pequeñas, hasta 20 segundos para 150 paradas. Si se alcanza el límite, la herramienta devuelve igualmente la mejor ruta encontrada.
Para ir más lejos
Si quiere ver el algoritmo en acción sobre sus propias direcciones, el plan gratuito de OptiRoad incluye 5 rutas al mes hasta 10 paradas, exactamente la zona donde la fuerza bruta garantiza el óptimo absoluto. Es la mejor forma de medir concretamente lo que ganará.
¿Quiere profundizar en las variantes (franjas horarias, multi-vehículo)? Continúe con los otros artículos del blog o lea la documentación API.