Problema de ruta del vehículo

Problema de optimización

Una figura que ilustra el problema de ruta del vehículo.

El problema de ruteo de vehículos ( VRP ) es un problema de optimización combinatoria y programación entera que plantea la pregunta "¿Cuál es el conjunto óptimo de rutas que debe recorrer una flota de vehículos para realizar entregas a un conjunto determinado de clientes?". Generaliza el problema del viajante de comercio (TSP). Apareció por primera vez en un artículo de George Dantzig y John Ramser en 1959, ^[1] en el que se escribió el primer enfoque algorítmico y se aplicó a las entregas de gasolina. A menudo, el contexto es el de la entrega de bienes ubicados en un depósito central a clientes que han realizado pedidos de dichos bienes. El objetivo del VRP es minimizar el costo total de la ruta. En 1964, Clarke y Wright mejoraron el enfoque de Dantzig y Ramser utilizando un algoritmo voraz eficaz llamado algoritmo de ahorro.

Determinar la solución óptima para VRP es NP-hard , ^[2] por lo que el tamaño de los problemas que se pueden resolver de manera óptima mediante programación matemática u optimización combinatoria puede ser limitado. Por lo tanto, los solucionadores comerciales tienden a utilizar heurísticas debido al tamaño y la frecuencia de los VRP del mundo real que necesitan resolver.

El VRP tiene muchas aplicaciones directas en la industria. Los proveedores de herramientas de enrutamiento VRP a menudo afirman que pueden ofrecer ahorros de costos de entre el 5 % y el 30 %. ^[3]

Planteando el problema

El VRP se refiere al servicio de una empresa de reparto. Cómo se entregan las cosas desde uno o más depósitos que tienen un conjunto determinado de vehículos locales y son operados por un conjunto de conductores que pueden trasladarse por una red de carreteras determinada a un conjunto de clientes . Pide la determinación de un conjunto de rutas , S , (una ruta para cada vehículo que debe empezar y terminar en su propio depósito) de modo que se satisfagan todos los requisitos y restricciones operativas de los clientes y se minimice el coste global del transporte . Este coste puede ser monetario, de distancia o de otro tipo. ^[2]

La red vial se puede describir mediante un gráfico donde los arcos son las carreteras y los vértices las uniones entre ellas. Los arcos pueden ser dirigidos o no debido a la posible presencia de calles de un solo sentido o de diferentes costos en cada sentido. Cada arco tiene un costo asociado que generalmente es su longitud o tiempo de viaje que puede depender del tipo de vehículo. ^[2]

Para conocer el costo global de cada ruta, se debe conocer el costo del viaje y el tiempo de viaje entre cada cliente y el depósito. Para hacer esto, nuestro grafo original se transforma en uno donde los vértices son los clientes y el depósito, y los arcos son las carreteras entre ellos. El costo en cada arco es el costo más bajo entre los dos puntos en la red de carreteras original. Esto es fácil de hacer ya que los problemas de ruta más corta son relativamente fáciles de resolver. Esto transforma el grafo original disperso en un grafo completo . Para cada par de vértices i y j , existe un arco (i,j) del grafo completo cuyo costo se escribe como y se define como el costo de la ruta más corta de i a j . El tiempo de viaje es la suma de los tiempos de viaje de los arcos en la ruta más corta de i a j en el grafo de carreteras original. ${\displaystyle C_{ij}}$ ${\displaystyle t_{ij}}$

En ocasiones es imposible satisfacer todas las demandas de un cliente y en tales casos los solucionadores pueden reducir las demandas de algunos clientes o dejar a algunos clientes sin atender. Para lidiar con estas situaciones se puede introducir una variable de prioridad para cada cliente o asociar penalizaciones por el servicio parcial o nulo para cada cliente dado ^[2]

La función objetivo de un VRP puede ser muy diferente dependiendo de la aplicación particular del resultado, pero algunos de los objetivos más comunes son: ^[2]

• Minimizar el costo de transporte global en función de la distancia global recorrida, así como los costos fijos asociados con los vehículos y conductores usados.
• Minimizar el número de vehículos necesarios para atender a todos los clientes
• Menor variación en el tiempo de viaje y la carga del vehículo.
• Minimizar las sanciones por servicios de baja calidad
• Maximizar una ganancia/puntuación recolectada.

