System Design (HLD)Commerce & Infrastructure Systems

Uber / Lyft Ride-Sharing System Design

LevelAdvanced

Duration180 mins

TopicCommerce & Infrastructure Systems

3 / 6

Matching Algorithm: Dispatch Optimization

The Heart of Ride-Sharing

When a rider requests a trip, something remarkable happens in under 2 seconds:

The system identifies potentially thousands of nearby drivers
Calculates estimated pickup times for the most promising candidates
Scores each driver on dozens of factors
Atomically assigns the optimal driver (ensuring no double-booking)
Notifies both rider and driver in real-time

This matching algorithm is the intellectual core of ride-sharing platforms. It's where computer science meets economics—an optimization problem running 1,000+ times per second, each decision affecting the earnings of drivers, the wait times of riders, and the efficiency of the entire marketplace.

A 10% improvement in matching efficiency translates to:

Shorter wait times for riders (higher satisfaction, more trips)
Higher utilization for drivers (more earnings per hour)
Better unit economics for the platform (lower incentive spend)

The difference between good and great matching is worth billions annually for platforms like Uber and Lyft.

What You Will Learn

By the end of this page, you will understand how to design a production-grade matching system. You'll learn greedy vs. batch matching strategies, multi-factor driver scoring, concurrency control for atomic assignment, and fairness mechanisms that prevent driver starvation.

Matching System Architecture Overview

Before diving into algorithms, let's understand the overall architecture of a matching system and where it fits in the request flow.

Request-to-Match Flow

Converting Mermaid diagram...

Core Components

1. Matching Service

Orchestrates the matching process:

Receives ride requests from the Ride Service
Queries Location Service for nearby drivers
Enriches candidates with ETA data
Applies scoring model
Triggers assignment through Dispatch Service

2. Location Service

Provides spatial query capabilities (covered in previous page):

Returns drivers within specified radius
Filters by availability status
Returns driver metadata (vehicle type, rating)

3. ETA Service

Calculates travel times (covered in detail later):

Pickup ETA: Driver location → Rider location
Trip ETA: Pickup → Dropoff
Considers real-time traffic

4. Dispatch Service

Handles atomic assignment:

Locks driver for exclusive assignment
Sends push notification to driver
Manages accept/decline timeout
Handles reassignment if driver declines

Separation of Concerns

Splitting matching logic across services enables independent scaling and deployment. The Matching Service can be updated frequently (algorithm improvements) without affecting the stable Location Service. Different teams can own different components with clear interfaces.

Greedy Matching Strategies

The simplest matching approach is greedy: for each ride request, immediately find and assign the single best driver. Let's explore greedy strategies in increasing sophistication.

Strategy 1: Nearest Driver

Assign the geographically closest available driver.

nearest-driver-matching.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
async function matchNearestDriver(rideRequest):
    // Query nearby drivers
    candidates = await locationService.getDriversInRadius(
        center = rideRequest.pickupLocation,
        radius = 5000,  // meters
        filters = {
            status: "available",
            vehicleType: rideRequest.vehicleType
        }
    )
    
    if candidates.isEmpty():
        return null  // No drivers available
    
    // Sort by straight-line distance (already sorted by GEORADIUS)
    nearestDriver = candidates[0]
    
    // Attempt assignment
    assigned = await dispatchService.assignDriver(
        driverId = nearestDriver.id,
        rideId = rideRequest.id
    )
    
    if assigned:
        return nearestDriver
    else:
        // Driver became unavailable, try next
        return matchNearestDriver(rideRequest)  // Recursive retry

Advantages

•Extremely simple — Trivial to implement and debug
•Very fast — Single sort operation, O(n log n)
•Low latency — No external API calls for ranking
•Deterministic — Same input always produces same output

Disadvantages

•Ignores road network — Straight-line distance ≠ travel time
•Ignores driver direction — Stationary closer driver vs. approaching farther driver
•No global optimization — Locally optimal may be globally suboptimal
•Unfair to distant drivers — Creates 'hot zones' where some drivers never get trips

Strategy 2: Lowest ETA

Assign the driver with the shortest actual pickup time, considering road network and traffic.

lowest-eta-matching.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
async function matchLowestETA(rideRequest):
    // Get candidates (limit to reasonable set to reduce ETA calls)
    candidates = await locationService.getDriversInRadius(
        center = rideRequest.pickupLocation,
        radius = 5000,
        filters = { status: "available", vehicleType: rideRequest.vehicleType },
        limit = 20  // Only top 20 by distance
    )
    
    if candidates.isEmpty():
        return null
    
    // Calculate ETAs in parallel
    etaPromises = candidates.map(driver => 
        etaService.getPickupETA(driver.location, rideRequest.pickupLocation)
    )
    etas = await Promise.all(etaPromises)
    
    // Combine and sort
    candidatesWithETA = zip(candidates, etas)
        .filter(([_, eta]) => eta != null)  // Remove failed lookups
        .sortBy(([_, eta]) => eta.seconds)
    
    // Assign best driver
    for ([driver, eta] in candidatesWithETA):
        assigned = await dispatchService.assignDriver(driver.id, rideRequest.id)
        if assigned:
            return {driver, eta}
    
    return null  // All candidates became unavailable

Improvement over nearest driver:

Scenario	Nearest Driver	Lowest ETA
Driver A: 800m away across highway	Assigned (closer)	Not assigned
Driver B: 1.2km away on same street	Skipped	Assigned (faster ETA)
Actual pickup time A	8 minutes (detour)	—
Actual pickup time B	—	3 minutes

Tradeoff: ETA calculation requires routing API calls, adding latency and cost. Limiting candidates to top N by distance keeps API costs manageable.

Strategy 3: Multi-Factor Scoring

Rank drivers using a composite score that balances multiple objectives:

