Abstract
Large-scale ride-matching is computationally intensive, often requiring $O(n^2)$ comparisons to build shareability networks. This paper proposes a sub-quadratic algorithm that transforms the matching problem into a Near Neighbor Search (NNS) using Locality Sensitive Hashing (LSH). By representing routes as spatio-temporal vectors, the approach identifies high-utility matches with significantly lower computational overhead than brute-force methods. Evaluations on NYC taxi data demonstrate a 6% improvement in matching utility over standard heuristics while maintaining real-time feasibility.
Introduction
Shared mobility platforms aim to match multiple riders into a single vehicle to reduce congestion and costs. The core challenge lies in constructing a shareability network, where nodes represent rides and edges represent feasible matches. At an urban scale with tens of thousands of requests, a brute-force approach requiring $O(n^2)$ pairwise comparisons is computationally prohibitive for real-time deployment. Existing industry heuristics, such as proximity-based matching, often sacrifice utility by ignoring road network geometry and precise timing constraints.
Methodology: Matching as Hashing
The authors propose treating ride-matching as a similarity search in a high-dimensional vector space. The process involves several key steps:
- Spatio-Temporal Representation: The city is discretized into spatial blocks (e.g., Geohashes) and time into discrete intervals. A ride is represented as a sequence of "spatio-temporal edges."
- Vectorization: Each ride $r$ is mapped to a preprocessing vector ($p_r$) containing edge costs and a binary query vector ($q_r$) indicating edge presence. The inner product of these vectors approximates the cost savings of a match.
- LSH for MIPS: To avoid quadratic complexity, Asymmetric Locality Sensitive Hashing (ALSH) is used for Maximum Inner Product Search (MIPS). This allows finding top potential matches in approximately $O(n \log n)$ time.
Experimental Evaluation
The algorithm was evaluated using the New York City Yellow Taxi trip dataset, focusing on high-load "Morning Commute" (21,310 rides) and "Evening Commute" (19,610 rides) scenarios. Real-world routing was provided by the Open Source Routing Machine (OSRM).
Key Results
The LSH-based approach consistently outperformed state-of-the-art heuristics like CLOSEBY (pickup proximity) and HAVERSINE (straight-line overlap).
- Higher Utility: LSH achieved approximately 6 percentage points higher total matching utility than the best baseline, as shown in the utility comparison.
- Scalability: For 20,000 rides, computation took roughly 300 seconds on a single core, which can be further optimized through parallelization.
- Robustness: The performance advantage remained stable across varying request densities (sampling percentages).
Discussion and Future Work
The primary insight of this work is that matching utility can be modeled as an inner product, enabling the use of efficient similarity search techniques. Unlike geometric heuristics, this method is road-network aware, accounting for one-way streets and bridges.
However, the approach is sensitive to the level of discretization. Future work includes extending the model to handle non-linear cost functions and implementing incremental updates for dynamic, on-demand environments.
Summary updated