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

Abstract

The dynamic electric autonomous Dial-a-Ride Problem (e-ADARP) is a generalization of the dial-a-ride problem which employs electric Autonomous Vehicles (e-AVs) to provide shared rides to on-line requests. The goal of the dynamic e-ADARP is to maximize the number of served requests while minimizing operational cost and user excess ride time. To reach this goal, metaheuristics are designed to modify vehicle-trip assignments as information reveals over time. Differently from human-driven vehicles, e-AVs can be re-routed as often as desired in the course of operations. Given the on-line nature of the problem, plan modifications need to be efficiently performed 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 couples from a pool of competing algorithms. At each iteration, the machine learning component predicts the objective function improvement that is expected to be obtained after the employment of each of the competing algorithms. The destroy/repair couple is consequently drawn according to the expected improvement proportions. Worsening solutions are also considered and drawn with the same likelihood of descent solutions. The proposed metaheuristic is denoted by Predictive Large Neighborhood Search (PLNS) and is employed to efficiently solve dynamic e-ADARP instances. Computational results are performed on 244 100-request dynamic instances from Uber Technologies Inc. Results show that PLNS outperforms the state-of-the art in the context of on-line operations.