Solucionador de Rutas de Vehículos

Pseudocódigo

El problema de rutas de vehículos generaliza el TSP a una flota. La aproximación práctica sigue el patrón de agrupar primero y encaminar después: dividir los clientes entre vehículos y luego resolver un TSP por vehículo.

VRP(depósito, clientes, numVehiculos):
    // Fase 1: repartir los clientes entre vehículos
    grupos = agrupar(clientes, numVehiculos)
    // por sectores angulares, k-medias o ahorros de Clarke-Wright

    // Fase 2: encaminar cada vehículo
    para cada grupo g:
        ruta[g] = resolverTSP(depósito + g)

    // Fase 3: mejora entre rutas
    repetir hasta que no haya mejora:
        probar mover un cliente de una ruta a otra
        probar intercambiar clientes entre dos rutas
        volver a optimizar con 2-opt las rutas modificadas

La fase 3 es la que separa una solución mediocre de una buena. Agrupar y luego encaminar produce rutas razonables, pero los límites entre grupos suelen estar mal trazados, y mover un solo cliente de una ruta sobrecargada a su vecina con frecuencia ahorra más que cualquier reoptimización dentro de una ruta. Los movimientos entre rutas son, por tanto, esenciales y no un adorno final.

Ejemplo resuelto, paso a paso

Reparte seis clientes entre dos vehículos desde un único depósito y observa por qué la mejora entre rutas importa.

Grafo de ejemplo: Un depósito en el centro y seis clientes repartidos alrededor: tres agrupados al norte y tres al sur, pero con uno de los del norte situado bastante más cerca del grupo sur que del resto de su propio grupo.

1. Fase 1, agrupar por sector. Un barrido angular desde el depósito divide a los clientes en un sector norte y otro sur, tres y tres. Es un reparto equilibrado y geométricamente natural.
2. Fase 2, encaminar cada grupo. Cada vehículo resuelve un TSP sobre su propio grupo más el depósito, con vecino más cercano seguido de 2-opt. Ambas rutas quedan internamente limpias, sin cruces.
3. El problema del límite. El cliente del norte que en realidad está más cerca del grupo sur obliga a su vehículo a hacer un desvío largo. Ninguna cantidad de 2-opt dentro de la ruta norte lo arregla, porque el problema no es el orden de visita sino la pertenencia al grupo.
4. Fase 3, mover entre rutas. Mover ese cliente a la ruta sur acorta mucho la ruta norte y alarga poco la sur, con lo que la distancia total baja. Después se vuelve a aplicar 2-opt a ambas rutas.

El reparto final ya no está equilibrado en número, cuatro clientes frente a dos, y aun así la distancia total es menor. Este es el punto central del VRP: agrupar por geometría produce grupos de aspecto ordenado, pero el objetivo es la distancia total y no la simetría. Cualquier implementación que se detenga tras agrupar y encaminar deja sobre la mesa mejoras que suelen estar en el rango del 10 al 20 por ciento.

Complejidad y de dónde sale

Tiempo: NP-difícil; heurísticas O(n^2) a O(n^3) · Espacio: O(n^2)

El VRP contiene al TSP como caso particular, con un solo vehículo y sin capacidad, así que es NP-difícil de inmediato. La enumeración exacta es impensable salvo en instancias diminutas; los métodos exactos modernos, basados en generación de columnas y ramificación y corte, resuelven instancias de unos 100 clientes con esfuerzo considerable. Las heurísticas son lo que se usa en producción: la construcción por ahorros de Clarke-Wright es O(n al cuadrado log n) dominada por la ordenación de los ahorros, agrupar y encaminar cuesta el agrupamiento más un TSP por vehículo, y la búsqueda local entre rutas cuesta O(n al cuadrado) por pasada. La matriz de distancias por sí sola ocupa O(n al cuadrado), lo que en la práctica es la restricción de memoria dominante en instancias grandes.

Cuándo usar Rutas con Múltiples Vehículos y cuándo no

Identifica primero qué restricciones tiene tu problema real, porque cada una lo empuja a una familia distinta.

Errores frecuentes

• Detenerse tras agrupar y encaminar. Los límites entre grupos casi nunca son óptimos, y la mejora entre rutas suele recuperar entre el 10 y el 20 por ciento de la distancia. Omitir la fase 3 es el error más común y el más caro.
• Insistir en rutas equilibradas. Repartir los clientes a partes iguales entre vehículos parece ordenado pero rara vez minimiza la distancia. Si el objetivo es el coste total, deja que los tamaños de ruta queden desequilibrados; si el objetivo es la equidad entre conductores, dilo explícitamente y modélalo como restricción.
• Usar distancia en línea recta sobre una red viaria. La distancia euclídea ignora sentidos únicos, ríos y autopistas. En zonas urbanas los tiempos reales de conducción pueden diferir de la línea recta en más del doble, y las rutas optimizadas sobre la métrica equivocada no son óptimas sobre la real.
• Tratar el número de vehículos como fijo cuando no lo es. A veces usar un vehículo menos con rutas más largas resulta más barato que otro conductor y otro vehículo. Si el tamaño de la flota es una decisión y no un dato, inclúyelo en el modelo en lugar de fijarlo por costumbre.
• Ignorar los tiempos de servicio. El tiempo de descarga en cada parada suele dominar sobre el tiempo de conducción en repartos urbanos densos. Optimizar solo la distancia recorrida produce rutas que no caben en la jornada laboral.

Preguntas frecuentes

¿Qué es el problema de rutas de vehículos?

El VRP pide el conjunto de rutas de menor coste para una flota que parte de un depósito y debe atender a un conjunto de clientes, volviendo cada vehículo al depósito. Generaliza el problema del viajante a varios vehículos y es la base de la planificación de reparto, la recogida de residuos y la distribución de mercancías.

¿Cuál es la diferencia entre TSP y VRP?

El TSP encamina un único vehículo por todas las ciudades sin más restricción que visitar cada una una vez. El VRP encamina una flota desde un depósito, decidiendo además qué clientes asigna a qué vehículo. El TSP es el caso particular del VRP con un vehículo y capacidad ilimitada.

¿Cómo se resuelve un VRP en la práctica?

Con el patrón de agrupar primero y encaminar después: repartir los clientes entre vehículos mediante sectores angulares, k-medias o los ahorros de Clarke-Wright, resolver un TSP para cada vehículo, y después mejorar moviendo e intercambiando clientes entre rutas. Esa última fase es esencial, ya que los límites entre grupos rara vez son óptimos.

¿Por qué es difícil el VRP?

Porque contiene al TSP como caso particular y añade encima la decisión de asignación. Hay que decidir simultáneamente qué clientes van juntos y en qué orden se visitan, y esas dos decisiones interactúan. Es NP-difícil, y los métodos exactos actuales manejan del orden de 100 clientes con esfuerzo considerable.

¿Deben quedar equilibradas las rutas?

Solo si la equidad entre conductores es un objetivo explícito. Si el objetivo es la distancia o el coste total, forzar rutas del mismo tamaño casi siempre empeora la solución. Un reparto desequilibrado que reduce la distancia total es la respuesta correcta salvo que exista una restricción que diga lo contrario.