multi-factor-scoring.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
function calculateDriverScore(driver, rideRequest, eta):
    // Initialize base score
    score = 0
    
    // Factor 1: Pickup ETA (primary factor)
    // Lower ETA = higher score
    // Normalize: 5-minute ETA = baseline score of 50
    etaScore = 100 - (eta.seconds / 300) * 50
    etaScore = clamp(etaScore, 0, 100)
    score += etaScore * 0.40  // 40% weight
    
    // Factor 2: Driver Rating
    // 5.0 rating = 50 points, 4.0 rating = 30 points
    ratingScore = (driver.rating - 4.0) * 20 + 30
    ratingScore = clamp(ratingScore, 0, 50)
    score += ratingScore * 0.15  // 15% weight
    
    // Factor 3: Acceptance Rate (driver reliability)
    // Higher acceptance = more reliable
    acceptanceScore = driver.acceptanceRate * 50
    score += acceptanceScore * 0.10  // 10% weight
    
    // Factor 4: Driver Direction Alignment
    // Is driver heading toward pickup?
    headingDiff = abs(driver.heading - bearingToPickup)
    if headingDiff < 30:  // Within 30 degrees
        score += 10 * 0.10  // Bonus for aligned direction
    
    // Factor 5: Fairness / Time Since Last Trip
    // Penalize drivers who just completed trips (give others a chance)
    minutesSinceLastTrip = (now() - driver.lastTripEndTime) / 60000
    fairnessBonus = min(minutesSinceLastTrip, 10)  // Cap at 10 minutes
    score += fairnessBonus * 0.10  // 10% weight
    
    // Factor 6: Vehicle Quality Match
    // Premium ride + premium car = bonus
    if rideRequest.isPremuim and driver.vehicleYear >= 2020:
        score += 15 * 0.15
    
    return score
 
// Usage in matching
candidatesWithScores = candidatesWithETA.map(([driver, eta]) => ({
    driver,
    eta,
    score: calculateDriverScore(driver, rideRequest, eta)
}))
.sortBy(c => -c.score)  // Descending by score

Scoring Weight Tuning

The weights in scoring models are typically tuned using A/B testing and ML optimization. Small weight changes (e.g., 40% → 45% for ETA) can significantly impact rider wait times, driver utilization, and marketplace efficiency. Production systems use ML-trained models that adapt weights based on city, time of day, and market conditions.

Batch Matching for Global Optimization

Greedy matching makes locally optimal decisions but can produce globally suboptimal outcomes. Consider this scenario:

Example: Greedy Suboptimality

Rider A requests a trip (arrives first)
Driver 1 is 2 minutes away; Driver 2 is 4 minutes away
Greedy assigns Driver 1 to Rider A
Rider B requests 5 seconds later, directly next to Driver 2
Driver 2 must drive 3 minutes to reach Rider B (Driver 1 was right there!)

Total wait time with greedy: 2 + 3 = 5 minutes

Optimal assignment: Driver 1 → Rider B (0.5 min), Driver 2 → Rider A (4 min) = 4.5 minutes

Batch matching solves this by accumulating ride requests and available drivers over a short window, then computing globally optimal assignments.

How Batch Matching Works

Converting Mermaid diagram...

The Assignment Problem Formulation

Batch matching is a classic bipartite matching problem:

Left vertices: Ride requests {R₁, R₂, ..., Rₙ}
Right vertices: Available drivers {D₁, D₂, ..., Dₘ}
Edge weights: Cost of assigning Dⱼ to Rᵢ (negative ETA score, so minimizing cost maximizes quality)
Goal: Find a matching that minimizes total cost

Mathematical Formulation:

Minimize: Σᵢ Σⱼ cᵢⱼ × xᵢⱼ

Subject to:
  Σⱼ xᵢⱼ ≤ 1  for all i (each ride gets at most one driver)
  Σᵢ xᵢⱼ ≤ 1  for all j (each driver gets at most one ride)
  xᵢⱼ ∈ {0, 1}

Where cᵢⱼ is the cost of assigning driver j to ride i, and xᵢⱼ is the assignment decision.

Hungarian Algorithm

The Hungarian algorithm (Kuhn-Munkres) solves the assignment problem optimally in O(n³) time:

Create n×m cost matrix (rides × drivers)
Row reduction: Subtract minimum of each row from all elements in that row
Column reduction: Subtract minimum of each column from all elements
Cover zeros with minimum lines
If lines = n, optimal assignment found; else, adjust matrix and repeat

batch-matching-implementation.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class BatchMatcher:
    BATCH_WINDOW_MS = 2000  // 2 second batching window
    
    pendingRides = []
    pendingDrivers = []
    
    @scheduled(every=BATCH_WINDOW_MS)
    async function runBatchMatching():
        if pendingRides.isEmpty():
            return
        
        // Snapshot current state
        rides = pendingRides.copy()
        drivers = pendingDrivers.copy()
        pendingRides.clear()
        pendingDrivers.clear()
        
        // Build cost matrix
        n = rides.length
        m = drivers.length
        costMatrix = new Matrix(n, m)
        
        for i in range(n):
            for j in range(m):
                // Cost = negative score (we minimize cost = maximize score)
                costMatrix[i][j] = -calculateMatchScore(rides[i], drivers[j])
        
        // Run Hungarian algorithm
        assignments = hungarianAlgorithm(costMatrix)
        
        // Execute assignments
        for (rideIdx, driverIdx) in assignments:
            ride = rides[rideIdx]
            driver = drivers[driverIdx]
            
            success = await dispatchService.assignDriver(driver.id, ride.id)
            if !success:
                // Driver became unavailable, requeue ride
                pendingRides.append(ride)
    
    function onNewRideRequest(ride):
        pendingRides.append(ride)
        
        // If waiting too long, force immediate greedy match
        if ride.waitingTime > MAX_WAIT_BEFORE_GREEDY:
            forceGreedyMatch(ride)
    
    function onDriverBecameAvailable(driver):
        pendingDrivers.append(driver)

Greedy vs. Batch Matching Comparison
Aspect	Greedy Matching	Batch Matching
Latency	< 100ms (immediate)	Up to batch window + computation (2-3 sec)
Optimality	Locally optimal only	Globally optimal within batch
Complexity	O(n log n) per request	O(n³) per batch
Best for	Low-volume periods	High-volume periods
Fairness	First-come-first-served bias	More equitable distribution
Implementation	Simple	Moderate complexity

Hybrid Approach in Production

Production systems typically use hybrid approaches: immediate greedy matching during low-volume periods (faster user experience) and batch matching during high-volume periods (better global efficiency). The system monitors request rate and switches modes dynamically.

Concurrency Control and Atomic Assignment

The most critical correctness requirement in matching is: A driver can only be assigned to one ride at a time. Double-booking creates terrible experiences and operational nightmares.

But with 1,000+ matching attempts per second, concurrent assignment attempts to the same driver are common. We need robust concurrency control.

The Double-Booking Race Condition

