As the world becomes more technological, algorithms are increasingly making appearances in our lives. Whether it's the app that you use to order a pizza or the custom playlist that you listen to each week, there are more and more moments where we interact with algorithms.

One usage of algorithms is to make travel by car faster and more efficient. With the rise of ridesharing companies, engineers need to solve the problem of getting people to their destinations quickly. In order to meet the needs of riders and drivers alike, ride-sharing companies like Lyft commit tireless hours to create effective ridesharing algorithms.

Lyft is an on-demand transportation company that enables mobile app users to request private and shared rides. To provide this service, Lyft engineers balance a variety of criteria to get riders to their destinations on time. How do they accomplish this task and how do they do so in the most effective way?

In this article, you will learn about different algorithms for calculating routes, including the well-known Dijkstra's Algorithm. We'll also explore how engineers at Lyft use iteration to optimize algorithms in order to increase their efficiency and improve user experience.

How Do Algorithms Get Us Around?

Imagine that you're going to meet your friend at a coffee shop. It's too far to walk there from your house and your bike has a flat. Your friend tells you to take a Lyft Line, a cost-saving service from Lyft where people heading towards similar destinations share a car.

Great! You think. The car pulls up and you realize that you're the first pickup, meaning that at least one other person will get picked up before you reach your destination. How does the algorithm figure out which people to pick up along the way without turning your 15-minute trip into a three hour journey?

The algorithm's job is to take you from your initial location, known as the origin node, and deliver you to your drop-off, or the destination node. Other passenger pick-up locations are also nodes. The streets in between the origin node and the destination node are called paths, which together form a route. The algorithm’s job is to find a sequence of nodes and paths that will get you from the origin node to the destination node.

The Lyft Line picks you up from your house and calculates the route to the coffee shop. Once in the car, the algorithm starts looking for more passengers who are between the origin and destination nodes to add to your ride.

In this case, it finds Patrick at the grocery store and Michelle at the school, each one representing a node. The algorithm will choose between their nodes to determine who to pick-up on the way to your destination node.

image

There are a lot of different factors that the algorithm can take into consideration to make its decision - and that decision will make the difference between arriving at your destination on time or much later.

In the next few sections, we'll explore how different algorithms that can solve this problem and discuss why iterating on algorithms is important to improving a product.

Naïve Approach

Lyft could consider many approaches to find a route to your destination. To create a route, the algorithm just needs a method for picking a path to the next stop. So why not make it simple?

Algorithmic approaches that have a simple solution to a problem are known as naive algorithms. They're usually the first solution that you come up with and involve very few steps.

For example, what if Lyft Line was built on a coin-toss method? In this scenario, the algorithm would choose between picking up Patrick or Michelle based on the result of tossing a coin. Heads, Patrick get's picked up. Tails, Michelle.

image

Randomly deciding by coin-toss is a straight-forward approach where each passenger would have a 50/50 chance of joining your ride. However, it doesn't take into account other factors - like the fact that Michelle's stop takes you through a construction zone. When you're trying to get to your destination quickly, you need an algorithm that takes external information like construction and traffic into account. The last thing you want is 30 minutes added to your ETA!

While this approach gets the job done, Lyft knows that its algorithm needs to find the most convenient pick-ups and drop-offs that align with your trip. While these methods achieve the desired outcome, they are not the most efficient solution. That's when optimization comes in.

So, What’s Optimization?

In the context of algorithms, optimization is a process of improving another set of processes (in this case, an algorithm), by considering opportunities and identifying limitations.

Lyft algorithms need to consider several factors including current location, destination, and available cars every time a user requests a ride. This problem-solving approach leads to better decision making as it thoroughly tackles real-world challenges like traffic conditions.

image

So let’s think back to that Lyft Line ride bringing you to the cafe. If it were to use an optimization algorithm, your car would pick up Patrick from the store because it could detect delays on the path to Michelle at the school. This is why we can depend on algorithms on a daily basis! Now let’s explore what makes other, optimized algorithms “smarter” than their naive alternatives.

