El Método del Enrutamiento de Vehículos Generalizado: Optimización y Aplicaciones

El transporte de mercancías es un pilar fundamental en la economía global, impulsado por factores como la globalización, la apertura de mercados y el acceso a tecnologías. En este contexto, el Problema del Enrutamiento de Vehículos (VRP, por sus siglas en inglés) emerge como una herramienta esencial para optimizar la logística y mejorar la eficiencia operativa de las empresas. Este artículo explora el VRP generalizado, sus complejidades, métodos de solución y aplicaciones prácticas, utilizando como base la información proporcionada.

El Problema del Enrutamiento de Vehículos: Fundamentos y Evolución

El VRP, una generalización del Problema del Agente Viajero (TSP), se centra en determinar el conjunto óptimo de rutas para una flota de vehículos que deben visitar un conjunto de ubicaciones geográficamente dispersas, partiendo y regresando a un depósito central. A diferencia del TSP, el VRP considera explícitamente la capacidad limitada de los vehículos y, en sus variantes más complejas, otros factores como las ventanas de tiempo, las flotas heterogéneas y las restricciones de carga tridimensional.

Los orígenes del estudio del VRP se remontan a 1959 con el trabajo de Dantzig y Ramser sobre el despacho de camiones homogéneos. Posteriormente, en 1964, Clarke y Wright abordaron el problema con vehículos de capacidades heterogéneas, sentando las bases del VRP moderno. Desde entonces, el modelamiento de rutas de vehículos se ha convertido en un área de investigación intensiva en investigación de operaciones, ingeniería industrial, logística y transporte.

La complejidad matemática del VRP radica en su naturaleza combinatoria. El número de rutas posibles crece factorialmente con el número de ubicaciones, haciendo que una búsqueda exhaustiva sea computacionalmente intratable para problemas de tamaño real. Por ejemplo, un problema con solo 20 ubicaciones puede tener más de 2.4 quintillones de rutas posibles. Esta intratabilidad computacional impulsa la necesidad de emplear técnicas de optimización heurística y metaheurística para encontrar soluciones óptimas o casi óptimas.

Variantes y Generalizaciones del VRP

La literatura académica y las aplicaciones prácticas han dado lugar a numerosas variantes del VRP, cada una abordando desafíos logísticos específicos. Algunas de las más comunes incluyen:

• VRP con Ventanas de Tiempo (VRPTW): Impone restricciones temporales sobre cuándo se pueden visitar los clientes. Estas ventanas de tiempo pueden ser "duras" (que no permiten llegadas fuera del intervalo) o "blandas" (que permiten llegadas fuera del intervalo con penalizaciones). La mayoría de los estudios se centran en ventanas de tiempo duras, como se menciona en el análisis del caso de estudio.
• VRP con Flotas Heterogéneas (HFVRP): Considera una flota de vehículos con diferentes capacidades, costos operativos y características.
• VRP con Múltiples Depósitos (MDVRP): Permite que los vehículos partan y regresen a múltiples depósitos.
• VRP con Carga Tridimensional (3D-CVRP): Incorpora restricciones relacionadas con el volumen y la forma de los paquetes a cargar en los vehículos, asegurando un empaquetamiento eficiente.
• VRP Multiobjetivo: Busca optimizar simultáneamente múltiples objetivos, como minimizar la distancia total recorrida y maximizar la visita de Nodos Muy Importantes (VIP) al inicio de cada recorrido. Este enfoque utiliza el concepto de optimalidad de Pareto para encontrar un conjunto de soluciones de compromiso.

El caso de estudio presentado en la información proporcionada se centra en un problema de optimización multiobjetivo, buscando minimizar la distancia total recorrida y maximizar la visita de nodos VIP. La solución propuesta integra una heurística aleatoria con sesgo con la Búsqueda Local Iterativa (ILS) y emplea el concepto de optimalidad de Pareto.

