  Motivated by the popularity of online ride and delivery services, 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.

Data Structures and Algorithms