Ruteo de vehículos con ventana de tiempo y visita sincronizada

El artículo sucumbió a un borrado rápido. Ver el registro de borrado en Wikipedia

El problema puede verse como una extensión del Problema de generación de rutas para vehículos con ventanas de tiempo (VRPTW) con la adición de requisitos de sincronización. En un VRPTW estándar, las rutas son independientes, en el sentido de que una modificación a una ruta dada no tiene impacto en las otras rutas. Este no es el caso del VRPTW-Syn porque las rutas son interdependientes debido a los requisitos de sincronización en ciertas ubicaciones de los cliente o nodos.

El VRPTW-Syn dispone de dos tipos diferentes de vehículos: los vehículos regulares y especiales. Los vehículos regulares entregan mercancías a los clientes y tienen una capacidad limitada. Los vehículos especiales no entregan mercancías sino que prestan un servicio relacionado con las mercancías entregadas por los vehículos regulares. El conjunto de clientes se divide en dos subconjuntos: clientes habituales (también denominados clientes regulares) visitados solo por vehículos regulares y clientes especiales visitados tanto por un vehículo regular como por uno especial. Un cliente regular está representado por un solo vértice en la red de transporte, mientras que un cliente especial está representado por dos vértices, uno para la entrega por el vehículo regular y otro para el servicio prestado por el vehículo especial.

Explicación del problema

Un vértice regular tiene una demanda y una ventana de tiempo, mientras que un vértice especial tiene solo una ventana de tiempo, que se define en relación con el tiempo de entrega del vehículo regular. Más precisamente, si t es el tiempo de entrega en el vértice regular de un cliente especial, entonces el servicio del vértice especial debe comenzar dentro de la ventana de tiempo [t- δ, t+ γ]. donde δ y γ son parámetros, los cuales se explicarán a continuación. Se pueden representar diferentes requisitos de sincronización con diferentes valores de δ y γ. Por ejemplo, si el servicio del vehículo especial no puede comenzar antes de la entrega, entonces el límite inferior de la ventana de tiempo del vértice especial se establece en t (es decir, δ=0); Si el servicio del vehículo especial no puede comenzar antes del final de la entrega, entonces el límite inferior de la ventana de tiempo del vértice especial se establece en t más el tiempo de servicio del vehículo regular (es decir, δ se establece en menos del tiempo de servicio del vehículo regular), etc.

El problema entonces consiste en construir rutas para los dos tipos de vehículos de manera que:

1. Cada ruta comienza y termina en un solo depósito.
2. A cada cliente habitual (también denominado cliente regular) se le atiende en la ruta exactamente por un vehículo regular.
3. Cada cliente especial es atendido en la ruta exactamente por un vehículo regular y un vehículo especial.
4. La demanda total en la ruta de un vehículo regular no puede exceder su capacidad.
5. Un vehículo regular debe iniciar su entrega en un cliente regular o especial dentro de la ventana de tiempo del vértice regular correspondiente.
6. Un vehículo especial debe iniciar su servicio en un cliente especial dentro de la ventana de tiempo del vértice especial correspondiente, que se define con relación al tiempo de entrega del vehículo regular en el vértice regular.
7. Un vehículo regular puede esperar hasta el límite inferior de la ventana de tiempo del vértice regular si llega antes.
8. Un vehículo especial puede esperar hasta el límite inferior de la ventana de tiempo del vértice especial si llega antes
9. El objetivo es minimizar la distancia total recorrida por todos los vehículos (regulares y especiales).

Ejemplo del problema

Considerando un pequeño ejemplo, se dispone de dos vehículos regulares {<math>v_r^1, v_r^2 </math>}, un vehículo especial {<math>v_1^s</math>},un único depósito 0 y 5 clientes {1, 2, 3, 4, 5}, dos de los cuales son clientes especiales {1, 2}. En la Figura 11, el vértice 0 (cuadrado azul) es el depósito, los vértices 1 al 5 corresponden a vértices regulares, mientras que los vértices 6 y 7 corresponden a los vértices especiales de los clientes 1 y 2. Por lo tanto, los pares de vértices (1,6) y (2,7) requieren sincronización. En la Figura ( Ejemplo del VRPTW-Syn), cada par se agrega en un solo círculo gris. Sin pérdida de generalidad de tiempo de los vehículos especiales con respecto a los regulares, se asume que el servicio o tiempo de permanencia es igual, es decir δ=γ=0 para cada vértice especial, es decir, llegan a la misma hora.

Ejemplo del VRPTW-Syn

