La importancia del problema de ruteo de vehículos (vrp) en la industria de la última década
Roberto García Aguirre†
Universidad Autónoma Metropolitana,
Unidad Azcapotzalco
Roman Anselmo Mora Gutiérrez
Universidad Autónoma Metropolitana,
Unidad Azcapotzalco
Edwin Montes Orozco
Universidad Autónoma Metropolitana,
Unidad Cuajimalpa
emonteso@cua.uam.mx
Resumen
El presente trabajo realiza una búsqueda y análisis, en la última década, sobre el problema del ruteo de vehículos en la industria. A pesar de que el vrp es un problema propuesto en 1959, hoy en día sigue teniendo nuevas modificaciones en la industria actual, por ejemplo, los vehículos eléctricos y la logística de entrega por parte de drones. Dichas variantes se pueden manejar como problemas vrp, pero con sus respectivas restricciones.
Esta investigación tiene como objetivo realizar una revisión de la literatura existente en la última década con el fin de examinar como el vrp se ha adaptado a las necesidades de hoy. Para la selección de literatura se tomaron en cuenta varios filtros como el año de publicación, el cual no fue mayor a diez años atrás, y los temas a tratar de los artículos, los cuales debían ser actuales. Las búsquedas se realizaron en directorios científicos, tales como Google Scholar, Scopus y Elsevier.
Palabras clave
Problema de ruteo de vehículos, servicio de paquetería y logística de entrega.
Abstract
The present work makes a search and analysis of the vehicle routing problem in the industry in the last decade. Although the VRP is a problem proposed in 1959, today it continues to have new modifications to the current industry, we can mention electric vehicles and delivery logistics by drones. These types of problems can be handled as VRP problems, but with their own restrictions.
This paper aims to make a review of different articles in the last decade in order to review how the vehicle routing problem (vrp) has been adapted to today’s needs. Methods For the search of the articles several filters were taken, such as year of publication not older than ten years of publication, the topics to be addressed in the articles have to do with current issues and VRP, the searches were performed in scientific search engines, such as, Google Scholar, scopus, The Sevier.
apa: García, R., Mora-Gutiérrez, R. A. y Montes-Orozco, E. (2024). La importancia del problema de ruteo de vehículos (vrp) en la industria de la última década. Azcatl, 3, 8-22. doi: 10.24275/AZC2024B004
Keywords
Vehicle routing problem, parcel service, delivery logistics.
Introducción
Los desafíos en la logística y la distribución de mercancías han adquirido una importancia crítica en la economía actual. En consecuencia, constantemente se están explorando nuevas técnicas de optimización con el objetivo de minimizar costos. En los sistemas logísticos modernos, la optimización de las rutas de transporte de vehículos de distribución reviste una gran relevancia para mejorar la eficiencia del transporte y reducir los costos logísticos, como se observa en investigaciones recientes (Leng y Li, 2022).
El problema de ruteo de vehículos (vrp, por sus siglas en inglés) es un problema muy común y estudiado en optimización combinatoria. Fue en 1959 que Dantzing y otros autores propusieron una minimización del coste de rutas de una flota de camiones de reparto de gasolina que parten desde una terminal a diversas estaciones de servicio, resolviéndolo mediante una formulación de programación lineal. Dada la naturaleza del problema, esta solución puede ser bien aplicada a diversas problemáticas de la vida real, sobre todo en las áreas de redes de transporte y de suministro.
Modelo matemático
Se presenta el grafo G=(N, A) con el conjunto de nodos N={0, 1...n} indexando el depósito (nodo 0), el cliente 1 al n y el conjunto de arcos A=N×N, correspondiente a todos los enlaces entre los puntos en el problema. La longitud del arco ij es cij.
|
|
(1) |
donde
- la ecuación 1 representa la función objetivo, la cual debe minimizar el costo total de rutas al conjunto de vehículos asignados;
- dij es la distancia de transporte viajando desde los nodos de i a j;
es la variable de decisión binaria que indica si el vehículo viaja desde los nodos i a j.
|
|
(2) |
|
|
(3) |
|
|
(4) |
|
|
(5) |
|
|
(6) |
|
|
(7) |
|
(8) |
donde
- la ecuación 2 asegura que cada cliente debe ser visitado si y sólo si por un vehículo;
- la restricción 3 asegura que cada vehículo parta sólo una vez del depósito;
- la restricción 4 asegura que cada vehículo regrese al depósito;
- la ecuación 5, considerada como restricción de transbordo, asegura que cada vehículo al arribar a la ubicación de un cliente salga de ésta (sirve para evitar la formación de subciclos);
- la restricción 6 asegura que la cantidad entregada al cliente i por el vehículo v sea satisfecha en su totalidad;
- la ecuación 7 asegura que la cantidad entregada en cada ruta no exceda la capacidad del vehículo;
- la restricción 8 define el tipo de variables por utilizar.
Todo lo anterior puede ser visto de manera gráfica en la Figura 1. Podemos observar el depósito, que se encuentra al centro, y los diferentes clientes a su alrededor con sus respectivas necesidades, así como los vehículos con su carga preestablecida.
Figura 1. Ejemplificación gráfica del vrp.
vrp en la última década
Vehículos verdes en el problema
de ruteo de vehículos
En la actualidad se ha puesto especial atención en los problemas climáticos y sus consecuencias en el medio ambiente. Una de las causas de contaminación más graves es aquélla emitida por la industria del transporte. Se ha considerado como una solución el uso de autos eléctricos en sustitución de los de combustión interna. Los vehículos eléctricos son definidos como vehículos que usan energía eléctrica suministrada desde fuentes eléctricas (estaciones de carga)(Park y Jin, 2020). Como resultado, se ha introducido una nueva variante del vrp denominada enrutamiento de vehículo eléctrico (evrp, por sus siglas en inglés). Esta variante considera las limitaciones propias del vrp pero agregando las propias de los vehículos eléctricos (C. Lin et al., 2014).
La idea del cambio a vehículos más verdes no sólo tiene que ver con la lucha contra los efectos del cambio climático, sino también con una visión económica, ya que el coste del combustible representa el 39 % y el 60 % de los costos operativos del sector de transporte en carretera (Sahin et al., 2009).
El evrp debe considerar las características de los vehículos eléctricos, tales como el kilometraje limitado, el problema de la velocidad de carga y, debido a que se trata de una tecnología reciente, el alto costo de inversión. La distancia que pueden recorrer los vehículos está determinada por la capacidad y el tipo de batería, es por ello que los vehículos eléctricos necesitan estacionarse en paradas específicas para poder recargar su batería; la velocidad de carga varía de acuerdo con la tecnología del fabricante del vehículo.
Las ubicaciones de las estaciones de carga de batería son conocidas y se encuentran dentro del área de servicio, pueden ser visitadas varias veces por un mismo vehículo o por diferentes vehículos, sin embargo, también pueden no ser visitadas. Asimismo, un aspecto importante por considerar es el coste asociado a la electricidad con la que se carga la batería. En cada ubicación del cliente, así como en el vrp tradicional, hay una demanda de entrega o recogida. Existe un único depósito de donde parten y regresan los vehículos (J. Lin et al., 2016).
El objetivo del evrp es similar al del vrp, esto es, minimizar el costo de distribución, atender a todos los clientes y no exceder la capacidad de carga de los vehículos, todo esto sujeto a lo siguiente:
- Cada cliente debe de ser visitado sólo una vez y solamente por un vehículo.
- Cada ruta empieza y termina en el depósito.
- La demanda total requerida por los clientes en una ruta no debe exceder la capacidad del vehículo.
Las limitaciones del evrp implican la cantidad variable de energía restante en el vehículo al llegar a un cliente, cuando se inicie la ruta se debe hacer con carga completa y los tiempos de carga y de servicio (Asghari y Mirzapour Al-e-hashem, 2021).
Ruteo de vehículos con drones
En recientes años los drones han tomado gran relevancia para los investigadores y profesionales de la logística, esto debido a varias de sus aplicaciones, entre ellas las implementaciones en la logística. Los drones son aeronaves conducidas sin piloto que mantienen su equilibrio y su manejo a través de un sistema de computadora a bordo o también pueden ser manejados por una persona de forma remota.
El uso de los drones en el área de la logística de entrega se ha incrementado por las características de éstos, pues suelen ser más rápidos que los camiones, su costo es más bajo y debido a su vuelo pueden evitar congestiones en rutas terrestres convencionales (Wohlsen, 2014). Existen importantes compañías de entrega de paquetería que usan estas aeronaves, tales como Amazon o DHL (Wang y Sheu, 2019).
Debido a las limitaciones de los drones, como la cantidad de paquetes y las baterías que utilizan, se ha promovido el uso de camiones en conjunto con éstos, no sólo como una forma de cooperación, sino como una «plataforma de lanzamiento» (Wang y Sheu, 2019).
A diferencia del problema clásico de ruteo de vehículos, en el cual sólo hay un tipo de vehículo, en el problema de ruteo de vehículos con drones (vrpd) existen dos tipos de vehículos: un dron y un camión. El primero tiene diferentes vuelos y aterrizajes y éstos pueden estar asociados con un camión diferente, por lo tanto, el camión puede lanzar y recoger varios drones en diferentes tiempos y lugares. Uno de los inconvenientes de los drones es su limitado rango de vuelo, aunque este rango es sólo una aproximación basada en la máxima distancia o el límite de tiempo (Macrina et al., 2020).
Otra restricción es el consumo de energía, el cual dependerá de varios factores, entre ellos se encuentran el medio ambiente, las dinámicas del dron y las operaciones de entrega (Zhang et al., 2021). En varios de los enfoques el rango es independiente de la velocidad o se toma la misma velocidad para todos los drones
Estas características hacen del vrpd un desafío, ya que es difícil determinar el orden de atención a la necesidad del cliente por dos tipos de vehículos, los lugares donde los camiones recogen o lanzan los drones y las rutas de los vehículos (Kuo et al., 2022).
Referencias
Asghari, M. y Mirzapour Al-e-hashem, S. M. J. (2021). Green vehicle routing problem: A state of the art review. International Journal of Production Economics, 231. https://doi.org/10.1016/J.IJPE.2020.107899
Kuo, R. J., Lu, S. H., Lai, P. Y. y Mara, S. T. W. (2022). Vehicle routing problem with drones considering time windows. Expert Systems with Applications, 191. https://doi.org/10.1016/j.eswa.2021.116264
Leng, K. y Li, S. (2022). Distribution path optimization for intelligent logistics vehicles of urban rail transportation using VRP optimization model. IEEE Transactions on Intelligent Transportation Systems, 23(2), 1661-1669. https://doi.org/10.1109/TITS.2021.3105105
Lin, C., Choy, K. L., Ho, G. T. S., Chung, S. H. y Lam, H. Y. (2014). Survey of green vehicle routing problem: Past and future trends. Expert Systems with Applications, 41(4), 1118-1138. https://doi.org/10.1016/J.ESWA.2013.07.107
Lin, J., Zhou, W. y Wolfson, O. (2016). Electric vehicle routing problem. Transportation Research Procedia, 12, 508-521. https://doi.org/10.1016/j.trpro.2016.02.007
Macrina, G., Di Puglia Pugliese, L., Guerriero, F. y Laporte, G. (2020). Drone-aided routing: A literature review. Transportation Research Part C: Emerging Technologies, 120. https://doi.org/10.1016/J.TRC.2020.102762
Park, H. y Jin, S. (2020). Electric vehicle routing problem with heterogeneous vehicles and partial charge. International Journal of Industrial Engineering and Management, 11(4), 215-225. https://doi.org/10.24867/IJIEM-2020-4-266
Sahin, B., Yilmaz, H., Ust, Y., Guneri, A. F. y Gulsun, B. (2009). An approach for analysing transportation costs and a case study. European Journal of Operational Research, 193(1), 1-11. https://doi.org/10.1016/J.EJOR.2007.10.030
Wang, Z. y Sheu, J. B. (2019). Vehicle routing problem with drones. Transportation Research Part B: Methodological, 122, 350-364. https://doi.org/10.1016/j.trb.2019.03.005
Wohlsen, M. (18 de junio de 2014). The next big thing you missed: Amazon’s delivery drones could work. They just need trucks. Wired. https://www.wired.com/2014/06/the-next-big-thing-you-missed-delivery-drones-launched-from-trucks-are-the-future-of-shipping/
Zhang, J., Campbell, J. F., Sweeney, D. C. y Hupman, A. C. (2021). Energy consumption models for delivery drones: A comparison and assessment. Transportation Research Part D: Transport and Environment, 90. https://doi.org/10.1016/J.TRD.2020.102668