IMPROVED PUBLIC TRANSIT ROUTING ALGORITHM FOR FINDING THE SHORTEST K-PATH

Abstract. 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.