Title: On the Real-time Vehicle Placement Problem,
Abstract: Motivated by ride-sharing platforms' efforts to reduce their riders' wait
times for a vehicle, this paper introduces a novel problem of placing vehicles
to fulfill real-time pickup requests in a spatially and temporally changing
environment. The real-time nature of this problem makes it fundamentally
different from other placement and scheduling problems, as it requires not only
real-time placement decisions but also handling real-time request dynamics,
which are influenced by human mobility patterns. We use a dataset of ten
million ride requests from four major U.S. cities to show that the requests
exhibit significant self-similarity. We then propose distributed online
learning algorithms for the real-time vehicle placement problem and bound their
expected performance under this observed self-similarity.