Todas las tardes alguien se sentaba con la lista de servicios del día siguiente y armaba las rutas. Quién va dónde, en qué orden, con cuál vehículo. Se hacía con criterio y con años de conocer el país, pero se hacía a ojo. Eso funciona hasta que deja de funcionar, y deja de funcionar antes de lo que uno cree, por una razón que no es de esfuerzo sino de matemática.
Por qué esto no se resuelve a ojo
Un día de visitas tiene exactamente la misma clase de problema que un mazo de 52 cartas: con 52 elementos, la cantidad de órdenes posibles es la misma. Y ese número, 52 factorial, es una de las cifras más difíciles de tomarse en serio que existen.
- Poné un cronómetro con 52! segundos, en cuenta regresiva.
- Parate en el ecuador y dá un paso cada mil millones de años.
- Al completar la vuelta al planeta, sacá una gota del océano Pacífico.
- Cuando el Pacífico quede seco, poné una hoja de papel en el suelo. Volvé a llenar el océano y empezá de nuevo.
- Cuando la pila de papel llegue al Sol, mirá el cronómetro.
Por eso probar todas las combinaciones no es una opción lenta: es una opción imposible, y lo seguirá siendo por más rápido que se vuelvan las computadoras. Y el ruteo real es todavía peor, porque no es solo ordenar. Primero hay que decidir quién va con quién: repartir esas visitas entre varios vehículos y después ordenar cada grupo es un espacio de búsqueda aún más grande que el del mazo.
Hay además una trampa de intuición esperando. Uno tiende a agrupar por cercanía entre clientes: "estos tres quedan cerca, van juntos". Pero el costo real no es la distancia entre clientes, sino cuánto camino ahorrás al no volver a la base entre uno y otro, que no es lo mismo.
// Sin llamar a ningún mapa: distancia en línea recta corregida.
const RAD = Math.PI / 180, RT = 6371; // radio terrestre en km
function km(a, b){
const dLa = (b.y - a.y) * RAD, dLo = (b.x - a.x) * RAD;
const h = Math.sin(dLa/2)**2 + Math.cos(a.y*RAD)*Math.cos(b.y*RAD)*Math.sin(dLo/2)**2;
return 2 * RT * Math.asin(Math.sqrt(h)); // haversine
}
// Sinuosidad vial + velocidad creciente con la distancia:
// en ciudad se va lento, en carretera rápido.
function minutos(a, b){
const d = km(a, b) * 1.32; // las calles no son rectas
if (d < 0.02) return 0;
const v = 18 + 42 * (1 - Math.exp(-d / 22)); // km/h según distancia
return d / v * 60;
}Un día cualquiera en el Gran Área Metropolitana
Para que esto deje de ser teoría, corrimos el algoritmo real sobre un día ficticio de citas repartidas por el GAM, saliendo todas de una central en Guachipelín. Después lo comparamos contra cómo se arma un día a mano: agrupar por zona, hasta cinco citas por vehículo, y visitarlas en el orden en que entraron a la agenda, que es exactamente lo que hace una persona con criterio y sin herramientas.
Un día de trabajo en el GAM
El mismo día resuelto de dos formas. Salida y regreso a una central en Guachipelín, máximo 5 citas por vehículo.
Dónde estaba escondida la diferencia
No en manejar más rápido ni en cortar camino, sino en dos cosas que a ojo no se ven.
1. Los vehículos que salían casi vacíos
Agrupar por zona parece ordenado, pero deja residuos: la zona que tenía seis citas genera una ruta de cinco y otra de una. Ese sobrante sale igual a la calle, con un vehículo entero detrás.
2. El viaje a Cartago
Este es el caso que mejor lo explica. En el reparto por zona, Cartago tiene dos citas, así que un vehículo se va hasta allá y se devuelve para atender solo dos servicios: casi la mitad de su jornada en carretera por dos visitas. El algoritmo lo ve distinto: como ya hay que ir hasta allá, aprovecha el viaje y arma una sola ruta con las dos de Cartago más tres de Curridabat y San Pedro, que quedan de camino.
Nadie que arme rutas a mano va a mandar un vehículo de Guachipelín a Cartago pasando por Curridabat. Se siente mal, parece un desvío. Pero el desvío cuesta menos que el viaje vacío que se ahorra, y eso solo se ve calculando.
Empezar por el peor plan posible
La idea que resuelve esto se publicó en 1964 y sigue siendo difícil de superar por lo simple que es. Arranca desde el peor escenario imaginable: una ruta por cada cliente, es decir salir de la central, atender a uno y volver. Después se pregunta, para cada par de clientes, cuánto se ahorraría uniéndolos, y ese número tiene fórmula.
0 es la central. d es el tiempo de viaje entre dos puntos. λ (lambda) es una perilla que decide cuánto castigar la distancia entre los dos clientes.// Arranca desde el peor plan posible: una ruta por cada cliente.
function construir(idx, mx, lambda){
const {M, n} = mx;
let rutas = idx.map(i => [i]); // cada cita, sola
const dueño = new Map();
rutas.forEach((r, k) => dueño.set(r[0], k));
// ahorro de unir i y j = lo que se borra menos lo que se agrega
const ahorros = [];
for (let a = 0; a < idx.length; a++)
for (let b = a + 1; b < idx.length; b++){
const i = idx[a], j = idx[b];
ahorros.push([M[0*n+i] + M[0*n+j] - lambda * M[i*n+j], i, j]);
}
ahorros.sort((p, q) => q[0] - p[0]); // el mayor ahorro primero
for (const [, i, j] of ahorros){
const ri = dueño.get(i), rj = dueño.get(j);
if (ri === rj) continue; // ya viajan juntos
const A = rutas[ri], B = rutas[rj];
if (A.length + B.length > 5) continue; // tope operativo
// solo por las puntas: es lo que mantiene la ruta "en línea"
if (!(A[0] === i || A[A.length-1] === i)) continue;
if (!(B[0] === j || B[B.length-1] === j)) continue;
const fusion = A.concat(B);
rutas[ri] = fusion; rutas[rj] = [];
fusion.forEach(v => dueño.set(v, ri));
}
return rutas.filter(r => r.length);
}Se calculan todos los pares, se ordenan de mayor a menor ahorro, y se van uniendo de arriba hacia abajo mientras las reglas lo permitan. Es codicioso y no garantiza el óptimo, pero llega muy cerca en una fracción del tiempo.
Tres clientes. Desde la central: A a 20 min, B a 25 min, C a 30 min. Entre ellos: A-B a 8 min, A-C a 28 min, B-C a 10 min.
ahorro(B,C) = 25 + 30 − 10 = 45 min
ahorro(A,C) = 20 + 30 − 28 = 22 min
El orden de unión queda B-C, luego A-B, y A-C de último. Nótese que A y C son los que más lejos están entre sí (28 min), así que unirlos casi no ahorra nada: se gasta en el traslado lo que se ahorró en no volver a la base.
Uniendo los dos primeros pares queda una sola ruta con los tres. Contra los tres viajes separados, la diferencia es grande: 150 min de ida y vuelta por separado contra ~68 min haciendo el circuito.
Se calculan todos los pares, se ordenan de mayor a menor ahorro, y se van uniendo de arriba hacia abajo mientras las reglas lo permitan. Es codicioso y no garantiza el óptimo, pero llega muy cerca en una fracción del tiempo.
Lambda es una perilla: multiplica el castigo por la distancia entre los dos clientes. Con λ alto el algoritmo se pone exigente y solo une pares realmente cercanos, y salen rutas compactas pero más numerosas; con λ bajo une con más liberalidad. No hay un valor universalmente bueno porque depende de cómo estén repartidos los puntos ese día, así que Optimus Route corre varias configuraciones y se queda con la mejor.
Dos reglas que mantienen las rutas sanas
- Tope de cinco citas por ruta. No es una limitación técnica sino operativa: es lo que un técnico alcanza a hacer bien en un día, contando el tiempo del servicio y no solo el traslado.
- Solo se unen por los extremos. Si un cliente ya quedó en el medio de una ruta, no se puede pegar nada ahí. Esto evita que las rutas se conviertan en marañas y las mantiene en línea, que es como se manejan de verdad.
Con cinco paradas, no hace falta adivinar
El algoritmo decide qué citas van juntas, pero no en qué orden visitarlas. Ahí el tope de cinco paga un dividendo inesperado: cinco paradas tienen 120 órdenes posibles, y ciento veinte es nada para una computadora, así que Optimus Route no estima el mejor orden, los prueba todos. Dentro de cada ruta el resultado es exacto, no aproximado.
// Con tope de 5 son 120 permutaciones: se prueban todas.
// No es una estimación, es el óptimo garantizado de ese grupo.
function mejorOrden(ruta, mx){
const {M, n, memo} = mx, k = ruta.length;
// la búsqueda local vuelve a pedir los mismos grupos miles de veces
const clave = ruta.slice().sort((a, b) => a - b).join(",");
if (memo.has(clave)) return memo.get(clave);
let mejorC = Infinity, mejorO = null;
for (const p of PERMS[k]){
let c = M[0*n + ruta[p[0]]]; // central -> primera
for (let i = 1; i < k; i++)
c += M[ruta[p[i-1]]*n + ruta[p[i]]]; // entre paradas
c += M[ruta[p[k-1]]*n + 0]; // última -> central
if (c < mejorC){ mejorC = c; mejorO = p; }
}
const res = {orden: mejorO.map(i => ruta[i]), costo: mejorC};
memo.set(clave, res);
return res;
}Pulir, y después sacudir a propósito
Lo que sale de ahí es un buen punto de partida, no una respuesta final. Sigue una búsqueda local que prueba mover una cita de una ruta a otra, o intercambiar dos entre rutas, una y otra vez mientras algo mejore. Cuando ya nada mejora se llegó a un óptimo local, que puede estar lejos del bueno: es como estar en la cima de una loma y creer que es la montaña más alta, porque para cualquier lado que caminés vas para abajo.
Supongamos dos rutas ya armadas. La Ruta 1 lleva cuatro citas al oeste más una que quedó al este. La Ruta 2 lleva tres al este.
Esa cita del este dentro de la Ruta 1 obliga a un desvío largo. Mover esa sola cita a la Ruta 2 puede quitar 40 minutos de la primera y agregar solo 6 a la segunda, porque cae justo de paso. Ganancia neta: 34 min.
Clarke-Wright no lo vio porque decide por pares y de una sola pasada. La búsqueda local sí, porque mira la solución ya completa.
Para escapar de esa loma, Optimus Route hace algo que parece contraproducente: rompe a propósito la solución que ya tiene. Elige una cita al azar, saca del plan a sus vecinas más cercanas, las vuelve a insertar donde menos cuesten y vuelve a pulir. Si el resultado quedó mejor se queda con él; si no, lo descarta. Esto se repite decenas de veces por día, y es lo que permite saltar a otra loma a ver si es más alta.
Un detalle que costó una tarde: para barajar las citas antes de reinsertarlas se usaba un atajo común, ordenar con un comparador que devuelve valores al azar. Funciona hasta que dos motores distintos dan resultados distintos, porque el resultado depende del algoritmo de ordenamiento interno de cada uno. La solución fue usar Fisher-Yates con semilla fija, de modo que el mismo día produce siempre las mismas rutas.
// El atajo que fallaba: el resultado depende del algoritmo de
// ordenamiento del motor, y Node y el navegador daban rutas distintas.
// fuera.sort(() => Math.random() - 0.5); <- no hacer esto
// Fisher-Yates: cada permutación con la misma probabilidad.
for (let i = fuera.length - 1; i > 0; i--){
const j = Math.floor(rnd() * (i + 1));
[fuera[i], fuera[j]] = [fuera[j], fuera[i]];
}
// Y el azar con semilla fija: el mismo día produce siempre
// exactamente las mismas rutas, corra donde corra.
function mulberry32(a){
return function(){
a |= 0; a = a + 0x6D2B79F5 | 0;
let t = Math.imul(a ^ a >>> 15, 1 | a);
t = t + Math.imul(t ^ t >>> 7, 61 | t) ^ t;
return ((t ^ t >>> 14) >>> 0) / 4294967296;
};
}