Matchmaking in Lyft Line — Part 2
In part one of this series, we talked about the timing and design around our launch of Lyft Line. We described the basics of matchmaking and that we built a greedy Haversine system to get up and running quickly. Finally, we mentioned some of the limitations of our algorithm and issues that quickly arose. In this post, we’ll talk about some of the advancements we made that led to improvements to our passenger’s experience, to our system’s cost savings, and to the performance of our back-end servers.
Improving the Passenger Experience
We launched Line on Wednesday August 6th, 2014, the week of Outside Lands — a large music festival in San Francisco. We thought this was the perfect weekend to launch a ride-sharing product: there would be copious amounts of cost-sensitive and friendly millennials heading to Golden Gate park to listen to famous artists like Kanye West, Macklemore and Tom Petty. This also meant that passengers would be sharing almost the exact same drop-off or pickup — perfect for our matching algorithm.
What we didn’t realize until Day 1 of the festival, though, was that Golden Gate park would be impossible for drivers to traverse as traffic would be gridlocked, and our Haversine algorithm would probably be matching passengers on opposite sides of the park. Given the time constraints (3 hours until the first show), one of our engineers added some incredibly generic code to help reject matches across the park[1].
Obviously this code wasn’t ideal, but we had to move fast.
Geohashing
Outside Lands illuminated the fact that we needed to get away from using haversine estimates as they were just too inaccurate. We considered building a routing graph and using the A* algorithm, similar to OSRM and something we had done for our pricing estimates, but we knew it wouldn’t scale in our O(n^2) algorithm[2] without an investment in offline computational techniques like contraction hierarchies and a lot of work on building a scalable system. It was too early on in the product’s development to invest in that amount of work and so what we built instead was a geohash based model for estimates.
Geohashing is a technique for bucketing latitude and longitude coordinates. Using historical data from past Lyft rides, we could record the average speed of our rides from one geohash to another and store that in a simple hash-table lookup. Then, when calculating estimates, we would multiply the haversine distance between those two points with this speed to figure out a time estimate. This approach proved to be much more accurate and helped us avoid matching through mountains and to differentiate between highway and street travel. It was also very efficient (nested hash table O(1) lookup), but still didn’t do a great job of resolving one-way streets or rush-hour traffic as our estimates were the same for all hours of the day.
Fortunately, the geohash model was quick to implement and worked fairly well. We added another nested hash table for each hour of the week between origin and destination which reduced our inaccuracies around rush hour, and were able to continually iterate on this model to improve our estimates. This approach also became more accurate as we collected more data as we could break our model down into smaller geohash sizes.
As we started to reduce the error inherent to some of our initial naïve estimation techniques, the feedback we started to receive around bad matches became more focused around experiential issues. Many of these were less than obvious, and ultimately led to a bad passenger experience. For example, we learned that passengers are very sensitive to going backwards, even more than the proportional additional detour it added. Users would often rather have a 10 min detour that had no backtracking then a 5 minute detour with backtracking. We also learned that people would rather have a short pick up time and long detour than vice versa, even if it meant a longer overall route.
Many of these learnings are the types of things you can’t predict until building a product, but end up contributing to the polished experience your passengers expect. When we first built Line, we had 2 initial constraints — detour and pickup time. Now we have over 30.
Efficiency and Efficiency improvements
At this point, we had spent a lot of time focusing on passenger experience, but not a lot of time on product efficiency improvements that would let us provide larger discounts. So far, we had only considered putting two passengers together in a route. This left a lot of efficiency on the table — more passengers in the car at the same time meant more cost savings we could give back to our users. The obvious next step for us was to introduce Triple Matching — the ability to add a third, and fourth, passenger to the car.
Triple Matching
Triple Matching added significant efficiency to our system by increasing our average match rate[3], but also created a scaling nightmare. With two passengers in the car we had four permutations to consider, but with up to four passengers that meant we could now have routes such as ABCBCA or even ABACBDCD [4], adding up to a total of 1,776 permutations. This meant we had to quickly scale the efficiency of our system to handle this load, and also brought with it a new set of requirements for maintaining a good passenger experience.
One route that quickly became evident as a bad experience was ABCDBCDA. That’s six stops between pickup and drop-off for passenger A. Even on a route with no detours, that would be a long ride given the extra time it takes for pickup and drop-offs. Additionally, though we asked users how many riders they had in their party, if any rider reported an incorrect number, drivers would have to awkwardly decide how to handle the fifth passenger. Lastly, although riding in a full car with four others is ultimately the most efficient route we can make, it doesn’t always create the best experience[5]. To adjust for these issues, more constraints were added to the system, and we focused on how to handle the level of scale that was required to support all permutations.
Horizontally scaling a system with no clear partitioning pattern is difficult — tree structures (BSPs, quadtrees, etc) don’t work well when two pickups could be in different partitions yet still be a great match (e.g. riders could have origins 15 minutes apart), and we were building towards a future allowing continual matching at any point along the route. Solving this was difficult and is beyond the scope of this post, but one optimization we made was Longitudinal Sorting.
Longitudinal Sorting
One of our constraints for making a good match was the time it took for a passenger to be picked up. If it took 15 minutes to get picked up, it didn’t matter how fast the rest of the route was — passengers wouldn’t consider that an acceptable route. 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. If we sorted all of the passengers in San Francisco from west to east, we didn’t need to compare someone in the Outer Sunset with someone in the Marina. This didn’t change the complexity of our system, it was still O(n^2), but it did give us a huge boost in efficiency. This is one example of a constraint built for passenger experience that actually allows us to reduce the problem space and help scale our system.
Rerouting
With improvements to our system performance, like the longitudinal sort, we were next able to tackle another milestone in Lyft Line efficiency gains: rerouting. Up until this point we had only been willing to add a passenger to a route if it didn’t change the driver’s next stop. That meant that in a |AA route (where the vertical bar is the driver), we couldn’t turn this into a |BABA route as we would have to change the driver’s first pick up from passenger A to passenger B. Similarly, in an AB|AB route, where both passengers had already been picked up, we couldn’t add passenger C to make it AB|CABC, though we could do AB|ACBC.
There were multiple reasons to disallow rerouting, both on the technical and user-experience fronts. Imagine being 1 block away from your drop-off and the driver is told to turn right and pick up another passenger. Or even worse, the driver picked up the first passenger and merged onto a freeway onramp only to be told to get off the freeway, go backwards, and pick up a second passenger. It was a risky change, but for efficiency junkies like us, the gains were too tempting to ignore. Like most things at Lyft, we A/B tested it and made sure to add safe guards to prevent a bad user experience. Routes wouldn’t be rerouted if the driver was about to drop off a passenger, and we added some clever tricks to identify when a driver was about to get onto an onramp. All in all rerouting added quite a bit of efficiency gains and we were able to ship it with a minimal hit to the passenger experience.
At this point, we had implemented some of the more obvious efficiency features (many of which we haven’t talked about) and were reaching the limitations of a greedy system. Triple Matching was giving us huge wins, as was Rerouting, but we weren’t able to take full advantage of the volume of rides we were starting to see. As Line ridership passed that of Lyft Classic in San Francisco, we needed to not just choose the first acceptable match for a rider, but to optimize the entire system. Coming next time: more efficiency improvements on the road to becoming less Greedy.
Read the third and final part of the series here.
[1] Internally referred to as the “Golden Gate Mason Dixon Line”
[2] Our O(n^2) algorithm is described in Part 1.
[3] The Match Rate is calculated by dividing the number of passenger ride requests by the number of routes (driver rides). A match rate of 2.0 means that, on average, every rider is paired with another rider.
[4] For a refresher on what these letters mean, read the first post of the series.
[5] Lies! Who doesn’t love a full car?
If you’re interested in building the future of ridesharing, Lyft is hiring! Shoot me a message on Twitter or email me at tim@lyft.com