# A Hybrid Adaptive Large Neighborhood Heuristic for a Real-Life Dial-a-Ride Problem
## 4 Experimental Results
### Results on Benchmark Instances  
The 20 DARPTW benchmark instances proposed by [PERSON] and [PERSON] [22] involve from \(n=24\) up to \(n=144\) customers. In Table 2, column \"Instance\" indicates the name of the instance, column \"\(n\)\" indicates the number of customers and column \"\(m\)\" indicates the number of vehicles used by the heuristics for the DARPTW proposed by [PERSON] [PERSON] [12] and [PERSON] et al. [23]. The column \"\(m\)\"' indicates the number of vehicles used by HG-DARP heuristic [11] and Hybrid-ALNS. The columns \"\(\text{HGDARP}(m)\)\" and \(\text{HGDARP}(m\)\") indicate the best known route durations with \(m\) and \(m\)\" obtained with HG-DARP. The columns \"\(\text{HALNS}(m)\)\" and \"\(\text{HALNS}(m^{*})\)\"indicate the best route duration with \(m\) and \(m^{*}\) obtained with Hybrid-ALNS. The columns \"\(Avg_{f}(m)\)\" and \"\(Avg_{f}(m^{*})\)\" indicate the average total route duration obtained with \(m\) and \(m^{*}\), respectively, over 10 randomly seeded runs of Hybrid-ALNS. The columns \"\(Avg_{t}(m)\)\" and \"\(Avg_{t}(m^{*})\)\" indicate the average execution  
\begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline
**Week** & \multicolumn{3}{c}{**Instance**} & \multicolumn{3}{c}{**ALNS**} & \multicolumn{3}{c}{**Hybrid-ALNS**} \\ \hline
1 & Day & \(n\) & \(m\) & \(f(X)\) & \(f(X^{*})\) & Avg & Time & \(f(X^{*})\) & Avg & Time & \(\Delta_{f}\)\% \\ \hline  & Mon & 25 & 7 & 1615.15 & 1578.18 & 1683.67 & 19 & 1561.42 & 1622.56 & 17 & \(-\)3.33 \\  & Tue & 24 & 7 & 1706.94 & 1629.88 & 1728.79 & 43 & 1586.15 & 1707.20 & 44 & \(-\)7.08 \\  & Wed & 24 & 7 & 1671.41 & 1587.15 & 1749.41 & 56 & 1574.33 & 1681.28 & 57 & \(-\)5.81 \\  & Thu & 37 & 9 & 2444.96 & 2286.73 & 2507.29 & 63 & 2213.38 & 2472.65 & 67 & \(-\)9.47 \\  & Fri & 19 & 4 & 1350.88 & 1291.68 & 1303.11 & 11 & 1291.68 & 1303.85 & 12 & \(-\)4.38 \\ \hline
2 & Day & \(n\) & \(m\) & \(f(X)\) & \(f(X^{*})\) & Avg & Time & \(f(X^{*})\) & Avg & Time & \(\Delta_{f}\)\% \\ \hline  & Mon & 24 & 4 & 1308.32 & 1170.07 & 1178.57 & 24 & 1164.79 & 1180.01 & 26 & \(-\)10.57 \\  & Tue & 26 & 5 & 1474.19 & 1461.20 & 1498.50 & 25 & 1451.65 & 1487.40 & 24 & \(-\)1.53 \\  & Wed & 28 & 6 & 1743.93 & 1734.75 & 1798.12 & 29 & 1710.61 & 1776.45 & 27 & \(-\)1.91 \\  & Thu & 40 & 10 & 2619.14 & 2619.03 & 2725.26 & 79 & 2518.58 & 2642.31 & 82 & \(-\)3.84 \\  & Fri & 15 & 5 & 1131.32 & 1079.74 & 1112.85 & 13 & 1079.74 & 1086.86 & 13 & \(-\)4.19 \\ \hline  & Avg & 26.2 & 6.4 & 1706.62 & 1643.84 & 1728.56 & 36.2 & 1615.23 & 1696.06 & 36.9 & \(-\)5.25 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Results on real-life instances.  
Figure 8: Vancouver and Region routing, Week 2, Monday.  
time, with \(m\) and \(m^{*}\), respectively, in seconds. The columns \"\(\Delta_{f}(m)\)%\" and \"\(\Delta_{f}(m^{*})\)%\" indicate the gaps \(\frac{HGDARP(m)-HALNS(m)}{HGDARP(m)}\) and \(\frac{HGDARP(m^{*})-HALNS(m^{*})}{HALNS(m^{*})}\) in percentage.  
Hybrid-ALNS improved the best total duration on all instances with respect to HG-DARP. For instance pr02, Hybrid-ALNS reaches a minimum total duration lower by more than 12% when four vehicles are used, and by more than 7.6 % when five vehicles are used. For an average computational time below 5 min (300 s), these results show that the proposed hybrid-ALNS algorithm improves by 3.91% to 5.03%, on average, the overall best solution values reached by HG-DARP.