The shortest path problem, which centers on finding a path between two vertices, is one of the fundamental problems in graph theory. For example, take a navigation app: when planning a route from A to B, the app sifts through many options to find the optimal one. In major cities with countless roads and crossroads, this process requires complex computations if performed with conventional methods. The novel method suggested by the scientists is capable of accurately predicting the shortest routes, thus exponentially increasing processing speed without any accuracy loss.
Thanks to the suggested method, it would be possible to not only facilitate navigation and optimize cargo traffic logistics, but also efficiently apply abstract graph structures in various fields. For instance, the method can be applied in social media to quickly search for connections between users through common acquaintances or instantaneously access the necessary information. Moreover, there are potential applications in biomedicine – in particular, for the analysis of protein graph structure.
Gleb Gusev, the head of Sberbank’s Artificial Intelligence Lab:
“Logistics is one of the key sectors of the modern economy, and route optimization can help save billions of rubles for our country. The graph clustering-based optimization method we suggested requires significantly fewer computational resources in order to build effective routes, especially in giant urban networks found in major cities. At the same time, the fact that our results have been published in an international journal demonstrates that the global professional community values the contributions of Russian scientists. We have new ambitious goals ahead that will surely strengthen Russia’s scientific reputation even further.”
Sergey Mityagin, the head of ITMO’s Institute of Design and Urban Studies:
Sergey Mityagin. Photo by Dmitry Grigoryev / ITMO NEWS
“The idea for this study came as a result of experiments. We were testing conventional routing algorithms and noticed that as the delivery area and number of vehicles increased, the computations became significantly more complicated, requiring more resources. Additionally, we discovered an important pattern: topologically, cities have only several types of road system organization; this led us to the idea of using graph preprocessing to take into account typical road system topology. Our method is based on dividing the city into areas and the road system – into separate components; first, we optimize routes within each area and then build connections between them. Thanks to this two-level optimization, routing is conducted significantly faster compared to conventional methods that calculate routes for the entire city at once.”
