Problema de ruta de vehículos

Problema de optimizacion

Una figura que ilustra el problema de las rutas de vehículos.

El problema de enrutamiento de vehículos ( VRP ) es un problema de optimización combinatoria y programación entera que 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 coste total de la ruta. En 1964, Clarke y Wright mejoraron el enfoque de Dantzig y Ramser utilizando un algoritmo codicioso eficaz llamado algoritmo de ahorro.

Determinar la solución óptima para VRP es NP-difícil , ^[2] por lo que el tamaño de los problemas que pueden resolverse 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.

VRP tiene muchas aplicaciones directas en la industria. Los proveedores de herramientas de enrutamiento VRP suelen afirmar que pueden ofrecer ahorros de costes del 5 % al 30 %. ^[3]

Configurando 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 cuentan con un determinado conjunto de vehículos nacionales y son operados por un conjunto de conductores que pueden desplazarse por una determinada red de carreteras hacia un conjunto de clientes . Solicita la determinación de un conjunto de rutas , S , (una ruta para cada vehículo que debe comenzar y terminar en su propio depósito) de modo que se satisfagan todos los requisitos de los clientes y las restricciones operativas y se minimice el costo de transporte global . Este costo puede ser monetario, de distancia o de otro tipo. ^[2]

La red de carreteras se puede describir mediante un gráfico donde los arcos son carreteras y los vértices son cruces entre ellas. Los arcos pueden ser dirigidos o no dirigidos debido a la posible presencia de calles de un solo sentido o costos diferentes 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 coste global de cada ruta se debe conocer el coste del viaje y el tiempo de viaje entre cada cliente y el depósito. Para hacer esto, nuestro gráfico 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 de la red vial original. Esto es fácil de hacer ya que los problemas del camino más corto son relativamente fáciles de resolver. Esto transforma el gráfico original disperso en un gráfico completo . Para cada par de vértices i y j , existe un arco (i,j) del gráfico completo cuyo costo se escribe como y se define como el costo del camino más corto de i a j . El tiempo de viaje es la suma de los tiempos de viaje de los arcos en el camino más corto de i a j en el gráfico de ruta original. ${\displaystyle C_{ij}}$ ${\displaystyle t_{ij}}$

