Solucionador del problema del viajante

Porque el número de órdenes posibles se dispara. Con una salida fija, n paradas se pueden visitar en (n − 1)! órdenes, y un viaje de ida y vuelta y su inverso miden lo mismo, así que hay (n − 1)! ÷ 2 circuitos distintos.

Matemáticamente es NP-difícil: nadie conoce un método que garantice hallar rápido la mejor ruta en todos los casos. Por eso los planificadores de rutas reales usan heurísticas: métodos rápidos que encuentran rutas muy buenas, normalmente a pocos puntos porcentuales de la mejor posible.

1. 1

   Vecino más cercano

   Empieza en la base y maneja siempre a la parada más cercana que aún no has visitado. Es rápido y por lo general decente, pero se acorrala solo: las últimas paradas suelen quedar lejos unas de otras y la ruta se cruza consigo misma.

2. 2

   2-opt

   Toma dos tramos cualesquiera de la ruta. Si invertir el tramo que hay entre ellos acorta el viaje, que es justo lo que pasa cuando dos tramos se cruzan, hazlo. Repite hasta que ningún intercambio ayude. El resultado no tiene cruces.

Optimizar ruta de EZRoutePlanner funciona igual, vecino más cercano seguido de la mejora 2-opt, con tu salida fija y el final de vuelta en el inicio o fijado en una última parada. Después dibuja la ruta sobre calles reales y mide cada tramo. Lee cómo funciona la optimización de rutas.

Las rutas reales suman calles. Dos paradas que parecen cercanas pueden estar en lados opuestos de un río o una autopista. Un planificador de rutas busca cada dirección, ordena las paradas y luego sigue la red vial para obtener la distancia y el tiempo reales de manejo. Mientras más grande es la lista, mayor es la diferencia entre el orden en que ésta resulta estar y uno bueno.