Hispanopedia Wiki
Articulo de referencia

Vehicle routing problem

An illustration of an instance of the vehicle routing problem in a road network, containing routes for three vehicles to deliver goods from a central depot (D) to 11 locations. ...

Hispanopedia WikiContenido en espanolLectura gratuita
An illustration of an instance of the vehicle routing problem in a road network, containing routes for three vehicles to deliver goods from a central depot (D) to 11 locations.

The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?" The problem first appeared, as the truck dispatching problem, in a paper by George Dantzig and John Ramser in 1959,[1] in which it was applied to petrol deliveries. Often, the context is that of delivering goods located at a central depot to customers who have placed orders for such goods.[2] However, variants of the problem consider, e.g, collection of solid waste[3] and the transport of the elderly and the sick to and from health-care facilities.[4][5] The standard objective of the VRP is to minimise the total route cost.[6]:5 Other objectives, such as minimising the number of vehicles used or travelled distance are also considered.[7]

The VRP generalises the travelling salesman problem (TSP), which is equivalent to requiring a single route to visit all locations. As the TSP is NP-hard, the VRP is also NP-hard.[6]:5

VRP has many direct applications in industry. Vendors of VRP routing tools often claim that they can offer cost savings of 5%–30%.[8] Commercial solvers tend to use heuristics due to the size and frequency of real world VRPs they need to solve.

Setting up the problem

The VRP concerns the service of a delivery company. How things are delivered from one or more depots which has a given set of home vehicles and operated by a set of drivers who can move on a given road network to a set of customers. It asks for a determination of a set of routes, S, (one route for each vehicle that must start and finish at its own depot) such that all customers' requirements and operational constraints are satisfied and the global transportation cost is minimized. This cost may be monetary, distance or otherwise.[6]

La red vial se puede describir mediante un grafo donde los arcos representan las carreteras y los vértices, las intersecciones entre ellas. Los arcos pueden ser dirigidos o no dirigidos debido a la posible presencia de calles de sentido único o a la diferencia de costes en cada dirección. Cada arco tiene un coste asociado, que generalmente corresponde a su longitud o tiempo de viaje, el cual puede depender del tipo de vehículo. [ 6 ]

Para conocer el costo global de cada ruta, se debe conocer el costo de viaje y el tiempo de viaje entre cada cliente y el depósito. Para ello, nuestro grafo original se transforma en uno donde los vértices son los clientes y el depósito, y los arcos son las carreteras que los conectan. El costo en cada arco es el costo más bajo entre los dos puntos de 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 comodoij{\displaystyle C_{ij}}y se define como el costo del camino más corto de i a j . El tiempo de viajetij{\displaystyle t_{ij}}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 carretera original.

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 otros sin atender. Para abordar estas situaciones, se puede introducir una variable de prioridad para cada cliente o asociar penalizaciones por el servicio parcial o la falta de servicio para cada cliente dado [ 6 ].

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: [ 6 ]

  • Minimizar el coste global del transporte en función de la distancia global recorrida, así como de los costes fijos asociados a los vehículos y conductores utilizados.
  • Minimizar el número de vehículos necesarios para atender a todos los clientes.
  • Mínima variación en el tiempo de viaje y la carga del vehículo.
  • Minimizar las penalizaciones por un servicio de baja calidad.
  • Maximizar el beneficio/puntuación obtenido.

