El Problema del Ruteo Vehicular con Ventanas de Tiempo
El problema del transporte con ventanas de tiempo, VRPTW (por sus siglas en inglés, Vehicle Routing Problem with Time Windows), es un modelo que se aplica a cadena de suministros y transporte escolar. A continuación se presenta el modelo de programación lineal entera que representa al problema:
La función objetivo presentada en (1), representa el costo total, el cual se puede interpretar como el tiempo de viaje o distancia recorrida total. Se requiere encontrar la mínima distancia de recorrido total utilizando el menor número de vehículos. La variable xijk, toma valor de uno cuando el vehículo k atiende la ruta que va del cliente i al cliente j. El depósito se representa como i = 0 ó i = 1 + n. Las restricciones que se deben cumplir se presentan de (2) a (11).
Restricciones en (2), restringen la asignación de cada cliente a una sola ruta vehicular, esto es, el cliente es atendido por un sólo vehículo.
Restricciones de (3) a (5), dan las características de la ruta a seguir por cada vehículo k.
Restricciones en (3), definen el número de clientes j que son directamente alcanzables desde el depósito 0 utilizando el vehículo k, esto es, para cada vehículo k, sólo un cliente j se puede alcanzar partiendo del deposito.
Restricciones en (4), indica para cada unidad vehicular que, la diferencia del número de clientes i desde los cuales el cliente j es directamente alcanzable, con respecto del número de clientes i que son directamente alcanzables desde el cliente j, es cero, esto es, el número de vehículos que llegan a un cliente es el mismo número de vehículos que sale.
Restricciones en (5), indica para cada unidad vehicular que, el número de clientes i desde los cuales el deposito n + 1 es directamente alcanzable, es sólo uno, esto es, cada ruta vehicular tiene un sólo cliente que conecta al depósito.
Restricciones (6) a (8) y (9), garantizan la factibilidad de la secuencia con respecto a condiciones de tiempo y aspectos de capacidad respectivamente.
Restricciones en (6), indica para cada unidad vehicular y cada arco entre par de clientes, que la suma del tiempo inicial del servicio wik para el cliente i más su tiempo de servicio dado al cliente i más su tiempo de recorrido desde el cliente i al cliente j, menos el tiempo inicial del servicio wik es menor o igual que (1 - xijk ) = Mij, esto es, no se puede iniciar un servicio en j si el cliente i no ha sido atendido y el vehículo no ha llegado al cliente j. Aquí M es una constante muy grande.
Restricciones en (7), indican para cada unidad vehicular y cada cliente i, que el tiempo inicial del servicio wik debe iniciar dentro de la ventana de tiempo [ai, bi], donde ai es el tiempo más temprano posible que puede iniciar el servicio en el cliente i y bi es el tiempo más tarde posible que puede iniciar el servicio en el cliente i.
Restricciones en (8), indican para cada unidad vehicular y en el depósito 0, que el tiempo inicial del servicio wik debe iniciar dentro de la ventana de tiempo [E, L], esto es, el vehículo k, debe tener una salida posible más temprana desde el depósito y una llegada posible más tarde al depósito.
Restricciones en (9), indican que para todo vehículo k, la suma de las demandas de todos los clientes atendidos no debe exceder la capacidad del vehículo.
Restricciones (10), son restricciones de no negatividad de las variables x.
Restricciones (11), son restricciones que definen al modelo lineal como un modelo lineal entero binario.
Una instancia de este problema se puede representar por medio de un grafo disyuntivo el cual forma un clique. A continuación se presenta el grafo para el problema de 8 clientes:
En este grafo, cada vértice representa a un cliente. Cada cliente tiene una ventana de tiempo [t1,t2] en la cual puede recibir la mercancía transportada por el vehículo que lo atiende. El problema es minimizar el recorrido y así también minimizar el número de vehículos a utilizar. Se debe definir el número de rutas a utilizar (una ruta por vehículo), de tal manera que se cumplan con las restricciones de ventana de tiempo de cada cliente en el cual se debe de iniciar la atención del servicio. También se debe de cumplir con la restricción de capacidad de cada vehículo. Es requisito que cada cliente sea atendido por un solo vehículo.
Una solución a este problema, representada por un digrafo se presenta a continuación:
El grafo solución presenta en color rojo el tiempo de atención de servicio al cliente. Define tres rutas, esto es, utiliza tres vehículos para la repartición. También se presenta el orden de atención que cada vehículo da a sus clientes.
El grafo solución presenta claramente las restricciones (2), (3), (4), (5), (6) y (7) del modelo entero. Las instancias de prueba más conocidas para este tipo de problemas son los benchmarks de Solomon.
