Problema de Ruteo de Vehículos (VRP): Definición y Variantes

En las cadenas de suministro, el transporte se considera como uno de los procesos más importantes y críticos debido a los costos que se derivan de este, además del substancial aporte que genera a la contaminación ambiental. Por lo cual, los modelos de ruteo de vehículos representan una herramienta eficaz que pueden articular un gran número de variables acordes a los contextos reales para la toma de decisiones y organizar un ruteo que permita la obtención de soluciones eficientes y sustentables en la asignación del transporte.

El proceso de ruteo en el transporte, considerado como uno de los problemas más habituales en las cadenas de suministro, se traduce en un reto cada vez más grande que obliga a las empresas a ser más innovadoras a la hora de organizar el movimiento y traslado de sus productos. Con el desarrollo de los modelos de ruteo de vehículos (VRP) originados en 1959 como problemas de optimización combinatoria solucionados en primera instancia a través de la programación lineal y que cada vez se ajustan más a los problemas reales, se obtienen ruteos eficientes que inciden directamente en la minimización de costos y que adicionalmente pueden considerar las minimizaciones de emisiones de CO2 para la protección del ambiente.

Es así, que el VRP supone una gran cantidad de variantes que contextualizan diversas condiciones de los problemas de ruteo del mundo real. Una de estas variantes son las entregas y recogidas simultáneas (VRPSPD), la cual se ha aplicado a diferentes sistemas de logística inversa que manejan un flujo de bienes en ambas direcciones. Con esta variante se modela un sistema que permite que los clientes puedan recibir un producto y devolver bienes al mismo tiempo.

Generalmente los modelos matemáticos de VRP presentan una función objetivo lineal que pretende la minimización de distancias recorridas, el costo de viaje y/o tiempos de recorrido. Sin embargo, dadas las implicaciones ambientales que genera el transporte, se hace necesario considerar variantes asociadas a la logística verde para medir el consumo de energía y las contaminaciones emitidas al ambiente (suelo, aire y agua).

Por otra parte, los modelos de VRP pueden pretender la optimización de un objetivo a la vez o de un conjunto de ellos. Lo cual, puede generar combinaciones de minimización y/o maximización en una misma función objetivo; cuando se formula un modelo con una sola función objetivo, se denomina mono-objetivo, sin embargo, cuando hay más de un objetivo en un mismo problema, se denomina multi-objetivo. En este trabajo se considera un modelo multi-objetivo, cuya finalidad es la reducción de los costos por emisiones de CO2, la minimización de costos por violación de ventanas de tiempo y el costo fijo y variable por distancia recorrida de los vehículos.

Adicionalmente, presenta una combinación de las siguientes variantes: flota heterogénea capacitada, entregas y recogidas simultáneas, ventanas de tiempos suaves y múltiples depósitos, lo que robustece el modelo propuesto categorizándolo como Np-hard.

Los problemas de VRP cuyo objetivo es la asignación de rutas a vehículos para cumplir la demanda de clientes en un área determinada partiendo de un depósito y retornado a él al final del recorrido, han aumentado su complejidad durante la última década, combinando diversas variantes para poder modelar los sistemas reales y obtener resultados eficientes.

Ahora bien, dadas las implicaciones ambientales que generan las actividades del trasporte, se inició el desarrollo de una línea de modelos con variantes verdes introducido por el cual calculó las emisiones de Dióxido de Carbono en el trayecto y tiempo de recorrido del vehículo.

Las variantes de los modelos de VRP pretenden asemejar la realidad para poder solucionar los problemas contextualizados; uno de los sistemas que se están empleando a lo largo de las cadenas de suministros es la logística inversa, en donde el VRP modela un sistema que permite al vehículo recoger productos (Pickup) y hacer entregas (Delivery) en la misma ruta. Uno de los primeros aportes a esta variante direccionada a los sistemas dial-a-ride (transporte de personas) fue realizada por quienes modelaron un sistema de ruta de autobuses teniendo en cuenta el origen y destino de los pasajeros.

Otros autores como desarrollaron heurísticas para solucionar un Traveling Salesman Problem (TSP) pickup and Delivery (TSPPD). Posteriormente desarrolló un modelo de VRPPD, que combinaba variantes de ventanas de tiempo duras y multi-depósito. Esta sub-variante del VRPPD establece que se puede recolectar bienes y transportarlos en la dirección inversa, al mismo tiempo en que se entreguen otros bienes al mismo cliente. El primer autor del VRPSPD fue quien modeló el problema de una biblioteca y lo solucionó agrupando los nodos y resolviéndolos cada grupo como un TSP.

