AI DevelopmentWeb DevelopmentApp Development
Basemap - Digital mapping and transport data solutions
The Task
Routing in complex networks is one of the most computationally - intensive tasks in computer science. After relying on the battle - tested Dijkstra algorithm for several years, Basemap aimed to improve its core algorithm and add several new features to it.
The requirements for the new algorithm were that it must be faster than Dijkstra and provide additional 'Depart At' and 'Arrive By' queries. Furthermore, no approximation or stochastic output was allowed.
Communere's Approach
By doing extensive research on the business requirements, Communere offered a modified version of the Round - based Public Transit Routing algorithm. The algorithm was successfully implemented and integrated into the TRACC application through rigorous R&D sprints.
One of the core values during the implementation was maintaining a clean architecture to facilitate the improvement and debugging of such a complex system.
Results
By exploiting the internal structure of public transportation timetables, the algorithm significantly outperformed the previous methods in terms of speed while maintaining the optimality guarantees. The speed-up in such a core aspect of the software, dramatically improved User Experience.
