The online electric autonomous dial-a-ride problem

The DARP (Dial-a-Ride Problem) is concerned with providing service to a number of requests, specifying their location of origin and destination, as well as time windows indicating their desired service time for at least one of the locations. In the dynamic DARP, requests can also occur in real-time which, in case the request is accepted, must then be inserted into the existing vehicle routes. In this work, an online algorithm for the dynamic DARP with electric, autonomous vehicles, the e-ADARP (Electric Autonomous Dial-a-Ride Problem) is developed. 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. We develop a two-step heuristic which, in the general framework, is comprised of a simple insertion heuristic for the dynamic requests, followed by an improvement phase. In this work, we present the first step, namely the insertion heuristic. 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.