Variantes del VRP

Un mapa que muestra la relación entre los subproblemas comunes de VRP.

Existen varias variaciones y especializaciones del problema de enrutamiento de vehículos:

• Problema de Ruteo de Vehículos con Ganancias (VRPP): Problema de maximización en el que no es obligatorio visitar a todos los clientes. El objetivo es visitar una sola vez a los clientes maximizando la suma de las ganancias obtenidas respetando un límite de tiempo del vehículo. Los vehículos deben empezar y terminar en el depósito. Entre los VRPP más conocidos y estudiados, citamos:
  • El Problema de Orientación en Equipo (TOP), que es la variante más estudiada del VRPP, ^{[4] [5] [6]}
  • El problema de orientación en equipo capacitado (CTOP),
  • El TOP con Ventanas de Tiempo (TOPTW).
• Problema de enrutamiento de vehículos con recogida y entrega (VRPPD): es necesario trasladar una cantidad de mercancías desde determinados lugares de recogida a otros lugares de entrega. El objetivo es encontrar rutas óptimas para que una flota de vehículos visite los lugares de recogida y entrega.
• Problema de enrutamiento de vehículos con LIFO : similar al VRPPD, excepto que se impone una restricción adicional en la carga de los vehículos: en cualquier lugar de entrega, el artículo que se entrega debe ser el artículo recogido más recientemente. Este esquema reduce los tiempos de carga y descarga en los lugares de entrega porque no hay necesidad de descargar temporalmente artículos distintos de los que deben entregarse.
• Problema de enrutamiento de vehículos con ventanas de tiempo (VRPTW): Las ubicaciones de entrega tienen ventanas de tiempo dentro de las cuales se deben realizar las entregas (o visitas).
• Problema de enrutamiento de vehículos con capacidad: CVRP o CVRPTW. Los vehículos tienen una capacidad de transporte limitada de las mercancías que deben ser entregadas.
• Problema de enrutamiento de vehículos con viajes múltiples (VRPMT): Los vehículos pueden realizar más de una ruta.
• Problema de ruta abierta de vehículos (OVRP): no es necesario que los vehículos regresen al depósito.
• Problema de enrutamiento de inventario (IRP): Los vehículos son responsables de satisfacer las demandas en cada punto de entrega ^[7]
• Problema de enrutamiento de vehículos en múltiples depósitos (MDVRP): existen múltiples depósitos desde los cuales los vehículos pueden comenzar y terminar. ^[8]
• Problema de enrutamiento de vehículos con transferencias (VRPWT): las mercancías se pueden transferir entre vehículos en centros de transferencia especialmente designados.
• Problema de enrutamiento de vehículos eléctricos (EVRP): son VRP especiales que toman en cuenta como restricción adicional la capacidad de la batería de los vehículos eléctricos.

Varios proveedores de software han creado productos de software para resolver diversos problemas de VRP. Hay numerosos artículos disponibles para obtener más detalles sobre sus investigaciones y resultados.

Aunque el VRP está relacionado con el problema de programación de talleres , ambos problemas suelen resolverse utilizando técnicas diferentes. ^[9]

Métodos de solución exacta

Hay tres enfoques principales diferentes para modelar el VRP

1. Formulaciones de flujo de vehículos : utiliza variables enteras asociadas con cada arco que cuentan la cantidad de veces que un vehículo atraviesa el borde. Generalmente se utiliza para VRP básicos. Esto es bueno para casos en los que el costo de la solución se puede expresar como la suma de los costos asociados con los arcos. Sin embargo, no se puede utilizar para manejar muchas aplicaciones prácticas. ^[2]
2. Formulaciones de flujo de mercancías : se asocian variables enteras adicionales con los arcos o bordes que representan el flujo de mercancías a lo largo de las rutas recorridas por los vehículos. Esto se ha utilizado recientemente para encontrar una solución exacta. ^[2]
3. Problema de partición de conjuntos : estos tienen una cantidad exponencial de variables binarias , cada una de las cuales está asociada con un circuito factible diferente. El problema de partición de conjuntos se formula entonces como un problema de partición de conjuntos que pregunta cuál es la colección de circuitos con un costo mínimo que satisface las restricciones del problema de partición de conjuntos. Esto permite costos de ruta muy generales. ^[2]

