Picture a dispatcher standing at a busy airport curb with a clipboard, trying to figure out which arriving passengers can share one shuttle van without making any single passenger sit through someone else’s detour. Two people flying in from the same gate might be headed to hotels four blocks apart, a genuinely good pairing, or they might be headed to opposite ends of the city, a pairing that only looks convenient until you actually trace the roads between them. The dispatcher’s real job isn’t finding two people going “roughly the same way,” it’s finding two people whose actual road-network paths overlap enough that combining them costs less time than either one would lose by riding alone.

Now replace the clipboard with a matching engine, replace the one shuttle line with an entire city’s worth of vehicles, and replace a dozen arriving flights with thousands of ride requests arriving every few seconds, each one needing an answer, pooled or solo, before the rider gives up and closes the app. That is the ride-pooling matching problem: for every open request, find zero or more other open requests whose routes overlap enough to share a vehicle, compute the actual extra time each rider would absorb by accepting a detour to pick up or drop off a stranger, and commit to the best set of pairings across the whole city, not just the first plausible pairing found, all within a couple of seconds.

The naive approach, match the first two requests that happen to be near each other, fails in an obvious way: “near each other” at the moment of pickup says nothing about whether their destinations pull in the same direction, and a rider who accepts a pool expecting a five-minute detour and gets fifteen minutes instead churns out of the product for good. The opposite naive approach, wait and collect a large batch of requests before computing the single best global matching, fails just as badly in the other direction: riders are staring at a spinner, and the very act of waiting to build a bigger batch means some of those riders would have been better served by a decision made three seconds ago. Both mistakes come from treating matching as either a purely local, greedy decision or a purely global, patient one, when the real system has to behave like both depending on how loaded a given part of the city currently is.

We need to solve for three things simultaneously: a scoring mechanism that can tell a genuinely compatible pair of routes from two riders who just happen to be standing near each other, a matching strategy that trades off greedy speed against globally optimal quality depending on load, and a way to keep every match honest after it’s made, both because a rider has to actually agree to share their trip and because the road conditions a match was computed against can change before the vehicle ever arrives.

Requirements and Constraints

Functional Requirements

• Accept a ride request carrying an origin, a destination, a party size, and an optional maximum detour tolerance, and hold it as an open candidate for pooling until it is matched, expires, or falls back to a solo dispatch
• Score any two (or more) open requests by how much their routes overlap, using actual road-network proximity, not straight-line distance between pickup points
• Calculate the concrete detour cost, in added seconds, that each existing rider in a candidate vehicle would absorb if a new rider’s pickup and dropoff were inserted into that vehicle’s route
• Batch open requests into a rolling match window and compute either a greedy or a globally optimal assignment across the batch, chosen based on how many open requests are competing in that batch
• Enforce vehicle capacity as a hard constraint during matching, never proposing a combination that exceeds a vehicle’s remaining seats
• Require every rider in a proposed match to explicitly consent within a bounded time window before the match is treated as confirmed and dispatched to a vehicle
• Recalculate a vehicle’s live route in real time whenever a new rider is added mid-trip, a rider cancels, or actual travel time diverges meaningfully from the plan the match was computed against
• Fall back to a solo dispatch for any request that has cycled through multiple match windows without finding a compatible partner, rather than leaving the rider waiting indefinitely for a pool that may never materialize

Non-Functional Requirements

• Scale: a single metro-area matching cluster handling on the order of 1,500 new ride requests/sec sustained at peak, with up to 9,000 concurrently open (unmatched) requests in flight across the city at any instant
• Latency: a match decision, pooled or solo, must be produced within a p99 of 2 seconds measured from the moment a matching window closes; end-to-end, a rider should never wait more than roughly 6-8 seconds from request to a definite answer
• Correctness guarantee: a vehicle must never be assigned more riders than its remaining seat capacity allows, under any level of concurrent matching activity across zones
• Consent guarantee: no match is dispatched to a vehicle until every rider in it has explicitly accepted; a single non-response must not indefinitely block the other riders in that same candidate match
• Freshness: a route recalculation triggered by a mid-trip event (new rider added, rider cancels, live traffic diverges from plan) must reach the driver’s navigation within 3 seconds
• Availability: the request-ingestion and solo-dispatch fallback path targets 99.95% uptime, since a rider must always be able to get a car even if the pooling optimization layer is degraded
• Fairness bound: no rider’s detour, measured against their own solo trip time, may exceed a configured cap (the lesser of 8 minutes or 30% of their solo ETA)

Constraints and Assumptions

