考虑时空约束的地铁乘客出行路径集生成算法

Path Set Generation Algorithm for Schedule based Rail Transit with Constraints of Time and Space

摘要:

从时空棱柱的视角出发，在列车运行图搜索算法的基础上，通过“O点正搜、D点反推，取时空棱柱交集”的思路确定出行可达区域，以此构建考虑时空约束的乘客出行路径集生成算法.以上海轨道交通网络为例进行案例分析.结果表明,该算法在正确生成出行路径外还可以搜索特殊的可行路径，较传统算法更具有实际应用价值.

Abstract:

An algorithm for the valid path set generation of passenger was proposed under both space and time constraints. It was developed on the basis of train trajectory searching algorithm and space time prism. The train trajectory searching algorithm allowed us to obtain passenger’s travel trajectories. Within the method of space time prism, these trajectories could form an accessible region searching from origin and a passing region searching from destination. A set of valid paths was then generated from the intersection of the two regions. Finally, Shanghai Metro Network was taken as an example to illustrate the correctness and effectiveness of the algorithm. The results show that the proposed algorithm generated new valid paths and delete invalid paths in comparison with conventional methods.