A Learning Large Neighborhood Search for the Dynamic Electric Autonomous Dial-A-Ride Problem

Abstract

In the dynamic Dial-a-Ride Problem (DARP) a fleet of vehicles provide door-to-door transport to on-line requests. The problem typically aims at minimizing the total operational cost while maximizing the company revenue, measured by means of the number of served trip requests. In its standard version, the dynamic DARP considers time-window, capacity, maximum ride time, and maximum route duration constraints. The dynamic electric Autonomous Dial-a-Ride Problem (e-ADARP) extends the dynamic DARP by considering the employment of electric autonomous vehicles (e-AVs). Differently from human-driven vehicles, e-AVs can be diverted as often as desired in the course of the operations and operated on a non-stop schedule. Given the electric nature of the vehicles, 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. We propose an exact scheduling algorithm for the eADARP, which efficiently provides optimal vehicle schedules in quadratic time. The second phase introduces a new Learning Large Neighborhood Search (LLNS) algorithm that re-optimizes 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.