The Data and Science Behind GrabShare Part I: Verifying Potential and Developing the Algorithm

Summary

Expanding from point-to-point dispatch services to dynamic carpooling requires matching independent passenger requests traveling in similar directions without causing unacceptable delays. Grab evaluated the feasibility of its GrabShare service by analyzing historical trip data with DBSCAN clustering on coordinates projected into a Universal Transverse Mercator system. This analysis demonstrated that 35% to 46% of rides across typical daytime windows fell into tight geographic clusters with near-identical pickup and drop-off coordinates. The resulting matching framework adapts the baseline dispatch flow by searching for in-transit drivers and enforcing real-time seat reservation constraints. Route assignment decisions subsequently evaluate detour times, trip angles, and expected arrival times to ensure driver utilization improves while total driving distance decreases.

Context

Real-time dynamic pooling can reduce traffic congestion and improve driver utilization, but scaling it requires matching strangers traveling in similar directions while preserving seat availability and acceptable travel times.

Approach / What changed

Grab verified ride-pooling potential using DBSCAN clustering on historical booking coordinates mapped to Universal Transverse Mercator projections, then formulated a real-time matching algorithm that queries in-transit drivers, tracks occupied vehicle capacity, and filters routes using detour and efficiency constraints.

Takeaways

• DBSCAN clustering with a 300-meter neighborhood threshold demonstrated that 35% to 46% of daytime GrabCar trips shared near-identical pickup and drop-off areas.
• GrabShare modifies the standard booking flow by searching active in-transit drivers and enforcing dynamic vehicle capacity checks before assignment.
• Matching routes are evaluated against trip angle, detour, arrival time, and efficiency metrics to minimize extra passenger transit time while significantly reducing total driven distance.

Related reading

• Grab · Feb 20, 2019

  Understanding Supply & Demand in Ride-hailing Through the Lens of Data

  Grab measures ride-hailing supply and demand across space and time to resolve geo-temporal allocation mismatches between moving drivers and ride-seeking passengers. The analytics pipeline defines supply as idle online drivers and demand as passengers checking fares within brief time slots, aggregating locations into geohashes. Each driver is mapped across neighbouring demand units and inversely weighted by straight-line distance, which yields the effective supply, supply-demand ratio, and supply-demand difference for each geographic polygon. Grab uses these aggregated metrics to identify marketplace imbalances, deploying driver heatmaps to shift excess supply and passenger travel trend widgets to defer time-insensitive ride requests.

  Aayush Garg

• Grab · Dec 13, 2017

  GrabShare at the Intelligent Transportation Engineering Conference

  Grab presented a technical paper on the construction of its real-time ridesharing service, GrabShare, at the Intelligent Transportation Engineering Conference in Singapore. The platform pairs passengers heading along similar routes with drivers immediately while handling network drops, volatile supply and demand, and heavy traffic conditions in Southeast Asian cities. To deliver accurate pairings, the scheduling system generates and filters through hundreds of travel time estimates for each candidate match before finalizing an itinerary. Operational teams on the ground evaluate complaints about poor matches, enabling engineers to refine the online matching systems. Over the course of one month, the service cut more than 4.5 million kilometers of driving distance and brought in over 100,000 new users within two weeks.

  Dominic Widdows

• Grab · Jul 20, 2018

  Grab Senior Data Scientist Liuqin Yang Wins Beale-Orchard-Hays Prize

  Grab Senior Data Scientist Dr. Liuqin Yang, Professor Defeng Sun, and Professor Kim-Chuan Toh received the 2018 Beale-Orchard-Hays Prize for their research paper introducing SDPNAL+. The software employs a majorised semismooth Newton-CG augmented Lagrangian method to solve large-scale semidefinite programming problems with nonnegative constraints. While traditional methods struggled beyond matrix dimensions of 2,000 and 5,000 constraints, SDPNAL+ successfully scales to matrix dimensions of 9,261 and over 12 million constraints. In benchmark testing, the software solved a problem on a desktop PC in 1.5 hours that required 122 hours on a 56-core CPU and 128-GPU cluster using a traditional solver. Grab implements these optimisation techniques to accelerate its passenger-driver allocation algorithms by hundreds of times.

  Yang Liuqin

• Grab · Nov 22, 2021

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

  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.

  Tenindra Abeywickrama