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

[Grab](https://yomu.fyi/company/grab) · Tenindra Abeywickrama · Nov 22, 2021

**Type:** Problem & solution

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

## Context

In continuous ride-hailing matching, computing the complete cost matrix of shortest-path travel times between all driver-passenger pairs dominates execution time over the assignment algorithm itself.

## Approach / What changed

Modifying the Kuhn-Munkres algorithm to run incrementally by using priority queues and lower-bound virtual edge costs to calculate exact shortest paths only when triggered by refinement rules.

## Takeaways

- 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.
- The Incremental Kuhn-Munkres algorithm produces the exact same optimal assignment as standard Kuhn-Munkres while computing only a fraction of the cost matrix.
- Using real Grab booking workloads, the incremental approach reduced optimal assignment running times by over an order of magnitude and supported higher batching throughput.

**Tags:** [Architecture](https://yomu.fyi/topic/architecture), [Performance](https://yomu.fyi/topic/performance), [Scalability](https://yomu.fyi/topic/scalability)

[Read original post](https://engineering.grab.com/using-real-world-patterns-to-improve-matching)