Dijkstra's Algorithm

One of the need-to-know algorithms is Dijkstra's Algorithm because it's the foundation for many of the routing algorithms. Developed in the 1950s, Dijkstra tries to choose the most convenient of the paths between the origin and destination. Dijkstra's Algorithm works by determining the weight of a path and constructing a route by choosing the paths with the lowest weights. A weight represents time or distance units determined by the engineering team. By making a decision based on the weight of a path, an engineer is building in constraints.

If Lyft Line used Dijkstra’s Algorithm, the algorithm would construct the route by finding the unvisited node option with the lowest path weight. In this case, it would choose to add Patrick to your ride over Michelle because her path has a higher weight due to the presence of construction.

image

What if there were multiple nodes on the way to your destination? Let's use Dijkstra's Algorithm to find the route between Node A and Node E on the map below:

image

If we implement Dijkstra, these are the steps our route would take:

  • The algorithm would start at A, which is the origin node.
  • The algorithm would then decide between two options: B (4 units away) and C (2 units away). The algorithm chooses C since it has the lower weight.
  • After selecting C, the next node options are B (1 unit), D (4 units), and E (5 units). Even though E is the destination node, B is chosen because the path has the lowest weight of one unit.
  • From B, the next options are D and E. Although the path to D has a lower value of two units, there are no node options after D, so E (3 units) is chosen.

Here's what the final solution looks like: image

According to Dijkstra, the optimal route is A ⇒ C ⇒ B ⇒ E because it is the lowest weight route on the map. While the benefit of this method is that it disregards stops with higher weights, as we saw, Dijkstra is only optimal when there’s no prior knowledge of the map.

Lyft doesn’t implement Dijkstra because the algorithm only uses the initial location to plan the entire route. So, while Patrick’s path has a lower weight than Michelle’s path with construction, what if we discover that the path after Patrick’s stop has traffic that’s worse? So eventhough Dijkstra's is an improvement from randomly deciding by coin-toss, it's optimal route is not guaranteed to be the best option.

Lyft Line Matchmaking and Iteration

In 2016, Lyft engineers published a three-part series (part one, part two, part three) outlining the design and implementation of the Lyft Line algorithm. This series does an excellent job of taking the reader through the process of developing an algorithm from a naive approach to a robust, scaled, efficient system that continually strives for improvement.

As we saw in the two previous examples, improving an algorithm means including constraints. Dijkstra's Algorithm is an improvement on the coin-toss method because it is built on a constraint of always having to choose the path with the lowest weight.

The development of Lyft's Line algorithm also depends on constraints. Lyft engineers set out to determine what were the most important factors to consider when deciding who to match for a journey. In their first iteration, they landed on pickup time, the time you wait for a Lyft car to arrive, and detour time, the time it takes to pick up another passenger.

Once they developed an algorithm that met those constraints, they then thought about what other constraints they could include to improve the system for users, such as cost-effectiveness and timing. They started with two constraints, but by the second iteration, they had more than 30.

While they started off with their own naive approach, they continually iterated on their algorithms - or, in some cases, scrapped it completely for an entirely new, optimized algorithm. Lyft's current algorithm is the result of building off of Dijkstra and other algorithms and data structures, such as A* and geohash models. While their current algorithm is highly detailed, it still builds off of the same concepts of nodes, weights, routes, and efficiency.

Summary

Regardless of the algorithms chosen, Lyft and other companies rely on the ability of algorithms to consider many variables and improve itself based on them. People still make decisions from a coin-toss and after 60 years, Dijkstra is still the foundation of many exceptional search algorithms.

As companies like Lyft develop algorithms, they start with the most fundamental solution to a problem and keep iterating and optimizing their experience as new constraints and challenges emerge. As Timothy Brown, the author of the series writes, "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."

As you begin writing your own algorithms, remember that your first attempt may not address all of your problems needs, but with time and iteration, you can continue to improve your solution.

Made in NYC © 2018 Codecademy