Cómo funciona la optimización de rutas (en palabras simples)

La optimización de rutas consiste en elegir el mejor orden para visitar un conjunto de paradas, dado dónde empiezas y dónde necesitas terminar. "Mejor" suele significar la menor distancia o el menor tiempo de conducción. Para un negocio con varios vehículos, también implica decidir qué vehículo visita qué paradas.

Funciona junto con la navegación, no en lugar de ella. Tu app de navegación encuentra las mejores calles de una parada a la siguiente; la optimización de rutas decide qué parada va después. Se confunden porque ambas terminan en una línea sobre un mapa.

Todo optimizador de rutas, desde una herramienta web gratuita hasta un sistema de despacho empresarial, ejecuta alguna versión de los mismos cuatro pasos.

1. Geocodificación

Cada dirección se compara con una base de datos de calles y puntos de dirección y se convierte en un par de coordenadas. Es el paso que la gente olvida y el que está detrás de la mayoría de las rutas malas: una parada ubicada en la ciudad equivocada arrastra todo el orden. Consulta por qué las direcciones caen en el lugar equivocado.

2. La matriz de distancias

Luego viene una tabla con la distancia entre cada par de paradas: 20 paradas forman una cuadrícula de 20 × 20 con 380 entradas que importan. Algunos optimizadores la llenan con distancias por carretera o tiempos de viaje de un servicio de rutas. Otros usan la distancia en línea recta, que es instantánea y ordena las paradas cercanas casi igual en zonas urbanas. Las tablas basadas en carreteras tardan más en construirse y manejan mejor los ríos, las autopistas y los sistemas de calles de un solo sentido.

3. El orden

La parte difícil: encontrar un orden corto sin revisar todos los posibles. La siguiente sección explica cómo.

4. Las indicaciones

Por último, el orden elegido pasa por un motor de rutas por carretera, del mismo tipo que usa tu app de navegación, que devuelve la línea por las calles reales, la longitud de cada tramo y un tiempo de conducción estimado.

No prueban todos los órdenes; son demasiados. Un viaje de ida y vuelta por 15 lugares ya tiene más de 43 mil millones. En cambio, usan heurísticas: métodos que arman una buena ruta rápidamente y luego la mejoran, cambiando la garantía de perfección por una respuesta inmediata que suele estar muy cerca de la mejor.

1. 1

   Armar una primera ruta

   El vecino más cercano parte de la base y siempre va a la parada más próxima que aún no ha visitado. Es rápido y sensato, pero codicioso: tiende a dejar las paradas dispersas para el final, y la ruta se cruza consigo misma. Los métodos de inserción, en cambio, hacen crecer un circuito agregando cada parada donde cuesta menos.

2. 2

   Mejorarla con intercambios

   2-opt toma dos tramos de la ruta e invierte el trecho que hay entre ellos siempre que eso acorte el viaje. Así elimina los cruces, y se repite hasta que ningún intercambio ayude. Or-opt mueve una secuencia corta de una a tres paradas a un lugar mejor de la ruta.

3. 3

   Buscar más a fondo, si hay tiempo

   Métodos más pesados como Lin-Kernighan, conocido sobre todo por el programa LKH, encadenan muchos intercambios. Las metaheurísticas como el recocido simulado, la búsqueda tabú y los algoritmos genéticos a veces aceptan a propósito una ruta peor para salir de un callejón sin salida. Los solucionadores exactos pueden demostrar la mejor ruta posible, a un costo mucho mayor de tiempo de cómputo.

Depende de qué tan desordenadas estuvieran las paradas al principio. En nuestras 48 rutas de ejemplo de 7 a 12 paradas en carreteras reales de 24 ciudades, optimizar paradas que partían en orden aleatorio redujo la distancia en una mediana de 39% y el tiempo de conducción en una mediana de 36%.

Mediana de distancia ahorrada

39%

Mediana de tiempo de conducción ahorrado

36%

Rutas de ejemplo medidas en carreteras reales

48

Si ya ordenas tus paradas con cuidado a mano, espera menos: el optimizador sobre todo detecta algún cruce o tramo en el que se retrocede. Cuanto más grande la lista y menos conocida la zona, mayor la mejora. Ponle cifra en dólares con la calculadora de costo de rutas.

El problema del viajante (TSP) es un solo vehículo que visita cada parada una vez por la ruta más corta. El problema de ruteo de vehículos (VRP) incorpora una flota: varios vehículos y la decisión de qué paradas le toca a cada uno. Las versiones del mundo real suman reglas encima, y cada regla hace el problema más difícil de resolver.

Eso explica en buena parte por qué el software de rutas va de gratuito a cientos de dólares al mes. Las paradas de un día para un vehículo son un trabajo rápido para una computadora. Veinte camionetas con ventanas horarias y capacidades es un problema realmente difícil, y necesita datos que hay que mantener al día: ventanas, duración de las visitas, tamaños de los vehículos.

EZRoutePlanner resuelve el problema de una sola ruta: una ruta a la vez, en el orden más corto que encuentra. Pulsa Optimizar ruta y las paradas se ordenan por vecino más cercano seguido de mejoras 2-opt, con tu inicio fijo y el final de regreso al inicio (Viaje de ida y vuelta) o en una parada que hayas fijado como última.

Compara órdenes usando la distancia en línea recta entre paradas, lo bastante rápida para ejecutarse en tu navegador mientras trabajas, y luego dibuja el resultado sobre calles reales con la distancia de cada tramo. Los planes de pago suman tiempos de viaje e indicaciones que evitan autopistas o peajes. Donde un río o una autopista separa dos paradas que parecen cercanas, revisa el orden y mueve una parada a mano si las calles no coinciden.

Para varios conductores, haces el reparto tú mismo: marca con el lazo cada zona del mapa como su propia ruta y luego optimiza cada una. Para un negocio con pocas rutas en una zona conocida, suele ser más rápido que configurar un VRP completo. Consulta cómo planificar rutas para varios conductores.