race-condition-example.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// DANGEROUS: Race condition without proper locking
 
// Thread 1: Matching ride A
driver = findBestDriver(rideA)  // Returns driver_123
if driver.status == "available":  // CHECK
    driver.status = "assigned"    // SET
    createAssignment(rideA, driver)
 
// Thread 2: Matching ride B (concurrent)
driver = findBestDriver(rideB)  // Also returns driver_123!
if driver.status == "available":  // Also passes CHECK (data stale!)
    driver.status = "assigned"    // SET again - DOUBLE BOOKING!
    createAssignment(rideB, driver)
 
// Result: driver_123 is assigned to BOTH rides

Solution 1: Optimistic Locking with Version Numbers

Each driver record has a version number. Updates succeed only if the version matches expected value.

optimistic-locking.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
async function assignDriverOptimistic(driverId, rideId):
    MAX_RETRIES = 3
    
    for attempt in range(MAX_RETRIES):
        // Read current state with version
        driver = await db.query("""
            SELECT id, status, version FROM drivers WHERE id = $1
        """, [driverId])
        
        if driver.status != "available":
            return {success: false, reason: "driver_unavailable"}
        
        // Attempt atomic update with version check
        result = await db.query("""
            UPDATE drivers 
            SET status = 'assigned', current_ride_id = $1, version = version + 1
            WHERE id = $2 AND version = $3 AND status = 'available'
            RETURNING id
        """, [rideId, driverId, driver.version])
        
        if result.rowCount == 1:
            // Success - we won the race
            await createTrip(rideId, driverId)
            await notifyDriver(driverId, rideId)
            return {success: true}
        
        // Version mismatch - someone else updated, retry
        await sleep(random(10, 50))  // Jittered backoff
    
    return {success: false, reason: "contention_exceeded"}

Solution 2: Distributed Locking with Redis

For systems where the database isn't the source of truth for driver availability (e.g., Redis-based location system), use distributed locks.

distributed-locking.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
async function assignDriverWithLock(driverId, rideId):
    lockKey = f"driver_lock:{driverId}"
    lockValue = generateUUID()  // Unique per attempt
    lockTTL = 5000  // 5 second max lock duration
    
    // Attempt to acquire lock
    acquired = await redis.set(lockKey, lockValue, "NX", "PX", lockTTL)
    
    if not acquired:
        return {success: false, reason: "driver_locked"}
    
    try:
        // Check availability (with lock held, this is safe)
        driverMeta = await redis.hGetAll(f"driver:{driverId}")
        
        if driverMeta.status != "available":
            return {success: false, reason: "driver_unavailable"}
        
        // Perform assignment
        pipeline = redis.pipeline()
        pipeline.hSet(f"driver:{driverId}", "status", "assigned")
        pipeline.hSet(f"driver:{driverId}", "current_ride", rideId)
        pipeline.sRem(f"available_drivers:{driverMeta.city_id}", driverId)
        await pipeline.exec()
        
        // Persist to database (async, can be eventually consistent)
        await db.createTrip(rideId, driverId)
        
        return {success: true}
        
    finally:
        // Release lock (only if we still own it)
        await redis.eval("""
            if redis.call('get', KEYS[1]) == ARGV[1] then
                return redis.call('del', KEYS[1])
            else
                return 0
            end
        """, [lockKey], [lockValue])

Solution 3: Sharded Actor Model

Partition drivers into shards, each managed by a single actor/worker that serializes all assignment decisions for its drivers.

Converting Mermaid diagram...

Actor model advantages:

No locks needed—single-threaded processing per shard
Deterministic ordering—makes debugging easier
Natural affinity—driver state stays in actor's memory
Scales horizontally—add more actors for more drivers

Trade-off: Cross-shard coordination is complex if one ride might be assigned to drivers in different shards. Typically mitigated by having actors handle disjoint driver sets based on geographic partition.

Lock Timeout Considerations

Lock TTLs must be chosen carefully. Too short = lock expires mid-operation, causing inconsistency. Too long = failed process holds lock, causing prolonged unavailability. 5-10 seconds is typical, with heartbeat extension for longer operations.

Fairness and Driver Experience

A matching system that only optimizes for rider wait time creates severe fairness problems for drivers:

Hotspot concentration: Drivers near busy areas get constant requests; drivers 1km away get none
Starvation: A driver could wait hours without a single trip despite being online
Gaming incentives: Drivers learn to crowd into known hotspots, creating supply imbalances

Why fairness matters:

Unhappy drivers leave the platform (supply crisis)
Drivers who feel the system is 'rigged' lose trust
Regulatory scrutiny (fair labor practices)
Legal exposure (driver classification lawsuits)

Fairness Mechanisms

Techniques for Fair Dispatch

•Time-since-last-trip bonus — Drivers who haven't had a trip recently get scoring boost, preventing starvation
•Randomized tie-breaking — When scores are similar, random selection rather than deterministic (prevents gaming)
•Rotation within zones — Track dispatch counts per driver per zone; balance over time
•Minimum guarantees — If a driver has been online for X minutes without a trip, prioritize them
•Long pickup distance limits — Don't send drivers more than Y km for pickup; prevents unfair long empty miles

fairness-adjusted-scoring.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function calculateFairScore(driver, baseScore, matchingContext):
    fairnessAdjustment = 0
    
    // Factor 1: Time since last trip
    minutesWaiting = (now() - driver.lastTripEndTime).toMinutes()
    if minutesWaiting > 5:
        // Progressive boost: +1 point per minute waiting, up to 15
        fairnessAdjustment += min(minutesWaiting - 5, 15)
    
    // Factor 2: Trips today relative to average
    cityAvgTripsToday = matchingContext.cityAverageTrips
    driverTripsToday = driver.tripsToday
    tripDeficit = cityAvgTripsToday - driverTripsToday
    if tripDeficit > 0:
        // +2 points for each trip below average, up to 10
        fairnessAdjustment += min(tripDeficit * 2, 10)
    
    // Factor 3: Long pickup penalty (protect driver from unfair requests)
    if matchingContext.pickupDistance > 3000:  // meters
        // Reduce score to give closer drivers preference
        fairnessAdjustment -= (matchingContext.pickupDistance - 3000) / 500
    
    // Factor 4: Acceptance rate protection
    // Don't penalize drivers for declining long pickups
    if driver.recentDeclines > 0:
        declinedLongPickups = driver.recentDeclinesForLongPickup
        adjustedDeclineRate = (driver.recentDeclines - declinedLongPickups) / driver.recentOffers
        // Only use adjusted rate in scoring
        
    return baseScore + fairnessAdjustment

