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

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.