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.

The Route Overlap Candidate Generator

This component’s job is to take a zone’s pool of open requests and produce a short list of plausible pairs, and occasionally small groups, whose route corridors actually overlap enough to be worth the expensive detour calculation.

A smart engineer’s first instinct is to score overlap purely by counting shared cells, but that alone rewards two routes that cross paths briefly in the middle of the city just as much as two routes that run parallel for their entire length. A brief crossing is not a good pool candidate, since the two riders diverge immediately after; a long parallel run is. We weight the raw cell-intersection score against how similar the two routes’ overall direction (bearing) is, so a genuine shared corridor scores higher than a coincidental crossing.

# Route overlap scoring: combines cell-intersection (Jaccard) with a
# bearing-similarity term so a genuine shared corridor outranks a
# brief incidental crossing between two otherwise unrelated routes
import math

def bearing(origin: tuple[float, float], dest: tuple[float, float]) -> float:
    lat1, lng1 = map(math.radians, origin)
    lat2, lng2 = map(math.radians, dest)
    d_lng = lng2 - lng1
    x = math.sin(d_lng) * math.cos(lat2)
    y = math.cos(lat1) * math.sin(lat2) - math.sin(lat1) * math.cos(lat2) * math.cos(d_lng)
    return (math.degrees(math.atan2(x, y)) + 360) % 360

def angle_diff(a: float, b: float) -> float:
    diff = abs(a - b) % 360
    return diff if diff <= 180 else 360 - diff

def overlap_score(req_a, req_b, resolution: int = 8) -> float:
    cells_a = route_cells(req_a.origin, req_a.dest, resolution)
    cells_b = route_cells(req_b.origin, req_b.dest, resolution)
    union = cells_a | cells_b
    if not union:
        return 0.0

    jaccard = len(cells_a & cells_b) / len(union)
    bearing_gap = angle_diff(
        bearing(req_a.origin, req_a.dest),
        bearing(req_b.origin, req_b.dest),
    )
    bearing_similarity = 1.0 - min(bearing_gap / 180.0, 1.0)

    return 0.7 * jaccard + 0.3 * bearing_similarity

MIN_OVERLAP_SCORE = 0.35  # below this, don't bother running detour cost at all

This is the same technique a search engine uses when ranking documents: a cheap inverted-index lookup narrows millions of documents down to a few hundred candidates before an expensive relevance model ever runs on any of them. What breaks if this step is skipped: the detour cost engine, which has to call into an actual road-network routing function, would need to evaluate every pair in a zone, and at a few hundred open requests per zone that’s tens of thousands of expensive routing calls per window instead of a few hundred.

The Detour Cost Engine

This component’s job is to take a shortlisted candidate pair or small group and compute the real, road-network-aware extra time each individual rider absorbs if that combination were actually built into one vehicle’s route.

The non-obvious part is that detour cost is not a property of a pair of requests in isolation, it’s a property of where a new rider’s pickup and dropoff get inserted into an existing sequence of stops. Two requests can look like an excellent overlap match and still produce a terrible detour if the only way to insert the second rider’s stops is at an awkward point in the first rider’s route. We use a cheapest-insertion heuristic: try every valid position to insert the new rider’s pickup and dropoff into the existing stop sequence, keep whichever insertion adds the least total travel time, and reject the combination if any individual rider’s own added time exceeds their configured detour cap.

# Cheapest-insertion detour cost: finds the best position to insert a
# new rider's pickup and dropoff into an existing vehicle route, and
# reports the per-rider added time so detour caps can be enforced
import math
from dataclasses import dataclass

@dataclass
class Stop:
    request_id: str
    kind: str  # "pickup" or "dropoff"
    lat: float
    lng: float

def travel_time_seconds(a: Stop, b: Stop, eta_fn) -> float:
    return eta_fn((a.lat, a.lng), (b.lat, b.lng))

def route_duration(stops: list[Stop], eta_fn) -> float:
    return sum(
        travel_time_seconds(stops[i], stops[i + 1], eta_fn)
        for i in range(len(stops) - 1)
    )