Driver Destination Matching

Many drivers drive part-time and have a final destination (heading home after work). Matching them to trips going toward their destination:

Increases driver satisfaction (useful miles, not empty miles)
Reduces supply in the area they're leaving (natural rebalancing)
Increases supply in their destination area

destination-mode-matching.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function scoreWithDestinationMode(driver, rideRequest, baseScore):
    if driver.destinationMode == null:
        return baseScore  // No destination set
    
    // Calculate how well this trip aligns with driver's destination
    tripDirection = bearing(rideRequest.pickup, rideRequest.dropoff)
    driverDirection = bearing(rideRequest.dropoff, driver.destination)
    
    // Ideal: trip drops off driver closer to their destination
    distanceToDestinationBefore = haversine(driver.location, driver.destination)
    distanceToDestinationAfter = haversine(rideRequest.dropoff, driver.destination)
    
    if distanceToDestinationAfter < distanceToDestinationBefore:
        // Trip moves driver toward destination
        progressPercent = (distanceToDestinationBefore - distanceToDestinationAfter) / distanceToDestinationBefore
        destinationBonus = progressPercent * 30  // Up to 30 point bonus
        return baseScore + destinationBonus
    else:
        // Trip moves driver away from destination - don't assign
        return baseScore - 50  // Heavy penalty

Uber's Driver Destination Feature

Uber allows drivers to set a destination (with limited uses per day). The system then prioritizes trips heading toward that destination. This dramatically improves driver satisfaction for part-timers while also helping with supply rebalancing—drivers naturally flow toward underserved areas.

Machine Learning in Matching

Modern matching systems increasingly rely on machine learning to improve decision quality beyond hand-tuned scoring rules.

What ML Adds to Matching

1. Acceptance Probability Prediction

Predict whether a driver will accept a given trip:

Features: Driver's historical acceptance patterns, current earnings, time of day, pickup distance, trip value, driver's home location, etc.
Output: P(accept | driver, trip)
Use: Avoid offering trips to drivers likely to decline (wastes time, delays rider)

2. Trip Value Prediction

Predict the total value of a trip before confirmation:

Features: Origin, destination, day/time, weather, events, historical data
Output: Expected fare (considering surge, traffic, route variations)
Use: Show more accurate fare estimates; inform driver dispatching

3. Future Supply Prediction

Predict where drivers will be in 10-30 minutes:

Features: Current driver distribution, trip patterns, historical flows, events
Output: Expected supply density per zone
Use: Dispatch decisions that consider future supply, not just current

ml-enhanced-matching.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class MLEnhancedMatcher:
    acceptanceModel = loadModel("driver_acceptance_v12")
    tripValueModel = loadModel("trip_value_v8")
    
    async function scoreDriver(driver, rideRequest):
        // Traditional scoring
        baseScore = calculateBaseScore(driver, rideRequest)
        
        // ML: Acceptance probability
        acceptanceFeatures = extractAcceptanceFeatures(driver, rideRequest)
        acceptanceProbability = acceptanceModel.predict(acceptanceFeatures)
        
        // ML: Expected trip value for driver
        tripFeatures = extractTripFeatures(rideRequest)
        expectedTripValue = tripValueModel.predict(tripFeatures)
        
        // Combine: Expected value = P(accept) × Value if accept
        // We want drivers who will accept AND deliver good experience
        expectedValue = acceptanceProbability * (
            baseScore * 0.5 +  // Experience score
            expectedTripValue * 0.5  // Economic value
        )
        
        return {
            driver,
            baseScore,
            acceptanceProbability,
            expectedTripValue,
            finalScore: expectedValue
        }
    
    async function match(rideRequest):
        candidates = await getCandidateDrivers(rideRequest)
        
        // Score all candidates with ML models
        scoredCandidates = await Promise.all(
            candidates.map(d => scoreDriver(d, rideRequest))
        )
        
        // Filter low-acceptance drivers (don't waste time offering)
        likelyCandidates = scoredCandidates.filter(
            c => c.acceptanceProbability > 0.3
        )
        
        // Sort by expected value
        likelyCandidates.sortBy(c => -c.finalScore)
        
        // Sequential offers to maximize acceptance
        for candidate in likelyCandidates:
            result = await offerTrip(candidate.driver, rideRequest)
            if result.accepted:
                return candidate.driver
        
        return null  // No driver accepted

Training Data and Feedback Loop

ML models improve through feedback loops:

Log every match decision — Driver offered, accepted/declined, pickup time, rating
Measure outcomes — Actual pickup time vs. predicted, actual fare vs. predicted
Retrain periodically — Weekly model updates with recent data
A/B test new models — 5% traffic to new model, measure KPIs
Monitor for drift — Alert if prediction accuracy degrades over time

Example ML Features for Matching
Feature Category	Example Features	Model Used
Driver Profile	Historical acceptance rate, average rating, tenure, vehicle type	Acceptance prediction
Temporal	Hour of day, day of week, minutes until driver's shift ends	Acceptance prediction
Trip Characteristics	Pickup distance, trip length, estimated fare, surge multiplier	Acceptance + Value prediction
Context	Weather, nearby events, airport queue length	Value prediction
Historical	Driver's past responses to similar trips	Acceptance prediction

ML Model Risks

ML models can encode biases. If historical data shows drivers decline trips to certain neighborhoods (for any reason), the model may learn to avoid offering those trips—creating a self-reinforcing discrimination pattern. Careful monitoring for fairness across demographics and geographies is essential.

Summary: Matching Algorithm Mastery

The matching algorithm is the intellectual core of ride-sharing systems. Let's consolidate the key learnings:

Key Takeaways

•Greedy matching is insufficient — Simple nearest-driver assignment ignores road networks, driver trajectories, and global optimization opportunities.
•Multi-factor scoring balances objectives — ETA, driver rating, acceptance rate, fairness, and vehicle quality all contribute to optimal matching.
•Batch matching improves global efficiency — Accumulating requests over short windows and solving assignment problems produces better total outcomes than greedy.
•Concurrency control is critical — Optimistic locking, distributed locks, or actor models prevent double-booking race conditions.
•Fairness prevents driver churn — Time-since-last-trip bonuses, rotation mechanisms, and destination mode keep drivers satisfied and supply healthy.
•ML enhances human-designed rules — Acceptance prediction, value estimation, and supply forecasting improve matching quality when combined with domain-engineered scoring.