Formulaciones de flujo de vehículos

La formulación del TSP de Dantzig, Fulkerson y Johnson se amplió para crear las dos formulaciones de flujo de vehículo de índice para el VRP

${\displaystyle {\text{min}}\sum _{i\in V}\sum _{j\in V}c_{ij}x_{ij}}$

sujeto a

En esta formulación representa el costo de ir de nodo a nodo , es una variable binaria que tiene valor si el arco que va de a se considera como parte de la solución y en caso contrario, es el número de vehículos disponibles y corresponde al número mínimo de vehículos necesarios para dar servicio al conjunto . También estamos asumiendo que es el nodo de depósito. ${\displaystyle c_{ij}}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle x_{ij}}$ ${\displaystyle 1}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle 0}$ ${\displaystyle K}$ ${\displaystyle r(S)}$ ${\displaystyle S}$ ${\displaystyle 0}$

Las restricciones 1 y 2 establecen que exactamente un arco entra y exactamente uno sale de cada vértice asociado con un cliente, respectivamente. Las restricciones 3 y 4 establecen que el número de vehículos que salen del depósito es el mismo que el número de vehículos que entran. Las restricciones 5 son las restricciones de corte de capacidad, que imponen que las rutas deben estar conectadas y que la demanda en cada ruta no debe exceder la capacidad de vehículos. Finalmente, las restricciones 6 son las restricciones de integralidad. ^[2]

Una restricción arbitraria entre las restricciones está realmente implícita en las restantes, por lo que puede eliminarse. Cada corte definido por un conjunto de clientes está atravesado por una cantidad de arcos no menor que ⁠ ⁠ (cantidad mínima de vehículos necesarios para dar servicio al conjunto ). ^[2] ${\displaystyle 2|V|}$ ${\displaystyle 2|V|-1}$ ${\displaystyle S}$ ${\displaystyle r(S)}$ ${\displaystyle S}$

Se puede obtener una formulación alternativa transformando las restricciones de recorte de capacidad en restricciones de eliminación de subrutas generalizadas (GSEC).

${\displaystyle \sum _{i\in S}\sum _{j\in S}x_{ij}\leq |S|-r(S)}$

lo que impone que al menos ⁠ ⁠ ${\displaystyle r(S)}$ arcos salgan de cada conjunto de clientes . ^[2] ${\displaystyle S}$

Los GCEC y los CCC tienen un número exponencial de restricciones, por lo que es prácticamente imposible resolver la relajación lineal. Una forma posible de resolver esto es considerar un subconjunto limitado de estas restricciones y agregar el resto si es necesario. La identificación de las restricciones necesarias se realiza mediante un procedimiento de separación. Se han desarrollado métodos de separación exactos y eficientes para tales restricciones (basados ​​en la programación entera mixta). ^[10]

Un método diferente es utilizar una familia de restricciones que tienen una cardinalidad polinomial, conocidas como restricciones MTZ, que fueron propuestas por primera vez para el TSP ^[11] y posteriormente extendidas por Christofides, Mingozzi y Toth. ^[12]

${\displaystyle u_{j}-u_{i}\geq d_{j}-C(1-x_{ij})~~~~~~\forall i,j\in V\backslash \{0\},i\neq j~~~~{\text{s.t. }}d_{i}+d_{j}\leq C}$

${\displaystyle 0\leq u_{i}\leq C-d_{i}~~~~~~\forall i\in V\backslash \{0\}}$

donde es una variable continua adicional que representa la carga que queda en el vehículo después de visitar al cliente y es la demanda del cliente . Estos imponen tanto los requisitos de conectividad como de capacidad. Cuando la restricción no es vinculante, ya que y mientras que imponen que . ${\displaystyle u_{i},~i\in V\backslash \{0\}}$ ${\displaystyle i}$ ${\displaystyle d_{i}}$ ${\displaystyle i}$ ${\displaystyle x_{ij}=0}$ ${\displaystyle i}$ ${\displaystyle u_{i}\leq C}$ ${\displaystyle u_{j}\geq d_{j}}$ ${\displaystyle x_{ij}=1}$ ${\displaystyle u_{j}\geq u_{i}+d_{j}}$

