Minimizing Latency in Online Ride and Delivery Services
Abstract
Motivated by the popularity of online ride services such as Uber,
Lyft, and Ola, we study natural variants of classical multi-vehicle
minimum latency problems where the objective is to route a set
of vehicles located at depots to serve request located on a metric
space so as to minimize the total latency. In this paper, we consider
point-to-point requests that come with source-destination pairs
and release-time constraints that restrict when each request can be
served. The point-to-point requests and release-time constraints
model taxi rides and deliveries. For all the variants considered, we
show constant-factor approximation algorithms based on a linear
programming framework. To the best of our knowledge, these
are the first set of results for the aforementioned variants of the
minimum latency problems. Furthermore, we provide an empirical
study of heuristics based on our theoretical algorithms on a real
data set of taxi rides.