Matching Strategy Decision Guide
Scenario	Recommended Strategy	Rationale
Low volume (< 10 requests/min)	Greedy with multi-factor scoring	Batch window would add unnecessary latency
High volume (> 100 requests/min)	Batch matching with 2-3s window	Global optimization benefits outweigh latency
Event surge (concert ending)	Batch matching + queue management	Manage flash crowd fairly
Sparse areas	Greedy with extended radius	Few drivers means little optimization opportunity
Airport queue	FIFO queue (separate system)	Structured pickup area needs different model

What's Next

With matching fundamentals understood, we now turn to Surge Pricing—the dynamic pricing mechanism that balances supply and demand in real-time. You'll learn how to compute optimal price multipliers, communicate surge to users, and handle the complex interplay between pricing and marketplace dynamics.

3 / 6

Loading learning content...

System Design (HLD)Commerce & Infrastructure Systems

Uber / Lyft Ride-Sharing System Design

LevelAdvanced

Duration180 mins

TopicCommerce & Infrastructure Systems

3 / 6

Matching Algorithm: Dispatch Optimization

The Heart of Ride-Sharing

When a rider requests a trip, something remarkable happens in under 2 seconds:

The system identifies potentially thousands of nearby drivers
Calculates estimated pickup times for the most promising candidates
Scores each driver on dozens of factors
Atomically assigns the optimal driver (ensuring no double-booking)
Notifies both rider and driver in real-time

A 10% improvement in matching efficiency translates to:

Shorter wait times for riders (higher satisfaction, more trips)
Higher utilization for drivers (more earnings per hour)
Better unit economics for the platform (lower incentive spend)

The difference between good and great matching is worth billions annually for platforms like Uber and Lyft.

What You Will Learn

Matching System Architecture Overview

Before diving into algorithms, let's understand the overall architecture of a matching system and where it fits in the request flow.

Request-to-Match Flow

Converting Mermaid diagram...

Core Components

1. Matching Service

Orchestrates the matching process:

Receives ride requests from the Ride Service
Queries Location Service for nearby drivers
Enriches candidates with ETA data
Applies scoring model
Triggers assignment through Dispatch Service

2. Location Service

Provides spatial query capabilities (covered in previous page):

Returns drivers within specified radius
Filters by availability status
Returns driver metadata (vehicle type, rating)

3. ETA Service

Calculates travel times (covered in detail later):

Pickup ETA: Driver location → Rider location
Trip ETA: Pickup → Dropoff
Considers real-time traffic

4. Dispatch Service

Handles atomic assignment:

Locks driver for exclusive assignment
Sends push notification to driver
Manages accept/decline timeout
Handles reassignment if driver declines

Separation of Concerns

Greedy Matching Strategies

The simplest matching approach is greedy: for each ride request, immediately find and assign the single best driver. Let's explore greedy strategies in increasing sophistication.

Strategy 1: Nearest Driver

Assign the geographically closest available driver.

nearest-driver-matching.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
async function matchNearestDriver(rideRequest):
    // Query nearby drivers
    candidates = await locationService.getDriversInRadius(
        center = rideRequest.pickupLocation,
        radius = 5000,  // meters
        filters = {
            status: "available",
            vehicleType: rideRequest.vehicleType
        }
    )
    
    if candidates.isEmpty():
        return null  // No drivers available
    
    // Sort by straight-line distance (already sorted by GEORADIUS)
    nearestDriver = candidates[0]
    
    // Attempt assignment
    assigned = await dispatchService.assignDriver(
        driverId = nearestDriver.id,
        rideId = rideRequest.id
    )
    
    if assigned:
        return nearestDriver
    else:
        // Driver became unavailable, try next
        return matchNearestDriver(rideRequest)  // Recursive retry

Advantages

•Extremely simple — Trivial to implement and debug
•Very fast — Single sort operation, O(n log n)
•Low latency — No external API calls for ranking
•Deterministic — Same input always produces same output

Disadvantages

•Ignores road network — Straight-line distance ≠ travel time
•Ignores driver direction — Stationary closer driver vs. approaching farther driver
•No global optimization — Locally optimal may be globally suboptimal
•Unfair to distant drivers — Creates 'hot zones' where some drivers never get trips

Strategy 2: Lowest ETA

Assign the driver with the shortest actual pickup time, considering road network and traffic.

lowest-eta-matching.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
async function matchLowestETA(rideRequest):
    // Get candidates (limit to reasonable set to reduce ETA calls)
    candidates = await locationService.getDriversInRadius(
        center = rideRequest.pickupLocation,
        radius = 5000,
        filters = { status: "available", vehicleType: rideRequest.vehicleType },
        limit = 20  // Only top 20 by distance
    )
    
    if candidates.isEmpty():
        return null
    
    // Calculate ETAs in parallel
    etaPromises = candidates.map(driver => 
        etaService.getPickupETA(driver.location, rideRequest.pickupLocation)
    )
    etas = await Promise.all(etaPromises)
    
    // Combine and sort
    candidatesWithETA = zip(candidates, etas)
        .filter(([_, eta]) => eta != null)  // Remove failed lookups
        .sortBy(([_, eta]) => eta.seconds)
    
    // Assign best driver
    for ([driver, eta] in candidatesWithETA):
        assigned = await dispatchService.assignDriver(driver.id, rideRequest.id)
        if assigned:
            return {driver, eta}
    
    return null  // All candidates became unavailable

Improvement over nearest driver:

Scenario	Nearest Driver	Lowest ETA
Driver A: 800m away across highway	Assigned (closer)	Not assigned
Driver B: 1.2km away on same street	Skipped	Assigned (faster ETA)
Actual pickup time A	8 minutes (detour)	—
Actual pickup time B	—	3 minutes

Tradeoff: ETA calculation requires routing API calls, adding latency and cost. Limiting candidates to top N by distance keeps API costs manageable.

Strategy 3: Multi-Factor Scoring

Rank drivers using a composite score that balances multiple objectives:

