# A Hybrid Adaptive Large Neighborhood Heuristic for a Real-Life Dial-a-Ride Problem
## 4 Experimental Results
### Results on Real-Life Instances  
The real-life instances are collected on 10 consecutive days, representing two consecutive weeks, in the Canadian city of Vancouver, its region and suburbs: Richmond, Surrey, Coquitlam, North Vancouver, etc. The physical addresses of all pick-up and drop points were first geocoded, i.e., converted to longitude and latitude coordinates. Based on Google's map and distance API, these geocodes were used to compute the travel times and distances between each pair of nodes in the given day's graph. The test instances involve from 30 stops up to 80 stops. They detail the demand for impaired people and elderly transportation by a private company. In these instances, the first \(n\) stops represent the pick-ups and the last \(n\) stops represent their corresponding drops. The demand is around 25 requests per business day. It peaks on Thursdays and drops on Fridays. The company does not take requests for weekends. The company has 12 medium size shuttle buses equipped for elderly and reduced mobility passengers. The maximum capacity of each bus is of eight passengers at the same time, as a large passage corridor between the seats and an empty storage space for wheel chairs and other luggage are needed. Each route has a maximum duration of 360 min, as any driver is not supposed to spend more than six consecutive hours on duty. The time windows for the customers are very large for the pick-ups, but tight for their corresponding drops, with exactly one hour span. For example, a customer could be picked-up at any time between 7:00 am and 7:00 pm, but needs to be dropped between 10:00 a.m. and 11:00 a.m. at his destination, as he may have a medical appointment. If a customer needs to be picked-up again and taken home, it is treated as a new request: a new pick-up with a new drop. Each customer's maximum transit time is of 90 min, as some passengers need to be picked-up quite far from their destination. The service time at each stop is of 5 to 10 min. The company uses a transportation optimization software for its routing activity. These instances were provided by BeTeLL, a transportation optimization and research oriented company based in Montreal, QC, Canada.  
In Table 1, the column \"Day\" indicates the day of the instance. The column \"\(n\)\" indicates the number of customers. The column \"\(m\)\" indicates the number of vehicles used. The column \"\(f(X)\)\" indicates the total duration in minutes of the routes scheduled by the company's current optimization software. The columns \"\(f(X^{*})\)\", \"Avg\" and \"Time\" indicate the best and average solution values, and the average execution times (in seconds) obtained by ALNS (without GA) and Hybrid-ALNS, respectively. The column \"\(\Delta_{f}\)%\" indicates the gap \(\frac{f(X)-f(X^{*})}{f(X^{*})}\) in percentage between the best solution obtained with Hybrid-ALNS and the company's overall route duration.  
The results in Table 1 show that our Hybrid-ALNS heuristic was able to save about 5.25% on average routing durations compared to the business solution currently used by the company. These results were obtained in less than 37 s in average, which could give the company the required flexibility to adapt to re-routing requests or deal with dynamic ones in the future. The results in Table 1 also show that Hybrid-ALNS outperforms ALNS (without GA). Hybrid-ALNS provides not only better solution quality, but also better general results.  
Figure 8 illustrates the routing optimization solution obtained on week 2 Monday's solution using BeTeLL's routing visualizer.