Minimizing Latency in Online Ride and Delivery Services.

RSS Source
Abhimanyu Das, Sreenivas Gollapudi, Anthony Kim, Debmalya Panigrahi, Chaitanya Swamy

Motivated by the popularity of online ride and delivery services, we studynatural variants of classical multi-vehicle minimum latency problems where theobjective is to route a set of vehicles located at depots to serve requestlocated 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 andrelease-time constraints that restrict when each request can be served. Thepoint-to-point requests and release-time constraints model taxi rides anddeliveries. For all the variants considered, we show constant-factorapproximation algorithms based on a linear programming framework. To the bestof our knowledge, these are the first set of results for the aforementionedvariants of the minimum latency problems. Furthermore, we provide an empiricalstudy of heuristics based on our theoretical algorithms on a real data set oftaxi rides.

Stay in the loop.

Subscribe to our newsletter for a weekly update on the latest podcast, news, events, and jobs postings.