A predictive large neighborhood search for the dynamic electric autonomous dial-a-ride problem

The dynamic electric autonomous Dial-a-Ride Problem (e-ADARP) is a generalization ofthe dial-a-ride problem which employs electric Autonomous Vehicles (e-AVs) to provide sharedrides to on-line requests. The goal of the dynamic e-ADARP is to maximize the number of servedrequests while minimizing operational cost and user excess ride time. To reach this goal, meta-heuristics are designed to modify vehicle-trip assignments as information reveals over time. Dif-ferently from human-driven vehicles, e-AVs can be re-routed as often as desired in the courseof operations. Given the on-line nature of the problem, plan modifications need to be efficientlyperformed to timely notify users and provide new instructions to the vehicles.In this work, we present a new extension to the family of Large Neighborhood Search(LNS) metaheuristics, which employs a machine learning component to select destroy/repair cou-ples from a pool of competing algorithms. At each iteration, the machine learning componentpredicts the objective function improvement that is expected to be obtained after the employmentof each of the competing algorithms. The destroy/repair couple is consequently drawn accord-ing to the expected improvement proportions. Worsening solutions are also considered and drawnwith the same likelihood of descent solutions. The proposed metaheuristic is denoted by Predic-tive Large Neighborhood Search (PLNS) and is employed to efficiently solve dynamic e-ADARPinstances. Computational results are performed on 244 100-request dynamic instances from UberTechnologies Inc. Results show that PLNS outperforms the state-of-the art in the context of on-line operations.