Sberbank: RIDE Python library to speed up the calculation of the shortest path

2024: Creating the RIDE Python Library

Specialists of the Laboratory of Artificial Intelligence of Sberbank in partnership with colleagues from ITMO created the Python-library RIDE, which reduces the time to find the shortest path on the graph. The solution allows you to increase the performance of logistics calculations of an arbitrary scale from urban to regional or the scale of an entire country. Sberbank announced this on December 13, 2024.

The approach is based on the idea of ​ ​ clustering the graph. Thanks to it, RIDE significantly reduces the area of ​ ​ solution search and eliminates suboptimal route options in advance. As a result, on large graphs, the result is achieved up to 30 times faster than the basic algorithms.

The RIDE library provides methods that greatly speed up the process of constructing suboptimal routes, especially on large (transport graphs of large cities, regions and countries) and abstract graphs (citation graphs). The library is most relevant when you need to repeatedly form routes in a short time. RIDE allows developers to make a high-performance product from a mobile application to an AI tool, quickly test scientific hypotheses and save a lot of time.

The RIDE library is based on the cluster division approach of the graph, which allows you to exclude many suboptimal route options during the preprocessing stage. This method was tested on graphs containing more than 500 cities, and demonstrated a significant acceleration of calculations without significant losses in accuracy. With RIDE, developers can control the balance between speed and accuracy by estimating preliminary acceleration results by graph size. All this makes RIDE an effective tool for solving real problems of finding shortest paths.