Using real-world patterns to improve matching in theory and practice

Summary

Continuous ride-hailing assignment relies on solving the minimum weight bipartite matching problem between passengers and driver-partners. While traditional implementations assume a precalculated cost matrix, computing shortest-path travel times across large road networks dominates total execution time. Researchers introduced an Incremental Kuhn-Munkres algorithm that leverages the spatial locality of optimal matches to compute edge costs on demand. The approach integrates priority queues and lower-bounding techniques with refinement rules to avoid evaluating distant pairs while guaranteeing the same optimal assignment. Evaluated on Singapore road network data and real Grab production workloads, the incremental techniques reduced exact cost calculations and decreased assignment running times by over an order of magnitude.

Takeaways

1. 1

   On Singapore's 400,000-node road network, cost matrix computation time dominates the assignment phase until the number of matched entities exceeds 2,500.

2. 2

   The Incremental Kuhn-Munkres algorithm produces the exact same optimal assignment as standard Kuhn-Munkres while computing only a fraction of the cost matrix.

3. 3

   Using real Grab booking workloads, the incremental approach reduced optimal assignment running times by over an order of magnitude and supported higher batching throughput.