Minimizing Latency in Online Ride and Delivery Services

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

This paper, presented by researchers from Google, Stanford, Duke, and the University of Waterloo, tackles the algorithmic heart of modern on-demand economy services like Uber, Lyft, and DoorDash. It provides the first theoretical guarantees for minimizing user wait times in complex routing scenarios.

TL;DR

The authors develop the first constant-factor approximation algorithms for the multi-vehicle minimum latency problem involving point-to-point requests and release-time constraints. Beyond the theory, they demonstrate a practical heuristic that outperforms standard greedy strategies by up to 13% on real-world taxi data from New York City and Chicago.

What Problem Does This Paper Address?

In the world of vehicle routing, most classical research focuses on the "Traveling Salesman Problem" (TSP) variant—minimizing the total distance traveled. This is a platform-side objective (saving fuel/time for the fleet). However, for ride-sharing and delivery, the client-side objective is more critical: minimizing latency, or the time a user waits to be dropped off.

While the "Minimum Latency Problem" (MLP) has been studied for decades, real-world services add two complicating layers:

  1. Point-to-Point (P2P) Requests: A vehicle doesn't just visit a location; it must pick up a passenger at point $A$ and drop them off at point $B$ before moving to the next task.
  2. Release Times: Requests aren't all known at the start of the day; they appear at specific times, and a vehicle cannot start a task before its "release."

Prior to this paper, there were no polynomial-time algorithms with provable performance guarantees for this specific combination of constraints.

Methods

The authors bridge the gap between theory and practice using a multi-step approach:

  • Metric Transformation: They show that P2P requests can be mathematically reduced to simpler "point" requests by modifying the underlying distance metric. For single-depot systems, this reduction is "lossless," meaning it doesn't sacrifice any accuracy.
  • Linear Programming (LP) Framework: They utilize an LP formulation that treats the routing problem as a flow over time. To solve this, they use "arborescence packing"—a technique that finds a set of branching paths (trees) that cover the requests.
  • Concatenation Graphs: To turn these abstract "trees" into actual vehicle routes, they use a concatenation graph. This structure helps determine the optimal order in which a vehicle should visit different "frontiers" (groups of requests) to minimize the cumulative wait time.
  • kMLP-Fast Heuristic: Recognizing that the full theoretical algorithm is too computationally heavy for a real-time dispatch system, they developed a streamlined version. This heuristic uses a min-cost flow algorithm to stitch together greedy sub-routes across different time "layers."

Datasets

The authors evaluated their work using two massive, real-world datasets:

  • Chicago Taxi Data: 27 million trips (2013–2016), mapped to 1000-sq. meter geographical cells.
  • NYC Taxi Data: Over 1 billion trips (2009–2015).
  • Google Maps API: Used to calculate realistic driving times between centroids of the geographical cells to ensure the simulation mirrored actual traffic conditions.

Key Insights and Ideas

  • The "Frontier" Strategy: Instead of a vehicle simply heading to the nearest available passenger (the "Greedy" approach), the optimal strategy involves identifying "frontiers" of requests. By serving requests in an order dictated by these expanding frontiers, the system minimizes the average wait time across all users.
  • Latency vs. Distance: A surprising "aha" moment was that optimizing for the client (latency) often naturally improved platform metrics. By being smarter about the order of service, the vehicles actually traveled less total distance than the greedy baseline.
  • Backtracking for Analysis: The authors introduced "backtracking paths" as a tool for proof. By analyzing a hypothetical path where a vehicle returns to a source after every drop-off, they were able to bound the performance of the actual, more efficient shortcut paths.

Key Results

  • Theoretical Guarantees: They achieved constant approximation ratios for all variants. For example, they proved a ~3.59 ratio for MLP and an ~8.98 ratio for single-depot multi-vehicle latency.
  • Empirical Gains: In simulations using NYC and Chicago data, their kMLP-Fast heuristic consistently beat the greedy baseline:
  • Latency: Improved by 5–8% in NYC and 6–13% in Chicago.
  • Total Distance: Reduced by 5–15%, despite not being the primary goal.
  • Idle Time: Reduced by a staggering 15–35%, meaning taxis spent significantly less time driving empty between fares.

Limitations and Future Work

  • Unit Capacity: The current model assumes each vehicle carries only one request at a time (like a standard taxi). It does not account for "ride-pooling" (e.g., UberPool), where multiple passengers with different destinations share a car simultaneously.
  • Static vs. Dynamic: While the paper uses real-time release constraints, the algorithms are evaluated in "batches." A truly dynamic version where vehicles are already mid-route when a new request arrives remains a complex area for future exploration.
  • Computational Overhead: Even the "Fast" heuristic is more complex than a simple greedy search, which might pose challenges for platforms handling millions of requests per second without further optimization.

Summary updated

Abstract

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.
BibTeX
@inproceedings{das2018minimizing,
  author = {Abhimanyu Das and Sreenivas Gollapudi and Anthony Kim and Debmalya Panigrahi and Chaitanya Swamy},
  title = {{Minimizing Latency in Online Ride and Delivery Services}},
  booktitle = {The Web Conference},
  year = {2018},
  doi = {10.1145/3178876.3186104},
}

Loading related content...

Figure