Joint seminar with the CIRRELT-Canada Research Chair in Distribution Management-Canada Research Chair in Logistics and Transportation
TITLE: The Electric Autonomous Dial-A-Ride Problem
SPEAKER: Claudia Bongiovanni, École Polytechnique Fédérale de Lausanne, Switzerland
DATE and VENUE: May 15, 2018, 10h30, room 5441, André-Aisenstadt Building, Université de Montréal Campus
ORGANIZER: Gilbert Laporte
ABSTRACT: The 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, providing multiple depots becomes a crucial feature since autonomous vehicles can operate non-stop and need to continuously wait and relocate around the urban network. 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 and devise a Branch-and-Cut algorithm with new valid inequalities derived from e-ADARP properties. Benchmark instances from literature as well as real data from Uber Technologies Inc. in San Francisco are employed for testing purposes.
Joint work with Mor Kaspi and Nikolas Geroliminis, EPFL.