Dynamic Trip-Vehicle Dispatch with Scheduled and On-Demand Requests
  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.