En la solución que se muestra, los arcos sólidos se utilizan para representar las rutas de los vehículos regulares y los arcos discontinuos para la ruta del vehículo especial. Cada arco está etiquetado con su tiempo de viaje y cada vértice i está etiquetado con el tiempo de llegada del vehículo t_i . El tiempo de regreso de cada vehículo al depósito, denotado t₀ , también se indica en el último arco de la ruta correspondiente. El plan de enrutamiento es el siguiente:

• <math>v_r^1=0,5,1,0 </math>
• <math>v_r^2=0,2,3,4,0 </math>
• <math>v_1^s=0,7,6,0 </math>
• <math>t_1=8, t_2=3, t_3=8, t_4=12, t_5=4, t_6=8 </math>

Para comprender mejor los requisitos de sincronización, se sigue la ruta del vehículo regular <math>v_r^1 </math>. Su ruta comienza con el cliente habitual 5, en donde comienza la entrega en t₅=4. Después de dedicar 1 unidad de tiempo a servir al cliente, se necesitan 3 unidades de tiempo más para llegar al cliente especial 1 donde también se necesita un vehículo especial. El vehículo especial llega al mismo tiempo t₁=t₆=8. Por lo tanto, vehículo está perfectamente sincronizado con el vehículo especial . Entonces, el vehículo  sale del cliente especial 1 a la hora 9 para el depósito. Finalmente, llega al depósito a la hora 13. Tenga en cuenta que el vehículo especial ya está sincronizado con el vehículo normal en el cliente especial 2 a la vez t₂=t₇=3.

Modelo analítico

Sea G=(N,A) un grafo completo y dirigido con conjunto de vértices <math>N=V_r \cup V_s \cup V_r^+ \cup V_s^+ \cup V_r^- \cup V_s^-</math>, donde <math>V_r</math> y <math>V_s</math> son los conjuntos de vértices regulares y especiales  respectivamente, con <math>V_r \cup V_s =V</math>. Un vértice (V) está asociado con cada cliente regular (<math>V_r </math>) y dos vértices con cada cliente especial (<math>V_s</math>), es decir, un vértice regular en <math>V_r </math> y un vértice especial en <math>V_s</math>. También, <math>V_r^+ </math> y <math>V_s^+ </math> contienen varias copias del depósito, una para el inicio y el final de la ruta de cada vehículo regular. Es decir, <math>\mid V_r^+ \mid</math> y <math>\mid V_r^- \mid</math> son ambos iguales al número de vehículos regulares. Similar a <math>V_s^+</math> y <math>V_s^-</math> contienen varias copias del depósito para el inicio y el final de la ruta de cada vehículo especial. De nuevo, <math>\mid V_s^+ \mid</math> y <math>\mid V_s^- \mid</math> son ambos iguales al número de vehículos especiales. También se define <math>V_r^- \cup V_s^- =V</math>. Finalmente, con cada arco ( i, j ) <math>\in</math> A se asocia una distancia no negativa d_ij y un tiempo de viaje t_ij. La notación utilizada para el modelo VRPTW-Syn se resume en la siguiente Tabla:

Símbolo	Descripción
dij	Distancia entre los vértices i y j, i ,  j  ∈  N, i  ≠  j
tij	Tiempo de viaje entre los vértices i y j, i ,  j  ∈  N, i  ≠  j
qi	Demanda del vértice i  ∈  V
di	Servicio o tiempo de permanencia en el vértice i ∈ V.
ai	Límite inferior de la ventana de tiempo en el vértice regular i  ∈  Vr
bi	Límite superior de la ventana de tiempo en el vértice regular i  ∈  Vr
δi	Decremento para derivar el límite inferior de la ventana de tiempo en el vértice especial i  ∈  Vs
γi	Incremento para derivar el límite superior de la ventana de tiempo en el vértice especial i  ∈  Vs
ri	Vértice regular asociado con vértice especial i  ∈  Vs
Vr	Conjunto de vértices regulares
Vs	Conjunto de vértices especiales
V	conjunto de vértices regulares y especiales
Kr	Conjunto de vehículos regulares
Ks	Conjunto de vehículos especiales
K	Conjunto de vehículos especiales
Q	Capacidad de cada vehículo regular k  ∈  Kr

Variables

1. <math>s_i:</math> Sucesor de vértice i <math>\in</math> <math>V \cup V^+ </math>
2. <math>K_i:</math>Vehículo que visita el vértice i <math>\in</math> N
3. <math>t_i:</math> Hora de inicio del servicio en el vértice i <math>\in</math> N
4. <math>l_i:</math> Carga del vehículo después de servir el vértice i <math>\in</math> <math>V_r \cup V_r^+ \cup V_r^- </math>

Objetivo

5. <math>Minimizar=\sum_{i \in V \in V^+} d_{i,s_i} </math>

Restricciones