Además de los aportes de la heurística de que buscaba minimizar las infactibilidades, fueron los primeros que propusieron una metaheurística de algoritmo híbrido basada en búsqueda tabú (TS) y búsqueda de vecindarios más cercanos (VNS) para solucionar un VRPSPD. Otros autores empezaron a combinar otras variantes de VRP con el VRPSPD, tales como quienes desarrollan un VRPSPD con ventanas de tiempos teniendo en cuenta la importancia del tiempo en la toma de decisiones gerenciales.

Asimismo, combina variantes de flota de vehículos heterogénea (HVRPSPD) el cual fue solucionado mediante un algoritmo híbrido compuesto por recocido simulado y búsqueda local. En también desarrollaron un modelo de VRPSPD con flota heterogénea y resuelto con un algoritmo híbrido basado en búsqueda local y búsqueda tabú.

Por otra parte, combinan variantes de múltiples depósitos tratando de contextualizar los problemas reales. Para el caso del VRPSPD desarrollaron un modelo pickup and delivery simultaneo verde (g-VRPSPD) para una flota homogénea en donde se minimizaban los costos por emisiones de CO2. Para los sistemas que implican la recolección y descargue de bienes de manera simultánea en un mismo cliente, los modelos de VRPSPD representan una eficiente herramienta de modelación que puede ser resuelta a través de métodos exactos o aproximados según su complejidad.

La función multi-objetivo de este modelo está conformada por los objetivos, en donde se da la minimización de los costos por uso del vehículo, minimización costos de las violaciones de ventanas de tiempo y minimización de emisiones de CO2 respectivamente. La restricción asegura que un cliente es visitado exactamente una vez por un solo vehículo. La restricción asegura el flujo en la red.

La restricción garantiza que cada vehículo debe salir máximo de un depósito. Restricciones son las ecuaciones de cargue y descargue respectivamente. Para el origen las cargas se hacen cero al igual que las descargas al iniciar la ruta empleando las ecuaciones. Las ecuaciones garantiza que si un arco es realizado por un vehículo entonces una cantidad deberá cargada y descargada.

La capacidad del vehículo está dada en. Las restricciones establecen las cantidades máximas y mínimas que deben llegar a los depósitos. El tiempo de llegada al primer cliente está dado por. La restricción establece el tiempo de visita a los clientes. Si los clientes no pertenecen a la misma ruta, se introduce M como un valor muy grande que multiplica a la variable binaria para no considerar el cliente.

La restricción asegura el tiempo de ruta total del vehículo considerando el trayecto de retorno desde el último nodo al depósito. La restricción limita el tiempo de ruta total. con las restricciones respectivamente. Se consideraron inicialmente once nodos con dos depósitos y dos vehículos de prueba.

El área frontal de los vehículos, osciló entre los 4 y 3 mt2 y la relación del paso de la transmisión se tomó en 1,5 y 1,34, como lo expresa. multiplicando el costo de emisiones de una tonelada de CO2 emitidas en cada arco, por el consumo de combustible e. y la fracción oxidada del combustible, cuyo valor es de 0,99 para para petróleos y derivados.

Similar a el modelo multiobjetivo se resuelve a través del método de suma ponderada, considerado el segundo mayor utilizado en la literatura. El modelo fue programado en GAMS y resuelto óptimamente mediante el solver CPLEX. Se emplearon treinta y dos variaciones de pesos obteniendo un conjunto de cinco resultados extremos eficientes, diferenciados por las variaciones en los tiempos computacionales.

Posteriormente, se verificaron los resultados de cada objetivo comparando uno con otro para establecer la frontera de Pareto y así, identificar la mejor solución no dominada bajo el concepto de la dominancia de Pareto. Se evaluaron las instancias de cuatro rutas diferentes usando los pesos de la Tabla 1. Comparando los costos reales con los costos que arroja en modelo.

La instancia g-MHSPD_01 presentó un conjunto de ocho soluciones. La mejor solución fue obtenida con pesos de α = 0,6, β = 0,1 y γ = 0,3 con una distancia recorrida 193,589 km, litros de combustible consumidos: 68,83 Lt, tiempo de ruta: 439,44 min con 8,19 min de violación de ventanas de tiempo.

Ejecutando la instancia g-MHSPD_02 se obtuvo un conjunto de 28 soluciones acotando solo las que presentaron un GAP menor al 5% (26 conjuntos de soluciones). Las instancias g-MHSPD_03 y g-MHSPD_04 presentaron la particularidad de un solo depósito y vehículo. Con g-MHSPD_03 se obtuvo cuatro conjuntos de soluciones, de las cuales se seleccionó α = 0,2, β = 0,5 y γ = 0,6 arrojando una distancia recorrida 31,6 km, litros de combustible consumidos: 13,04 Lt, tiempo de ruta: 128,9 min sin violación de ventanas de tiempo.

