Problema Dial-a-Ride

Contenido de esta página:

Introducción
Modalidades
Itinerario
Ejemplo

Introducción

El dial-a-ride problem (DARP) consiste en el diseño de rutas y horarios de vehículos que especifican las paradas (llegadas y salidas) del vehículo entre el origen y el destino de n usuarios. El objetivo consiste en minimizar los costes de las rutas del vehículo de manera que el número de viajeros sea máximo, pero bajo ciertas restricciones.

Modalidades

Los servicios dial-a-ride deben operar según el modo estático (static mode) o dinámico (dynamic mode). En el static mode las paradas del vehículo se conocen de antemano mientras que en el dynamic mode las paradas se conocen a lo largo del día y las rutas del vehículo han de ir obteniendose a tiempo real. En la práctica los DARPs dinámicos puros raramente existen ya que el conjunto de las restricciones ya se conoce de antemano.

La mayoría de los estudios sobre el DARP asume la disponibilidad de una flota homogénea de m vehículos con base en un solo almacén. Aunque esta hipótesis refleja a menudo la realidad y puede servir como una base sólida para el diseño de modelos y algoritmos, es importante darse cuenta de que existen diferentes situaciones en la práctica. Puede haber varios depósitos, sobre todo en amplias zonas geográficas y la flota, a veces, es heterogénea.

Itinerario (scheduling)

Dada una ruta k = ( v₀, …, v_i,…,v_q) donde v₀ y v_q son el depósito, el problema de scheduling consiste en determinar el tiempo de salida y el tiempo en el que en cada vértice v₁,…,v_q-1 debería salir de nuevo el vehículo de manera que los tiempos en pantalla u horario (time window) se cumplan y la duración de la ruta sea mínima.

Usaremos la siguiente notación:

Notemos que:

1), es decir, la hora de salida del vehículo en v_i ha de ser mayor que la hora esperada de salida y la de llegada del vehículo a v_i

2), ya que la hora real de salida del vehículo en v_i ha de ser la hora del comienzo del servicio en v_i más el tiempo empleado en la parada v_i antes de partir.

3) , si se da la desigualdad significa que el comienzo del servicio en v_i se produce con retraso, puesto que la hora esperada de salida es l_i.

Llegar a v_i antes que e_i está permitido y el tiempo de espera en ese vértice es W_i = B_i - A_i , es decir, la hora de salida en v_i menos la hora de llegada a v_i.

Si el problema de scheduling es posible, una solución, la evidente y más sencilla, es la siguiente:

Dicho en palabras: que el primer servicio comience a la hora prevista y que el servicio en v_i comience a la hora prevista ( e_i) si el vehículo ya ha llegado al vértice v_i. Si todavía no ha llegado, que salga al hacerlo.

Pero reducir la duración de la ruta y disminuir el tiempo de espera puede ser ventajoso para retrasar la salida del depósito y el de los vértices. Para ello, en cada v_i debemos calcular el plazo máximo que debe pasar antes de que el servicio comience, F_i, para que el tiempo del time window no sea violado. Se calcula como sigue, (1) (las fórmulas se explican más abajo):

Teniendo en cuenta que, (2):

Podemos reescribir (1) como sigue, (3):

Veamos por qué (1) ha de tener esa expresión:

Recordemos que F_i es el tiempo máximo que puede retrasarse el vehículo en el vértice v_i para que no se violen los tiempos del time window.

En el interior del sumatorio tenemos el tiempo en de duración de un vértice al siguiente y más la duración del tiempo de servicio en éste primero. Es decir, el tiempo empleado desde la llegada a un vértice hasta la llegada al siguiente. En el sumatorio sumamos estos tiempos entre los vértices v_i y v_j, es decir, el tiempo empleado desde la llegada al vértice v_i a la llegada al vértice v_j.

Al sumatorio le sumamos B_i, la hora del comienzo del servicio en v_i. Por tanto, la cantidad obtenida es la hora de llegada al vértice v_j.

A l_j, hora máxima de salida de v_j, le restamos la cantidad anterior. Es decir, calculamos el tiempo entre la hora de llegada y la hora de salida.

Si esto lo hacemos para i menor o igual que j menor o igual que q y buscamos el mínimo tenemos el tiempo máximo de retraso en v_i para que se cumpla el time window.

La expresión (2) es fácil de comprender y la (3) tercera se obtiene de (1) y (2).

La hora óptima de salida del vehículo del depósito puede ser determinada por el cálculo de F₀.

Ejemplo sencillo de DARP

Consideremos los vértices v₁ y v₂ con l₁ = 0, l₂ = 20, d₁ = 2, t_1,2 = 12 expresados en minutos.

Un diagrama del problema sería

Como el vehículo llega en el minuto 0 (como máximo) a v₁ podemos reducir l₂ en 6 minutos ya que: el vehículo saldrá en el minuto 2 (como máximo) de v₁ y llegará en el minuto l₁ + d₁ + t_1,2 = 0 + 2 + 12 = 14 a v₂ (como máximo), por tanto, podemos evitar los 6 minutos entre la llegada del vehículo a v₂ y su salida de v₂.

O bien, si dejamos fijos los datos, podemos calcular el F₁, esto es, el tiempo máximo de retraso del vehículo en el vértice v₁:

Hemos utilizado la expresión (1) teniendo en cuenta que i = 1, q = 2 y B₁ = l₁ (la última igualdad la hemos supuesto ya que no se nos indica ningún B₁).

Referencias

The Dial-a-Ride Problem (DARP): Variants, modeling issues and algorithms, Jean-François Cordeau, Gilbert Laporte.

Combining Multicriteria Analysis and Tabu Search for Dial-a-Ride Problems, Julie Paquette, Jean-François Cordeau, Gilbert Laporte and Marta M. B. Pascoal.

Matesfacil.com by J. Llopis is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.