multi-factor-scoring.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
function calculateDriverScore(driver, rideRequest, eta):
    // Initialize base score
    score = 0
    
    // Factor 1: Pickup ETA (primary factor)
    // Lower ETA = higher score
    // Normalize: 5-minute ETA = baseline score of 50
    etaScore = 100 - (eta.seconds / 300) * 50
    etaScore = clamp(etaScore, 0, 100)
    score += etaScore * 0.40  // 40% weight
    
    // Factor 2: Driver Rating
    // 5.0 rating = 50 points, 4.0 rating = 30 points
    ratingScore = (driver.rating - 4.0) * 20 + 30
    ratingScore = clamp(ratingScore, 0, 50)
    score += ratingScore * 0.15  // 15% weight
    
    // Factor 3: Acceptance Rate (driver reliability)
    // Higher acceptance = more reliable
    acceptanceScore = driver.acceptanceRate * 50
    score += acceptanceScore * 0.10  // 10% weight
    
    // Factor 4: Driver Direction Alignment
    // Is driver heading toward pickup?
    headingDiff = abs(driver.heading - bearingToPickup)
    if headingDiff < 30:  // Within 30 degrees
        score += 10 * 0.10  // Bonus for aligned direction
    
    // Factor 5: Fairness / Time Since Last Trip
    // Penalize drivers who just completed trips (give others a chance)
    minutesSinceLastTrip = (now() - driver.lastTripEndTime) / 60000
    fairnessBonus = min(minutesSinceLastTrip, 10)  // Cap at 10 minutes
    score += fairnessBonus * 0.10  // 10% weight
    
    // Factor 6: Vehicle Quality Match
    // Premium ride + premium car = bonus
    if rideRequest.isPremuim and driver.vehicleYear >= 2020:
        score += 15 * 0.15
    
    return score
 
// Usage in matching
candidatesWithScores = candidatesWithETA.map(([driver, eta]) => ({
    driver,
    eta,
    score: calculateDriverScore(driver, rideRequest, eta)
}))
.sortBy(c => -c.score)  // Descending by score

Scoring Weight Tuning

Batch Matching for Global Optimization

Greedy matching makes locally optimal decisions but can produce globally suboptimal outcomes. Consider this scenario:

Example: Greedy Suboptimality

Rider A requests a trip (arrives first)
Driver 1 is 2 minutes away; Driver 2 is 4 minutes away
Greedy assigns Driver 1 to Rider A
Rider B requests 5 seconds later, directly next to Driver 2
Driver 2 must drive 3 minutes to reach Rider B (Driver 1 was right there!)

Total wait time with greedy: 2 + 3 = 5 minutes

Optimal assignment: Driver 1 → Rider B (0.5 min), Driver 2 → Rider A (4 min) = 4.5 minutes

Batch matching solves this by accumulating ride requests and available drivers over a short window, then computing globally optimal assignments.

How Batch Matching Works

Converting Mermaid diagram...

The Assignment Problem Formulation

Batch matching is a classic bipartite matching problem:

Left vertices: Ride requests {R₁, R₂, ..., Rₙ}
Right vertices: Available drivers {D₁, D₂, ..., Dₘ}
Edge weights: Cost of assigning Dⱼ to Rᵢ (negative ETA score, so minimizing cost maximizes quality)
Goal: Find a matching that minimizes total cost

Mathematical Formulation:

Minimize: Σᵢ Σⱼ cᵢⱼ × xᵢⱼ

Subject to:
  Σⱼ xᵢⱼ ≤ 1  for all i (each ride gets at most one driver)
  Σᵢ xᵢⱼ ≤ 1  for all j (each driver gets at most one ride)
  xᵢⱼ ∈ {0, 1}

Where cᵢⱼ is the cost of assigning driver j to ride i, and xᵢⱼ is the assignment decision.

Hungarian Algorithm

The Hungarian algorithm (Kuhn-Munkres) solves the assignment problem optimally in O(n³) time:

Create n×m cost matrix (rides × drivers)
Row reduction: Subtract minimum of each row from all elements in that row
Column reduction: Subtract minimum of each column from all elements
Cover zeros with minimum lines
If lines = n, optimal assignment found; else, adjust matrix and repeat

batch-matching-implementation.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class BatchMatcher:
    BATCH_WINDOW_MS = 2000  // 2 second batching window
    
    pendingRides = []
    pendingDrivers = []
    
    @scheduled(every=BATCH_WINDOW_MS)
    async function runBatchMatching():
        if pendingRides.isEmpty():
            return
        
        // Snapshot current state
        rides = pendingRides.copy()
        drivers = pendingDrivers.copy()
        pendingRides.clear()
        pendingDrivers.clear()
        
        // Build cost matrix
        n = rides.length
        m = drivers.length
        costMatrix = new Matrix(n, m)
        
        for i in range(n):
            for j in range(m):
                // Cost = negative score (we minimize cost = maximize score)
                costMatrix[i][j] = -calculateMatchScore(rides[i], drivers[j])
        
        // Run Hungarian algorithm
        assignments = hungarianAlgorithm(costMatrix)
        
        // Execute assignments
        for (rideIdx, driverIdx) in assignments:
            ride = rides[rideIdx]
            driver = drivers[driverIdx]
            
            success = await dispatchService.assignDriver(driver.id, ride.id)
            if !success:
                // Driver became unavailable, requeue ride
                pendingRides.append(ride)
    
    function onNewRideRequest(ride):
        pendingRides.append(ride)
        
        // If waiting too long, force immediate greedy match
        if ride.waitingTime > MAX_WAIT_BEFORE_GREEDY:
            forceGreedyMatch(ride)
    
    function onDriverBecameAvailable(driver):
        pendingDrivers.append(driver)

Greedy vs. Batch Matching Comparison
Aspect	Greedy Matching	Batch Matching
Latency	< 100ms (immediate)	Up to batch window + computation (2-3 sec)
Optimality	Locally optimal only	Globally optimal within batch
Complexity	O(n log n) per request	O(n³) per batch
Best for	Low-volume periods	High-volume periods
Fairness	First-come-first-served bias	More equitable distribution
Implementation	Simple	Moderate complexity

Hybrid Approach in Production

Concurrency Control and Atomic Assignment

The most critical correctness requirement in matching is: A driver can only be assigned to one ride at a time. Double-booking creates terrible experiences and operational nightmares.

But with 1,000+ matching attempts per second, concurrent assignment attempts to the same driver are common. We need robust concurrency control.

