Problema dial-a-ride

El problema dial-a-ride (en inglés, dial-a-ride problem) o DARP consiste en el diseño de rutas y horarios de vehículos de transporte con conductor (VTC) 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. Se distinguen dos modalidades: modo estático y modo dinámico.

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 obteniéndose 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 o scheduling

Dada una ruta $k=v_{0},...,v_{p},...,v_{q}$ donde $v_{0}$ y $v_{q}$ son los depósitos inicial y final y $v_{k}$ los intermedios ($0<k<q$), el problema del scheduling consiste en determinar el tiempo de salida y el tiempo en el que en cada vértice $v_{1},...,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:

$T_{k}$: la máxima duración de la ruta $k$.

$[e_{i},l_{i}]$: time window en el comienzo del servicio en el vértice $v_{i}$, entre $e_{i}$ y $l_{i}$.

$t_{ij}$: tiempo entre $v_{i}$ y $v_{j}$.

$d_{i}$: duración del servicio en $v_{i}$.

$A_{i}$: hora de llegada del vehículo a $v_{i}$.

$B_{i}$: hora de comienzo del servicio en $v_{i}$.

$D_{i}$ : hora de salida en $v_{i}$.

$W_{i}$ : tiempo de espera en $v_{i}$.

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

$B_{0}=e_{0}$.

$B_{i}=max(e_{i},A_{i})$.

$i=1,...,q$.

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. 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

$F_{i}=\min _{i\leq j\leq q}\{l_{i}-(B_{i}+\sum _{i\leq m<j}(t_{p,p+1}+d_{p}))\}$

Bibliografía

• Jean-François Cordeau, Gilbert Laporte. The Dial-a-Ride Problem (DARP): Variants, modeling issues and algorithms. 
• Julie Paquette, Jean-François Cordeau, Gilbert Laporte and Marta M. B. Pascoal. Combining Multicriteria Analysis and Tabu Search for Dial-a-Ride Problems. 

Enlaces externos

• Más información y ejemplos: Problema dial a ride.