Helping Drivers Take a Turn for the Better

Running into a one-way or no-left-turn street can be pretty frustrating as a driver. It’s an even bigger problem for vehicles responsible for mapping streets as well. But new research from Maryland Smith has a solution.

Published in the INFORMS Journal on Computing, Debdatta Sinha Roy, PhD ’19, working alongside Bruce Golden, The France-Merrick Chair in Management Science at the University of Maryland’s Robert H. Smith School of Business, Adriano Masone of the University of Naples, and Edward Wasil of American University, developed new algorithms to help city government and highway authority road inspection vehicles find the most optimal routes for inspecting intersections.

In 2019, RoadBotics, a Pittsburgh-based road inspection and management company that had been carrying out road image analysis projects for local governments, approached the researchers with a unique problem. Their vehicles struggled to fully capture intersections during inspections. Vehicles that took right turns or U-turns through intersections often missed out on important details compared to those traveling straight or making a left turn.

The reason? Right turns do not always fully traverse an intersection and U-turns fail to traverse them at all.

The researchers, Sinha Roy says, dubbed this the intersection inspection rural postman problem (IIRPP), a variant of the rural postman problem (RPP) – identifying the shortest way of connecting a set of required street segments to form a full route.

Following the proper intersection strategy, along with ensuring that the vehicles abide by specific driving instructions or turn restrictions, makes the routing process a difficult mathematical problem, says Sinha Roy, now a senior research scientist at Oracle. But these algorithms, the first of their kind, are not only easily accessible for any government agency or private body seeking to do road inspections, but also applicable to a variety of other vehicle routing applications.

“For this particular example, the algorithm restricts right turns. But tomorrow, someone can use the same algorithm and restrict turning left because it operates on the idea of restricting certain turns,” says Sinha Roy. “It’s very easily scalable. Anyone who can code can pull the algorithm from the paper and implement it – that’s it.”

The algorithms, which can solve problems with hundreds of intersections in a matter of seconds, are less than 1% off of the optimal solution, Sinha Roy says. Any government agency or private organization is able to implement them, he says, and there’s good reason to do so, given the positive incentives to efficient vehicle routing.

There’s the business side, where they can help cut costs on last-mile delivery for companies like Amazon. Then there are the uses for government vehicles, like street sweepers and snowplows, that can better map out their routes. Even truck drivers could utilize the algorithms to avoid difficult U-turns, Sinha Roy says.

Another major net positive, he says, is the potential environmental impact. Efficient vehicle routing can help decrease carbon emissions through lowered gas expenditures, mileage and time on the road.

“This research strikes at the core of any other routing problem that we see all around us,” says Sinha Roy. “You always want to travel the route that takes the least amount of time. It’s the same for all of us.”

Golden also sees its potential to make a tangible difference.

“This is exactly the kind of problem I like to see my PhD students work on. It is mathematically challenging, but also of obvious practical importance. I was very pleased with Debdatta’s work on this project,” says Golden.

Read More: “Modeling and Solving the Intersection Inspection Rural Postman Problem,” published in the INFORMS Journal on Computing.