The Electric Autonomous Dial-a-Ride Problem
Claudia Bongiovanni  1@  , Mor Kaspi  1@  , Nikolas Geroliminis  1@  
1 : Ecole Polytechnique Federale de Lausanne (EPFL)

Ride sharing is changing urban mobility by offering reliable and convenient on-demand services at any time. Given the constant increase in demand, ride-sharing businesses are currently planning to expand their portfolio to include Dial-a-Ride Transit (DART) by the use of electric Autonomous Vehicles (AVs). This novel type of service introduces new operational challenges. First, as the vehicles are electric, battery management needs to be considered during route planning. Second, DART is provided 24/7 and autonomous vehicles are not required to return to a specific depot. Providing multiple depots becomes a crucial feature since vehicles need to continuously wait and relocate around the urban network during the non-stop service. 

In this study, we present a new multi-objective Dial-a-Ride formulation for electric AVs (e-ADARP) which integrates tracking battery levels, decisions regarding detours to recharging stations, recharging times and decisions regarding destination depots with the classic Dial-a-Ride features. We formulate the problem as a Mixed Integer Linear Problem (MILP) and devise a Branch-and-Cut algorithm with new valid inequalities derived from e-ADARP properties. Large instances of the problem are decomposed to tractable sub-instances using machine learning techniques. Real data from Uber Technologies Inc. in San Francisco is employed for testing purposes.


Online user: 2 RSS Feed