# A Hybrid Adaptive Large Neighborhood Heuristic for a Real-Life Dial-a-Ride Problem
## 1 Introduction  
The dial-a-ride problem (DARP) is a subfamily of Vehicle Routing Problems (VRPs) where customers' needs are met considering a fleet of heterogeneous vehicles. The most common application happens in senior or impaired people door-to-door transportation. The DARP's goal is to set a vehicle routing schedule with minimum cost meeting all requests and satisfying a number of conditions. These conditions include maximum vehicle capacity, maximum route duration and maximum customer transit time. Cases where requests are known at the time of planning define static DARP, while cases where some requests are received during routing operations define dynamic DARP. In addition, cases where servicing operations at stops start within pre-defined time windows are called DARP with time windows (DARPTW). Solving the DARPTW requires the application of approximate algorithms such as adaptive large neighborhood search (ALNS) and genetic algorithms (GA).  
[PERSON] and [PERSON] [1] proposed ALNS as an extension of the Large Neighborhood Search [2] for the Rich Pickup and Delivery Problem with Time Windows (RPDPTW). Its general principal is to remove requests from the routing solution and reinsert them at potentially more profitable positions. This is performed repeatedly with the help of adaptive destroy and repair operators. While the Large Neighborhood Search (LNS) heuristic uses a single destroy and repair operator, ALNS uses many of them. At each iteration, one or more specific destroy and repair operators are applied. The selection is based on the continuous updating of the operators' success rates. While most local search heuristics can only apply very small modifications to a given solution, ALNS covers a large search space, which defines the neighborhood of the current solution. Within one single iteration, ALNS can modify up to 30 to 40% of a solution. This revealed to be efficient with tightly constrained problems like the RPDPTW.  
The common principles of GA are inspired from population genetics [3]. The generation of new individuals follows the general evolutionary scheme: selection, recombination and mutation. The selection phase is usually based on one or more characteristics that depend on the problem. The recombination phase selects parents' genes that may be inherited or not by their offspring. The mutation phase changes the offspring to maintain genetic diversity. Mutation happens with a marginal probability. [PERSON] et al. [4] detailed local search operators adapted for the DARP within a multi-objective evolutionary hybrid heuristic applied to real-life instances. [PERSON] et al. [5] described a GA for the heterogeneous DARP (H-DARP). They proposed efficient operators adapted to the H-DARP: construction, crossover and local search operators.  
Based on the strengths of ALNS and GA, this paper proposes a hybrid-ALNS heuristic for a real-life DARPTW. While every known heuristic contains both diversification and intensification elements, one can observe that single-solution based methods give more importance to intensification, and population-based methods give more importance to diversification. Through its main three features, the hybrid-ALNS heuristic offers a fair compromise between diversification and intensification search strategies. First, it keeps track not only of the current and best solutions, but also of a pool of best solutions which constitutes the genetic crossovers' input. Second, it enhances standard ALNS with newly customized operators. Third, it applies genetic crossover operators that diversify the solution neighborhood and help ALNS recover from suboptimal valleys.  
Section 2 details the DARPTW and compiles a number of references on Neighborhood Search-based and Genetic Algorithm-based heuristics proposed in the DARP context. Section 3 details the proposed new algorithm and presents its phases. Section 4 compiles the experimental results on real-life and benchmark instances. Finally, Section 5 summarizes the paper.