Proactive shuttle dispatching in large-scale dynamic dial-a-ride systems

The problem of dispatching shuttles to serve trip requests can be mathematically formulated as a dial-a-ride problem (DARP). With on-demand mobility services gaining more popularity due to the recent developments in the gig economy, communication technologies, and urbanization, the real-time application of DARP is attracting ever more interest. However, the fact that the size of DARP grows exponentially with number of requests and number of available seats renders the current solution methodologies inadequate for online applications. In order to tackle this issue, we propose a general framework that shifts much of the computational burden of the optimization problems that need to be solved into an offline phase, thereby addressing on-demand requests with fast and high-quality solutions in real time. Using numerical experiments, we demonstrate the benefits of the proposed method. Furthermore, we conduct sensitivity analyses to show the performance of our methodology under different parameter settings.