El Problema de Enrutamiento de Vehículos (VRP) Explicado

1. ¿Qué es el Problema de Enrutamiento de Vehículos?

El Problema de Enrutamiento de Vehículos (VRP) es un problema de optimización combinatoria y programación entera que plantea: "¿Cuál es el conjunto óptimo de rutas que debe recorrer una flota de vehículos para entregar a un conjunto dado de clientes?"

Introducido en 1959 por George Dantzig y John Ramser, el VRP es un problema central en los campos del transporte, la distribución y la logística. El objetivo suele ser minimizar el costo total de la ruta (lo que podría significar minimizar la distancia, el tiempo, el combustible o la cantidad de vehículos utilizados) mientras se garantiza que cada cliente sea visitado exactamente una vez.

En un VRP estándar:

• Hay un Depósito central donde todos los vehículos comienzan y terminan sus viajes.
• Hay una Flota de vehículos, que en el problema base se asumen idénticos.
• Hay un conjunto de Clientes, cada uno ubicado en un nodo específico de un grafo.

2. VRP vs. TSP: Entendiendo la Diferencia

Si estás familiarizado con la teoría de grafos, el VRP suena sospechosamente parecido al Problema del Viajante de Comercio (TSP). De hecho, el VRP es una generalización del TSP.

La diferencia principal es la cantidad de actores:

• TSP: Tienes un vendedor que debe visitar todas las ciudades y volver a casa.
• VRP: Tienes múltiples vehículos. Primero debes agrupar (clusterizar) las ciudades (asignando un grupo específico de ciudades al Vehículo A, otro grupo al Vehículo B), y luego resolver un mini-TSP para cada vehículo.

Debido a que el TSP ya es NP-Hard (computacionalmente intratable para soluciones exactas a gran escala), el VRP también es NP-Hard, pero significativamente más complejo debido a la dimensión adicional de agrupamiento (clustering).

3. Variaciones Comunes de VRP

El VRP básico asume una capacidad infinita de los vehículos y la ausencia de restricciones de tiempo. En el mundo real, un camión de FedEx no puede transportar un número infinito de paquetes. Esto ha llevado a la creación de varias variaciones altamente prácticas del VRP.

Problema de Enrutamiento de Vehículos con Capacidad (CVRP)

En el CVRP, cada vehículo tiene una capacidad de carga máxima (por ejemplo, un camión puede contener 500 kg), y cada cliente tiene una demanda específica (por ejemplo, el Cliente A necesita 50 kg de mercancías). La ruta de un vehículo debe terminar, y debe regresar al depósito, antes de que la suma de las demandas en su ruta exceda su capacidad. Esta es la variación más común estudiada en la investigación de operaciones.

Problema de Enrutamiento de Vehículos con Ventanas de Tiempo (VRPTW)

En el VRPTW, los clientes requieren entregas dentro de marcos de tiempo específicos. Por ejemplo, un restaurante podría necesitar que se le entreguen sus ingredientes entre las 8:00 AM y las 10:00 AM. Si un camión llega a las 7:30 AM, debe esperar. Si llega a las 10:15 AM, la entrega falla. Esto añade severas restricciones de tiempo a la lógica de enrutamiento.

Otras Variaciones Notables

• VRPPD (Recogida y Entrega): Los vehículos no solo dejan mercancías; también las recogen de los clientes y las entregan a otros clientes (como Uber o DoorDash).
• MDVRP (VRP Multi-Depósito): Una empresa tiene múltiples almacenes (depósitos). El algoritmo debe decidir no solo las rutas sino también qué depósito atiende a qué cliente.
• SDVRP (VRP de Entrega Dividida): La demanda de un cliente es tan grande que se puede dividir y cumplir mediante múltiples vehículos diferentes.

4. ¿Cómo se resuelve el VRP?

Debido a que el VRP es NP-Hard, calcular el conjunto de rutas absolutamente perfecto para cientos de clientes es prácticamente imposible. En su lugar, las empresas de logística confían en un enfoque de dos fases para encontrar rutas "casi óptimas" muy rápidamente.

Fase 1: Agrupar Primero, Enrutar Después (Cluster First, Route Second)

El enfoque humano más intuitivo también es utilizado por los algoritmos. Primero, agrupa a los clientes en clústeres basados en la proximidad geográfica y la capacidad del vehículo. Una vez que tienes un grupo de clientes asignado a un camión específico, tratas ese clúster como un Problema del Viajante de Comercio independiente y resuelves para encontrar el camino más corto.

Fase 2: Metaheurísticas

Una vez que se establece un conjunto inicial de rutas, los algoritmos intentan mejorarlas continuamente. Estas se conocen como metaheurísticas.

• Recocido Simulado (Simulated Annealing): El algoritmo ocasionalmente acepta rutas "peores" a corto plazo para escapar de óptimos locales, "enfriándose" lentamente para establecerse en una ruta globalmente eficiente.
• Algoritmos Genéticos: Toma múltiples buenas soluciones de enrutamiento, las "cruza" entre sí intercambiando secciones de rutas, y mantiene a la descendencia "más apta" (más corta).
• Búsqueda Tabú (Tabu Search): Una búsqueda local agresiva que mantiene una memoria (una lista tabú) de rutas evaluadas recientemente para evitar que el algoritmo se atasque en bucles infinitos.

5. El Algoritmo de Ahorros de Clarke y Wright

Si quieres escribir un solucionador de VRP, el mejor lugar para empezar es el Algoritmo de Ahorros de Clarke y Wright, desarrollado en 1964. Sigue siendo una de las heurísticas más famosas y ampliamente implementadas para el VRP con Capacidad (CVRP).

La lógica se basa en el concepto de "ahorros".

1. Comienza con el peor de los casos: Imagina que tienes 10 clientes. Envías 10 camiones separados desde el depósito. El camión 1 va al Cliente 1 y regresa. El camión 2 va al Cliente 2 y regresa, etc.
2. Calcula los Ahorros: Si combinas las rutas (Depósito -> Cliente 1 -> Cliente 2 -> Depósito), ¿cuánta distancia ahorras en comparación con el envío de dos camiones separados? Calculas este valor de "ahorro" para cada par posible de clientes.
3. Ordena y Fusiona: Ordenas los pares por el mayor ahorro. Luego fusionas agresivamente las rutas juntas, comenzando con el mayor ahorro, siempre que la ruta combinada no exceda la capacidad máxima del vehículo.

Este algoritmo se ejecuta en tiempo O(n^2 log n) y produce rutas altamente eficientes casi al instante, sirviendo como base sobre la cual las metaheurísticas pueden mejorar.

6. Aplicaciones Reales

Una mejora del 5% en la optimización del VRP se traduce en millones de dólares en ahorros para las grandes corporaciones.

• Entrega de Paquetes (UPS/FedEx): UPS utiliza un famoso sistema de optimización llamado ORION (On-Road Integrated Optimization and Navigation). Al penalizar fuertemente los giros a la izquierda en sus cálculos de VRP (que desperdician gasolina mientras esperan en los semáforos), UPS ahorra más de 10 millones de galones de combustible al año.
• Viajes Compartidos (Uber/Lyft): UberPool es un VRP Dinámico masivo en tiempo real con Recogida y Entrega. El algoritmo debe reagrupar y redirigir continuamente los vehículos a medida que aparecen dinámicamente nuevas solicitudes de viaje.
• Gestión de Residuos: Los camiones de basura deben recorrer todas las calles de una ciudad (un subconjunto de VRP conocido como Problema de Enrutamiento de Arcos con Capacidad), asegurando que los camiones regresen al vertedero antes de alcanzar sus límites de peso.