Logo: University of Southern California

Clearing L.A. traffic, one problem at at time

Together, Cyrus Shahabi and Ugur Demiryurek are making it easier to navigate Los Angeles, from personal vehicles to fleets of delivery trucks.
By: Erin Rode
June 11, 2015 —

A scene from Los Angeles' notoriously crowded freeways. Demiryurek and Shahabi hope to help drivers avoid traffic jams like this one through new routing systems.
Ugur Demiryurek loves problems. While most researchers are frustrated by seemingly unsolvable problems, Demiryurek gets more joy out of problems themselves than solutions.

“As a researcher, problems are more important for me than the solutions. When someone brings me a difficult problem, I definitely like the problem more than the solution, and the rest follows” said Demiryurek.

Problematic Path Planning

In 2006, Ugur Demiryurek began his Ph.D. in computer science at USC Viterbi under the direction of Cyrus Shahabi.  Recognizing Demiryurek’s love of problems, Shahabi challenged him with a personally bothersome dilemma.

Every day, Shahabi commutes from his home in Irvine to work at USC. While using routing apps on his commute, he noticed a problem: areas marked as high-traffic zones at the time he began driving would be clear by the time he reached them – and vice versa.

“I realized that given all the information we have on traffic, we can do better,” Shahabi said.   

Shahabi began researching predictive path planning, a routing system that’s more accurate than existing system, because it adjusts to real-time traffic changes. When Demiryurek came to Shahabi for a PhD project, Shahabi realized that Demiryurek’s love of problems made him the perfect partner to bring predictive path planning to fruition.

“I go to a lot of students with problems, but they cannot put the problem in the context of a research objective and approach it. Ugur understood the problem from my description, and brought it to the research stage through his Ph.D. dissertation,” Shahabi said.

Flash forward five years later, and the two are coworkers: Demiryurek serves as the assistant director of USC’s Integrated Media Systems Center (IMSC), with Shahabi as director.  And through funding from agencies like the National Science Foundation and Fortune 500 companies, what began as Demiryurek’s Ph.D. dissertation has branched into an array of research ventures, all with the common goal of routing Los Angeles.

“Before he actually got his Ph.D., I was already looking at him more as a colleague than a student. . . the transition just happened naturally, so it was a no-brainer to work with him,” Shahabi said.

Using real traffic data from the Los Angeles Metro Authority, Demiryurek and Shahabi turned a project into a product with ClearPath. ClearPath sets itself apart from other routing apps, like Waze and GoogleMaps, by predicting traffic changes that will occur over the course of the route, utilizing historic traffic patterns and updating with real-time events. According to Demiryurek, the application shaves travel time by 18 percent. ClearPath attracted much interest from venture capitalists and companies alike, and is set to launch as a spin-off from USC by raising funding later this year.

A comparison of GoogleMaps with ClearPath. The blue line represents Google Maps; the green line is ClearPath. When traffic patterns are taken into consideration, the Google Maps route would take 26 minutes, while the ClearPath route would only take 20.

More Vehicles, More Problems

Now that they’ve solved the predictive routing problem for individual vehicles, Shahabi and Demiryurek have moved onto a new problem: predictive routing for fleets of vehicles, such as delivery trucks.

Minimizing the time delivery trucks spend on the road would bring an array of benefits. Customers would receive packages faster, truck companies would save money on fuel; even the environment would benefit through lessened carbon emissions. The traffic-fighting pair partnered with Oracle, an engineering hardware and software company, for this new venture.

“The problem became much harder, because instead of just one car, we need to consider multiple cars going different places, and minimizing the total travel time for all delivery points.  The overall goal is to reduce the total travel time for all the cars, not the time for each individual car.  So, instead of single optimization I now get to do group optimization,” Demiryurek said.

An example of what a delivery truck routing system would look like when optimized for three delivery trucks, each with a variety of unique stops.

As with ClearPath, Demiryurek and Shahabi rely on real-life traffic data provided by a local company, instead of mere hypothetical situations, to develop a predictive route planning system for delivery trucks. The system will take into account the number of necessary stops and available trucks, and historical traffic patterns, and then create a scheduled route that minimizes time for each individual truck.

According to Bloomberg Business, reducing travel distance by just one mile per day for every truck would save a company the size of UPS up to 50 million dollars a year in time, fuel, and vehicle maintenance. Demiryurek and Shahabi believe their system could save even more than one mile per day, per vehicle.

“I am pretty sure that our idea will save even more. . . because seeing in front of you what will happen, with a system that reacts to real time events, is priceless,” Demiryurek said.

And the traffic-fighting duo isn’t stopping with delivery trucks. For their next project, Demiryurek and Shahabi hope to streamline the city’s notorious public transportation system by analyzing bus routes, continuing their quest for clearer, faster commutes for Angelenos.