[Review] Matchmaking in Lyft Line

https://eng.lyft.com/matchmaking-in-lyft-line-part-3-d8f9497c0e51#.rzljpynuz

Matchmaking in Lyft Line

Basic Matching System

- Haversine system(greedy)

- Bucketed matching system : bucket interval -> stay in matching pool for 10m  

: a variable bucket interval would allow us to adapt to lower density:

 

 

2 constraints

1) detour time = ABA - AA  = travel time when matched - when unmatched

2) pick up time = |A 

for 2nd passenger(like B) -> less detour time but increased pickup time

 

Preference of passengers --> Get polished experience after building a product

- Go backward X ex) 10 min detour with no backtracking (better) > 5m with backtracking

- short pickup time (better) > long detour time

- angle of the lines on map affects satisfaction

-  2 initial constraints(detour and pickup time)--> Now, over 30 :-((

 

Geohashing

A*algorithm -> hard to scale in O(n^2) 

So, Geohashing!
record avg speed of one geohash to another in simple hash-table lookup (O(1) lookup)

multiply haversine distance and calculate time estimate

--> Advantage: much more accurate & avoid weird matching

--> Not Yet Resolved: one-way streets, rush-hour traffic

 

Hash table for each hour of week -->  can break model down into smaller geohash sizes

 

 

Efficiency improvements

match 2 passengers -> 3 -> 4 -> 

 

Triple Matching

increased match rate but scaling problem

2 passenger = 4 permutations vs 4 passenger = 1776 permutations to consider

 

*Issues

ABCDBCDA -> bad experience for A (b/c 6stops -> takes extra pickup, drop-offs time)

drivers would have to awkwardly decide how to handle the fifth passenger

the most efficient route we can make, it doesn’t always create the best experience

==> how to handle the level of scale that was required to support all permutations !

 

 

Longitudinal Sorting

For less pick up time 

 This meant that when considering pairing A and B together, there was some maximum distance they could be apart from each other. What we discovered, was that we could leverage this in our outer loop: if we sorted the outer and inner loops by longitude, we could short circuit out of that loop when we’ve passed this maximum distance.

 

Rerouting

Until now) add a passenger if it didn't change the driver's next stop

 AB|CABC (disallowed) vs AB|ACBC (allowed) , | = driver

 

New Policy)

- Reroute, If not about to drop off & about to get onto an onramp

 

Become less Greedy

- find best possible match

- consider all riders & predict future demand

--> maximum matching problem for a weighted graph combined with elements of a Secretary Problem

Secretary problem - Wikipedia

 

Rouote Swapping(Express Re-route)

- take a rider from one route, and swap them into another route &  passenger could be swapped before pickup

-> increasing matching window from 60 seconds to a few minutes as we could keep looking for a better route even if we had already chosen a driver

 

- Advantage : reduce the burden of predicting future demand

- some issue so, only reroute when reducing pickup or detour time 

 

Matching Exchange

before) keep comparing riders if possibile to put an unmatched rider into a route

Plus) compare matched riders with other existing routes

-> doing millions of comparisons a second, in hopes that a driver’s positional update might open up a match that wasn’t valid before

- wait for accumulating enough number of rides -> optimize to reduce the total detour, pickup time, and cost of the entire system

 

- Identifying the right partitioning pattern and solving for optimal system efficiency is the secret sauce behind our Matching Exchange.

 

The Road Ahead

-Hotspots: aggregate demand

-Standby: wait upto 10m -> increasing matching window