6. <math>AllDiffenet(s_{i: ,i \in V \cup V^+}) </math>

7. <math>NoSubTour(s_{i: ,i \in V \cup V^+}) </math>

8. <math>i \in V_r \cup V_r^+ \Longrightarrow s_i \in V_r \cup V_r^- </math>

9. <math>i \in V_s \cup V_s^+ \Longrightarrow s_i \in V_s \cup V_s^- </math>

10. <math>i \in V_r \cup V_r^+ \cup V_r^- \Longrightarrow k_i \in K_r </math>

11. <math>i \in V_s \cup V_s^+ \cup V_s^- \Longrightarrow k_i \in K_s </math>

12. <math>s_i=j \Longrightarrow k_j= k_i, i \in V \cup V^+ </math>

Limitación de capacidad

13. <math>l_i=0, i \in V^+ </math>

14. <math>l_i=Q, i \in V_r \cup V_r^+ </math>

15. <math>s_i=j \Longrightarrow l_i=l_j, i \in V_r \cup V_r^+ </math>

Limitaciones de sincronización y ventana de tiempo

16. <math>t_i=0, i \in V^+ </math>

17. <math>a_i \leqslant t_i \leqslant b_i , i \in V_r </math>

18. <math>t_{r_i}-\delta_i \leqslant t_i \leqslant t_{r_i}+\gamma_i , i \in V_s </math>

19. <math>s_i=j \Longrightarrow t_j \geq t_i + d_i + t_{i,j}, i \in V \cup V^+ </math>

Explicación de las ecuaciones

En una solución cada vértice debe tener exactamente un predecesor y un sucesor. La naturaleza de las variables <math>s_i </math>es tal que cualquier vértice i solo puede tener un sucesor, pero también se debe asegurarnos de que solo tenga un predecesor. Para ello, debe estar prohibido que dos vértices diferentes tengan el mismo sucesor, lo que corresponde a la ecuación (6) llamado AllDifferent. La restricción (7) prohíbe los subtours, Las restricciones (8), (9), (10) y (11) definen las variables y  para vértices regulares y especiales. Restricción (12) establece que un vértice y su sucesor deben ser atendidos por el mismo vehículo. Las restricciones (13), (14) y (15) imponen restricciones de carga y capacidad. Sin pérdida de generalidad, se supone que los vehículos inician sus rutas en el depósito en el momento 0 a través de la restricción (16) . La ecuación (17) impone restricciones de ventana de tiempo en vértices regulares. Los requisitos de sincronización entre vehículos regulares y especiales en vértices especiales se establecen en la restricción (18). La restricción (19) impone la coherencia de cada horario de ruta. Finalmente, la función objetivo (5) minimiza la distancia total recorrida por todos los vehículos.

Algoritmos aplicados para resolver el problema

Pecin et al., (2017) empiezan aclarando que el termino ventana de tiempo es aplicable para que el vehículo llegue en dicho intervalo de tiempo, pero puede salirse del horario pagando una penalización, la cual es un costo adicional para costo de transporte. Para solucionarlo introducen dos mejoras al algoritmo branch-price-and-cut (BPC). Primero desarrollan unas desigualdades al subconjunto filas de la memoria limitada, representando la memoria como un arco de subconjuntos en vez de subconjuntos de nodos. Segundo, de las desigualdades elementales introducida por el autor del método (Balas en 1977), Pecin et al., (2017) lo derivan a una familia de desigualdades que lo dominan. Dichas mejoras están integradas en un algoritmo branch-price-and-cut (BPC) exacto que incluye funciones de vanguardia como el etiquetado bidireccional, relajación decremental del espacio de estados, límites de finalización, fijación variable y enumeración de rutas. Los resultados computacionales muestran que estas mejoras son particularmente efectivas para las instancias más difíciles y que el algoritmo BPC puede resolver las 56 instancias con 100 clientes y 51 de 60 instancias de Gehring & Homberger, (2001) con 200 clientes.

Bianchessi et al., (2019) resolvieron el clásico problema de ruteo de vehículos con ventana de tiempo con la suma de sus respectivas restricciones de entregas divididas y especificaciones del cliente o nodo, usaron el diseño extendido del algoritmo “branch-and-cut”, mostrando que la división de entrega permite mayor grados de libertad, pues admite más opciones en las rutas, realizando las siguientes recomendaciones: (a) las entregas divididas dan buenos resultados, considerándola independiente del objetivo. (b) aunque un número de visitas mayor al clásico problema de ruteo de vehículo se cambie, esto puede repercutir económicamente al disminuir costo por penalización y reducción de rutas y (c) dividir las visitas también permite una mejor distribución de los bienes, logrando reducir pérdidas de tiempo también.