Revisiting Large Neighborhood Search with On-the-Fly Charging Station Insertion for the Electric Autonomous Dial-a-Ride Problem

Abstract

We address the electric autonomous dial-a-ride problem (E-ADARP), a challenging extension of the dial-a-ride problem with the goal of finding minimum-cost routes serving given transportation requests with a fleet of electric and autonomous vehicles (EAVs). Special emphasis lies on the minimization of user excess ride time under consideration of the charging requirements of the EAVs, while operational constraints have to be satisfied. We propose a novel large neighborhood search (LNS) approach for the E-ADARP together with two alternatives for handling the charging of the EAVs, the scheduling, and route evaluation. One deals with these challenges separately using dedicated LNS operators and a forward labeling algorithm, and the other provides a combined approach with on-the-fly charging stop insertion during route evaluation. The performance of the algorithms is evaluated on various configurations of two common benchmark sets as well as some very large-scale instances. Results show that especially the approach with the on-the-fly insertion almost consistently outperforms former state-of-the-art techniques on the common benchmark instances, finding many new best known solutions. For this best performing approach, multiple variants of a more advanced destroy operator for the underlying LNS are investigated. This enhancement can yield significantly improved performance, especially on the very large instances, as illustrated by further empirical results.