The dynamic electric Autonomous Dial-a-Ride Problem (e-ADARP) extends the dynamic dial-a-ride problem by considering the employment of electric autonomous vehicles (e-AVs). The problem maximizes the number of served demand and minimizes a cost function composed of the total operational cost and user inconvenience. The operation of e-AVs introduces new opportunities that must be taken into account in real-time planning processes. That is, differently from human-driven vehicles, e-AVs operate non-stop and offer more flexibility to modify vehicle plans in real-time. The operation of e-AVs also introduces new challenges that need to be tackled on-line. Namely, the planning process needs to continuously re-optimize the vehicle battery levels, decisions regarding detours to charge stations, recharge times, together with the classic dial-a-ride features.

In this work, we propose a two-phase heuristic approach to solve the dynamic e-ADARP. The first phase consists of an insertion heuristic that efficiently modifies both vehicle routes and schedules with the arrival of new transportation requests. The second phase introduces a new Learning Large Neighborhood Search (LLNS) algorithm to re-optimize both vehicle plans and schedules through intra- or inter-route customer exchanges. The LLNS utilizes multiple neighborhoods defined from problem-specific characteristics. We formulate the choice of the operator by a classification problem, where the operator represents a class and selected characteristics of the problem instances or solutions represent the features. Numerical results are produced from an event-based simulation based on existing benchmark instances and real-world data from ride-hailing services.