A Schedule-based Pathfinding Algorithm for Transit Networks Using Pattern First Search |
| |
Authors: | Ruihong Huang |
| |
Affiliation: | (1) Department of Geography, Planning and Recreation, Northern Arizona University, South San Francisco Street, P. O. Box 15016, Flagstaff, AZ 86011-5016, USA |
| |
Abstract: | The lack of effective and efficient schedule-based pathfinding algorithms for transit networks has limited the application
of GIS in transit trip planning services. This paper introduces a schedule-based path finding algorithm for transit networks.
Based on a pattern-centered spatiotemporal transit network model, the algorithm searches the network by following route patterns.
A pattern is a spatial layout of a route in transit terminology. A route usually has many patterns to serve various locations
at different times. This path search algorithm is significantly different from traditional shortest path algorithms that are
based on adjacent node search. By establishing a set of lemmas and theorems the paper proves that paths generated by the PFS
algorithm are schedule-coordinated fastest paths for trips with given constraints. After analyzing computation and database
query complexities of the algorithm the paper indicates that the PFS is efficient in computation and database query. Finally,
effectiveness and efficiency of the algorithm are demonstrated by implementations in GIS-based online transit trip planners
in Wisconsin, US.
|
| |
Keywords: | GIS transportation transit network pathfinding algorithm trip planning complexity |
本文献已被 SpringerLink 等数据库收录! |
|