Skip to main content

Minimizing latency in online ride and delivery services

Publication ,  Other
Das, A; Gollapudi, S; Kim, A; Panigrahi, D; Swamy, C
Published in: The Web Conference 2018 - Proceedings of the World Wide Web Conference, WWW 2018
April 10, 2018

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 requests 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.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

The Web Conference 2018 - Proceedings of the World Wide Web Conference, WWW 2018

DOI

Publication Date

April 10, 2018

Start / End Page

379 / 388
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Das, A., Gollapudi, S., Kim, A., Panigrahi, D., & Swamy, C. (2018). Minimizing latency in online ride and delivery services. The Web Conference 2018 - Proceedings of the World Wide Web Conference, WWW 2018. https://doi.org/10.1145/3178876.3186104
Das, A., S. Gollapudi, A. Kim, D. Panigrahi, and C. Swamy. “Minimizing latency in online ride and delivery services.” The Web Conference 2018 - Proceedings of the World Wide Web Conference, WWW 2018, April 10, 2018. https://doi.org/10.1145/3178876.3186104.
Das A, Gollapudi S, Kim A, Panigrahi D, Swamy C. Minimizing latency in online ride and delivery services. The Web Conference 2018 - Proceedings of the World Wide Web Conference, WWW 2018. 2018. p. 379–88.
Das, A., et al. “Minimizing latency in online ride and delivery services.” The Web Conference 2018 - Proceedings of the World Wide Web Conference, WWW 2018, 10 Apr. 2018, pp. 379–88. Scopus, doi:10.1145/3178876.3186104.
Das A, Gollapudi S, Kim A, Panigrahi D, Swamy C. Minimizing latency in online ride and delivery services. The Web Conference 2018 - Proceedings of the World Wide Web Conference, WWW 2018. 2018. p. 379–388.

Published In

The Web Conference 2018 - Proceedings of the World Wide Web Conference, WWW 2018

DOI

Publication Date

April 10, 2018

Start / End Page

379 / 388