Los experimentos realizados con la instancia g-MHSPD_04 arrojaron 15 conjuntos de soluciones del cual se seleccionó el resultado con pesos a = 0,8, b = 0,1 y g = 0,1. El GAP de esta solución fue del 2,07% y el mayor GAP global fue de 16,9%. Considerando las distancias y tiempos en las matrices correspondientes según la posición geográfica de las instancias para todas las rutas, el rango de tiempo necesario para obtener soluciones de la instancia g-MHSPD_01 fue de 13 a 731 min y el porcentaje de reducción fue del 13,75%.

Para la instancia g-MHSPD_02 fue de 69 a 1540 min y el porcentaje de reducción fue del 18,12%. Esta instancia presentó un GAP global máximo de 9,23%. Para la instancia g-MHSPD_03 fue de 0,18 a 0,25 min y el porcentaje de reducción fue del 7,8%. En la última instancia g-MHSPD_04 se tardó entre 211 a 777 min para obtener resultados, y el porcentaje de reducción fue del 8,35% considerando un GAP global máximo de 16,9.

Se desarrolló un modelo multi-objetivo que contribuye a la minimización de los costos en términos de: (i) costo fijo y costos variables por distancia recorrida, (ii) costos por multas de violaciones de tiempo y (iii) costo de las emisiones de CO2. Se incluye la variante "verde" debido al aumento considerable de las emisiones y los problemas de efecto invernadero que generan en gran participación los sistemas de transporte. Este tipo de problema deben ser tratados en las cadenas de suministros sostenibles.

En este trabajo se consideraron los consumos de combustible por movimiento del vehículo, carga en cada arco, aceleración inicial, además del consumo del vehículo en ralentí al realizar los servicios de cargue y descargue. Se obtuvieron soluciones óptimas no dominadas con un método de agregación para resolver problemas multi-objetivos. Se empleó el método de pesos ponderados, segundo de mayor uso en la literatura especializada y aplicado a modelos de VRPSPD.

La aplicación de este modelo genera reducciones en los costos diarios de las rutas estudiadas desde 7,8% a 18,12%. El ruteo se trabajó de manera clusterizada, debido a la complejidad computacional del modelo al ser Np-Hard. Se Agruparon los datos por cada zona obteniendo así un ruteo particular y reducciones de costos en cada una. Los modelos de pickup and delivery se caracterizan por ser de tipo Np-hard, por lo cual se pueden desarrollar y aplicar diferentes métodos aproximados. Generalmente se desarrollan algoritmos híbridos para obtener soluciones computacionalmente buenas.

La implementación de un algoritmo de dos fases es recomendada: en la primera fase puede considerarse la aplicación de métodos exactos o heurísticas, tales como el algoritmo de Clarke and Wright (C&W) para generar soluciones factibles iniciales. Posteriormente, la segunda fase buscaría mejo... Afshar-Nadjafi, B., y A. Braekers, K., K. Ramaekers. e I. Campo-Zúñiga, B., y A. Contardo, C., y R. de Oliveira, F. B. Ding, Q., X. Hu, L. Sun e Y. Eksioglu, B., A. Vural, y A. Farahani, R. Z., S. Rezapour y L. Glover, F. W., y G. A. Kochenberger, Handbook of Metaheuristics, doi:10.1007/b101874, G. Fred y Gary A. Kochenberger Eds., Vol. Golden, B. L., S. Raghavan, y E. A. Wasil, The Vehicle Routing Problem: Latest Advances and New Challenges, doi:10.1007/978-0-387-77778-8, Vol. Jia, H., Y. Li, B. Dong, y H. Kergosien, Y., C. Lenté, J.-C. Billaut, y S. Khouadjia, M. R. Laporte, G., e Y. López-Santana, E., W. C. Rodríguez-Vásquez y G. Michallet, J. Montoya-Torres, J. R., J. L. Franco, S. N. Isaza, H. F. Jiménez y N. A. Pereira, F. B. y J. Pisinger, D. y S. Suarez-Chilma, V. F., W. A. Sarache e Y. J. Toth, P. y D. Turky, A., I. Moser, y A. Aleti, An Iterated Local Search with Guided Perturbation for the Heterogeneous Fleet Vehicle Routing Problem with Time Windows and Three-Dimensional Loading Constraints, In M. Wagner, X. Li, y T. Hendtlass (Eds.), Artificial Life and Computational Intelligence (pp. Wu, W., Y. Tian y T. Xu, Y., L. Wang e Y. [ Links ]

Tabla 1: Pesos Utilizados en las Instancias

tags: