A Two Phase Heuristic Approach For The Dynamic Electric Autonomous Dial-a-Ride Problem

In the Dial-a-Ride-Problem (DARP) a fleet of vehicles provide shared-ride services to users specifying their origin, destination, and preferred arrival time. In the dynamic version of the DARP, some trips are booked in advance while others come in real-time. In this work, a two-phase heuristic algorithm is designed for the dynamic DARP with the use of electric autonomous vehicles (the electric Autonomous Dial-a-Ride Problem, e-ADARP). In addition to classic constraints from the DARP (i.e. time-windows, origin-destination precedence, users’ maximum ride-times, vehicles’ maximum route durations), the e-ADARP includes online battery management, decisions regarding detours to charging stations, partial vehicles’ recharging, and selection of destination depots. The two-phase heuristic approach includes an insertion stage, in which online requests are introduced in existing routes, and an improvement stage, in which local search heuristics are applied in order to re-optimize the vehicles’ plans after a number of successful insertions. An event-based simulation environment is designed to perform computational experiments on adapted benchmark instances from DARP literature and instances based on real data from Uber Technologies Inc.