# A Hybrid Adaptive Large Neighborhood Heuristic for a Real-Life Dial-a-Ride Problem
## 3 Hybrid ALNS DARP
### Repair and Destroy Iterative Loop  
The iterative loop improves the initial solution \(X\) through repeated and alternated intensification and diversification search operations. For intensification, it applies a set of repair and destroy operators to \(X\) to obtain a solution \(X^{\prime}\). Two cases may rise: the repair and destroy is accepted or rejected. In the first case, the focal point of the search is changed to \(X^{\prime}\) setting the current solution \(X=X^{\prime}\). Furthermore, when this new local minimum \(X^{\prime}\) improves \(X^{*}\), \(X^{*}\) and \(f(X^{*})\) are updated. In the second case, the counter of non-improving trials is incremented. For diversification, when the counter reaches a preset number of iterations without improvement, genetic crossovers are called. The iterative loop stops when the execution time \(t\) exceeds a preset threshold time limit \(t\).  
The current paper proposes a hybrid-ALNS algorithm, with operators not only based on infeasibilities as in [11], but rather on a destruction and repair mechanism which updates the success rate of each given operator. The repair and destroy phase combines regular and data-driven operators. Regular operators, such as 1-opt, 2-opt and X-opt, are provided with data on route infeasibilities and operators success history. The intuition behind these operators is that routes with infeasibilities could be repaired or avoided instead of being overlooked. A repair operator builds a new solution from \(X\) while maintaining or improving its overall feasibility, while the destroy operators randomly remove parts of it. While operators are called based on their increasing order of complexity in [11], the primary selection of a specific operator is performed through a roulette wheel mechanism in the current paper. Moreover, no records on the success rates of the operators, and no weights are assigned to them in HG-DARP [11], while a weight \(\tau_{g}\) which measures the success rate is associated with a given operator \(g\). We mainly use roulette wheel selection for its simplicity, as it allows operators with higher weights to have higher probabilities of selection. Considering that the weight of a given operator may follow a different updating scheme depending on the problem being solved, roulette wheel selection adapts to these differences.  
At the beginning of the single and multi-route repair-destroy phase, all weights are initialized to 1 and the probability of selecting the operator \(g\) equals \(\frac{1}{G}\), where \(G\) is overall number of single or multi-route operators used. The weights are adjusted after each iteration of the repair and destroy loop following their scores. If an operator \(g\) is applied, its weight \(\tau_{g}\) is updated depending on its success or failure to improve the overall or incumbent solution. If the new solution improves the overall best solution, the score of the operator is \(\eta_{g}=2\). If the new solution improves the incumbent solution, the score of the operator is \(\eta_{g}=1\). Otherwise, the score of the operator is \(\eta_{g}=0\). If the operator improves the overall or incumbent solution, its weight is increased: \(\tau_{g}=\left[(1-\epsilon)\tau_{g}+\epsilon\eta_{g}\right]/o_{g}\), where \(\epsilon\in[0,1]\) is the reaction factor controlling how quickly the weight reacts to score changes, and \(o_{g}\) is the number of times operator \(g\) was called. For example, if an operator \(g\) succeeds on its first call to improve the overall best solution, its weight \(\tau_{g}\) increases from \(\frac{1}{G}\) to \(\frac{1+\epsilon(2G-1)}{G}\). While if it succeeds on its first call to improve the incumbent solution, its weight increases from \(\frac{1}{G}\) to \(\frac{1+\epsilon(G-1)}{G}\). Otherwise, if it fails to make any improvement, its weight decreases from \(\frac{1}{G}\) to \(\frac{1-\epsilon}{G}\). In the following, we detail the ALNS operators we implemented.