Finding the K-shortest paths in timetable-based public transportation systems is an important problem in practice. It has three typical variants: the K-earliest arrival problem (K-EAP), the K-shortest travel time problem (K-STTP), and the K-minimum number of transfers problem (K-MNTP). In this article we show that these problems can be solved efficiently by first modeling the timetable information with the time-expanded approach, then applying the Martins and Santos (MS) algorithm. Then we model the timetable information with the time-dependent approach and propose a modified version of the MS algorithm for solving the K-EAP. Experimental results on real-world data show that for K smaller than 100, which is enough for most applications, the execution times of the MS algorithm for the problems in the time-expanded model are less than 100 ms on a server with a 1.86-GHz central processing unit (CPU) and 4 GB of memory. For solving the K-EAP the modified MS algorithm in the time-dependent model is even more efficient (about three times faster for K ≤ 100) than the original algorithm in the time-expanded model. Our results imply the great potential of the MS algorithms in practical transportation service systems.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Solving the K-shortest paths problem in timetable-based public transportation systems


    Beteiligte:
    Wang, Shuai (Autor:in) / Yang, Yang (Autor:in) / Hu, Xiaolin (Autor:in) / Li, Jianmin (Autor:in) / Xu, Bingji (Autor:in)

    Erschienen in:

    Erscheinungsdatum :

    02.09.2016


    Format / Umfang :

    15 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Timetable information and shortest paths

    Schulz, Frank | DataCite | 2005



    Region Public Transportation Timetable Optimization Based on Node and Line's Wait Analysis

    Sun, W.-x. / Song, T. / Ma, L.-x. | British Library Conference Proceedings | 2009