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

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 the authors 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 they 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. The authors' results imply the great potential of the MS algorithms in practical transportation service systems.

Language

  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01615731
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Sep 3 2016 3:01PM