Letting a Large Neighborhood Search for an Electric Dial-A-Ride Problem Fly: On-The-Fly Charging Station Insertion

Abstract

We consider 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 constraints regarding, for example, user ride times and time windows have to be satisfied. We propose a novel large neighborhood search (LNS) approach for the E-ADARP employing the concept of battery-restricted fragments for route representation and efficient cost computations. For the charging of the EAVs, the scheduling, and route evaluation, we introduce two approaches where one deals with these challenges separately and one provides a combined approach. The first approach uses dedicated LNS operators and a forward labeling algorithm whereas the latter employs a novel route evaluation procedure for inserting charging stops on-the-fly as needed. The performance of our LNS-based algorithms is evaluated on common benchmark instances and results show that especially the approach with the on-the-fly insertion almost consistently outperforms former state-of-the-art techniques, finding new best-known solutions for many instances.