Stochastic DARP

home

problem description

The static DARP is defined on a complete digraph G=(V,A) corresponding to a weighted directed transportation network. A set of n transportation requests, known in advance, has to be handled by a homogeneous fleet of K vehicles. The vehicles capacity is Q. The set of nodes is V={0,1,...,2n,2n+1} with 1,...,n the pickup nodes and n+1,...,2n the delivery nodes. Two copies 0 and 2n+1 of the depot model respectively the beginning and the end of the trips. Given an arc (i,j), tij and cij are respectively the transportation time and the transportation cost to go directly from i to j. A time window [ei; li] is associated to each node i; ei is the earliest starting time of service while li is the latest starting time of service. The service duration is sdi and qi is the number of customers to handle at node i. Thus, given a transportation request i, qi > 0 at its pickup node and qi+n = - qi < 0 at its delivery node.

Each customer must be picked up at his pickup node and dropped off at his delivery node. No transfer is allowed. Each trip starts and ends at the depot. The capacity constraint of any vehicle must hold at any node of the trip and the beginning of service must fit the time windows at any visited node, including nodes 0 and 2n+1. A waiting delay is allowed before the beginning of service at any node. This can be used to satisfy the time window constraints, the riding time constraints or the driving time constraints. No waiting delay is allowed at the node after the service time and the vehicle leaves the node just after finishing its service. The objective function is to minimize the total travel distance. A solution must satisfy the following constraints:

The Stochastic DARP (SDARP) variant is similar to the static DARP, except that the transportation time tij is modeled as a positive random variable Tij. The SDARP is NP-hard as it generalizes the DARP.


The folowing picture illustrates the connections between the transportation times and the time windows. Given a node i, Ai is the arrival time, Bi is the beginning of service, Di is the departure time. Nodes si and si+1 are visited in sequence by the vehicle. Due to the stochastic nature of the travel time Tij, several situations may happen at node si+1 with respect to its time window.


stochastic DARP picture Fig. 1: stochastic transportation times and time windows constraints.

instances

Two sets of DARP instances have been proposed by (Cordeau and Laporte, 2003) and (Ropke and Pisinger, 2007). They can be downloaded here and here. The data are also available online here.

results

Table 1 : Robustness of best known solution (BKS)
instancemnc(BKS)r_(P_1)F_(P_1)r_(P_2)F_(P_2)r_(P_3)F_(P_3)
pr01324190.0274.8%86.4%66.8%25.90%66.8%50.00%
pr02548301.3476.8%85.4%48.6%28.40%48.6%72.60%
pr03772532.004.8%0.1%3.1%0.00%3.1%0.00%
pr04996570.2514.3%0.3%9.4%0.00%9.4%0.10%
pr0511120626.9313.1%0.7%5.0%0.00%5.0%0.70%
pr0613144785.263.9%0.0%3.0%0.00%3.0%0.00%
pr07436291.7121.9%14.7%14.7%0.30%14.7%7.90%
pr08672487.848.9%0.2%5.9%0.00%5.9%0.20%
pr098108658.319.4%0.4%4.3%0.00%4.3%0.30%
pr1010144851.821.3%0.0%0.6%0.00%0.6%0.00%
pr11324164.4663.2%61.0%57.6%36.10%57.6%69.00%
pr12548295.6632.0%5.8%25.0%0.20%25.0%3.70%
pr13772484.8332.5%16.5%19.3%0.80%19.3%6.20%
pr14996529.3359.3%64.6%35.6%9.20%35.6%27.80%
pr1511120577.2937.9%72.0%17.9%1.90%17.9%25.10%
pr1613144730.6716.2%11.1%7.5%0.20%7.5%3.40%
pr17436248.2126.8%1.6%23.8%0.30%23.8%0.90%
pr18672458.7362.2%72.9%43.8%17.00%43.8%54.40%
pr198108593.495.8%0.0%3.5%0.00%3.5%0.10%
pr2010144785.683.8%0.0%2.8%0.00%2.8%0.10%
avg. 24.7%6.02%16.13%


Table 2. Robustness of solutions obtained by our ELS metaheuristic
instancec(s)gap_(P_1)r_(P_1)F_(P_1)time
pr01200.485.50%100.0%100.0%0.25
pr02307.111.92%100.0%100.0%1.25
pr03587.9610.52%100.0%100.0%2.30
pr04643.7512.89%100.0%100.0%7.37
pr05744.9218.82%100.0%100.0%12.07
pr06979.7824.77%100.0%100.0%21.92
pr07306.695.13%100.0%100.0%0.47
pr08573.6517.59%100.0%100.0%2.68
pr09774.5317.65%99.7%100.0%11.25
pr101049.2323.18%99.4%99.5%21.33
pr11168.812.64%100.0%100.0%0.28
pr12310.665.07%100.0%100.0%1.37
pr13527.108.72%100.0%100.0%3.70
pr14634.1619.80%100.0%100.0%10.20
pr15634.089.84%100.0%100.0%19.93
pr16891.8622.06%100.0%100.0%32.32
pr17266.837.50%100.0%100.0%0.58
pr18494.547.81%100.0%100.0%4.32
pr19699.7017.89%100.0%100.0%12.43
pr20978.6124.56%100.0%100.0%31.45
avg.13.19100.0%100.0%9.87
computer: Core i7-3770 CPU with 3.40Ghz

meaning:

references

  • Cordeau J-F and Laporte G. A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Research Part B: Methodological, 37(6): 579-594, 2003.
  • Parragh SN and Schmidt V. Hybrid column generation and large neighborhood search for the dial-a-ride problem. Computers & Operations Research, 40(): 490–497, 2013.
  • Braekers K, Caris A. and Janssens GK. Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots. Transportation Research Part B: Methodological, 67(): 166-186, 2014.
  • Schilde M, Doerner KF and Hartl RF. Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem. European Journal of Operational Research, 238 (1): 18-30, 2014.
  • Tas D, Gendreau M, Dellaert NP, van Woensel T and de Kok AG. Vehicle routing with soft time windows and stochastic travel times: A column generation and branch-and-price solution approach. European Journal of Operational Research, 236 (3): 789-799, 2014.