Dynamic Trip-Vehicle Dispatch with Scheduled and On-Demand Requests
This addresses a practical challenge for transportation service providers by integrating scheduled and on-demand rides, though it appears incremental as it builds upon existing dispatch methods.
The paper tackles the problem of dispatching vehicles for both scheduled and on-demand ride requests, designing algorithms that incorporate estimated on-demand request distributions, and achieves improved performance as demonstrated through experiments on a real-world dataset.
Transportation service providers that dispatch drivers and vehicles to riders start to support both on-demand ride requests posted in real time and rides scheduled in advance, leading to new challenges which, to the best of our knowledge, have not been addressed by existing works. To fill the gap, we design novel trip-vehicle dispatch algorithms to handle both types of requests while taking into account an estimated request distribution of on-demand requests. At the core of the algorithms is the newly proposed Constrained Spatio-Temporal value function (CST-function), which is polynomial-time computable and represents the expected value a vehicle could gain with the constraint that it needs to arrive at a specific location at a given time. Built upon CST-function, we design a randomized best-fit algorithm for scheduled requests and an online planning algorithm for on-demand requests given the scheduled requests as constraints. We evaluate the algorithms through extensive experiments on a real-world dataset of an online ride-hailing platform.