Real-time, scalable route planning using a stream-processing infrastructure

Abstract

A key transportation service is traffic-dependent route planning, i.e., finding a path from a source to a destination on a road network that incurs the minimum travel time delay and that considers current and future traffic conditions on all road links. This kind of route planning requires dynamic time-dependent shortest path computations, since the cost of each link is different at different intervals of time, and these time-dependent costs get updated as new traffic information is obtained. In this paper, we describe a stream-processing infrastructure that can perform scalable, real-time, time-dependent shortest path computations with high throughput and low latency on large road networks. In our performance experiments, we show that it can perform hundreds of such shortest path computations per second, with an average delay of less than 1 second on a road network with tens of thousands of nodes and links. Our experiments were carried out on the Stockholm road network, and the traffic data for purposes of getting the travel time delay on each link was derived from a real GPS data-set obtained from vehicles on this network. In this paper, we also highlight the benefits of performing dynamic, time-dependent shortest path computations. For example, our data from Stockholm suggests that computing traffic-dependent shortest paths can help decrease travel time by up to 62% compared to using a less dynamic method based on fixed road speed limits. Also the shortest path for various origin-destination pairs changes frequently during the course of a day. These findings motivate the need for highly scalable, real-time time-dependent shortest-path computations, as performed by our stream processing infrastructure. ©2010 IEEE.