def cheapest_insertion(existing_stops: list[Stop], new_pickup: Stop,
                        new_dropoff: Stop, eta_fn) -> tuple[float, list[Stop]] | None:
    base_duration = route_duration(existing_stops, eta_fn)
    best_cost = math.inf
    best_route = None
    n = len(existing_stops)

    for i in range(n + 1):
        for j in range(i, n + 1):
            candidate = (
                existing_stops[:i] + [new_pickup]
                + existing_stops[i:j] + [new_dropoff]
                + existing_stops[j:]
            )
            cost = route_duration(candidate, eta_fn) - base_duration
            if cost < best_cost:
                best_cost = cost
                best_route = candidate

    if best_route is None:
        return None
    return best_cost, best_route

def detour_within_cap(rider_solo_eta_seconds: float, added_seconds: float,
                       cap_seconds: float = 480.0, cap_ratio: float = 0.30) -> bool:
    cap = min(cap_seconds, rider_solo_eta_seconds * cap_ratio)
    return added_seconds <= cap

Think of this like slotting a new errand into an already-planned driving loop: the question is never “is this errand generally on the way,” it’s “where in my existing loop does this errand cost me the least extra driving,” and the answer depends entirely on the order of stops you’ve already committed to. What breaks without per-rider detour capping: a combination can look cheap in aggregate (the vehicle’s total added distance is small) while one specific rider, whose pickup happened to land at the worst point in the sequence, absorbs nearly all of that added time alone.

The Rolling Match Window Scheduler

This component’s job is the matching decision itself: given a zone’s shortlisted, detour-scored candidates, decide which combinations actually get proposed, using a strategy that adapts to how loaded that zone currently is.

Matching on every single request the instant it arrives sounds responsive, but it throws away information: a request that arrives half a second before a much better partner would have shown up gets matched to a worse partner, or dispatched solo, purely because of timing. Waiting to collect a large, city-wide batch before matching anything sounds thorough, but it means every rider waits for the slowest possible decision even when their own neighborhood is quiet. The rolling match window splits the difference: every zone closes a short batch, by default every 4 seconds, of the requests that arrived since the last window, and matches only within that batch, giving up a small amount of matching quality in exchange for a bounded, predictable wait.

Within a window, the actual assignment problem is solved one of two ways depending on batch size. For a small batch, we solve it as an assignment problem and find the provably optimal matching using the Hungarian algorithm; for a large batch, where the cubic cost of an optimal solve would blow the 2-second decision budget, we fall back to a greedy matching that processes candidates in score order.

// Greedy matching: processes scored, capacity-checked candidate pairs
// in descending order and commits each one if neither rider is
// already claimed by a higher-scoring pairing earlier in the list
package matching

import "sort"

type Candidate struct {
	RequestA string
	RequestB string
	Score    float64
	Feasible bool // false if capacity or detour cap already ruled this out
}

func GreedyMatch(candidates []Candidate) map[string]string {
	sort.Slice(candidates, func(i, j int) bool {
		return candidates[i].Score > candidates[j].Score
	})

	claimed := make(map[string]bool)
	assignment := make(map[string]string)

	for _, c := range candidates {
		if !c.Feasible || claimed[c.RequestA] || claimed[c.RequestB] {
			continue
		}
		claimed[c.RequestA] = true
		claimed[c.RequestB] = true
		assignment[c.RequestA] = c.RequestB
		assignment[c.RequestB] = c.RequestA
	}
	return assignment
}

# Optimal matching via the Hungarian algorithm: models the batch as a
# bipartite assignment problem where "matched to yourself" represents
# the solo-dispatch option, so every request always has a valid
# assignment even when no partner clears the capacity or detour caps
import numpy as np
from scipy.optimize import linear_sum_assignment

INFEASIBLE = 1e6

def build_cost_matrix(requests, score_fn, feasible_fn) -> np.ndarray:
    n = len(requests)
    cost = np.full((n, n), INFEASIBLE)
    for i in range(n):
        cost[i][i] = 0.0  # solo dispatch: always a valid, zero-cost fallback
        for j in range(n):
            if i == j or not feasible_fn(requests[i], requests[j]):
                continue
            cost[i][j] = -score_fn(requests[i], requests[j])
    return cost