A veces 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 sin atender. Para hacer frente a estas situaciones se puede introducir una variable de prioridad para cada cliente o asociar penalizaciones por el servicio parcial o falta de servicio para cada cliente prestado ^[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 la cantidad de vehículos necesarios para atender a todos los clientes.
• Mínima variación en el tiempo de viaje y carga del vehículo.
• Minimizar las sanciones por un servicio de baja calidad
• Maximice una ganancia/puntaje recolectado.

variantes de VRP

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

Existen varias variaciones y especializaciones del problema de generación de rutas de vehículos:

• Problema de rutas de vehículos con beneficios (VRPP): un problema de maximización en el que no es obligatorio visitar a todos los clientes. El objetivo es visitar una vez a los clientes maximizando la suma de los beneficios recaudados respetando el límite de tiempo del vehículo. Los vehículos deben comenzar y terminar en el depósito. Entre los PPVR 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 la orientación de equipos capacitados (CTOP),
  • El TOP con Ventanas de Tiempo (TOPTW).
• Problema de ruta de vehículos con recogida y entrega (VRPPD): Es necesario trasladar una serie de mercancías desde ciertos 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 devolución.
• Problema de ruta de vehículos con LIFO : similar al VRPPD, excepto que se impone una restricción adicional a 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 a los que se deben dejar.
• Problema de rutas de vehículos con ventanas de tiempo (VRPTW): Los lugares de entrega tienen ventanas de tiempo dentro de las cuales se deben realizar las entregas (o visitas).
• Problema de rutas de vehículos capacitados: CVRP o CVRPTW. Los vehículos tienen una capacidad de carga limitada de las mercancías que deben ser entregadas.
• Problema de rutas de vehículos con viajes múltiples (VRPMT): Los vehículos pueden hacer más de una ruta.
• Problema de ruta abierta para vehículos (OVRP): no es necesario que los vehículos regresen al depósito.
• Problema de ruta de inventario (IRP): Los vehículos son responsables de satisfacer las demandas en cada punto de entrega ^[7]
• Problema de rutas de vehículos con múltiples depósitos (MDVRP): existen múltiples depósitos desde los cuales los vehículos pueden comenzar y terminar. ^[8]
• Problema de ruta 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 tienen 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 VRP está relacionado con el problema de programación del taller , los dos problemas generalmente se resuelven utilizando técnicas diferentes. ^[9]

Métodos de solución exacta.

Hay tres enfoques diferentes principales para modelar el VRP.

1. Formulaciones de flujo de vehículos : utiliza variables enteras asociadas con cada arco que cuentan el número de veces que un vehículo atraviesa el borde. Generalmente se utiliza para VRP básicos. Esto es bueno para los 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 aristas que representan el flujo de mercancías a lo largo de las trayectorias recorridas por los vehículos. Esto se ha utilizado recientemente para encontrar una solución exacta. ^[2]
3. Problema de partición de conjuntos : tienen un número exponencial de variables binarias , cada una de las cuales está asociada a un circuito factible diferente. Luego, el VRP se formula como un problema de partición de conjuntos que pregunta cuál es el conjunto de circuitos con costo mínimo que satisfacen las restricciones del VRP. 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 índice de flujo de vehículos 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 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. necesario para servir el conjunto . También suponemos 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 dicen 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 del vehículo. 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 es atravesado por un número de arcos no inferior a (número mínimo 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 corte de capacidad en restricciones de eliminación de subtours generalizadas (GSEC).

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

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

Los GCEC y CCC tienen un número exponencial de restricciones por lo que es prácticamente imposible resolver la relajación lineal. Una posible forma 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 eficientes de separación exacta para tales restricciones (basados ​​en programación entera mixta). ^[10]

Un método diferente nuevamente es utilizar una familia de restricciones que tienen una cardinalidad polinómica que se conocen como restricciones MTZ, fueron propuestas por primera vez para el TSP ^[11] y posteriormente ampliadas 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 requisitos tanto de conectividad como de capacidad. Cuando la restricción entonces no es vinculante, ya que la imponen . ${\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 se limita a estos simples problemas. Sólo se pueden utilizar cuando el costo de la solución se puede expresar como la suma de los costos de los costos del arco. Tampoco podemos saber qué vehículo atraviesa cada arco. Por lo tanto, no podemos usar esto para modelos más complejos donde el costo o la viabilidad dependen del pedido de los clientes o de los vehículos utilizados. ^[2]

Enrutamiento óptimo manual versus automático

Existen muchos métodos para resolver manualmente los problemas de generación de rutas de vehículos. Por ejemplo, la ruta óptima es un gran problema de eficiencia para los montacargas en grandes almacenes. Algunos de los métodos manuales para decidir la ruta más eficiente son: Espacio más grande, forma de S, pasillo por pasillo, combinado y combinado +. Mientras que el método combinado + es el más complejo y, por lo tanto, el más difícil de utilizar por parte de los operadores de montacargas. , es el método de enrutamiento 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 rutas de vehículos, se ha dedicado un importante esfuerzo de investigación a metaheurísticas como los algoritmos genéticos , la búsqueda tabú , el recocido simulado y la búsqueda adaptativa de grandes vecindarios (ALNS). Algunas de las metaheurísticas más recientes y eficientes para problemas de rutas de vehículos alcanzan soluciones dentro del 0,5% o 1% del óptimo para casos de problemas que cuentan cientos o miles de puntos de entrega. ^[15] Estos métodos también son más sólidos en el sentido de que pueden adaptarse más fácilmente para hacer frente a una variedad de limitaciones secundarias. Como tal, la aplicación de técnicas metaheurísticas a menudo se prefiere para aplicaciones a gran escala con restricciones y conjuntos de decisiones complicados.

Ver 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) . Ciencias de la gestión . 6 (1): 80–91. doi :10.1287/mnsc.6.1.80.
2. Toth, P.; Vigo, D., eds. (2002). El problema de las rutas de 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; La mentira de Knut-Andreas; Ewald Quak, eds. (2007). Modelado Geométrico, Simulación Numérica y Optimización:: Matemática Aplicada en SINTEF. Berlín: Springer Verlag. págs. 397–398. ISBN 978-3-540-68783-2.
4. Chao, I-Ming; Dorado, 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 ruta de vehículos con ganancias". En Toth, P.; Vigo, D. (eds.). Rutas 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". Investigación de operaciones y computadoras . 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). "Resolver el problema de rutas de vehículos de depósito múltiple (MDVRP) mediante un algoritmo genético" . 2019 Congreso Internacional de Ingeniería Eléctrica, Informática y Comunicaciones (ECCE). doi :10.1109/ECACE.2019.8679429.
9. Beck, JC; Prosser, P.; Selensky, E. (2003). "Ruteo 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 de Inteligencia Artificial .
10. Pávlikov, K.; Petersen, Carolina del Norte; 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. Molinero, 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. Cristofides, N.; Mingozzi, A.; Toth, P. (1979). El problema de las rutas de vehículos . Chichester, Reino Unido: Wiley. págs. 315–338.
13. "¿Por qué el enrutamiento óptimo del almacén manual es tan ineficiente?". Localizable.com . 26 de septiembre de 2016 . Consultado el 26 de septiembre de 2016 .
14. Roodbergen, Kees Jan (2001). "Métodos de enrutamiento para almacenes con múltiples pasillos transversales" (PDF) . www.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 generación de rutas 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.

Otras lecturas

• Oliveira, HCBde; Vasconcelos, GC (2008). "Un método de búsqueda híbrido para el problema de rutas 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 Decisión y Control (CDC) (IEEE Cat. No.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 dinámicos de rutas de vehículos" (PDF) . Rutas de vehículos: métodos y estudios . 16 : 223–248.
• Bertsimas, DJ; Van Ryzin, G. (1991). "Un problema estocástico y dinámico de rutas de vehículos en el plano euclidiano". La 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ística para problemas de enrutamiento de vehículos con múltiples atributos: 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 [cuántico-ph].