Métodos de Solución: Heurísticas y Metaheurísticas

Dada la complejidad del VRP, se recurre a una variedad de algoritmos de optimización, principalmente heurísticas y metaheurísticas, para encontrar soluciones eficientes en un tiempo computacional razonable.

Heurísticas

Las heurísticas son métodos que buscan una solución buena en un tiempo razonable, aunque no garantizan la optimalidad.

• Heurística de Clarke-Wright: Este algoritmo, utilizado por el software VRP Solver 3.0 en el caso de estudio, comienza con una solución de viajes de ida y vuelta a cada cliente y combina las rutas que ofrecen el mayor "ahorro" (reducción de costos al fusionar dos rutas pequeñas en una más grande). Su utilidad ha sido demostrada en diversas aplicaciones de optimización de distribución.
• Heurísticas de Construcción: Construyen una solución factible paso a paso, añadiendo clientes a las rutas existentes o creando nuevas rutas según ciertos criterios.
• Heurísticas de Mejora: Parten de una solución factible y buscan mejorarla mediante movimientos locales.

Metaheurísticas

Las metaheurísticas son estrategias de alto nivel que guían a las heurísticas para explorar el espacio de soluciones de manera más efectiva y evitar quedarse atrapadas en óptimos locales.

• Búsqueda Local Iterativa (ILS): Un enfoque robusto que aplica iterativamente movimientos de perturbación y mejora para escapar de óptimos locales y encontrar mejores soluciones. En el caso de estudio, se integra con una heurística aleatoria sesgada.
• Algoritmos Genéticos (GA): Inspirados en la evolución biológica, utilizan operadores como la selección, el cruce y la mutación para evolucionar una población de soluciones hacia una óptima.
• Recocido Simulado (SA): Simula el proceso de enfriamiento de metales para explorar el espacio de soluciones, permitiendo movimientos a soluciones peores con una probabilidad decreciente para evitar óptimos locales.
• Optimización por Colonia de Hormigas (ACO): Basada en el comportamiento de las hormigas al buscar alimento, utiliza "feromonas" para guiar la búsqueda de soluciones.
• Búsqueda Tabú (TS): Mantiene una lista de movimientos "tabú" (prohibidos temporalmente) para evitar ciclos y explorar nuevas áreas del espacio de soluciones.
• Búsqueda Adaptativa de Vecindarios (Adaptive Large Neighborhood Search - ALNS): Una metaheurística versátil que destruye y reconstruye partes de una solución para explorar el espacio de búsqueda de manera efectiva. El VRP Solver implementa una variante de esta técnica.

Aplicación Práctica: Mejora de Rutas en Cali

El caso de estudio presentado detalla la aplicación del VRP para resolver problemas de despacho en la zona "centro" de la ciudad de Cali, Colombia, para una empresa de transporte de mercancías con 64 años de trayectoria. La empresa experimentaba un represamiento de mercancía de aproximadamente el 20%, lo que equivalía a 21,565 Tm mensuales no entregadas.

Metodología y Herramientas

La solución del problema se basó en un análisis exhaustivo del proceso actual y la aplicación de herramientas de simulación y optimización.

1. Análisis del Proceso Actual:

   • Entrevistas estructuradas: Se entrevistó a 20 personas del personal encargado de la planeación de rutas para evaluar la eficiencia, la posibilidad de ampliar la jornada, la frecuencia de quejas y la disponibilidad de recursos.
   • Observación directa: Se observó el proceso de entrega de mercancía.
   • Diagrama SIPOC: Se utilizó para comprender la operación general de forma sistémica y identificar oportunidades de mejora en las áreas de digitación y embarque.
   • Diagrama de Pareto: Se aplicó para clasificar a los 201 clientes de la zona "volumen centro" por el peso de sus ventas, identificando 61 clientes de "alto peso" que representaban el 70.8% de los ingresos.