def optimal_match(requests, score_fn, feasible_fn) -> dict[str, str]:
    cost = build_cost_matrix(requests, score_fn, feasible_fn)
    row_idx, col_idx = linear_sum_assignment(cost)

    assignment = {}
    for i, j in zip(row_idx, col_idx):
        if i == j or cost[i][j] >= INFEASIBLE:
            continue  # solo dispatch, or no feasible partner this window
        assignment[requests[i].id] = requests[j].id
    return assignment

This is the same tradeoff an air traffic controller makes between clearing planes for landing in strict first-come order versus holding a short queue to sequence them for maximum runway throughput: the strict order is faster to decide but leaves throughput on the table, while the short, bounded hold produces a better overall outcome at the cost of a small amount of predictable wait. What breaks if every zone always used the optimal solver: the Hungarian algorithm is O(n^3), and a busy downtown zone’s batch of a thousand or more requests would take far longer than the 2-second decision budget to solve exactly, stalling every rider in that zone waiting for a globally perfect answer none of them can afford to wait for.

The Rider Consent Service

This component’s job is to hold a proposed match open just long enough for every rider in it to explicitly accept, without letting one slow or unresponsive rider indefinitely block the others.

A system that dispatches a pooled match the instant the matching engine computes it, without asking anyone, is efficient but wrong: a rider might be mid-call, might have changed their plans since requesting, or might simply object to sharing a ride with a stranger on that particular trip. But a system that waits indefinitely for every rider’s response holds a vehicle’s seat capacity hostage against a single unresponsive rider, starving everyone else who could have used that seat. We give every rider in a proposed match a short, bounded window, by default 6 seconds, to accept or reject, and resolve the match the instant a definite outcome is reachable rather than waiting out the full timeout unnecessarily.

# Consent resolution: finalizes a proposed match the instant every
# member has responded, and treats a timeout the same as a rejection
# so one unresponsive rider can't indefinitely block the others' seats
CONSENT_TIMEOUT_SECONDS = 6.0

def resolve_consent(member_states: dict[str, str], proposed_at: float, now: float) -> str:
    if any(state == "rejected" for state in member_states.values()):
        return "rejected"
    if all(state == "accepted" for state in member_states.values()):
        return "confirmed"
    if now - proposed_at > CONSENT_TIMEOUT_SECONDS:
        return "expired"
    return "pending"

def on_consent_change(match, member_states: dict[str, str], proposed_at: float, now: float,
                       requeue_fn, dispatch_fn) -> str:
    outcome = resolve_consent(member_states, proposed_at, now)
    if outcome == "confirmed":
        dispatch_fn(match)
    elif outcome in ("rejected", "expired"):
        requeue_fn(match, reason=outcome)
    return outcome

Think of this like a group dinner reservation that only gets confirmed once everyone in the group has replied, but with a firm reply-by time, so the restaurant isn’t holding the table hostage against one friend who never checks their messages. What breaks without a bounded timeout: a rider who accepted their half of a two-person match sits waiting on a partner who never responds, and that partner’s silent non-answer costs both riders a seat and several seconds of wall-clock time that could have gone to a solo dispatch or a different pairing.

Dispatch and Dynamic Route Recalculation

This component’s job is to take a confirmed match, hand it to an actual vehicle, and keep that vehicle’s route correct as reality, new riders joining, riders cancelling, or traffic diverging from plan, changes after the match was originally computed.

The mistake a simpler design makes is treating the route computed at match time as fixed for the life of the trip. A vehicle’s actual route is a living plan: a third rider might get matched into a vehicle that already has two riders aboard, an existing rider might cancel before pickup, or live traffic might make the originally planned stop order meaningfully worse than an alternative ordering. Any of those events has to trigger the same cheapest-insertion logic the detour cost engine already uses, run again against the vehicle’s current, live stop sequence rather than its original one.