Variantes de VRP

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

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

  • Problema de enrutamiento de vehículos con beneficios (VRPP): Un problema de maximización con beneficios atribuidos a cada cliente y costos (generalmente en términos de tiempo) atribuidos a cada arco (viaje de cliente a cliente), y restricciones sobre estos beneficios y costos. [ 9 ] Los subproblemas comunes del VRPP son:
    • Problema de orientación (PO), donde se da una restricción de precio (o de tiempo) y el objetivo es maximizar la suma de las ganancias obtenidas respetando el límite de costos. Los vehículos deben comenzar y terminar en el depósito. Entre los PO más conocidos y estudiados se encuentran:
      • El problema de orientación en equipo (TOP), que es la variante más estudiada del VRPP, [ 10 ] [ 11 ] [ 12 ]
      • El problema de orientación de equipos con capacidad limitada (CTOP),
      • El TOP con ventanas de tiempo (TOPTW).
    • Problema del viajante de comercio (PCTSP), en el que el objetivo es minimizar el costo total, sujeto al requisito de que la ganancia recaudada supere un valor dado.
    • Problema del Tour Rentable (PTP, por sus siglas en inglés), cuyo objetivo es maximizar la diferencia entre el beneficio y el coste.
  • Problema de enrutamiento de vehículos con transporte de retorno (VRPB): Se dan conjuntos disjuntos de clientes de entrega y recogida. Las mercancías deben entregarse desde el depósito al cliente de entrega y desde los clientes de recogida al depósito. [ 13 ] Se puede prohibir a los vehículos recoger mercancías de los clientes hasta que todas las mercancías transportadas se hayan entregado a los clientes de entrega o permitir el intercambio de recogidas con entregas a un coste potencial. [ 13 ] [ 14 ]
  • Problema de enrutamiento de vehículos con recogida y entrega (VRPPD): Se necesita trasladar una cantidad de mercancías desde ciertos puntos de recogida a otros puntos de entrega. El objetivo es encontrar las rutas óptimas para que una flota de vehículos visite los puntos de recogida y entrega.
  • Problema de enrutamiento de vehículos con LIFO : Similar al VRPPD, con la excepción de que se impone una restricción adicional a la carga de los vehículos: en cada punto de entrega, el artículo que se entrega debe ser el que se recogió más recientemente. Este esquema reduce los tiempos de carga y descarga en los puntos de entrega, ya que no es necesario descargar temporalmente artículos que no sean los que se deben entregar.
  • Problema de enrutamiento 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 enrutamiento de vehículos con capacidad limitada: CVRP o CVRPTW. Los vehículos tienen una capacidad de transporte limitada de las mercancías que deben entregar.
  • Problema de enrutamiento de vehículos con múltiples viajes (VRPMT): Los vehículos pueden realizar más de una ruta.
  • Problema de enrutamiento de vehículos abiertos (OVRP): Los vehículos no están obligados a regresar al depósito.
  • Problema de enrutamiento de inventario (IRP): Los vehículos son responsables de satisfacer las demandas en cada punto de entrega [ 15 ].
  • Problema de enrutamiento de vehículos con múltiples depósitos (MDVRP): Existen múltiples depósitos desde los cuales los vehículos pueden comenzar y terminar. [ 16 ]
  • 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): Una variante en la que se utilizan vehículos eléctricos, lo que requiere consideraciones adicionales como la autonomía limitada de la batería y las decisiones de carga.

Varios proveedores de software han desarrollado productos para resolver diversos problemas de VRP. Existen numerosos artículos que ofrecen información más detallada sobre sus investigaciones y resultados.

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

Métodos de solución exactos

Existen tres enfoques principales para modelar el VRP utilizando programación lineal entera mixta (MILP): [ 6 ]

  1. Formulaciones de flujo vehicular : este método utiliza variables enteras asociadas a cada arco que contabilizan el número de veces que un vehículo recorre la arista. Generalmente se utiliza para problemas de enrutamiento vehicular básicos. Es adecuado para casos en los que el coste de la solución puede expresarse como la suma de los costes asociados a los arcos. Sin embargo, no es aplicable a muchas situaciones prácticas. [ 6 ]
  2. Formulaciones de flujo de mercancías : se asocian variables enteras adicionales a los arcos o aristas 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. [ 6 ]
  3. Particionamiento de conjuntos : este enfoque modela el VRP como un problema de cobertura de conjuntos , en el que las ubicaciones conforman el universo y el conjunto de todas las rutas factibles ( ciclos ) conforma la colección de conjuntos entre los que elegir. [ 18 ] El problema puede entonces modelarse utilizando un modelo de programación lineal para el problema de cobertura de conjuntos ponderado , donde el peso de una ruta se establece según su costo. Modelar el VRP de esta manera posiblemente resultará en un número exponencial de variables binarias en el programa lineal, ya que una está asociada con cada una de un número potencialmente exponencial de rutas factibles. [ 6 ]

Formulaciones de flujo vehicular

La formulación del TSP de Dantzig, Fulkerson y Johnson se extendió para crear las dos formulaciones de flujo vehicular de índice para el VRP.

min∑i∈V∑j∈Vdoijincógnitaij{\displaystyle {\text{min}}\sum _{i\in V}\sum _{j\in V}c_{ij}x_{ij}}

sujeto a

