Solucionador CVRP

Pseudocódigo

El CVRP es el VRP con un límite de carga por vehículo. Esa única restricción cambia qué agrupaciones son siquiera factibles, y por tanto cambia toda la estructura de la búsqueda.

CVRP(depósito, clientes, capacidad Q):
    // Construcción por ahorros de Clarke-Wright
    empezar con una ruta dedicada por cliente
    para cada par (i, j):
        ahorro[i][j] = d(dep,i) + d(dep,j) - d(i,j)
    ordenar los pares por ahorro decreciente

    para cada par (i, j) en ese orden:
        si i y j están en rutas distintas
           y ambos son extremos de su ruta
           y demanda(ruta_i) + demanda(ruta_j) <= Q:
            fusionar las dos rutas

    // Después: 2-opt dentro de rutas y movimientos entre rutas,
    // rechazando siempre los que violen la capacidad

El valor de ahorro mide cuánto se gana al servir i y j en la misma ruta en lugar de en dos viajes de ida y vuelta separados. La comprobación de capacidad es lo que distingue el CVRP del VRP: una fusión puede ser muy rentable en distancia y sencillamente inadmisible por carga. Toda la búsqueda local posterior debe repetir esa comprobación en cada movimiento, porque un intercambio entre rutas que mejore la distancia puede volver inviable una ruta.

Ejemplo resuelto, paso a paso

Encamina cinco clientes con un vehículo de capacidad 10 y observa cómo la restricción de carga rechaza la fusión más rentable.

Grafo de ejemplo: Depósito más cinco clientes con demandas C1 igual a 4, C2 igual a 4, C3 igual a 3, C4 igual a 3 y C5 igual a 2. Cada vehículo puede transportar 10 unidades.

1. Empezar con rutas dedicadas. Cinco rutas, una por cliente, cada una un viaje de ida y vuelta desde el depósito. Es factible pero caro, y es el punto de partida del método de ahorros.
2. Fusionar por ahorro decreciente. El par con mayor ahorro es C1 y C2, que además son geográficamente cercanos. Su demanda combinada es 4 + 4 = 8, dentro de la capacidad 10, así que la fusión se acepta.
3. La siguiente fusión rentable se rechaza. El siguiente mejor ahorro añadiría C3 a esa misma ruta. La distancia mejoraría claramente, pero la demanda pasaría a 8 + 3 = 11, por encima de la capacidad 10. La fusión se rechaza pese a ser la mejor por distancia.
4. Continuar con las fusiones admisibles. C3, C4 y C5 se fusionan entre sí con demanda total 3 + 3 + 2 = 8, dentro de la capacidad. Quedan dos rutas: una con C1 y C2 con carga 8, y otra con C3, C4 y C5 con carga 8.

La solución usa dos vehículos con cargas 8 y 8, aunque la fusión más atractiva por distancia habría sido añadir C3 a la primera ruta. Ese rechazo es toda la diferencia entre VRP y CVRP: en el VRP puro esa fusión se habría aceptado y la solución sería más corta pero inviable. Fíjate además en que la demanda total es 16 y la capacidad por vehículo es 10, así que dos vehículos es el mínimo posible; ninguna solución con uno solo existe, por muy buena que sea la optimización.

Complejidad y de dónde sale

Tiempo: NP-difícil; Clarke-Wright O(n^2 log n) · Espacio: O(n^2)

La construcción por ahorros de Clarke-Wright calcula un valor de ahorro para cada uno de los O(n al cuadrado) pares y los ordena, lo que domina el coste con O(n al cuadrado log n). Cada intento de fusión es una comprobación de tiempo constante sobre las cargas y los extremos de ruta si se mantienen estructuras adecuadas. La búsqueda local posterior cuesta O(n al cuadrado) por pasada. El problema en sí es NP-difícil, ya que contiene al TSP, y añadir la capacidad lo endurece más al reducir el espacio de soluciones factibles de forma irregular. Los métodos exactos mediante generación de columnas resuelven instancias de referencia de unos 100 clientes; más allá de eso se usan metaheurísticas. Una cota inferior útil y barata es la demanda total dividida entre la capacidad, redondeada hacia arriba, que da el número mínimo de vehículos.

Cuándo usar Rutas de Vehículos con Capacidad y cuándo no

Cada restricción adicional define una variante distinta con su propia literatura y sus propios solucionadores.

Errores frecuentes

• Comprobar la capacidad solo al construir. Todo movimiento de la búsqueda local, mover un cliente, intercambiar dos, invertir un tramo entre rutas, puede violar la capacidad. La comprobación debe repetirse en cada movimiento, no únicamente durante la construcción inicial.
• Olvidar la cota inferior por demanda total. La demanda total dividida entre la capacidad, redondeada hacia arriba, da el número mínimo de vehículos. Es gratuita de calcular y te dice de inmediato si una solución con menos vehículos es siquiera posible, además de servir para medir la calidad de la que tienes.
• Suponer que menos vehículos siempre es mejor. Reducir la flota alarga cada ruta, y si hay costes por hora de conductor o límites de jornada, la solución con menos vehículos puede resultar más cara. Optimiza el coste real, no el recuento de vehículos.
• Modelar demandas fraccionables cuando no lo son. El CVRP estándar supone que cada cliente se atiende por completo en una sola visita. Si en realidad puedes dividir una entrega entre dos vehículos, se trata del VRP con entregas divisibles, un problema distinto con soluciones estructuralmente diferentes y a menudo más baratas.
• Pasar por alto la carga de retorno. En recogidas, la carga aumenta a lo largo de la ruta en lugar de disminuir, así que la restricción vinculante está al final del recorrido y no al principio. Mezclar entregas y recogidas en la misma ruta exige comprobar la carga en cada parada.

Preguntas frecuentes

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

El CVRP pide el conjunto de rutas de menor coste para una flota que parte de un depósito, donde cada cliente tiene una demanda y ningún vehículo puede superar su capacidad de carga. Es la variante estándar del VRP en logística real y en distribución de mercancías.

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

El VRP encamina una flota sin límite de carga; el CVRP añade una capacidad por vehículo que ninguna ruta puede exceder. Esa restricción cambia qué agrupaciones de clientes son siquiera factibles, así que soluciones más cortas en distancia pueden quedar descartadas por inviables, como en el ejemplo donde la fusión más rentable se rechaza por superar la capacidad en una unidad.

¿Cómo funciona el algoritmo de ahorros de Clarke-Wright?

Empieza con una ruta dedicada por cliente y calcula, para cada par, cuánta distancia se ahorra sirviéndolos en la misma ruta en lugar de en dos viajes separados. Después recorre los pares por ahorro decreciente y fusiona las rutas correspondientes siempre que ambos clientes sean extremos de ruta y la carga combinada respete la capacidad.

¿Cuál es el número mínimo de vehículos en un CVRP?

Al menos la demanda total dividida entre la capacidad de un vehículo, redondeada hacia arriba. Es una cota inferior derivada del problema de empaquetado en contenedores, se calcula al instante y es útil tanto para saber si una solución con pocos vehículos es posible como para evaluar la calidad de la solución actual.

¿Para qué se usa el CVRP?

Para planificar reparto de mercancías, distribución de alimentación y bebidas, logística de contenedores, recogida de residuos y reposición de tiendas. Es el modelo estándar allí donde una flota con capacidad finita debe atender a un conjunto de clientes con demandas conocidas desde un depósito central.