# A Hybrid Adaptive Large Neighborhood Heuristic for a Real-Life Dial-a-Ride Problem
## 3 Hybrid ALNS DARP
### Repair and Destroy Iterative Loop
#### 3.2.2 Multiple Route Repair and Destroy Operators  
The multiple-route repair and destroy are applied to the routes of two vehicles with three different operators: the repair-destroy inter-route relocate (RDIR), the repair-destroy inter-route swap (RDIS) and the repair-destroy inter-route cross (RDIC). All customers are eligible to be relocated with the destroy-repair multiple route operators, in particular those with time windows' infeasibilities.  
RDIR detects any drop in a different route than its corresponding pick-up. It attempts two different relocate moves. Firstly, it attempts to insert the drop stop in its corresponding pick-up route. Secondly, if that fails, it tries to insert the pick-up in its corresponding drop route. If the move is accepted, this partially repairs both routes \(k\) and \(k^{\prime}\). If the move is rejected, both stops are ejected from their corresponding routes. Therefore, the two routes are partially repaired or destroyed. Theoretically, as every given route may contain a maximum of \(2n\) nodes to be moved to a maximum of \(2n-1\) possible positions in the second route, the complexity order of RDIR is \(o(4m^{2}n^{2})\). Figure 4 shows how the drop \((v_{-})\) in route \(k\) is moved to route \(k^{\prime}\) and inserted in a position after its corresponding drop \((v^{+})\).  
Figure 3: Repair-Destroy Arc (RDA).  
Figure 2: Repair-Destroy Node (RDN).  
RDIS seeks through all routes for different pairs of pick-ups, drops or non-related pick-up and drop. Firstly, it tries to exchanges two drops \((i_{-})\) and \((j_{-})\) if one's pick-up is scheduled in the other's route, and vice versa. Secondly, it tries to exchange two pick-ups \((i^{+})\) and \((j^{+})\) if one's drop is scheduled in the other's route, and vice versa. Finally, it tries to exchange two non-related drop \((i_{-})\) and pick-up \((j^{+})\) if \((i^{+})\) is scheduled in \((j^{+})\)'s route and \((j_{-})\) is scheduled in \((i_{-})\)'s route. If the move is accepted, this partially repairs both routes. If the move is rejected, the two pairs of stops are ejected from their routes. As every given route may contain a maximum of \(2n\) nodes to be interchanged with \(2n-1\) possible nodes in the second route, the theoretical complexity order of RDIS is \(o(4m^{2}n^{2})\). Figure 5 shows how the drop \((v_{-})\) from route \(k\) is exchanged with the drop \((i_{-})\) from route \(k^{\prime}\).  
RDIC seeks through all routes for a particular configuration that involves pairs of drops, pick-ups, or non-related drops and pick-ups requiring to be shifted to the same route. Firstly, it attempts to shift the arc \((i^{+},j^{+})\) to the route containing \((i_{-})\) or \((j_{-})\), or attempts to shift the arc \((i_{-},j_{-})\) to the route containing \(i^{+}\) or \(j^{+}\). Secondly, it attempts to shift the arc \((i^{+},j_{-})\) to the route containing \((i_{-})\) or \((j^{+})\), or attempts to shift the arc \((i_{-},j^{+})\) to the route containing \(i^{+}\) or \(j_{-}\). If the shifting is accepted, this repairs both routes. Otherwise, the stops are ejected from their routes. As every given route may contain a maximum of \(2n+1\) arcs to be interchanged with \(2n+1\) possible arcs in the second route, the theoretical complexity order of RDIC is \(o(4m^{2}n^{2})\). Figure 6 shows how the arc \((u_{-},v_{-})\) is shifted from route \(k\) to route \(k^{\prime}\).  
Figure 4: Repair-Destroy Inter-route Relocate (RDIR).  
Figure 5: Repair-Destroy Inter-route Swap (RDIS).  
Figure 6: Repair-Destroy Inter-route Cross.