En esta formulacióndoij{\displaystyle c_{ij}}representa el costo de ir de nodo a nodoi{\displaystyle i}al nodoj{\displaystyle j},incógnitaij{\displaystyle x_{ij}}es una variable binaria que tiene valor1{\displaystyle 1}si el arco va desdei{\displaystyle i}aj{\displaystyle j}se considera parte de la solución y0{\displaystyle 0}de lo contrario,K{\displaystyle K}es el número de vehículos disponibles yr(S){\displaystyle r(S)}corresponde al número mínimo de vehículos necesarios para dar servicio al conjuntoS{\displaystyle S}También estamos asumiendo que0{\displaystyle 0}es el nodo del depósito.

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

Una restricción arbitraria entre las2|V|{\displaystyle 2|V|}Las restricciones están realmente implícitas en lo que queda.2|V|−1{\displaystyle 2|V|-1}para que pueda ser eliminado. Cada corte definido por un conjunto de clientesS{\displaystyle S}es atravesada por un número de arcos no menor que ⁠r(S){\displaystyle r(S)}( número mínimo de vehículos necesarios para dar servicio al conjuntoS{\displaystyle S}). [ 6 ]

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

∑i∈S∑j∈Sincógnitaij≤|S|−r(S){\displaystyle \sum _{i\in S}\sum _{j\in S}x_{ij}\leq |S|-r(S)}

lo cual impone que al menosr(S){\displaystyle r(S)}Los arcos salen de cada conjunto de clientes.S{\displaystyle S}. [ 6 ]

Los GCEC y CCC tienen un número exponencial de restricciones, por lo que resulta prácticamente imposible resolver la relajación lineal. Una posible solución consiste en considerar un subconjunto limitado de estas restricciones y añadir el resto si fuera 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 este tipo de restricciones (basados ​​en programación entera mixta ). [ 19 ]

Otro método diferente consiste en utilizar una familia de restricciones con cardinalidad polinomial , conocidas como restricciones MTZ. Fueron propuestas inicialmente para el TSP [ 20 ] y posteriormente extendidas por Christofides, Mingozzi y Toth [ 21 ] .

túj−túi≥dj−do(1−incógnitaij)      ∀i,j∈V∖{0},i≠j    calle di+dj≤do{\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}
0≤túi≤do−di      ∀i∈V∖{0}{\displaystyle 0\leq u_{i}\leq C-d_{i}~~~~~~\forall i\in V\backslash \{0\}}

dóndetúi, i∈V∖{0}{\displaystyle u_{i},~i\in V\backslash \{0\}}es una variable continua adicional que representa la carga que queda en el vehículo después de visitar al cliente.i{\displaystyle i}ydi{\displaystyle d_{i}}es la demanda del clientei{\displaystyle i}Estos imponen tanto los requisitos de conectividad como los de capacidad. Cuandoincógnitaij=0{\displaystyle x_{ij}=0}restricción entoncesi{\displaystyle i}no es vinculante' ya quetúi≤do{\displaystyle u_{i}\leq C}ytúj≥dj{\displaystyle u_{j}\geq d_{j}}mientrasincógnitaij=1{\displaystyle x_{ij}=1}ellos imponen esotúj≥túi+dj{\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 potencia se limita a estos problemas sencillos. Solo se pueden usar 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 recorre cada arco. Por lo tanto, no podemos usarlos para modelos más complejos donde el costo o la viabilidad dependen del orden de los clientes o de los vehículos utilizados. [ 6 ]

Enrutamiento óptimo manual frente a automático

Existen muchos métodos para resolver manualmente los problemas de enrutamiento de vehículos. Por ejemplo, el enrutamiento óptimo es un problema importante de eficiencia para las carretillas elevadoras en grandes almacenes. Algunos de los métodos manuales para determinar la ruta más eficiente son: Mayor espacio, Forma de S, Pasillo por pasillo, Combinado y Combinado +. Si bien el método Combinado + es el más complejo y, por lo tanto, el más difícil de usar para los operadores de carretillas elevadoras, es el método de enrutamiento más eficiente. Aun así, la diferencia porcentual entre el método de enrutamiento óptimo manual y la ruta óptima real fue, en promedio, del 13 %. [ 22 ] [ 23 ]

Soluciones aproximadas

Muchas aplicaciones del mundo real utilizan métodos computacionales que producen soluciones aproximadas, debido a la complejidad computacional del VRP. Estos métodos suelen basarse en heurísticas y pertenecen a una de dos clases: [ 6 ] : 109

  • Las heurísticas clásicas realizan un conjunto de operaciones relativamente sencillas para construir rápidamente una solución relativamente buena.
  • Metaheurísticas : clasifican y exploran las partes más prometedoras del espacio de soluciones.

Metaheurística

