Dynamic Routing for Large-Scale Mobility On-Demand Transportation Systems

Abstract

We study a prospective large-scale Ride-Sharing Mobility-on-Demand (RSMoD) transportation system. In this system, a fleet of Shared Autonomous Vehicles (SAVs) provides services to a very large number of passengers (up to 300,000). Passenger requests are submitted throughout the service horizon and require an immediate response from the system. We formulate the resulting decision problem as a dynamic dial-aride problem (DARP), characterized by its very large size, necessitating well-fitted filtering devices. We first derive a static version of this dynamic DARP from a statistical knowledge of the requests. Solving this static DARP version allows us to identify reference requests and related routes, which we incorporate into a Guided Insertion Mechanism (GIM). This mechanism aims to expedite the insertion of real dynamic requests. To handle requests that do not fit the GIM learning basis, we complement this mechanism with a Filtering System (FS), creating an algorithmic GIM-FS framework that dynamically routes the SAVs and assigns them to requests. Numerical tests focus on the behavior of both this prospective system RSMoD and the GIM-FS algorithmic scheme. They show that a large-scale RSMoD system involving SAVs is likely to significantly reduce the number of on-route vehicles as well as the energy consumption and that the twophase GIM-FS approach is more efficient than a baseline method that does not learn from a pre-processed static version of the DARP.