Texas Engineers have developed a new algorithm which calculates the most reliable route between two points, allowing for a more exact level of certainty for logistics industries such as supply chain management.

UT Austin Researchers: Alireza Khani, civil engineering postdoctoral researcher (currently assistant professor at University of Minnesota), Stephen Boyles, civil engineering associate professor

Discovery: A new, exact algorithm for the mean-standard deviation shortest path problem with independent link costs. This algorithm finds the most reliable route between two points, with reliability defined as the sum of the mean and standard deviation of path cost.

Although finding the route which is fastest on average is easy, accounting for standard deviation in the route is much more difficult, and the problem was only solved approximately or with great computational effort.

Why It Matters: Reliability is important in many routing and logistics problems. For many drivers, uncertainty in congestion is just as important as how congested a route is on a typical day. In commercial supply chains, there are major impacts when shipments are delayed.

How it Works: While the mean-standard deviation shortest path problem is known to be difficult, the mean-variance shortest path problem is much easier. The researchers discovered a relationship between these two problems, that when viewed as a bicriterion optimization problem, the mean-standard deviation efficient frontier is a subset of the mean-variance frontier. Furthermore, the mean-variance problem is additive and admits a definition of link reduced costs, which the researchers used to accelerate the search along the mean-variance efficient frontier. This new method is more than 10 times faster than previous exact methods for this problem.

Published: Transportation Research Part B, "An Exact Algorithm for the Mean-Standard Deviation Shortest Path Problem."

What's Next: The researchers are exploring whether other nonlinear shortest path problems can be addressed using the same techniques.

They are also exploring whether this approach can be extended to the case where link costs are spatially correlated, rather than statistically independent.