Improved public transit routing algorithm for finding the shortest k-path

Inwoo Jeon, Hyunwoo Nam, Chulmin Jun

Research output: Contribution to journalConference articlepeer-review


Most of the existing public transit routing algorithms were developed on the basis of graph theory. Recently, algorithms are being developed that can compute for O-D public transit paths by using timetable information only, not using network structure consisting of nodes and links. The timetable-based public transit routing algorithm produces one shortest path to destination, using departure time and arrival time by stop. But it has limitations in reflecting additional factors, such as transfer penalty and alternative path selection, in the process of path calculation. In addition, since public transit passengers tend to choose one among various alternative paths, it is necessary to calculate multiple paths rather than a single path as in the existing methods. Therefore, this study proposes an improved RAPTOR algorithm that can consider transfer penalty and produce multiple paths, while it is based on RAPTOR, the existing timetable-based public transit routing algorithm. The transfer penalty was applied at the point of transfer, and differently according to transfer types. As a result of analyzing computed paths of the algorithms before and after improvement, it was found that computed paths with the improved RAPTOR algorithm proposed by this study were more similar to Seoul public transit passengers‟ actual travel paths than computed paths by the existing RAPTOR alone.

Original languageEnglish
Pages (from-to)255-264
Number of pages10
JournalInternational Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences - ISPRS Archives
Issue number4/W9
StatePublished - 26 Oct 2018
Event2018 International Conference on Geomatic and Geospatial Technology: Geospatial and Disaster Risk Management, GGT 2018 - Kuala Lumpur, Malaysia
Duration: 3 Sep 20185 Sep 2018


  • Multiple paths
  • Public transit routing
  • Similar paths
  • Timetable
  • Transfer penalty


Dive into the research topics of 'Improved public transit routing algorithm for finding the shortest k-path'. Together they form a unique fingerprint.

Cite this