Assistant Professor of Operations
Assistant Professor of Operations
From a customer’s perspective, using a ride-hailing service such as Uber or Lyft seems simple. Tap a request into your phone, and a car magically appears.
But on the company’s end, operating an efficient service involves a host of complex issues. Among those: How can firms encourage people to share rides with strangers, which reduces costs and carbon emissions, instead of having the car to themselves? And, when drivers are waiting for new requests, how should they decide whether to stay put or head to another neighborhood?
Two studies by Kellogg faculty have tackled these questions. The first investigated the best way to address one of the reasons customers often opt to travel alone: detours to pick up a fellow rider. The researchers developed a mathematical model that shows it’s possible for companies to significantly reduce detours in shared rides and improve efficiency, and that a key component of that is convincing more people to use that type service.
“The name of the game is to convince people to use these shared services.”
— Sébastien Martin
A second group of researchers examined how companies could more efficiently route drivers who are waiting for ride requests. Using an optimized algorithm to make these decisions, they found, could substantially increase the chances that customers will be picked up quickly.
“This is something that has to be carefully engineered and designed,” says Anton Braverman, an assistant professor of operations at Kellogg, who worked on the routing research.
The first paper focused on shared rides because splitting a car with another customer has many benefits over solo rides. They’re cheaper for passengers, and they cause less traffic congestion and produce fewer carbon emissions. (Shared rides are currently suspended in many locations because of the risk of COVID-19 transmission.)
Even pre-pandemic, however, many people opted to ride alone because they disliked having the driver go out of their way to pick up or drop off another person. Ride-hailing companies generally try to match passengers who want to go in the same direction. But sometimes, even if the second passenger is very close by, “you have to turn left four times just to pick up someone because you’re going around the block, which can be very frustrating,” says Sebastien Martin, an assistant professor of operations at Kellogg, who did the research while he was a postdoctoral fellow at Lyft.
Ride-hailing firms have taken some steps to minimize detours. For example, Uber offers a ride-share option called Express Pool and Lyft offers Shared Saver, which allows customers to pay an even lower rate if they’re willing to walk a few minutes to a pick-up spot that’s convenient for the driver; the customer also is dropped off near, but not necessarily exactly at, their destination in order to stay on a more direct route for the other passengers.
But Martin wanted to more rigorously understand the relationship between detours and value. Value, in this case, meant the efficiency gained from taking two passengers on a shared ride rather than transporting each person in a separate car, measured as the reduction in total drive time.
Martin conducted the research with Ilan Lobel at New York University, who was a visiting researcher at Lyft Marketplace Labs at the time. To investigate, they created a mathematical model of the process of matching passengers on shared rides. The researchers confirmed that detour and value have a negative relationship. That is, when detour is low, value is high.
“If we match people well, with high value, typically they will also get low detour,” Martin says. “You can have the best of both worlds.”
So how should a company decide whether to match two riders? In an extreme case, its algorithm might allow zero detours, putting passengers together only if those people are travelling along the exact same path. Or the firm might prioritize maximizing value, no matter how much detour is involved.
Martin and Lobel tried various permutations using their mathematical model to predict the effects of prioritizing high value or low detours, and how those would change as the number of ride requests rose. The researchers ran the analysis for several types of hypothetical city structures, such as a grid, a tree (similar to a city center with paths branching outward), and a simplified highway. They also ran a separate simulation of Manhattan’s city structure, incorporating data on about 847,000 real trips using ride-hailing services in that area.
The researchers found that even if the company’s ride-matching algorithm allows a small amount of detour, value can still be very high. But the key factor, the team found, was the number of people using the ride system. If the number of customers doubled, detours fell dramatically while yielding the same amount of value.
The results led them to propose a new system: offering two types of shared-ride services, in order to appeal to as many people as possible. The first, more expensive option would guarantee very little detour, in order to attract customers who hate going out of their way. The second, cheaper option would allow more detours and draw people who want to save money and don’t mind spending more time in the car to do so.
“The name of the game is to convince people to use these shared services,” Martin says.
Braverman and his coauthors looked for another opportunity to improve efficiency. When a car drops off a passenger and there are no other immediate requests in the area, the driver must make a choice. Do they linger and wait for a nearby request to pop up? Or do they head to another neighborhood with the hope that requests there might be more frequent?
If this “rebalancing” of cars isn’t done properly, “you just have drivers driving around empty for no good reason, and they’re wasting money on gas,” Braverman says.
Right now, these decisions seem to be somewhat ad hoc. Uber does nudge drivers using price surges; if a certain neighborhood has a lot of requests, the firm increases the pay rate in that area. But beyond that, it appears that drivers “just do what they please,” says Braverman, who collaborated with J. G. Dai at Cornell University and Lei Ying and Xin Liu, both at the University of Michigan, on the study.
The researchers investigated how companies could develop a better algorithm to guide drivers. They created a mathematical model and wrote software to simulate a ride-hailing service, taking into account factors such as the frequency of ride requests in different areas and traffic congestion. The goal was to maximize availability—that is, the likelihood that when a customer requested a ride, a driver was nearby to pick them up.
The computer program solved the optimization problem and directed drivers to either stay or go somewhere else after dropping off their last passenger. (While there isn’t a simple way to describe how the algorithm makes these decisions, the program is straightforward enough for a company to easily implement its own version, Braverman says.)
Next, the team wanted to know how much their algorithm improved the system’s efficiency. To calibrate their model with real-world data, the researchers obtained details on about three weeks of rides with Didi Chuxing (a service similar to Uber) in an unnamed city in China. They then ran computer simulations of a typical day.
The simulations allowed them to compare the performance of their algorithm to basic heuristics that drivers might use in the absence of explicit instructions from the ride-hailing company. For example, perhaps drivers try to predict where they will most quickly find another customer, taking into account factors such as how long it takes to drive to that neighborhood and the likely frequency of requests. If they followed this rule of thumb, about 30 percent of customers’ ride requests would go unfulfilled, the team found. But if drivers followed the algorithm that Braverman’s team had developed, that number would fall to 20 percent.
However, the team’s algorithm assumed that traffic patterns and request rates stayed the same throughout the day. In a more realistic simulation where the rate of ride requests varied at different hours, the algorithm didn’t perform that well during rush hour. For example, from 7 to 8 p.m., 33 percent of customers’ requests were unfulfilled.
So they devised another heuristic called the “look-ahead policy,” which predicted future traffic and requests based on past data, and routed cars accordingly. With this policy, unfulfilled requests during rush hour dropped to 14 percent.
The model still needs more work to be realistic enough for real-world use, Braverman says. But the study suggests that rebalancing cars properly is an important part of running an efficient operation.
“You should reposition intelligently,” he says. “Because if you’re not, you’re leaving a lot on the table.”
Lobel, Ilan, and Sebastien Martin. 2020. “Detours in Shared Rides.”
Braverman, Anton, J. G. Dai, Xin Liu, and Lei Ying. 2019. “Empty-Car Routing in Ridesharing Systems.” Operations Research. 67: 1437–1452.