首页 | 官方网站   微博 | 高级检索  
     


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.
Contact Information Ruihong HuangEmail:
Keywords:GIS  transportation  transit network  pathfinding  algorithm  trip planning  complexity
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号