Estos se han utilizado ampliamente para modelar el VRP básico (CVRP) y el VRPB. Sin embargo, su poder está limitado a estos problemas simples. Solo se pueden utilizar cuando el costo de la solución se puede expresar como la suma de los costos de los arcos. Tampoco podemos saber qué vehículo atraviesa cada arco. Por lo tanto, no podemos utilizar esto para modelos más complejos donde el costo y/o la viabilidad dependen del orden de los clientes o de los vehículos utilizados. ^[2]

Enrutamiento óptimo manual versus automático

Existen muchos métodos para resolver problemas de rutas de vehículos de forma manual. Por ejemplo, la ruta óptima es un gran problema de eficiencia para las carretillas elevadoras en grandes almacenes. Algunos de los métodos manuales para decidir la ruta más eficiente son: el mayor espacio libre, la forma de S, pasillo por pasillo, combinado y combinado + Si bien el método combinado + es el más complejo, por lo tanto el más difícil de utilizar por los operadores de carretillas elevadoras, es el método de ruta más eficiente. Aún así, la diferencia porcentual entre el método de ruta óptima manual y la ruta óptima real fue en promedio del 13%. ^{[13] [14]}

Metaheurística

Debido a la dificultad de resolver de manera óptima instancias a gran escala de problemas de enrutamiento de vehículos, se ha dedicado un esfuerzo de investigación significativo a metaheurísticas como algoritmos genéticos , búsqueda tabú , recocido simulado y búsqueda adaptativa de grandes vecindarios (ALNS). Algunas de las metaheurísticas más recientes y eficientes para problemas de enrutamiento de vehículos alcanzan soluciones dentro del 0,5% o 1% del óptimo para instancias de problemas que cuentan con cientos o miles de puntos de entrega. ^[15] Estos métodos también son más robustos en el sentido de que se pueden adaptar más fácilmente para lidiar con una variedad de restricciones secundarias. Como tal, la aplicación de técnicas metaheurísticas a menudo se prefiere para aplicaciones a gran escala con restricciones complicadas y conjuntos de decisiones.

Véase también

• Problema del cartero chino
• Problema de reprogramación de vehículos
• Enrutamiento de arco
• Lista de temas de teoría de grafos

Referencias