# Dynamic route recalculation: re-runs cheapest insertion (add) or a
# direct removal-and-resequence (cancel) against a vehicle's live stop
# list, so a mid-trip event never leaves the driver navigating a stale plan
def recalculate_for_addition(live_stops: list[Stop], new_pickup: Stop,
                              new_dropoff: Stop, eta_fn, capacity_ok: bool) -> list[Stop] | None:
    if not capacity_ok:
        return None
    result = cheapest_insertion(live_stops, new_pickup, new_dropoff, eta_fn)
    return result[1] if result else None

def recalculate_for_cancellation(live_stops: list[Stop], cancelled_request_id: str,
                                  eta_fn) -> list[Stop]:
    remaining = [s for s in live_stops if s.request_id != cancelled_request_id]
    # Re-run a lightweight nearest-neighbor resequencing on what's left,
    # rather than assuming the old relative order is still the cheapest one.
    if len(remaining) <= 2:
        return remaining
    resequenced = [remaining[0]]
    pool = remaining[1:]
    while pool:
        last = resequenced[-1]
        nxt = min(pool, key=lambda s: eta_fn((last.lat, last.lng), (s.lat, s.lng)))
        resequenced.append(nxt)
        pool.remove(nxt)
    return resequenced

The analogy is a delivery driver’s handheld device updating their stop list mid-route when dispatch adds a package: the driver doesn’t restart the day’s plan, the device re-slots the new stop into wherever it costs the least extra driving from the driver’s current position. What breaks without live recalculation: a vehicle keeps navigating toward a plan built minutes ago, and every event since then, a new rider, a cancellation, worsening traffic, either gets silently ignored or bolted onto the end of the route regardless of whether that’s still the cheapest place for it.

Data Model

The data model spans five entities: open ride requests, proposed and confirmed matches, per-match rider consent state, live vehicle state, and the ordered route stops a vehicle is actually driving.

-- Ride requests: the open pool the matching engine draws from each window
CREATE TABLE ride_requests (
    request_id          UUID        PRIMARY KEY,
    rider_id            TEXT        NOT NULL,
    party_size          INT         NOT NULL CHECK (party_size > 0),
    origin_lat          DOUBLE PRECISION NOT NULL,
    origin_lng          DOUBLE PRECISION NOT NULL,
    dest_lat            DOUBLE PRECISION NOT NULL,
    dest_lng            DOUBLE PRECISION NOT NULL,
    zone_id             TEXT        NOT NULL,
    corridor_cells      TEXT[]      NOT NULL,
    max_detour_seconds  INT         NOT NULL DEFAULT 480,
    status              TEXT        NOT NULL DEFAULT 'pending'
        CHECK (status IN ('pending', 'proposed', 'matched', 'solo_dispatched', 'expired', 'cancelled')),
    requeue_count       INT         NOT NULL DEFAULT 0,
    requested_at        TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    window_id           BIGINT
);

CREATE INDEX ON ride_requests (zone_id, status) WHERE status = 'pending';
CREATE INDEX ON ride_requests USING GIN (corridor_cells);

-- Matches: one row per proposed or confirmed pooling combination
CREATE TABLE matches (
    match_id       UUID        PRIMARY KEY,
    vehicle_id     TEXT,
    window_id      BIGINT      NOT NULL,
    status         TEXT        NOT NULL DEFAULT 'proposed'
        CHECK (status IN ('proposed', 'confirmed', 'rejected', 'expired')),
    proposed_at    TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    confirmed_at   TIMESTAMPTZ
);

-- Match members: per-rider consent state within a proposed match
CREATE TABLE match_members (
    match_id         UUID   NOT NULL REFERENCES matches(match_id),
    request_id       UUID   NOT NULL REFERENCES ride_requests(request_id),
    pickup_sequence  INT    NOT NULL,
    dropoff_sequence INT    NOT NULL,
    detour_seconds   INT    NOT NULL,
    consent_status   TEXT   NOT NULL DEFAULT 'pending'
        CHECK (consent_status IN ('pending', 'accepted', 'rejected')),
    consented_at     TIMESTAMPTZ,
    PRIMARY KEY (match_id, request_id)
);