The Double-Booking Race Condition

race-condition-example.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// DANGEROUS: Race condition without proper locking
 
// Thread 1: Matching ride A
driver = findBestDriver(rideA)  // Returns driver_123
if driver.status == "available":  // CHECK
    driver.status = "assigned"    // SET
    createAssignment(rideA, driver)
 
// Thread 2: Matching ride B (concurrent)
driver = findBestDriver(rideB)  // Also returns driver_123!
if driver.status == "available":  // Also passes CHECK (data stale!)
    driver.status = "assigned"    // SET again - DOUBLE BOOKING!
    createAssignment(rideB, driver)
 
// Result: driver_123 is assigned to BOTH rides

Solution 1: Optimistic Locking with Version Numbers

Each driver record has a version number. Updates succeed only if the version matches expected value.

optimistic-locking.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
async function assignDriverOptimistic(driverId, rideId):
    MAX_RETRIES = 3
    
    for attempt in range(MAX_RETRIES):
        // Read current state with version
        driver = await db.query("""
            SELECT id, status, version FROM drivers WHERE id = $1
        """, [driverId])
        
        if driver.status != "available":
            return {success: false, reason: "driver_unavailable"}
        
        // Attempt atomic update with version check
        result = await db.query("""
            UPDATE drivers 
            SET status = 'assigned', current_ride_id = $1, version = version + 1
            WHERE id = $2 AND version = $3 AND status = 'available'
            RETURNING id
        """, [rideId, driverId, driver.version])
        
        if result.rowCount == 1:
            // Success - we won the race
            await createTrip(rideId, driverId)
            await notifyDriver(driverId, rideId)
            return {success: true}
        
        // Version mismatch - someone else updated, retry
        await sleep(random(10, 50))  // Jittered backoff
    
    return {success: false, reason: "contention_exceeded"}

Solution 2: Distributed Locking with Redis

For systems where the database isn't the source of truth for driver availability (e.g., Redis-based location system), use distributed locks.

distributed-locking.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
async function assignDriverWithLock(driverId, rideId):
    lockKey = f"driver_lock:{driverId}"
    lockValue = generateUUID()  // Unique per attempt
    lockTTL = 5000  // 5 second max lock duration
    
    // Attempt to acquire lock
    acquired = await redis.set(lockKey, lockValue, "NX", "PX", lockTTL)
    
    if not acquired:
        return {success: false, reason: "driver_locked"}
    
    try:
        // Check availability (with lock held, this is safe)
        driverMeta = await redis.hGetAll(f"driver:{driverId}")
        
        if driverMeta.status != "available":
            return {success: false, reason: "driver_unavailable"}
        
        // Perform assignment
        pipeline = redis.pipeline()
        pipeline.hSet(f"driver:{driverId}", "status", "assigned")
        pipeline.hSet(f"driver:{driverId}", "current_ride", rideId)
        pipeline.sRem(f"available_drivers:{driverMeta.city_id}", driverId)
        await pipeline.exec()
        
        // Persist to database (async, can be eventually consistent)
        await db.createTrip(rideId, driverId)
        
        return {success: true}
        
    finally:
        // Release lock (only if we still own it)
        await redis.eval("""
            if redis.call('get', KEYS[1]) == ARGV[1] then
                return redis.call('del', KEYS[1])
            else
                return 0
            end
        """, [lockKey], [lockValue])

Solution 3: Sharded Actor Model

Partition drivers into shards, each managed by a single actor/worker that serializes all assignment decisions for its drivers.

Converting Mermaid diagram...

Actor model advantages:

No locks needed—single-threaded processing per shard
Deterministic ordering—makes debugging easier
Natural affinity—driver state stays in actor's memory
Scales horizontally—add more actors for more drivers

Lock Timeout Considerations

Fairness and Driver Experience

A matching system that only optimizes for rider wait time creates severe fairness problems for drivers:

Hotspot concentration: Drivers near busy areas get constant requests; drivers 1km away get none
Starvation: A driver could wait hours without a single trip despite being online
Gaming incentives: Drivers learn to crowd into known hotspots, creating supply imbalances

Why fairness matters:

Unhappy drivers leave the platform (supply crisis)
Drivers who feel the system is 'rigged' lose trust
Regulatory scrutiny (fair labor practices)
Legal exposure (driver classification lawsuits)

Fairness Mechanisms

Techniques for Fair Dispatch

•Time-since-last-trip bonus — Drivers who haven't had a trip recently get scoring boost, preventing starvation
•Randomized tie-breaking — When scores are similar, random selection rather than deterministic (prevents gaming)
•Rotation within zones — Track dispatch counts per driver per zone; balance over time
•Minimum guarantees — If a driver has been online for X minutes without a trip, prioritize them
•Long pickup distance limits — Don't send drivers more than Y km for pickup; prevents unfair long empty miles

fairness-adjusted-scoring.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function calculateFairScore(driver, baseScore, matchingContext):
    fairnessAdjustment = 0
    
    // Factor 1: Time since last trip
    minutesWaiting = (now() - driver.lastTripEndTime).toMinutes()
    if minutesWaiting > 5:
        // Progressive boost: +1 point per minute waiting, up to 15
        fairnessAdjustment += min(minutesWaiting - 5, 15)
    
    // Factor 2: Trips today relative to average
    cityAvgTripsToday = matchingContext.cityAverageTrips
    driverTripsToday = driver.tripsToday
    tripDeficit = cityAvgTripsToday - driverTripsToday
    if tripDeficit > 0:
        // +2 points for each trip below average, up to 10
        fairnessAdjustment += min(tripDeficit * 2, 10)
    
    // Factor 3: Long pickup penalty (protect driver from unfair requests)
    if matchingContext.pickupDistance > 3000:  // meters
        // Reduce score to give closer drivers preference
        fairnessAdjustment -= (matchingContext.pickupDistance - 3000) / 500
    
    // Factor 4: Acceptance rate protection
    // Don't penalize drivers for declining long pickups
    if driver.recentDeclines > 0:
        declinedLongPickups = driver.recentDeclinesForLongPickup
        adjustedDeclineRate = (driver.recentDeclines - declinedLongPickups) / driver.recentOffers
        // Only use adjusted rate in scoring
        
    return baseScore + fairnessAdjustment

Driver Destination Matching

Many drivers drive part-time and have a final destination (heading home after work). Matching them to trips going toward their destination:

Increases driver satisfaction (useful miles, not empty miles)
Reduces supply in the area they're leaving (natural rebalancing)
Increases supply in their destination area

destination-mode-matching.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function scoreWithDestinationMode(driver, rideRequest, baseScore):
    if driver.destinationMode == null:
        return baseScore  // No destination set
    
    // Calculate how well this trip aligns with driver's destination
    tripDirection = bearing(rideRequest.pickup, rideRequest.dropoff)
    driverDirection = bearing(rideRequest.dropoff, driver.destination)
    
    // Ideal: trip drops off driver closer to their destination
    distanceToDestinationBefore = haversine(driver.location, driver.destination)
    distanceToDestinationAfter = haversine(rideRequest.dropoff, driver.destination)
    
    if distanceToDestinationAfter < distanceToDestinationBefore:
        // Trip moves driver toward destination
        progressPercent = (distanceToDestinationBefore - distanceToDestinationAfter) / distanceToDestinationBefore
        destinationBonus = progressPercent * 30  // Up to 30 point bonus
        return baseScore + destinationBonus
    else:
        // Trip moves driver away from destination - don't assign
        return baseScore - 50  // Heavy penalty

Uber's Driver Destination Feature

Machine Learning in Matching

Modern matching systems increasingly rely on machine learning to improve decision quality beyond hand-tuned scoring rules.

What ML Adds to Matching

1. Acceptance Probability Prediction

Predict whether a driver will accept a given trip:

Features: Driver's historical acceptance patterns, current earnings, time of day, pickup distance, trip value, driver's home location, etc.
Output: P(accept | driver, trip)
Use: Avoid offering trips to drivers likely to decline (wastes time, delays rider)

2. Trip Value Prediction

Predict the total value of a trip before confirmation:

Features: Origin, destination, day/time, weather, events, historical data
Output: Expected fare (considering surge, traffic, route variations)
Use: Show more accurate fare estimates; inform driver dispatching

3. Future Supply Prediction

Predict where drivers will be in 10-30 minutes:

Features: Current driver distribution, trip patterns, historical flows, events
Output: Expected supply density per zone
Use: Dispatch decisions that consider future supply, not just current

ml-enhanced-matching.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class MLEnhancedMatcher:
    acceptanceModel = loadModel("driver_acceptance_v12")
    tripValueModel = loadModel("trip_value_v8")
    
    async function scoreDriver(driver, rideRequest):
        // Traditional scoring
        baseScore = calculateBaseScore(driver, rideRequest)
        
        // ML: Acceptance probability
        acceptanceFeatures = extractAcceptanceFeatures(driver, rideRequest)
        acceptanceProbability = acceptanceModel.predict(acceptanceFeatures)
        
        // ML: Expected trip value for driver
        tripFeatures = extractTripFeatures(rideRequest)
        expectedTripValue = tripValueModel.predict(tripFeatures)
        
        // Combine: Expected value = P(accept) × Value if accept
        // We want drivers who will accept AND deliver good experience
        expectedValue = acceptanceProbability * (
            baseScore * 0.5 +  // Experience score
            expectedTripValue * 0.5  // Economic value
        )
        
        return {
            driver,
            baseScore,
            acceptanceProbability,
            expectedTripValue,
            finalScore: expectedValue
        }
    
    async function match(rideRequest):
        candidates = await getCandidateDrivers(rideRequest)
        
        // Score all candidates with ML models
        scoredCandidates = await Promise.all(
            candidates.map(d => scoreDriver(d, rideRequest))
        )
        
        // Filter low-acceptance drivers (don't waste time offering)
        likelyCandidates = scoredCandidates.filter(
            c => c.acceptanceProbability > 0.3
        )
        
        // Sort by expected value
        likelyCandidates.sortBy(c => -c.finalScore)
        
        // Sequential offers to maximize acceptance
        for candidate in likelyCandidates:
            result = await offerTrip(candidate.driver, rideRequest)
            if result.accepted:
                return candidate.driver
        
        return null  // No driver accepted

Training Data and Feedback Loop

ML models improve through feedback loops:

Log every match decision — Driver offered, accepted/declined, pickup time, rating
Measure outcomes — Actual pickup time vs. predicted, actual fare vs. predicted
Retrain periodically — Weekly model updates with recent data
A/B test new models — 5% traffic to new model, measure KPIs
Monitor for drift — Alert if prediction accuracy degrades over time

Example ML Features for Matching
Feature Category	Example Features	Model Used
Driver Profile	Historical acceptance rate, average rating, tenure, vehicle type	Acceptance prediction
Temporal	Hour of day, day of week, minutes until driver's shift ends	Acceptance prediction
Trip Characteristics	Pickup distance, trip length, estimated fare, surge multiplier	Acceptance + Value prediction
Context	Weather, nearby events, airport queue length	Value prediction
Historical	Driver's past responses to similar trips	Acceptance prediction

ML Model Risks

Summary: Matching Algorithm Mastery

The matching algorithm is the intellectual core of ride-sharing systems. Let's consolidate the key learnings:

Key Takeaways

•Greedy matching is insufficient — Simple nearest-driver assignment ignores road networks, driver trajectories, and global optimization opportunities.
•Multi-factor scoring balances objectives — ETA, driver rating, acceptance rate, fairness, and vehicle quality all contribute to optimal matching.
•Batch matching improves global efficiency — Accumulating requests over short windows and solving assignment problems produces better total outcomes than greedy.
•Concurrency control is critical — Optimistic locking, distributed locks, or actor models prevent double-booking race conditions.
•Fairness prevents driver churn — Time-since-last-trip bonuses, rotation mechanisms, and destination mode keep drivers satisfied and supply healthy.
•ML enhances human-designed rules — Acceptance prediction, value estimation, and supply forecasting improve matching quality when combined with domain-engineered scoring.

Matching Strategy Decision Guide
Scenario	Recommended Strategy	Rationale
Low volume (< 10 requests/min)	Greedy with multi-factor scoring	Batch window would add unnecessary latency
High volume (> 100 requests/min)	Batch matching with 2-3s window	Global optimization benefits outweigh latency
Event surge (concert ending)	Batch matching + queue management	Manage flash crowd fairly
Sparse areas	Greedy with extended radius	Few drivers means little optimization opportunity
Airport queue	FIFO queue (separate system)	Structured pickup area needs different model

What's Next

3 / 6