A leading digital mapping provider
Travel time analysis and transport data solutions

The Task

Routing in complex networks is a highly demanding computational task within the field of computer science. Our client, having utilized the well-established Dijkstra algorithm for an extended period, sought to enhance their core algorithm and introduce new functionalities. The objectives for the new algorithm were twofold: surpass the performance of Dijkstra in terms of speed and incorporate additional features such as 'Depart At' and 'Arrive By' queries. It was essential to ensure that the new algorithm strictly adhered to deterministic output without any approximation or stochasticity.

Communere's Approach

After conducting thorough research on the business requirements, Communere proposed a customized version of the Round-based Public Transit Routing algorithm. The algorithm was effectively implemented and seamlessly integrated into our client's flagship application through intensive research and development (R&D) sprints. A key focus during the implementation process was to uphold a clean architecture, enabling easy enhancement and debugging of this intricate system.

The 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.