2. Herramientas de Simulación y Optimización:

   • VRP Solver 3.0: Un software basado en hojas de cálculo que implementa una variante de la búsqueda adaptativa de vecindarios y la heurística estocástica de Clarke-Wright. Permite definir parámetros como ubicaciones, distancias, vehículos, y restricciones, y visualizar las soluciones.
   • Google OR-Tools: Una suite de software de código abierto para la optimización, que permite modelar y resolver problemas de enrutamiento de vehículos utilizando programación basada en restricciones y diversas estrategias de solución. El artículo menciona la posibilidad de utilizar esta herramienta para abordar problemas de VRP básicos y sus variantes.

Implementación y Resultados

El análisis inicial reveló que el vehículo asignado a la ruta "volumen centro" solo disponía de medio día para la distribución, lo cual era insuficiente para atender la demanda, resultando en el represamiento de mercancía. Para abordar esta situación, se consideraron varias decisiones:

• Aumentar la jornada del vehículo "volumen centro": Se reconoció la necesidad de extender el tiempo de operación para reducir el represamiento.
• Reasignación de Rutas: Se propuso incorporar las rutas "centro 1" y "centro 2" como apoyo, utilizando una fracción de su capacidad en horas de la mañana.
• Simulación con Parámetros Modificados: Se configuró el VRP Solver con 26 clientes y un depósito, utilizando un vehículo a 40 km/h con ventanas de tiempo duras.

Los resultados de la simulación inicial mostraron que la capacidad del vehículo y el tiempo de entrega no cumplían con los parámetros establecidos, atendiendo a un máximo de diez clientes y terminando la jornada a las 11:41 a. m.

Tras incorporar las rutas de apoyo y ajustar los parámetros, se realizó una nueva simulación con tres vehículos. La Tabla V presenta la distribución de la mercancía en un día promedio, donde un vehículo atendía las cargas C1 y C2 (del vehículo "volumen centro" en la tarde), y los otros dos vehículos se utilizaban parcialmente para las cargas C3 y C4 (de las rutas "centro 1" y "centro 2" en la mañana).

La Figura 6 ilustra la distribución de la mercancía para los tres vehículos, atendiendo un total de 26 clientes. El vehículo uno (V1) muestra, por ejemplo, diez paradas con sus respectivos nombres de ubicación.

Una interesante observación del caso de estudio es la simulación de la eliminación de un vehículo. Sorprendentemente, la reducción de un vehículo en la flota resultó en una menor distancia total recorrida. Esto se explica por la reasignación de clientes a los vehículos restantes, lo que permitió que al menos un vehículo no necesitara desplazarse de regreso al depósito, optimizando así la distancia total. Sin embargo, se aclara que en la práctica, las limitaciones de capacidad de los vehículos podrían impedir tal reasignación.

Consideraciones Adicionales y Futuras Direcciones

El modelamiento de Cadenas de Suministro, y en particular el diseño de redes de abastecimiento, se beneficia enormemente de la aplicación del VRP. La flexibilidad de herramientas como Google OR-Tools permite adaptar los modelos a diversas realidades logísticas.

La posibilidad de integrar datos de entrada desde fuentes externas como archivos de Excel o servidores, y de desarrollar interfaces amigables, abre puertas a soluciones aún más robustas y accesibles. El desarrollo de scripts para procesar datos de salida y vincularlos con otros modelos o documentos también representa una dirección prometedora.

El futuro de la investigación en VRP abarca la exploración de variantes más complejas como el CVRP (Capacitated Vehicle Routing Problem), VRPTW, y la integración con tecnologías como Google Maps para una visualización y optimización en tiempo real. La comprensión profunda de estas metodologías es crucial para las empresas que buscan optimizar sus operaciones logísticas, mejorar la relación con sus clientes y alcanzar una mayor rentabilidad en un mercado cada vez más competitivo.

tags: #metodo #del #enrutamiento #del #vehiculo #generalizado