• Turn-by-turn routing, live traffic conditions, and ETA computation are owned by a separate routing/ETA service that this design treats as an upstream dependency, not something we build here
• Driver-side vehicle positioning, navigation rendering, and the physical pickup/dropoff experience belong to a separate driver-app system; this design’s responsibility ends once a confirmed match is handed off as a dispatch instruction
• Pricing and fare-splitting logic is out of scope; this system only decides who rides with whom and in what sequence, not what each rider pays
• We assume a single logical metro region per matching cluster; cross-city or interstate pooling is out of scope
• We assume the road network and an H3-style hexagonal geospatial index are available as a library, not something this design has to invent

High-Level Architecture

The system has six major components: the Request Ingestion and Geo-Indexer, the Route Overlap Candidate Generator, the Detour Cost Engine, the Rolling Match Window Scheduler (the matching engine itself), the Rider Consent Service, and the Dispatch and Dynamic Route Recalculation layer.

The Request Ingestion and Geo-Indexer is the front door: it validates an incoming request, samples its route into a corridor of geospatial cells, and assigns it to a geo-zone shard so downstream matching only ever has to reason about requests that are physically near each other. The Route Overlap Candidate Generator is a cheap pre-filter, it scans a zone’s open requests and produces a shortlist of plausible pairs whose route corridors actually overlap, before anything expensive gets computed. The Detour Cost Engine takes that shortlist and calculates the real, road-network-aware added time each rider would absorb if a candidate combination were built into an actual vehicle route. The Rolling Match Window Scheduler is the matching engine proper: every few seconds it closes a batch of scored, capacity-filtered candidates and decides, using either a greedy or a globally optimal strategy, which combinations actually get proposed. The Rider Consent Service holds a proposed match open just long enough for every rider in it to accept, reject, or time out. The Dispatch and Dynamic Route Recalculation layer takes a confirmed match, assigns it to a physical vehicle, and keeps that vehicle’s route current as the trip unfolds and reality diverges from the plan.

A request’s life looks like this: a rider opens the app, the gateway indexes their route into H3 cells and drops the request into its zone’s open pool. On the next window close, the candidate generator finds other open requests whose corridors overlap this one, the detour engine scores exactly how expensive each candidate combination actually is, and the matching scheduler decides whether this rider gets proposed a pool partner or, if the zone is quiet enough, computed a fully solo dispatch immediately. If a pool is proposed, the consent service pings every rider in it and waits, bounded, for everyone to accept. Only once every rider has said yes does the match get handed to dispatch, which assigns a vehicle and starts the trip; from there, any mid-trip event, another rider being added, a cancellation, or a large ETA drift, routes back through dynamic recalculation rather than treating the original plan as fixed.

Component Deep Dives

The Request Ingestion and Geo-Indexer

This component’s job is to turn a raw origin-destination request into something the rest of the system can reason about cheaply: a sampled route corridor assigned to the correct geo-zone shard.

The obvious mistake is indexing a request by its pickup point alone. Two riders can have pickup points thirty meters apart and be headed in completely unrelated directions, and two riders can have pickup points a kilometer apart but travel almost the exact same corridor for most of their trip. Indexing by pickup point alone would either miss the second pair entirely or force every zone’s candidate generator to consider every other request in a wide radius regardless of direction, which defeats the point of pre-filtering. Instead we sample each request’s route into a sequence of H3 hexagonal cells and index the request by that whole sequence, not a single point.

# Route corridor indexing: samples a route into H3 cells so requests
# can be pre-filtered by actual path overlap, not pickup proximity
import h3
import math

def route_cells(origin: tuple[float, float], dest: tuple[float, float],
                 resolution: int = 8, samples: int = 12) -> set[str]:
    lat1, lng1 = origin
    lat2, lng2 = dest
    cells = set()
    for i in range(samples + 1):
        t = i / samples
        lat = lat1 + (lat2 - lat1) * t
        lng = lng1 + (lng2 - lng1) * t
        cells.add(h3.latlng_to_cell(lat, lng, resolution))
    return cells

def zone_for_request(origin: tuple[float, float], zone_resolution: int = 6) -> str:
    # Coarser resolution used purely for shard assignment, distinct
    # from the finer resolution used for overlap scoring below.
    lat, lng = origin
    return h3.latlng_to_cell(lat, lng, zone_resolution)

Think of this like a subway map versus a street address: a street address tells you where someone stands, but the subway map tells you which lines they’d actually ride, and two people standing far apart at street level can still be riding the exact same train for most of the trip. What breaks without corridor indexing: the candidate generator either misses genuinely compatible pairs whose pickups are far apart, or has to fall back to scanning the entire zone’s open pool against every other request, which is the exact quadratic blowup we’re trying to avoid.