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), t_{ij} and c_{ij} are
respectively the transportation time and the transportation cost to go directly from i to j. A time window [e_{i}; l_{i}] is associated to each node i; e_{i} is the earliest
starting time of service while l_{i} is the latest starting time of service. The service duration is sd_{i} and q_{i} is the number of customers to handle at node i. Thus, given a
transportation request i, q_{i} > 0 at its pickup node and q_{i+n} = - q_{i} < 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:

- (C1) The number of customers in the vehicle at each node cannot exceed the capacity;
- (C2) The beginning of service at any node i belongs to its time window;
- (C3) The riding time for a transportation request i cannot exceed the time limit;
- (C4) The trip duration for each vehicle is at most H.

The Stochastic DARP (SDARP) variant is similar to the static DARP, except that the transportation time t_{ij} is modeled as a positive random variable T_{ij}. 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, A_{i} is the arrival time, B_{i} is the beginning of service, D_{i} is the departure time. Nodes s_{i} and s_{i+1} are visited in sequence by the vehicle. Due to the stochastic nature of the travel time T_{ij}, several situations may happen at node s_{i+1} with respect to its time window.

instance | m | n | c(BKS) | r_(P_1) | F_(P_1) | r_(P_2) | F_(P_2) | r_(P_3) | F_(P_3) |
---|---|---|---|---|---|---|---|---|---|

pr01 | 3 | 24 | 190.02 | 74.8% | 86.4% | 66.8% | 25.90% | 66.8% | 50.00% |

pr02 | 5 | 48 | 301.34 | 76.8% | 85.4% | 48.6% | 28.40% | 48.6% | 72.60% |

pr03 | 7 | 72 | 532.00 | 4.8% | 0.1% | 3.1% | 0.00% | 3.1% | 0.00% |

pr04 | 9 | 96 | 570.25 | 14.3% | 0.3% | 9.4% | 0.00% | 9.4% | 0.10% |

pr05 | 11 | 120 | 626.93 | 13.1% | 0.7% | 5.0% | 0.00% | 5.0% | 0.70% |

pr06 | 13 | 144 | 785.26 | 3.9% | 0.0% | 3.0% | 0.00% | 3.0% | 0.00% |

pr07 | 4 | 36 | 291.71 | 21.9% | 14.7% | 14.7% | 0.30% | 14.7% | 7.90% |

pr08 | 6 | 72 | 487.84 | 8.9% | 0.2% | 5.9% | 0.00% | 5.9% | 0.20% |

pr09 | 8 | 108 | 658.31 | 9.4% | 0.4% | 4.3% | 0.00% | 4.3% | 0.30% |

pr10 | 10 | 144 | 851.82 | 1.3% | 0.0% | 0.6% | 0.00% | 0.6% | 0.00% |

pr11 | 3 | 24 | 164.46 | 63.2% | 61.0% | 57.6% | 36.10% | 57.6% | 69.00% |

pr12 | 5 | 48 | 295.66 | 32.0% | 5.8% | 25.0% | 0.20% | 25.0% | 3.70% |

pr13 | 7 | 72 | 484.83 | 32.5% | 16.5% | 19.3% | 0.80% | 19.3% | 6.20% |

pr14 | 9 | 96 | 529.33 | 59.3% | 64.6% | 35.6% | 9.20% | 35.6% | 27.80% |

pr15 | 11 | 120 | 577.29 | 37.9% | 72.0% | 17.9% | 1.90% | 17.9% | 25.10% |

pr16 | 13 | 144 | 730.67 | 16.2% | 11.1% | 7.5% | 0.20% | 7.5% | 3.40% |

pr17 | 4 | 36 | 248.21 | 26.8% | 1.6% | 23.8% | 0.30% | 23.8% | 0.90% |

pr18 | 6 | 72 | 458.73 | 62.2% | 72.9% | 43.8% | 17.00% | 43.8% | 54.40% |

pr19 | 8 | 108 | 593.49 | 5.8% | 0.0% | 3.5% | 0.00% | 3.5% | 0.10% |

pr20 | 10 | 144 | 785.68 | 3.8% | 0.0% | 2.8% | 0.00% | 2.8% | 0.10% |

avg. | 24.7% | 6.02% | 16.13% |

instance | c(s) | gap_(P_1) | r_(P_1) | F_(P_1) | time |
---|---|---|---|---|---|

pr01 | 200.48 | 5.50% | 100.0% | 100.0% | 0.25 |

pr02 | 307.11 | 1.92% | 100.0% | 100.0% | 1.25 |

pr03 | 587.96 | 10.52% | 100.0% | 100.0% | 2.30 |

pr04 | 643.75 | 12.89% | 100.0% | 100.0% | 7.37 |

pr05 | 744.92 | 18.82% | 100.0% | 100.0% | 12.07 |

pr06 | 979.78 | 24.77% | 100.0% | 100.0% | 21.92 |

pr07 | 306.69 | 5.13% | 100.0% | 100.0% | 0.47 |

pr08 | 573.65 | 17.59% | 100.0% | 100.0% | 2.68 |

pr09 | 774.53 | 17.65% | 99.7% | 100.0% | 11.25 |

pr10 | 1049.23 | 23.18% | 99.4% | 99.5% | 21.33 |

pr11 | 168.81 | 2.64% | 100.0% | 100.0% | 0.28 |

pr12 | 310.66 | 5.07% | 100.0% | 100.0% | 1.37 |

pr13 | 527.10 | 8.72% | 100.0% | 100.0% | 3.70 |

pr14 | 634.16 | 19.80% | 100.0% | 100.0% | 10.20 |

pr15 | 634.08 | 9.84% | 100.0% | 100.0% | 19.93 |

pr16 | 891.86 | 22.06% | 100.0% | 100.0% | 32.32 |

pr17 | 266.83 | 7.50% | 100.0% | 100.0% | 0.58 |

pr18 | 494.54 | 7.81% | 100.0% | 100.0% | 4.32 |

pr19 | 699.70 | 17.89% | 100.0% | 100.0% | 12.43 |

pr20 | 978.61 | 24.56% | 100.0% | 100.0% | 31.45 |

avg. | 13.19 | 100.0% | 100.0% | 9.87 |

: instance**name**: number of vehicles**m**: number of clients**n**: cost of the Best Known Solution using results from (Cordeau and Laporte 2003), (Parragh and Schmid 2013) and (Braekers et al. 2014)**c(BKS)**: cost of the Best Found Solution with ELS**c(S)**- : robustness criterion
- : robustness of the solution
- i>
**gap (%)**: relative optimality gap : CPU time in minutes (average on 5 runs)**time**