<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by timothybrownsf on Medium]]></title>
        <description><![CDATA[Stories by timothybrownsf on Medium]]></description>
        <link>https://medium.com/@timothybrownsf?source=rss-9586ebbfe412------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*SdElf96aPg7E0CCmny6YFg.png</url>
            <title>Stories by timothybrownsf on Medium</title>
            <link>https://medium.com/@timothybrownsf?source=rss-9586ebbfe412------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Mon, 16 Nov 2026 01:15:41 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@timothybrownsf/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Ramblings on Experimentation Pitfalls, Part 1.]]></title>
            <link>https://eng.lyft.com/ramblings-on-experimentation-pitfalls-dd554ff87c0e?source=rss-9586ebbfe412------2</link>
            <guid isPermaLink="false">https://medium.com/p/dd554ff87c0e</guid>
            <category><![CDATA[experimentation]]></category>
            <category><![CDATA[lyft]]></category>
            <category><![CDATA[marketplaces]]></category>
            <category><![CDATA[data-science]]></category>
            <dc:creator><![CDATA[timothybrownsf]]></dc:creator>
            <pubDate>Fri, 19 May 2017 20:50:59 GMT</pubDate>
            <atom:updated>2017-05-30T18:53:59.166Z</atom:updated>
            <content:encoded><![CDATA[<h3>Rollouts via changing variant distribution</h3><p>A common pitfall we see when people try to rollout an experiment, is to rollout by changing the distribution of the variants. I’ll give an example below to demonstrate how this leads to biased results.</p><p>Let’s take the story of Bob, the online mango salesman who is interested in testing to see if he can increase his prices to make more money. Currently he sells mangos for $5.00 each (after all, they are <em>Alphonso</em> mangos), and he wants to see how it would effect business if he increased prices by 50 cents. He sets up an experiment with two variants, control and treatment, and sets the price for mangos to be $5 for control and $5.50 for treatment. He’s worried about rolling this out to 100% of users, as his livelihood depends on mango sales, so he starts with a 90/10 split (control/treatment). After a week he decides it seems safe and rolls it out to 50/50.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/484/1*5hwaYznjaih2phvoc8x7_w.png" /><figcaption>Alphonso Mangos (my favorite)</figcaption></figure><p>He waits another week* and then starts to analyze the experiment. Looking at analytics events he finds that there were 100 users the first week (split 90/10) and 100 users the second week (split 50/50). He happened to have no repeat visitors (how convenient for the math)! This means there were a total of 140 users in control and 60 in treatment. He then looks at total mangos purchased and total revenue. 90 mangos were purchased the first week for the control group, and 10 for the treatment. In the second week there were 25 mangos purchased for the control group and 25 for the treatment group. He adds this up and sees that there were a total of 115 mangos for control and 35 for the treatment group.</p><p>Now let’s do some math.</p><p><em>115 mangos / 140 users = .82 mangos per user for control<br>35 mangos / 60 users = .58 mangos per user for treatment</em></p><p>Clearly this 50 cent increase doesn’t pay off, even if we look at it in terms of total revenue:</p><p><em>.82 * $5.00 = $4.10 per user for the control<br>.58 * $5.50 = $3.19 per user for the treatment</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/570/1*zG4jFNqW42CWuc7m8XmPjw.png" /></figure><p>Bob turns off his experiment and decides that he was doing just fine selling mangos at $5 a pop.</p><h3>Wait! Bob was wrong!</h3><p>This is an example of a common mistake that we see people making in experimentation. The reality is that the treatment ($5.50 per mango) actually performed better, and here’s why.</p><p>Unbeknownst to the mango salesman, there was some bad news on CNN (who knows if it’s real…) about an international mango virus, which was announced at the start of the second week of the experiment. Notice that mango purchases changed from 1 per person in the first week (90/10 mangos for 90/10 users) to .5 per person in the second week (25/25 mangos for 50/50 users). However, in both week 1 and week two, the <strong>number of mangos per person was equal between control and treatment</strong>.</p><p>This can be seen when plotted out on a weekly graph of mangos per user for control vs treatment, but when looking at cumulative numbers, it is biased due to the distribution change between variants. This actually means in both weeks of the experiment, <strong>the treatment performed better on a revenue per customer basis.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/510/1*rXuqKcBVJ1MxSs5ve6kUmw.png" /><figcaption>Mangos per Customer</figcaption></figure><h3>So how do we solve this?</h3><p>We introduce a new concept of a rollout, which is separate from variant distribution. It means you keep your experiment at 50/50 the entire time, but start by only rolling it out to 20% of users, then ramp that up to 80% of users. What this actually means under the hood is that we have a third variant, called “Holdout”, which is not included in analysis, and we start with 10/10/80 (control / treatment / holdout). Then as we increase the rollout, we do so by adding users from the holdout group so it becomes 50/50/0.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/774/1*mRQAY5ulr1QpBC7rs9Vs8Q.png" /><figcaption>Rolled out with a Holdout</figcaption></figure><p>If Bob had used a holdout he’d actually be making $.50 more per mango (since mango sales per user did not change between control and treatment). That means Bob would be bringing home an extra 10%!</p><p>This pitfall is actually an example of the Simpson’s Paradox. Check out the <a href="https://en.wikipedia.org/wiki/Simpson%27s_paradox">Wikipedia</a> entry for more examples.</p><blockquote>* A week is an arbitrary amount of time and should not be taken as the correct time-frame to analyze an experiment. An entire post could be dedicated to the challenges of identifying the correct length of time to wait to analyze an experiment.</blockquote><p>Interested in experimentation and having a big impact? Lyft is hiring! Drop me a note on <a href="https://twitter.com/TimothyBrownSF">Twitter</a> or at <a href="/service/mailto:mklein@lyft.com">tim@lyft.com</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=dd554ff87c0e" width="1" height="1" alt=""><hr><p><a href="https://eng.lyft.com/ramblings-on-experimentation-pitfalls-dd554ff87c0e">Ramblings on Experimentation Pitfalls, Part 1.</a> was originally published in <a href="https://eng.lyft.com/">Lyft Engineering</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Matchmaking in Lyft Line]]></title>
            <link>https://eng.lyft.com/matchmaking-in-lyft-line-part-3-d8f9497c0e51?source=rss-9586ebbfe412------2</link>
            <guid isPermaLink="false">https://medium.com/p/d8f9497c0e51</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[lyft]]></category>
            <category><![CDATA[ridesharing]]></category>
            <category><![CDATA[engineering]]></category>
            <category><![CDATA[marketplaces]]></category>
            <dc:creator><![CDATA[timothybrownsf]]></dc:creator>
            <pubDate>Wed, 20 Apr 2016 16:38:09 GMT</pubDate>
            <atom:updated>2016-04-20T16:39:28.381Z</atom:updated>
            <content:encoded><![CDATA[<h3>Matchmaking in Lyft Line — Part 3</h3><p>This is the final post of a three part series around the history of Lyft Line. In the <a href="https://eng.lyft.com/matchmaking-in-lyft-line-9c2635fe62c4#.le50784zs">first post</a> we talked about our motivation and some design decisions we considered when building the product, including an alternate version of Line that we decided not to build. We also talked a bit about the initial implementation of our matchmaking algorithm and the main constraints we put in place — pickup and detour time. This system was built fast and we quickly started to see its limitations.</p><p>In the <a href="https://eng.lyft.com/matchmaking-in-lyft-line-691a1a32a008#.w6cx1kt65">second post</a>, we talked about how we improved the Line experience by addressing issues such as backtracking and predicting rush hour traffic. We also talked about Triple Matching — the ability to match up to four passengers — and the changes we made, like Longitudinal Sorting, to build an efficient system that could handle the exponential increase in comparisons needed for this feature. Lastly, we talked about Rerouting, an efficiency feature that let us change a driver’s route mid-ride to pick up a passenger along the way.</p><p>This post will focus on some of the more recent changes we’ve made as we’ve continued to work on efficiency gains. Many of these features have unlocked massive cost savings for our passengers, as ultimately the more efficient our system is, the greater the discount we can provide.</p><h4>The Road to Becoming Less Greedy</h4><p>There were many efficiency gains along the way, but the next major development in our algorithm was to adapt to a well established product with high demand. Our greedy algorithm was built to find <em>a</em> match, and we made the first match that came along. As Line grew to become the <a href="http://venturebeat.com/2015/03/16/lyft-ceo-says-lyft-line-now-accounts-for-majority-of-rides-in-san-francisco/">majority of Lyft rides in San Francisco</a>, we could no longer just pick the first match we found as that was leaving significant efficiency on the table. We instead had to find the best possible match. This included considering all riders in our system in addition to predicting future demand.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/270/1*sICSglgYVz7V-W36QJhfAw.png" /></figure><p>For those interested in Algorithms, this became something of a <a href="https://en.wikipedia.org/wiki/Matching_(graph_theory)">maximum matching</a> problem for a weighted graph combined with elements of a <a href="https://en.wikipedia.org/wiki/Secretary_problem">Secretary Problem</a>. The optimal solution would combine an accurate prediction of future demand with an algorithm that optimized for all possible matches before making any one. Overhauling our architecture to solve the problem in this way was an ambitious change, and given our agile culture, we realized there was an intermediary step we could take along the way — Route Swapping.</p><h4>Route Swapping (a.k.a Express Re-route)</h4><p><a href="http://www.buzzfeed.com/johanabhuiyan/lyft-is-trying-to-make-line-more-efficient#.ipkp4PW9k">Route Swapping</a> was a feature that would take a rider from one route, and swap them into another route. The passenger could be swapped before pickup and would be notified via SMS that we had a found a more efficient route for them. This gave us the ability to re-match passengers after they had already been matched if we found a more optimal pairing — essentially increasing our 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. An example of this is shown in the animation below, where passenger A is swapped from Route 2 to Route 1 after our system identified that the combined efficiency was more optimal with this pairing.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*xFxV6g6glGL8eFQZ." /><figcaption>Route Swapping passenger A into Route 1</figcaption></figure><p>Route Swapping reduced the burden of having to predict future demand, but also came with its own challenges. For example, if during our initial match we told a passenger that they would be picked up in six minutes, they might take that time to make breakfast or brush their teeth. If we then swapped them to a new route with only a 30 second pickup time, they might be unavailable and miss their ride. Similarly, if we had found an initial match with a low pickup time (e.g. one minute), but then found a better match that had a four minute pickup time (and perhaps a much smaller detour), the passenger might now have to wait on the curb for three more minutes — not the best user experience. In all scenarios, we would only swap the passenger if the new route reduced their pickup or detour time, but we had to be cautious about making drastic changes[1]. Needless to say, Route Swapping came with its own constraints but led to significant efficiency gains, and more importantly, faster rides for our passengers.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/176/1*TgrbjI0u8b8haBS0kvgnsA.png" /></figure><h4>Matching Exchange</h4><p>After we had Route Swapping in place we began to whittle away on a more optimal solution. As mentioned before, this is a weighted maximal matching problem and solving this required many changes to our algorithm. Previously, our matching algorithm would constantly try to compare riders to see if we could put an unmatched rider into a route. When we added Route Swapping we also started comparing matched riders with other existing routes in our system. We would do this in a very tight loop, doing <em>millions</em> of comparisons a second, in hopes that a driver’s positional update might open up a match that wasn’t valid before. When switching to a more optimal solution, we no longer wanted to compare riders as frequently, instead we wanted to “accumulate” rides for a period of time before attempting to solve in a more complete way. Once we’d accumulated a large number of rides, we would look at all possible matches and determine the optimal set of matches to reduce the total detour, pickup time, and cost of the entire system. This is somewhat similar to the bucketed matching design we discussed in <a href="https://eng.lyft.com/matchmaking-in-lyft-line-9c2635fe62c4#.le50784zs">part one</a> of the series, except with a very small bucket window (e.g. 30 seconds).</p><p>This approach, though more efficient, still provides significant challenges on both the algorithmic and technical fronts. Building an optimal solution in a distributed way is challenging — it requires being able to partition your graph into smaller components in real-time without hurting your system’s efficiency. Attempting to do a static partitioning in a city like San Francisco by neighborhood would mean that matching passengers in the Marina and Cow Hollow on their way to work downtown wouldn’t be possible, yet we know those are some of our best matched routes. Identifying the right partitioning pattern and solving for optimal system efficiency is the secret sauce behind our Matching Exchange.</p><h4>The Road Ahead</h4><p>Many of the improvements we’ve talked about in this series have been attempts to eke out efficiency in our matchmaking system while maintaining a quality user experience. Optimizing our matchmaking code, however, wasn’t the only way we could achieve a higher level of efficiency and we’ve tried other product changes along the way. <a href="http://blog.lyft.com/posts/100hotspots">Hotspots</a> was a feature we launched that suggested pickup locations to our passengers in exchange for a cheaper ride. These Hotspots were designed to aggregate demand and reduce pickup and detour times. <a href="http://techcrunch.com/2015/04/27/lyft-is-testing-a-feature-that-will-make-line-cheaper-if-youre-willing-to-wait-longer/">Standby</a> was a feature that allowed passengers to wait up to 10 minutes for a match in exchange for an additional discount. This would increase our matching window and result in a higher match rate, quality, and system efficiency. A combination of these types of changes — algorithmic optimizations and product changes — allowed us to continue to improve our system efficiency without settling on a <a href="https://en.wikipedia.org/wiki/Maxima_and_minima">local maxima</a>.</p><p>As we have along the way, we A/B test most changes to our system, and build on knowledge we’ve learned from previous tests. In parallel we’re adapting our algorithm to work for cities of different composition — sparse cities like LA, North-South neighborhoods like Manhattan, and centralized downtown commuter cities like Chicago. We’re also refining what makes a good match for our passengers and learning from the feedback they give us — changing the weights of our constraints to meet their requirements.</p><p>We’ve come a long way since launching Lyft Line in August 2014, but we never consider our work done. We’ll always continue to improve how we help you share rides as we strive for the perfect match.</p><p>[1] Notice that this Route Swap animation is actually an example of Rerouting plus Route Swapping — passenger A was the next pickup for the driver in Route 2 and by route swapping we changed the driver’s next stop, making it a reroute. A swap like this would require significant cost savings to be worth all of the potential risks.</p><blockquote>If you’re interested in building the future of ridesharing, <a href="https://www.lyft.com/jobs#job-openings">Lyft is hiring</a>! Shoot me a message on <a href="https://twitter.com/TimothyBrownSF">Twitter</a> or email me at <a href="/service/mailto:tim@lyft.com">tim@lyft.com</a></blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d8f9497c0e51" width="1" height="1" alt=""><hr><p><a href="https://eng.lyft.com/matchmaking-in-lyft-line-part-3-d8f9497c0e51">Matchmaking in Lyft Line</a> was originally published in <a href="https://eng.lyft.com/">Lyft Engineering</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Matchmaking in Lyft Line]]></title>
            <link>https://eng.lyft.com/matchmaking-in-lyft-line-691a1a32a008?source=rss-9586ebbfe412------2</link>
            <guid isPermaLink="false">https://medium.com/p/691a1a32a008</guid>
            <category><![CDATA[lyft]]></category>
            <category><![CDATA[marketplaces]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[ridesharing]]></category>
            <category><![CDATA[engineering]]></category>
            <dc:creator><![CDATA[timothybrownsf]]></dc:creator>
            <pubDate>Tue, 01 Mar 2016 19:51:50 GMT</pubDate>
            <atom:updated>2016-08-28T03:49:04.828Z</atom:updated>
            <content:encoded><![CDATA[<h3>Matchmaking in Lyft Line — Part 2</h3><p>In <a href="https://eng.lyft.com/matchmaking-in-lyft-line-9c2635fe62c4">part one of this series</a>, we talked about the timing and design around our launch of Lyft Line. We described the basics of matchmaking and that we built a <a href="https://en.wikipedia.org/wiki/Greedy_algorithm">greedy</a> <a href="https://en.wikipedia.org/wiki/Haversine_formula">Haversine</a> 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.</p><h4>Improving the Passenger Experience</h4><p>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.</p><p>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].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/629/0*7pM947fjKJqyM42Z." /><figcaption>Very Generic Code</figcaption></figure><p>Obviously this code wasn’t ideal, but we had to move fast.</p><p><strong>Geohashing</strong></p><p>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 href="https://en.wikipedia.org/wiki/A*_search_algorithm">A* algorithm</a>, 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 <a href="https://en.wikipedia.org/wiki/Contraction_hierarchies">contraction hierarchies</a> 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<a href="https://en.wikipedia.org/wiki/Geohash"> geohash</a> based model for estimates.</p><p>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.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/863/0*tWx-kgCgyncmfgFC." /><figcaption>Geohash Level 6</figcaption></figure><p>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.</p><p>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.</p><p>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.</p><h4>Efficiency and Efficiency improvements</h4><p>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.</p><p><strong>Triple Matching</strong></p><p>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.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/400/0*Vt-J56-F3EvLx3A7." /><figcaption>Example Triple Match — ABCABC</figcaption></figure><p>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.</p><p>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.</p><p><strong>Longitudinal Sorting</strong></p><p>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.</p><p><strong>Rerouting</strong></p><p>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.</p><p>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.</p><p>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 <a href="https://eng.lyft.com/matchmaking-in-lyft-line-part-3-d8f9497c0e51#.rzljpynuz">next time</a>: more efficiency improvements on the road to becoming less Greedy.</p><p>Read the third and final part of the series <a href="https://eng.lyft.com/matchmaking-in-lyft-line-part-3-d8f9497c0e51#.rzljpynuz">here</a>.</p><p>[1] Internally referred to as the “Golden Gate Mason Dixon Line”</p><p>[2] Our O(n^2) algorithm is described in <a href="https://eng.lyft.com/matchmaking-in-lyft-line-9c2635fe62c4#.gb2l4cycp">Part 1</a>.</p><p>[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.</p><p>[4] For a refresher on what these letters mean, read the <a href="https://eng.lyft.com/matchmaking-in-lyft-line-9c2635fe62c4#.kqiyidp39">first post</a> of the series.</p><p>[5] Lies! Who doesn’t love a full car?</p><blockquote>If you’re interested in building the future of ridesharing, <a href="https://www.lyft.com/jobs#job-openings">Lyft is hiring</a>! Shoot me a message on Twitter or email me at <a href="/service/mailto:tim@lyft.com">tim@lyft.com</a></blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=691a1a32a008" width="1" height="1" alt=""><hr><p><a href="https://eng.lyft.com/matchmaking-in-lyft-line-691a1a32a008">Matchmaking in Lyft Line</a> was originally published in <a href="https://eng.lyft.com/">Lyft Engineering</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Matchmaking in Lyft Line]]></title>
            <link>https://eng.lyft.com/matchmaking-in-lyft-line-9c2635fe62c4?source=rss-9586ebbfe412------2</link>
            <guid isPermaLink="false">https://medium.com/p/9c2635fe62c4</guid>
            <category><![CDATA[lyft]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[engineering]]></category>
            <category><![CDATA[marketplaces]]></category>
            <category><![CDATA[ridesharing]]></category>
            <dc:creator><![CDATA[timothybrownsf]]></dc:creator>
            <pubDate>Tue, 02 Feb 2016 18:45:02 GMT</pubDate>
            <atom:updated>2016-08-28T03:48:14.562Z</atom:updated>
            <content:encoded><![CDATA[<h3>Matchmaking in Lyft Line — Part 1</h3><p>Lyft Line is a ridesharing product that automatically pairs riders together with overlapping routes, allowing us to provide a cheaper ride for all passengers. The more overlap two routes have, the larger the discount we can provide. But what makes a good Lyft Line route? We think it’s a cheap, fast, efficient, and friendly ride. And how do we know if we’ve matched a passenger in a route that’s fast and efficient? How can we accurately predict whether two, three, or four passengers together would enjoy the route we’ve selected? That’s the challenge of our matching system, something we’ve been working on for over a year and a half. This is the story of how it’s evolved, and where it’s going, and will be laid out as a 3 part series.</p><h4>Motivation</h4><p>We launched Line in August of 2014, though it’s a project that Lyft has long been interested in building given its roots in ridesharing service Zimride. For several years before launch we’ve kept a pulse on the market, but wanted to wait until we had sufficient density before building a true ridesharing product. In May 2014, we ran a simulation on our existing Lyft Classic rides (rides that aren’t shared) and realized that in San Francisco, over 80% of rides shared a significant portion of their route with another ride[1]. This was a staggering number — only a portion of the cars in the city were Lyft rides, and yet potentially the majority of those could be paired together with other passengers. This was a huge opportunity to change transportation and provide more affordable rides to our users.</p><blockquote>In May 2014, we ran a simulation on our existing Lyft Classic rides and realized that in San Francisco, over 80% of rides shared a significant portion of their route with another ride.</blockquote><h4>Design Decisions</h4><p>In the initial design of Line, passengers would enter in their origin and destination, receive a fare for the ride, and then be put in the matching pool for 1 minute before being assigned a driver. If we didn’t find a good match at the end of that minute, we’d still dispatch a driver to the passenger, and they’d still receive the quoted fare. However, this wasn’t the only design we had considered.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*0sbuAC2FMy2_jma6." /></figure><p>We also contemplated building a bucketed matching system. Instead of being in the matching pool for a fixed period of time (1 minute), we’d have all requests stay in the matching pool until the next clock interval. A ten minute bucket interval would mean a ride requested at 8:03 or 8:09 would remain in the matching pool until 8:10, and a ride requested at 8:11 would be in the pool until 8:20. A longer time in the matching pool meant there would be more requests we could match together at one time and thus a higher likelihood of finding a match. Additionally, a variable bucket interval would allow us to adapt to lower density cities at launch, like Honolulu, as we could increase the bucket interval to be 15 or 20 minutes. However, this approach had some downsides.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1010/1*qJsLrqMF8aFRulDI2r70jQ.png" /></figure><p>Finding drivers for all of our passengers at the same time would add a supply shock to our system as we’d need to have a pool of drivers available on the ten minute mark. And a ten minute interval meant a longer wait for passengers before showing them their route. Given the initial implementation was going to have some rough edges, a ten minute wait might be too long if they were then put into a bad match. Ultimately we decided that the one minute matching pool could provide the best experience for our passengers and was what users had come to expect from Lyft as an on-demand service.</p><h4>Naive Matching</h4><p>Because of the opportunity we had to revolutionize transportation, and our engineering philosophy of being agile, we started with a simple <a href="https://en.wikipedia.org/wiki/Greedy_algorithm">greedy</a> <a href="https://en.wikipedia.org/wiki/Haversine_formula">haversine</a> matchmaking system. A greedy system is one in which we take the first match we find that satisfies our constraints, as opposed to the best one for the entire system. Choosing a greedy system made sense — optimizing for multiple potential matches wouldn’t be possible until we’d grown the product to a sufficient size. Haversine distances are straight-line distances between two points and are multiplied by the region’s average speed to get a time estimate. A haversine implementation is quick to implement and with tight enough constraints (e.g. detours, time until pickup, etc.) would make sure users had a good match.</p><p>The initial implementation compared every passenger with every other passenger in the system (<em>O(n^2)</em>), in all possible orderings. We denoted passengers as letters of the alphabet and every passenger has two stops — a pickup and drop-off — A and A’, B and B’, etc. So when comparing passenger A and B, we looked at 24 potential orderings: ABB’A’, ABA’B’, B’A’BA, B’AA’B, B’ABA’, BAA’B’, AA’B’B, B’BAA’, etc. We were able to reduce the number of permutations down to only 4 given that there would never be a drop-off before a pickup, and an ordering such as AA’BB’ had no overlap and thus wasn’t worth considering. We would look at all four permutations and eliminate ones that didn’t satisfy all of our constraints. We would then choose the most optimal ordering[2], make the match, and notify the passenger. For reference, we will now refer to an ABA’B’ route as ABAB since the second A is inferred to be A’ (drop-off).</p><pre>def make_matches(all_rides):<br>    for r1 in all_rides:<br>        for r2 in all_rides: <br>            orderings = []<br>            for ordering in get_permutations(r1, r2):<br>                if is_good_match(r1, r2, ordering):<br>                    orderings.append(ordering)</pre><pre>            best_ordering = get_best_ordering(r1, r2, orderings)<br>            if best_ordering:<br>                make_match(r1, r2, best_ordering)</pre><pre>            // etc ...</pre><p>Our constraints started off with some of the more obvious considerations: detour and pickup time. For a match to be made, the total detour that match added for each passenger would have to be below an absolute threshold, but would also have to be below a proportional threshold. This makes sense as one can imagine a 5 minute detour is much more tolerable on a 30 minute ride than on a 5 minute ride. Detours were simple and efficient to calculate — we would take the estimated time for each passenger to get to their destination without a match and compare that with the total time it would take them to get to their destination when matched. For an ABAB ordering this meant passenger A’s detour was ABA minus AA, and passenger B’s detour was BAB minus BB.</p><p>We had similar constraints for additional time until passengers were picked up, and would be calculated as follows for an ABAB route (assuming | represents the driver): |A is A’s pickup time, |AB is B’s pickup time. Clearly, being the second passenger in a Line ride reduced that rider’s average detour, as they might not have a another stop between pickup and drop-off (ABBA), but came with an increased pickup time.</p><p>After launch, we quickly started to realize the limitations of our system. Passengers would post examples of their routes that matched them with a stop on the other side of a mountain or in a way that required an additional loop through crowded downtown one-way streets in rush hour. We started learning that passengers didn’t want to go backwards, and in fact the angle of the lines they saw on the map would affect their satisfaction with the match. In ways both obvious to our initial implementation and in other not so rational ways, our system as it was currently built wasn’t going to give the ride quality that we wanted. We had to make some improvements, and we had to do it fast or people were going to get frustrated with their experience. Coming in <a href="https://eng.lyft.com/matchmaking-in-lyft-line-691a1a32a008#.qyjkdzf8k">part 2</a>: improvements to our passenger experience and algorithmic efficiency.</p><p>Read part 2 of the series <a href="https://eng.lyft.com/matchmaking-in-lyft-line-691a1a32a008#.qyjkdzf8k">here</a>.</p><p>[1] Our initial modeling required rides to share over 50% of their ride and allowed for a maximum detour of 10 minutes when paired.</p><p>[2] The most optimal ordering is the one in which the total matched distance is minimized. For example if an ABBA route had a total distance of 3.5 miles, but an ABAB route had a total distance of 3.2 miles, we would select the ABAB route.</p><blockquote>If you’re interested in building the future of ridesharing, <a href="https://www.lyft.com/jobs#job-openings">Lyft is hiring</a>! Shoot me a message on <a href="https://twitter.com/timothybrownsf">Twitter</a> or email me at <a href="/service/mailto:tim@lyft.com">tim@lyft.com</a></blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9c2635fe62c4" width="1" height="1" alt=""><hr><p><a href="https://eng.lyft.com/matchmaking-in-lyft-line-9c2635fe62c4">Matchmaking in Lyft Line</a> was originally published in <a href="https://eng.lyft.com/">Lyft Engineering</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>