New algorithm improves MOVESMART’s Innovative Route Planning Service

Posted October 26th, 2016 | Categories: Movesmart

The Innovative Route Planner (IRP) is a novel service developed by the CTI team within MOVESMART. IRP resides at MOVESMART’s dedicated cloud that has been established for providing a holistic Mobility-as-a-Service (MaaS) approach. IRP computes minimum-travel-time route plans in real-time for metropolitan-size urban road networks. The IRP service is based on time-dependent traffic data and metadata which are created and periodically updated by it, in collaboration with MOVESMART’s Traffic Prediction and Crowd-Sourcing services. IRP also takes into account live-traffic conditions, in order to provide route plans which are aware of traffic situations at the actual travel-time of the planned journey.


In a recent joint publication researchers from CTI and KIT teams managed to further improve both the cloud-side and the client-side parts of IRP, through a new algorithmic approach called “Hierarchical Time-Dependent Oracles“, which will be presented at the 27th International Symposium on Algorithms and Computation (ISAAC) that will be held on 12-14 December 2016.

The unique features of the new algorithm is: (i) its space efficiency, which now does not depend on the (time-dependent) metric’s characteristics (such a dependence blows up space); and (ii) its considerably improved query response time, which is the first ever method achieving time sublinear in the length of the optimal route. Extensive experimentation with real-world road networks has shown the practicality of the new algorithms.

Tags: ,