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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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


    Contributors:
    Wang, Shuai (author) / Yang, Yang (author) / Hu, Xiaolin (author) / Li, Jianmin (author) / Xu, Bingji (author)

    Published in:

    Publication date :

    2016-09-02


    Size :

    15 pages




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English