1. Dantzig, George Bernard; Ramser, John Hubert (octubre de 1959). "El problema del despacho de camiones" (PDF) . Management Science . 6 (1): 80–91. doi :10.1287/mnsc.6.1.80.
2. Toth, P.; Vigo, D., eds. (2002). El problema de la determinación de rutas para vehículos . Monografías sobre matemáticas discretas y aplicaciones. Vol. 9. Filadelfia: Sociedad de matemáticas industriales y aplicadas. ISBN 0-89871-579-2.
3. Geir Hasle; Knut-Andreas Lie; Ewald Quak, eds. (2007). Modelado geométrico, simulación numérica y optimización:: Matemáticas aplicadas en SINTEF. Berlín: Springer Verlag. pp. 397–398. ISBN 978-3-540-68783-2.
4. Chao, I-Ming; Golden, Bruce L; Wasil, Edward A (1996). "El problema de la orientación en equipo". Revista Europea de Investigación Operativa . 88 (3): 464–474. doi :10.1016/0377-2217(94)00289-4.
5. Archetti, C.; Sperenza, G.; Vigo, D. (2014). "Problemas de ruteo de vehículos con ganancias". En Toth, P.; Vigo, D. (eds.). Ruteo de vehículos: problemas, métodos y aplicaciones (segunda ed.). págs. 273–297. doi :10.1137/1.9781611973594.ch10.
6. Hammami, Farouk; Rekik, Monia; Coelho, Leandro C. (2020). "Una heurística de búsqueda híbrida adaptativa de vecindarios grandes para el problema de orientación en equipo". Computers & Operations Research . 123 : 105034. doi :10.1016/j.cor.2020.105034. S2CID  221134904.
7. Ekici, Ali; Özener, Okan Örsan; Kuyzu, Gültekin (noviembre de 2015). "Programaciones de entrega cíclicas para un problema de enrutamiento de inventario". Ciencia del transporte . 49 (4): 817–829. doi :10.1287/trsc.2014.0538.
8. Mahmud, Nafix; Haque, Md. Mokammel (febrero de 2019). Solución del problema de enrutamiento de vehículos en varios depósitos (MDVRP) mediante un algoritmo genético . Conferencia internacional de 2019 sobre ingeniería eléctrica, informática y de comunicaciones (ECCE). doi :10.1109/ECACE.2019.8679429.
9. Beck, JC; Prosser, P.; Selensky, E. (2003). "Enrutamiento de vehículos y programación de talleres: ¿cuál es la diferencia?" (PDF) . Actas de la 13.ª Conferencia internacional sobre planificación y programación con inteligencia artificial .
10. Pavlikov, K.; Petersen, NC; Sørensen, JL (2023). "Separación exacta de las desigualdades de capacidad redondeadas para el problema de enrutamiento de vehículos capacitados". Redes . 83 . Redes: 197–209. doi : 10.1002/net.22183 . S2CID  263321558.
11. Miller, CE; Tucker, EW; Zemlin, RA (1960). "Formulaciones de programación entera y problemas del viajante de comercio". J. ACM . 7 : 326–329. doi : 10.1145/321043.321046 . S2CID  2984845.
12. Christofides, N.; Mingozzi, A.; Toth, P. (1979). El problema de la asignación de rutas a los vehículos . Chichester, Reino Unido: Wiley. págs. 315–338.
13. "¿Por qué la planificación manual de rutas óptimas en almacenes es tan ineficiente?". Locatible.com . 2016-09-26 . Consultado el 2016-09-26 .
14. Roodbergen, Kees Jan (2001). "Métodos de enrutamiento para almacenes con múltiples pasillos transversales" (PDF) . roodbergen.com . Consultado el 26 de septiembre de 2016 .
15. Vidal T, Crainic TG, Gendreau M, Prins C (2014). "Un marco de solución unificado para problemas de enrutamiento de vehículos con múltiples atributos" (PDF) . Revista Europea de Investigación Operativa . 234 (3): 658–673. doi :10.1016/j.ejor.2013.09.045. S2CID  21037953.

Lectura adicional

• Oliveira, HCBde; Vasconcelos, GC (2008). "Un método de búsqueda híbrido para el problema de ruteo de vehículos con ventanas de tiempo". Anales de Investigación de Operaciones . 180 : 125–144. doi :10.1007/s10479-008-0487-y. S2CID  32406011.
• Frazzoli, E.; Bullo, F. (2004). "Algoritmos descentralizados para el enrutamiento de vehículos en un entorno estocástico que varía en el tiempo". 2004 43.ª Conferencia IEEE sobre decisiones y control (CDC) (IEEE Cat. N.º 04CH37601) . Vol. 4. IEEE. págs. 3357–3363. doi :10.1109/CDC.2004.1429220. ISBN. 0-7803-8682-5. ISSN  0191-2216.
• Psaraftis, HN (1988). "Problemas de enrutamiento dinámico de vehículos" (PDF) . Enrutamiento de vehículos: métodos y estudios . 16 : 223–248.
• Bertsimas, DJ; Van Ryzin, G. (1991). "Un problema de enrutamiento de vehículos estocástico y dinámico en el plano euclidiano". Investigación de operaciones . 39 (4): 601–615. doi :10.1287/opre.39.4.601. hdl : 1721.1/2353 . JSTOR  171167.
• Vidal T, Crainic TG, Gendreau M, Prins C (2013). "Heurísticas para problemas de enrutamiento de vehículos con múltiples atributos: un estudio y síntesis" (PDF) . Revista Europea de Investigación Operativa . 231 (1): 1–21. doi :10.1016/j.ejor.2013.02.053. S2CID  15983279.
• Hirotaka, Irie; Wongpaisarnsin, Goragot; Terabe, Masayoshi; Miki, Akira; Taguchi, Shinichirou (2019). "Recocido cuántico del problema de enrutamiento de vehículos con tiempo, estado y capacidad". arXiv : 1903.06322 [quant-ph].