-- Vehicles: live capacity and position, the row every dispatch touches
CREATE TABLE vehicles (
    vehicle_id       TEXT    PRIMARY KEY,
    capacity         INT     NOT NULL,
    seats_available  INT     NOT NULL CHECK (seats_available >= 0),
    current_lat      DOUBLE PRECISION,
    current_lng      DOUBLE PRECISION,
    active_route_id  UUID,
    status           TEXT    NOT NULL DEFAULT 'idle'
        CHECK (status IN ('idle', 'en_route', 'offline'))
);

-- Route stops: the live, ordered sequence a vehicle is actually driving
CREATE TABLE route_stops (
    route_id       UUID    NOT NULL,
    sequence_no    INT     NOT NULL,
    stop_type      TEXT    NOT NULL CHECK (stop_type IN ('pickup', 'dropoff')),
    request_id     UUID    NOT NULL REFERENCES ride_requests(request_id),
    planned_eta    TIMESTAMPTZ,
    actual_arrival TIMESTAMPTZ,
    PRIMARY KEY (route_id, sequence_no)
);

CREATE INDEX ON route_stops (request_id);

ride_requests is sharded by zone_id, the same coarse geo-cell used to route a request to its matching worker. Sharding any other way, by rider_id, for example, would scatter a single zone’s open requests across the whole cluster, forcing the candidate generator to fan out to every shard just to find requests physically near each other. Keeping a zone’s open pool on one shard means an entire matching window can run against local data with no cross-shard coordination during the 2-second decision budget.

A request is born the moment a rider submits it: it lands in ride_requests with status = 'pending', tagged with its zone and corridor cells. On the next window close, if the matching engine finds it a partner, a matches row and matching match_members rows are created and the request flips to status = 'proposed'. From there exactly one of three things happens: every member consents and the request flips to matched, dispatch fills in vehicle_id and writes route_stops; any member rejects or times out and the request flips back to pending with requeue_count incremented for the next window; or the request has already cycled through the maximum requeue count and instead gets status = 'solo_dispatched' with a single-rider route.

Key Algorithms and Protocols

Route Overlap Scoring

Covered in the Route Overlap Candidate Generator section above, this algorithm combines a Jaccard-style intersection of sampled H3 cells with a bearing-similarity term, running in O(k) time per pair for k sampled cells per route, cheap enough to run against every open pair in a zone before the expensive detour step.

Cheapest-Insertion Detour Cost

Covered in the Detour Cost Engine and Dynamic Route Recalculation sections above, this algorithm tries every valid insertion point for a new rider’s pickup and dropoff within an existing stop sequence, running in O(n^2) time for n existing stops, since it evaluates roughly n^2/2 candidate insertion positions.

Greedy versus Optimal Matching

Covered in the Rolling Match Window Scheduler section above, greedy matching sorts scored candidates and commits in O(m log m) time for m candidate pairs, while optimal matching via the Hungarian algorithm solves the batch as a bipartite assignment problem in O(n^3) time for n open requests in the batch.

Consent Resolution

Covered in the Rider Consent Service section above, this is a small bounded state machine per match: pending until every member responds or the timeout elapses, confirmed only if every member accepts, rejected or expired otherwise.

Scaling and Performance

The Rolling Match Window Scheduler is the component under the tightest latency budget, since every open request in a zone has to clear its matching decision inside the 2-second window, and it scales by partitioning the city into geo-zones that each run their own matching cycle independently, with hot zones split into finer sub-cells the same way a hot key gets split anywhere else in a distributed system.

A single downtown zone during rush hour can see a batch size that would make even the O(n^3) Hungarian solve blow its 2-second budget, so once a zone’s batch size crosses a threshold, it’s automatically subdivided into finer-resolution H3 sub-cells, each with its own independent matching window and worker. This costs a small amount of matching quality, since a pooling opportunity that spans the boundary between two sub-cells is missed, in exchange for keeping every sub-cell’s batch size, and therefore its solve time, bounded.

Capacity Estimation:

Given:
  - 1,500 new ride requests/sec sustained citywide at peak
  - 4-second rolling match window, 2-second matching decision budget
  - ~60 active geo-zones citywide (H3 resolution 7, subdivided to
    resolution 8 in dense downtown areas)
  - Average zone batch size: 150 open requests per window
  - Consent timeout: 6 seconds, up to 3 requeue cycles before solo fallback

