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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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


    Contributors:


    Publication date :

    2010-09-01


    Size :

    1968450 byte





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Robust algorithm for real-time route planning

    Szczerba, R.J. / Galkowski, P. / Glicktein, I.S. et al. | Tema Archive | 2000


    Robust algorithm for real-time route planning

    Szczerba, R.J. / Galkowski, P. / Glicktein, I.S. et al. | IEEE | 2000


    PAPERS - Robust Algorithm for Real-Time Route Planning

    Szczerba, R.J. | Online Contents | 2000


    A scalable, real-time, image processing pipeline

    Jonker, P. P. / Komen, E. R. / Kraaijveld, M. A. | British Library Online Contents | 1995


    Optimal route planning method considering real-time bus information

    DING JIANXUN / ZHAO ZHENXING / GUO NING et al. | European Patent Office | 2020

    Free access