Debido a la dificultad de resolver de forma ó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 vecindario grande (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 el 1 % del óptimo para instancias de problemas que cuentan con cientos o miles de puntos de entrega. [ 24 ] Estos métodos también son más robustos en el sentido de que pueden adaptarse más fácilmente para abordar una variedad de restricciones secundarias. Por lo tanto, la aplicación de técnicas metaheurísticas suele ser la preferida para aplicaciones a gran escala con restricciones y conjuntos de decisiones complejos.

Muchos métodos se basan en la optimización. Estos métodos suelen constar de una fase de construcción rápida de una ruta inicial, por ejemplo, mediante un algoritmo voraz, seguida de una fase de mejora iterativa, en la que se buscan pequeñas modificaciones que mejoren la puntuación de la ruta. Se emplean mecanismos para evitar óptimos locales, por ejemplo, permitiendo movimientos que no mejoran la puntuación de la ruta a corto plazo. [ 25 ]

Métodos no metaheurísticos

Se han propuesto métodos adicionales para resolver el problema de enrutamiento de vehículos (VRP), algunos de los cuales dependen de las condiciones específicas del problema.

En el caso de un VRP con beneficio dependiente del tiempo, se han propuesto varios algoritmos para tener en cuenta la dimensión temporal. En uno de estos enfoques, se aplica la optimización local, donde el beneficio de cada paso incorpora el cambio en el beneficio potencial de los vértices que aún no se han visitado. [ 26 ]

Otro algoritmo, que no se basa en la optimización, comienza con una discretización del tiempo. El grafo bidimensional de vértices de la forma(incógnita,y){\displaystyle (x,y)}se reemplaza por un gráfico tridimensional de vértices de la forma(incógnita,y,t){\displaystyle (x,y,t)}, dóndet{\displaystyle t}representa un punto en el tiempo. A cada vértice del nuevo grafo se le asigna una ganancia correspondiente, y las aristas dirigidas entre vértices representan la posibilidad de viajar de una ubicación en un momento dado a otra ubicación en un momento diferente. Luego se aplica programación dinámica para identificar una ruta de alta puntuación en el grafo acíclico dirigido resultante. [ 27 ]

Véase también

Referencias

  1. ↑ Dantzig, George Bernard; Ramser, John Hubert (octubre de 1959). "El problema de la asignación de camiones" (PDF) . Management Science . 6 (1): 80– 91. doi : 10.1287/mnsc.6.1.80 .
  2. ↑ Fisher, Marshall L.; Jaikumar, Ramchandran (junio de 1981). "Una heurística de asignación generalizada para el enrutamiento de vehículos". Networks . 11 (2): 109– 124. doi : 10.1002/net.3230110205 .
  3. ↑ Shuster, Kenneth A.; Schur, Dennis A. (1974). Enrutamiento heurístico para vehículos de recolección de residuos sólidos . Agencia de Protección Ambiental de los Estados Unidos.
  4. ↑ Cordeau, Jean-François; Laporte, Gilbert (julio de 2007). "El problema del transporte a demanda: modelos y algoritmos". Annals of Operations Research . 153 (1): 29– 46. doi : 10.1007/s10479-007-0170-8 .
  5. ↑ Cappart, Quentin; Thomas, Charles; Schaus, Pierre; Rousseau, Louis-Martin (2018). «Un enfoque de programación con restricciones para resolver problemas de transporte de pacientes». Principios y práctica de la programación con restricciones . Notas de clase en informática. Vol. 11008. págs. 490–506 . doi : 10.1007/978-3-319-98334-9_32 . hdl : 2078.1/202079 . ISBN   978-3-319-98333-2.
  6. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Toth, P.; Vigo, D., eds. (2002). El problema de enrutamiento 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.
  7. ↑ Gaskell, TJ (septiembre de 1967). "Bases para la programación de flotas de vehículos". Journal of the Operational Research Society . 18 (3): 281– 295. doi : 10.1057/jors.1967.44 .
  8. ↑ 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.
  9. ↑ Archetti, C.; Speranza, MG; Vigo, D. (2014). Problemas de enrutamiento de vehículos con beneficios (2.ª ed.). Sociedad de Matemáticas Industriales y Aplicadas. 
  10. ↑ Chao, I-Ming; Golden, Bruce L; Wasil, Edward A (1996). "El problema de la orientación en equipo". European Journal of Operational Research . 88 (3): 464– 474. doi : 10.1016/0377-2217(94)00289-4 .
  11. ↑ Archetti, C.; Sperenza, G.; Vigo, D. (2014). "Problemas de enrutamiento de vehículos con beneficios". En Toth, P.; Vigo, D. (eds.). Enrutamiento de vehículos: problemas, métodos y aplicaciones (segunda ed.). pp. 273– 297. doi : 10.1137/1.9781611973594.ch10 .  
  12. ↑ Hammami, Farouk; Rekik, Monia; Coelho, Leandro C. (2020). "Una heurística híbrida adaptativa de búsqueda en vecindarios grandes para el problema de orientación en equipo". Computers & Operations Research . 123 105034. doi : 10.1016/j.cor.2020.105034 . S2CID 221134904 . 
  13. 1 2 Deif, I.; Bodin, LA (1984). Kidder, A. (ed.). "Extensión del algoritmo de Clarke y Wright para resolver el problema de enrutamiento de vehículos con transporte de retorno". Actas de la Conferencia del Babson College sobre el uso de software en la gestión del transporte y la logística . Babson Park, MA, EE. UU.: 75–96 .
  14. ↑ Golden, BL; Baker, E.; Alfaro, J.; Schaffer, J. (1985). Hammesfahr, R. (ed.). "El problema de enrutamiento de vehículos con transporte de retorno: dos enfoques". Actas de la Vigésimo Primera Reunión Anual de SE TIMS . Myrtle Beach, SC, EE. UU.: 90–92 .
  15. ^ 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 .
  16. ↑ Mahmud, Nafix; Haque, Md. Mokammel (febrero de 2019). Resolución del problema de enrutamiento de vehículos con múltiples depósitos (MDVRP) mediante algoritmo genético . Conferencia Internacional de Ingeniería Eléctrica, Informática y de Comunicaciones (ECCE) de 2019. doi : 10.1109/ECACE.2019.8679429 .
  17. ↑ 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 de Inteligencia Artificial .
  18. ↑ Balinski, ML; Quandt, RE (abril de 1964). "Sobre un programa entero para un problema de entrega". Operations Research . 12 (2): 300– 304. doi : 10.1287/opre.12.2.300 .
  19. ↑ 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 con capacidad" . Networks . 83. Networks: 197–209 . doi : 10.1002/net.22183 . S2CID 263321558 . 
  20. ↑ Miller, CE; Tucker, EW; Zemlin, RA (1960). "Formulaciones de programación entera y problemas del viajante" . J. ACM . 7 : 326–329 . doi : 10.1145/321043.321046 . S2CID 2984845 . 
  21. ↑ Christofides, N.; Mingozzi, A.; Toth, P. (1979). El problema de enrutamiento de vehículos . Chichester, Reino Unido: Wiley. pp. 315–338 . 
  22. ↑ "¿Por qué el enrutamiento óptimo manual en almacenes es tan ineficiente?" . Locatible.com . 26/09/2016. Archivado del original el 18/03/2017 . Consultado el 26/09/2016 .
  23. ↑ 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 .
  24. ↑ 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) . European Journal of Operational Research . 234 (3): 658– 673. doi : 10.1016/j.ejor.2013.09.045 . S2CID 21037953 . 
  25. ↑ Chao, IM; Golden, BL; Wasil, EA (1996). "Una heurística rápida y eficaz para el problema de orientación". European Journal of Operational Research . 88 (3): 475– 489.
  26. ↑ Erkut, E.; Zhang, J. (1996). "El problema de la recolección máxima con recompensas dependientes del tiempo". Naval Research Logistics (NRL) . 43 (5): 749– 763.
  27. ↑ Ma, Z.; Yin, K.; Liu, L.; Sukhatme, GS (septiembre de 2017). "Una representación espaciotemporal para el problema de orientación con beneficios variables en el tiempo". 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) . IEEE. págs. 6785–6792 . 

Lecturas adicionales

  • Oliveira, HCBde; Vasconcelos, GC (2008). "Un método de búsqueda híbrido para el problema de enrutamiento de vehículos con ventanas de tiempo". Annals of Operations Research . 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 variable en el tiempo». 43.ª Conferencia IEEE sobre Decisión y Control (CDC) de 2004 (IEEE Cat. No. 04CH37601) . Vol.  4. IEEE. pp. 3357–3363 . doi : 10.1109/CDC.2004.1429220 . ISBN  0-7803-8682-5ISSN 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 estocástico y dinámico de enrutamiento de vehículos en el plano euclidiano". Operations Research . 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: una revisión y síntesis" (PDF) . European Journal of Operational Research . 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 ].