Concurrent open (unmatched) requests in flight (Little's Law: L = lambda * W):
  1,500/sec * 6 sec (4s window + 2s decision budget) = 9,000 concurrent
  open requests citywide at any instant

Per-zone matching cost (Hungarian assignment, O(n^3)):
  150^3 = 3,375,000 operations per zone per window
  60 zones * 3,375,000 = ~202,500,000 operations per 4-second window,
  fully parallel across zones - comfortably inside a single core's
  budget per zone within the 2-second decision window

Route corridor index footprint:
  9,000 open requests * ~12 H3 cells/request * 8 bytes/cell = ~864 KB
  resident in the geo-index at any instant

Consent fan-out:
  ~55% of requests are pool-eligible and matched per window; at
  1,500 requests/sec that is ~825 matches/sec * ~2.4 riders/match
  = ~1,980 consent push notifications/sec at peak

The dominant bottleneck is not aggregate citywide throughput, the numbers above are modest, it is the handful of downtown zones whose batch size threatens the 2-second decision budget during rush hour. Splitting a hot zone into finer sub-cells the moment its batch size crosses a threshold, rather than waiting for latency to already be breached, is what keeps the matching decision bounded everywhere, not just in quiet zones.

Failure Modes and Recovery

Failure	Detection	Impact	Recovery
A zone’s batch size grows faster than its matching worker can solve within the 2-second budget	Window solve-time metric approaching or exceeding the decision budget	Riders in that zone wait past the latency SLA, or receive stale-feeling matches	Zone automatically subdivides into finer H3 sub-cells with dedicated workers once batch size crosses a threshold, and the solver falls back from optimal to greedy under sustained pressure
A rider never responds to a proposed match	Consent timer expiry with no terminal consent_status recorded	The vehicle’s seat and the other rider’s time are held against a match that will never confirm	Timeout is treated identically to an explicit rejection; the match is torn down and every member requeued into the next window
Two zone workers race to reserve the same vehicle’s last seat	Seat count check fails on the second writer’s atomic decrement	Without protection, a vehicle could be assigned more riders than it has seats for	seats_available is decremented with a guarded, atomic compare-and-swap update, identical in shape to an inventory counter’s check-and-reserve, so only one writer ever wins the last seat
Live traffic conditions diverge meaningfully from the plan a match was computed against	ETA service reports a delta beyond a configured threshold against the vehicle’s current route	A rider’s actual detour could silently exceed the cap they consented to	Dynamic route recalculation reruns the same cheapest-insertion cost model against current conditions, and a rider whose live detour would breach their cap is proactively re-offered a solo completion for the remainder of the trip
Network partition isolates a zone’s matching worker from the central dispatch and consent services	Heartbeat loss between the zone worker and the central coordinator	The zone can’t confirm new matches or receive vehicle availability updates	The zone worker degrades to solo-dispatch-only mode using its last known local vehicle state, and reconciles matched state with the coordinator once connectivity returns
A vehicle goes offline (crash, connectivity loss) mid-trip with active riders aboard	Missed location heartbeat past a grace period	Riders already aboard have no live route, and any pending mid-trip addition can’t be dispatched to that vehicle	Pending additions are rerouted to the next-best vehicle by the detour cost engine; already-aboard riders are flagged for support intervention, since the design does not attempt physical vehicle failover

Comparison of Approaches

Approach	Latency	Complexity	Failure mode	Best fit
Per-request greedy matching, no batching (match instantly against whatever is open right now)	Fastest per request, but reacts to timing luck rather than true compatibility	Low	A slightly-better partner arriving a second later is missed entirely	Very low-density markets where pool opportunities are rare and speed matters more than match quality
Rolling window + greedy assignment (this design’s default under load)	Bounded, fast, O(m log m) per window	Medium	Occasionally settles for a locally good but not globally best combination	Busy zones where batch size makes an exact solve too slow for the decision budget
Rolling window + optimal Hungarian assignment (this design’s default when batch is small)	Bounded but O(n^3), can approach the decision budget as batch size grows	Medium-high	Solve time grows sharply once batch size crosses roughly a few hundred requests	Quiet-to-moderate zones where batch size stays small enough for an exact solve to stay fast
Continuous insertion (evaluate inserting each new request into every existing active route the instant it arrives, no batching wait at all)	No batching delay, but every arrival triggers an insertion search against every active vehicle	High	Insertion search cost grows with the number of active vehicles, and early arrivals can lock in suboptimal seats before better-fitting later requests appear	Low-volume, high-value markets (e.g. non-urban shuttle routes) where the number of active vehicles is small enough to search exhaustively
Full city-wide mixed-integer optimization solved centrally every cycle	Slowest, potentially far outside any real-time budget	Very high	A single slow solve blocks match decisions for the entire city, not just one zone	Offline network design and simulation, not live dispatch

We would pick the rolling window design with a per-zone, per-window choice between greedy and optimal assignment for any city-scale pooling product, because it is the only approach here that keeps the 2-second decision budget honest under both quiet and rush-hour load. The alternatives each fail on a different axis: pure per-request greedy throws away easy matching quality for no latency benefit once batching is cheap enough to do well, continuous insertion doesn’t scale past a small active fleet, and a fully centralized optimal solve trades away exactly the responsiveness a live rider is waiting on.

Key Takeaways

• Route overlap scoring must run before detour cost, never instead of it. A cheap geospatial pre-filter using sampled H3 cells and bearing similarity narrows a zone’s open pool down to a short, plausible list before the expensive road-network detour calculation ever runs.
• Detour cost is a property of where a stop gets inserted, not a property of a pair of requests in isolation. The same two requests can produce a great or a terrible detour purely depending on the existing stop sequence they’re inserted into.
• Greedy versus optimal matching is a per-window choice, not a fixed design decision. Small batches can afford a provably optimal Hungarian solve; large batches need a greedy fallback to stay inside the latency budget.
• The rolling match window trades a small, bounded wait for dramatically better matching quality than matching each request the instant it arrives.
• A proposed match isn’t a match until every rider consents, and consent needs a hard timeout. Treating a timeout identically to an explicit rejection is what prevents one unresponsive rider from indefinitely holding a seat hostage.
• Dynamic route recalculation has to reuse the exact same cost model the initial match used, so a mid-trip change is held to the same detour guarantee a rider originally consented to.
• Capacity constraints must be enforced as a hard filter before scoring, using an atomic seat decrement, the same shape as an inventory counter’s check-and-reserve, so two zone workers can never both claim a vehicle’s last seat.
• Hot zones need the same fix as any other hot shard: split them finer, don’t just add more compute to the same partition.

The counter-intuitive lesson is that the hardest-sounding requirement, finding the best possible set of matches across thousands of concurrent requests, is actually the part this design is willing to compromise on. It happily accepts a locally greedy, occasionally suboptimal matching under load. What it refuses to compromise on is the detour guarantee made to any individual rider and the capacity guarantee made to any individual vehicle, because a slightly worse match is a minor inconvenience, while a broken detour promise or an overbooked vehicle is a broken promise to a real person standing on a curb.

Frequently Asked Questions

Q: Why not always use the optimal Hungarian assignment instead of switching to greedy under load?

A: Because the Hungarian algorithm’s O(n^3) cost means a batch of even a few hundred requests can approach or exceed the 2-second decision budget, and a busy downtown zone during rush hour routinely produces batches that large. Falling back to greedy under load trades a small amount of matching quality for a hard guarantee that every rider gets an answer inside the latency budget, which matters more to the rider than a marginally better pairing that arrives late.

Q: Why not skip the rolling window and match every request the instant it arrives?

A: Matching instantly discards information: a slightly better partner arriving half a second later gets missed entirely, and a request that could have anchored a better three-way pool ends up locked into a worse pairing purely because of arrival timing. A short, bounded batching window costs a small, predictable amount of wait time in exchange for meaningfully better matching quality, since the engine can compare several candidates at once instead of committing to the first plausible one.

Q: How does the system prevent a vehicle capacity race condition when two zone workers try to fill the same vehicle’s last seat at once?

A: seats_available on the vehicle row is decremented through a guarded, atomic compare-and-swap update, the same technique an inventory system uses to prevent overselling the last unit of stock. Only one writer’s update can succeed against the current seat count; the losing writer’s update affects zero rows and that worker simply looks for a different vehicle.

Q: Why not score route overlap using straight-line distance between pickup points instead of sampled H3 corridor cells?

A: Straight-line pickup distance says nothing about whether two riders’ actual road-network paths run together or diverge immediately after pickup. Two pickups thirty meters apart can be headed in opposite directions, and two pickups a kilometer apart can share almost their entire route. Sampling each route into corridor cells and comparing those cells directly captures actual path overlap instead of a proxy that happens to correlate with it only some of the time.

Q: What happens if a rider’s live detour, recalculated mid-trip, would exceed the cap they originally consented to?

A: The dynamic route recalculation step reruns the same cheapest-insertion cost model against current conditions on every meaningful mid-trip event, and if a rider’s live detour would breach the cap they accepted at consent time, that rider is proactively offered a direct, solo completion of their remaining trip rather than being silently carried past the guarantee they were given.

Q: How many times should a request be allowed to requeue into a new window before falling back to a solo dispatch?

A: This design caps it at 3 requeue cycles, roughly 12 to 18 seconds of total wait depending on window and consent timing, after which the request is dispatched solo regardless of whether a pool partner might still materialize. Requeuing forever in pursuit of a marginally better match trades a small chance of pooling efficiency for a real, cumulative cost in rider wait time, and past a handful of cycles that trade stops being worth it.

Interview Questions

Q: Walk through what happens, end to end, when two riders whose routes genuinely overlap submit requests four hundred milliseconds apart in the same zone.

Expected depth: Cover how both requests land in the same zone’s open pool, how the candidate generator’s corridor-cell pre-filter surfaces them as a plausible pair before any expensive detour math runs, how the detour cost engine’s cheapest-insertion calculation decides whether the combination clears both riders’ detour caps, and why the actual match decision waits for the window to close rather than acting the instant the second request arrives.

Q: How would you decide, as a per-window design choice rather than a fixed rule, whether a zone’s batch should be solved greedily or optimally?

Expected depth: Discuss measuring batch size in real time, the O(n^3) cost of the Hungarian solve versus the O(m log m) cost of greedy, and what threshold or degrading-solve-time signal should trigger falling back from optimal to greedy mid-operation rather than picking one strategy permanently for a given zone.

Q: A rider consents to a proposed match, but their would-be partner never responds and the consent window expires. Design the logic that decides what happens next for each of them.

Expected depth: Cover the consent state machine treating a timeout identically to an explicit rejection, why the responding rider shouldn’t be penalized or made to wait further, and how both riders get requeued into the next matching window (or fall back to solo dispatch if they’ve already exhausted their requeue budget) rather than one of them being silently dropped.

Q: The system needs to support a mid-trip event where a vehicle already carrying two pooled riders picks up a third rider whose request just matched into that vehicle. What has to happen, and what could go wrong?

Expected depth: Discuss rerunning cheapest insertion against the vehicle’s live stop sequence rather than its original plan, checking the vehicle’s remaining seat capacity as a hard gate before the insertion is even attempted, verifying the newly inserted detour doesn’t breach either of the two already-aboard riders’ original detour caps, and what should happen if inserting the third rider would breach an already-aboard rider’s cap even though it fits within the new rider’s own cap.

Q: A single downtown zone is seeing three times its normal request volume during a major event letting out. What changes, if anything, from the steady-state design?

Expected depth: Discuss automatic subdivision of the zone into finer H3 sub-cells with dedicated matching workers, the solver falling back from optimal to greedy as batch size grows, whether the match window duration itself should shrink or grow under this kind of surge, and why the loss of some cross-boundary pooling opportunities from subdividing the zone is an acceptable tradeoff against blowing the 2-second decision budget for everyone in that zone.