公交站点换乘算法.pdf

: .
Algorithm for finding optie origin and destination. We precompute a lookup table of feasible paths
between the origin stop of every bus route to the terminus of every other bus route using the transfer
points. This precomputation of paths significantly reduces the computation time and number of real-time
arrival requests to transit agency servers, the bottleneck in computing this problem. The computational
complexity of the algorithm is linear in real-time and implementation results show that queries from a
webserver are returned in 3 seconds in the worst-case.
2Jariyasunant, Mai, Sengupta 3
1 INTRODUCTION
1 The focus of the paper is the introduction of a new algorithm which overcomes the problem of computing
2 shortest paths in a transit network which pulls real-time data from a third-party Application Programming
3 Interface (API). Over a web-based or smartphone interface, a user enters a geo-coded origin and destination
4 (O-D), and the algorithm must respond by returning K-shortest paths based on the real-time state of the
5 transit network. Thus, our principal performance measure is the time elapsing between input of the O-D
6 and output of the path, which we call the path computation time. Web usage studies show this time should
7 be less than 7 seconds [1, 2].
8 Paths cannot be wholly pre-computed since the aim is to return results based on real-time state, which
9 needs to be acquired at run-time. We call the time required to get this information the real-time state
10 acquisition time. Industry Service Level Agreements (SLAs) create constraints on how this real-time state
11 can be acquired. The industry appears to be evolving towards an open model where the pub