¿Tienes veinte direcciones y quieres saber en qué orden visitarlas para manejar lo menos posible? Eso es buscar la ruta más corta entre varios puntos, y aunque suena a un problema de sentido común, es de los más estudiados de la investigación de operaciones. Llevo más de veinte años construyendo modelos que lo resuelven para empresas, y aquí te explico por qué no es tan obvio como parece, por qué Google Maps no lo hace por ti, y cómo calcularlo gratis.
Ordenar puntos no es lo mismo que acomodarlos en el mapa
La intuición más común es ir siempre a la parada más cercana: sales de la bodega, vas a la entrega que tienes más a la mano, y de ahí a la siguiente más cercana. Se llama método del vecino más próximo, y casi nunca da la mejor ruta. El problema es que las últimas paradas te dejan cruzando toda la ciudad para cerrar el recorrido, porque nunca las tomaste en cuenta cuando decidías las primeras.
Encontrar la ruta más corta de verdad significa mirar el recorrido completo, no una parada a la vez. Y ahí es donde el número de combinaciones se dispara.
El problema del agente viajero
Este problema tiene nombre y más de un siglo de historia: se llama el problema del agente viajero (o del viajante), y consiste exactamente en eso — dada una lista de puntos y las distancias entre ellos, ¿cuál es el recorrido más corto que los visita todos y regresa al inicio? Puedes leer la definición formal en el artículo del problema del viajante en Wikipedia.
Lo que lo hace difícil es la explosión combinatoria. Con pocas paradas puedes probar todos los órdenes a mano; con muchas, ni todas las computadoras del mundo alcanzan. Solo con 15 paradas hay más de 43 mil millones de recorridos posibles. Por eso no existe una fórmula que te lo dé instantáneo: se resuelve con algoritmos que buscan de forma inteligente, no probando todo.
Cómo calcular la ruta más corta entre varios puntos, gratis
Para no pelearte con la teoría, publiqué una versión gratuita de estos modelos en la web. Para calcular la ruta más corta entre varios puntos solo tienes que hacer esto:
- Abre el optimizador de rutas en español.
- Pega tu lista de direcciones, una por renglón (el primer renglón es tu punto de partida).
- Dale optimizar. En segundos te devuelve el orden más corto y un enlace para abrirlo en Google Maps.
No pide registro ni tarjeta, y no tiene el límite de 10 paradas de Google Maps. Si quieres entender qué debería tener una herramienta así por dentro, lo cuento en detalle en mi guía del optimizador de rutas gratis.
¿Y si son cientos de puntos?
Cuando el problema crece, ya no se busca la respuesta perfecta sino una muy buena en un tiempo razonable. Los métodos que uso (búsqueda local guiada, del tipo que trae Google OR-Tools) mejoran una ruta inicial una y otra vez hasta que dejan de encontrar mejoras. En la práctica, para un reparto real, la diferencia entre la solución óptima y una buena heurística es mínima — y la heurística la tienes en segundos en vez de horas.
El error de medir en línea recta
Un detalle que arruina muchos cálculos caseros: la distancia en línea recta miente. Dos puntos pueden estar a 800 metros en el mapa y a 15 minutos manejando, porque hay un río, una vía rápida o calles de un solo sentido en medio. Una ruta corta de verdad se calcula con tiempos de manejo reales sobre la red de calles, no con la regla sobre el mapa. El optimizador ya usa esos tiempos reales por ti.
Preguntas frecuentes
¿Google Maps calcula la ruta más corta entre mis paradas? No. Google Maps navega muy bien entre dos puntos, pero cuando pones varias paradas las visita en el orden en que las escribiste; no reordena para acortar el recorrido.
¿Cuántos puntos aguanta el optimizador? Más de 100. El único tope es el tiempo de cómputo (hasta unos dos minutos por corrida), suficiente para un día de reparto completo.
¿Necesito saber programar o de matemáticas? No. Pegas las direcciones y listo; toda la parte del problema del agente viajero ocurre por dentro.
¿Y si tengo varias camionetas? Ahí ya no basta con ordenar puntos: hay que decidir qué parada le toca a cada vehículo. Eso lo cubro en mi guía de cómo planificar rutas de reparto.
En resumen
Encontrar la ruta más corta entre varios puntos no es acomodarlos a ojo: es el problema del agente viajero, y crece más rápido de lo que la intuición cree. La buena noticia es que ya está resuelto y lo puedes usar gratis — pega tus direcciones en el optimizador y deja que él haga las cuentas mientras tú manejas.
Things that I use, like, and am affiliated with:
Mint Mobile offers great cell phone service for $15 flat, get $15 off using the link. Get discounted phones with service activation and no contract.
I never spend money before I check Mr Rebates or Rakuten to get cashbacks, rebates, discounts, coupons or cheaper gift cards.