Séminaire conjoint CIRRELT-Chaire de recherche du Canada en distributique-Chaire de recherche du Canada en logistique et en transport

TITRE : The Electric Autonomous Dial-A-Ride Problem

CONFÉRENCIER : Claudia Bongiovanni, École Polytechnique Fédérale de Lausanne, Suisse

DATE et ENDOIT : 15 mai 2018, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l’Université de Montréal

RESPONSABLE : Gilbert Laporte

RÉSUMÉ : 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.