Ricard, L., and Bierlaire, M.

The stochastic electric dial-a-ride problem with recourse

Speaker: Ricard L�a

International Conference on Operations Research 2024

September 03, 2024

The dial-a-ride problem involves planning routes for a fleet of vehicles to pool passengers, based on ride requests that specify an origin, destination, and an arrival time window. The electric dial-a-ride problem also incorporates scheduling charging activities to ensure vehicles remain operational. Traditional deterministic approaches often plan conservatively for worst-case scenarios or lack robustness by only accounting for expected energy consumption. To address these limitations, we introduce a two-stage stochastic model with recourse for the electric dial-a-ride problem in this work. Our model leverages real-time data on the state of charge, permitting adjustments to the planned charging time if deviations in energy consumption occur. We also develop an extension of the event-based graph, the so-called event-energy graph, which encodes energy consumption information. This graph features separate layers for each energy level, where events are connected by energy-feasible arcs. Furthermore, we propose an adaptive large neighborhood search algorithm to solve benchmark instances of the electric dial-a-ride problem. We assess the effectiveness of our approach across different ride-pooling systems employing various battery electric vehicles.