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 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.
Introduction
In the logistics of the modern on-demand economy—services like Uber, Lyft, and DoorDash—the primary algorithmic challenge has shifted from traditional distance minimization (the Traveling Salesman Problem) to latency minimization. While distance optimization serves the platform's efficiency, minimizing latency—the time a user waits for service—directly impacts customer satisfaction. This research addresses the Multi-Vehicle Minimum Latency Problem (k-MLP) under two realistic constraints: Point-to-Point (P2P) requests and release-time constraints.
Algorithmic Framework
The researchers developed a multi-step approach to provide the first theoretical guarantees for these complex routing scenarios:
- Metric Transformation: P2P requests are reduced to simpler point requests by modifying the underlying distance metric. For single-depot systems, this reduction is lossless.
- Linear Programming (LP) and Arborescence Packing: The problem is modeled as a flow over time, using arborescence packing to find branching paths that cover requests efficiently.
- Concatenation Graphs: Abstract trees are converted into vehicle routes by determining the optimal order for visiting different "frontiers" of requests.
- kMLP-Fast Heuristic: A computationally efficient version of the theoretical algorithm was created for real-time dispatch, using min-cost flow to stitch together greedy sub-routes.
Key Insights: The Frontier Strategy
A central concept in this work is the "Frontier" strategy. Instead of a vehicle simply heading to the nearest available passenger (a standard greedy approach), the optimal strategy involves identifying expanding frontiers of requests. By serving requests in an order dictated by these boundaries, the system minimizes the average wait time across all users.
Surprisingly, optimizing for latency often naturally improves platform metrics. By being smarter about the order of service, vehicles in the simulation actually traveled less total distance than the greedy baseline.
Theoretical and Empirical Results
The study provides the first constant-factor approximation ratios for several MLP variants, establishing a new theoretical baseline for the field.
Beyond theory, the kMLP-Fast heuristic was tested against massive real-world datasets from Chicago (27 million trips) and NYC (over 1 billion trips), using the Google Maps API for realistic travel times. The results demonstrated significant improvements over greedy strategies:
- Latency: Improved by 5–8% in NYC and 6–13% in Chicago.
- Total Distance: Reduced by 5–15%.
- Idle Time: Reduced by 15–35%, significantly decreasing the time taxis spent driving empty.
Conclusion and Future Directions
While this work establishes a strong foundation for latency-optimized routing, it currently assumes unit capacity per vehicle, not accounting for ride-pooling. Future work will explore dynamic environments where requests arrive while vehicles are mid-route and further optimize computational overhead for massive-scale platforms.
Summary updated