Recently, transit agencies have begun opening their route configuration and schedule data to the public, as well as providing online application programming interfaces to real-time bus positions and arrival estimates. On the basis of this infrastructure for providing transit data over the Internet, the authors developed an algorithm to calculate the travel times of K shortest paths in a public transportation network where all wait and travel times were known only in real time. Although there was a large body of work on routing algorithms in transit networks, the authors took cues from an algorithm to find the shortest paths in road networks, called transit node routing. This approach was based on observation of intuitive behavior by humans: when taking transit, travelers looked for a particular set of transfer points that connected transit routes that led from the origin and destination. A lookup table was precomputed of feasible paths between the origin stop of every bus route to the terminus of every other bus route by using the transfer points. This precomputation of paths significantly reduced 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 web server are returned in 3 s in the worst case.
Get full access to this article
View all access options for this article.
References
1.
JainR., RaleighT., GraffC., and BereschinskyM.Mobile Internet Access and QoS Guarantees Using Mobile IP and RSVP with Location Registers. IEEE International Conference on Communications, Vol. 3, 1998, pp. 1690–1695.
2.
ErlT. (ed.). Service-Oriented Architecture (SOA): Concepts, Technology, and Design.Prentice Hall, Upper Saddle River, N.J., 2005.
Muller-HannemannM., and WeiheK.Pareto Shortest Paths Is Often Feasible in Practice. Proc., 5th Workshop on Algorithm Engineering (WAE 2001), Vol. 2141, 2001, pp. 185–198.
5.
PallottinoS., and ScutellaM. G.Equilibrium and Advanced Transportation Modelling.Kluwer Academic Publishers, 1998, Chap. 11.
6.
SchulzF., WagnerD., and WeiheK.Dijkstra's Algorithm On-line: An Empirical Case Study from Public Railroad Transport. ACM Journal of Experimental Algorithmics, Vol. 5, No. 12, 2000.
7.
SchulzF., WagnerD., and ZaroliagisC.Using Multi-Level Graphs for Timetable Information in Railway Systems. In Proc., 4th Workshop on Algorithm Engineering and Experiments (MountD. M., and SteinC., eds.), Springer, Berlin, 2002, pp. 43–59.
8.
BrodalG., and JacobR.Time-Dependent Networks as Models to Achieve Fast Exact Timetable Queries. Electronic Notes in Theoretical Computer Science, Vol. 92, No. 1, 2003.
9.
NachtigalK.Time Depending Shortest-Path Problems with Applications to Railway Networks. European Journal of Operations Research, Vol. 83, 1995, pp. 154–166.
10.
OrdaA., and RomR.Shortest-Path and Minimum-Delay Algorithms in Networks with Time-Dependent Edge-Length. Journal of the ACM, Vol. 37, No. 3, 1990.
11.
OrdaA., and RomR.Minimum Weight Paths in Time-Dependent Networks. Networks, Vol. 21, 1991.
12.
DijkstraE.A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, Vol. 1, No. 1, 1959, pp. 269–271.
13.
BellmanR.On a Routing Problem. Quarterly of Applied Mathematics, Vol. 16, No. 1, 1958, pp. 87–90.
14.
HartP. E., NilssonN. J., and RaphaelB.A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 1968, pp. 100–107.
15.
PyrgaE., SchulzF., WagnerD., and ZaroliagisC.Efficient Models for Timetable Information in Public Transportation Systems. ACM Journal of Experimental Algorithmics, Vol. 12, Article 2.4, 2008.
16.
BauerR., DellingD., and WagnerD.Experimental Study on Speed-Up Techniques for Timetable Information Systems. Networks, No. 0.1002/net.20382, 2009.
17.
DellingD., PajorT., and WagnerD.Engineering Time-Expanded Graphs for Faster Timetable Information. Lecture Notes in Computer Science, Vol. 5868, 2009, pp. 182–206.
18.
DesaulniersG., and VilleaneuveD.The Shortest Path Problem with Time Windows and Linear Waiting Costs. Transportation Science, Vol. 34, 2000, pp. 312–319.
19.
DialR.Transit Pathfinder Algorithms. In Highway Research Record 205, HRB, National Research Council, Washington, D.C., 1967, pp. 67–85.
20.
GranatJ., and GuerrieroF.The Interactive Analysis of the Multicriteria Shortest Path Problem by the Reference Point Method. European Journal of Operational Research, Vol. 151, No. 1, 2003, pp. 103–118.
21.
ChuangT.-N., and KungJ.-Y.The Fuzzy Shortest Path Length and the Corresponding Shortest Path in a Network. Computers and Operations Research, Vol. 32, No. 6, 2005, pp. 1409–1428.
22.
van der ZijppN. J., and CatalanoS. F.Path Enumeration by Finding the Constrained k-Shortest Paths. Transportation Research Part B, Vol. 39, No. 6, 2005, pp. 545–563.
23.
XuW., HeS., SongR., and ChaudhryS. S.Finding the k Shortest Paths in a Schedule-Based Transit Network. Computers and Operations Research, 2010.
24.
ChenY.-L., and YangH.-H.Finding the First k Shortest Paths in a Time-Window Network. Computers and Operations Research, Vol. 31, No. 4, 2004, pp. 499–513.
25.
ZhaoL., XiongY., and SunH.The K Shortest Transit Paths Choosing Algorithm in Stochastic Transit Network. In Proc., 3rd International Conference on Rough Sets and Knowledge Technology, Springer, Berlin, 2008.
26.
TanM., TongC., WongS., and XuJ.M.An Algorithm for Finding Reasonable Paths in Transit Networks. Journal of Advanced Transportation, Vol. 41, No. 3, 2010, pp. 285–305.
27.
HallR. W.The Fastest Path Through a Network with Random Time-Dependent Travel Times. Transportation Science, Vol. 20, No. 3, 1986, pp. 182–188.
28.
KaufmanD. E., and SmithR. L.Fastest Paths in Time Dependent Networks for Intelligent Vehicle-Highway Systems Applications. IVHS Journal, Vol. 1, No. 1, 1993, pp. 1–11.
29.
WellmanM. P., LarsonK., FordM., and WurmanP. R.Path Planning Under Time-Dependent Uncertainty. In Proc., Eleventh Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann, San Francisco, Calif., pp. 532–539.
30.
KarasanO. E., PinarM. C., and YamanH.The Robust Shortest Path Problem with Interval Data. Technical Report. Department of Industrial Engineering, Bilkent University, Ankara, Turkey, Aug. 2001. http://www.optimization-online.org/DB_HTML/2001/08/361.html.
31.
ZielinskiP.The Computational Complexity of the Relative Robust Shortest Path Problem with Interval Data. European Journal of Operational Research, Vol. 158, 2004, pp. 570–576.
32.
FederT., MotwaniR., O'CallaghanL., OlstonC., and PanigrahyR.Computing Shortest Paths with Uncertainty. Journal of Algorithms, Vol. 62, 2007, pp. 1–18.
33.
PallottinoS., and ScutellM.A New Algorithm for Reoptimizing Shortest Paths When the Arc Costs Change. Operations Research Letters, Vol. 31, No. 2, 2003, pp. 149–160.
34.
BastH., FunkeS., SandersP., and SchultesD.Fast Routing in Road Networks with Transit Nodes. Science, Vol. 316, No. 5824, 2007, p. 566.
35.
SchultesD.Route Planning in Road Networks. PhD dissertation. University of Karlsruhe, Germany, 2008.
JariyasunantJ., and MaiE.BayTripper: Real-Time Transit Information for Mobile Phones.2009. www.baytripper.org.
38.
JariyasunantJ., WorkD. B., KerkezB., SenguptaR., BayenA. M., and GlaserS.Mobile Transit Trip Planning with Real-Time Data. Presented at 89th Annual Meeting of the Transportation Research Board, Washington, D.C., 2010.
39.
FerrisB., WatkinsK., and BorningA.OneBusAway: Results from Providing Real-Time Arrival Information for Public Transit. In Proc., ACM Conference on Human Factors in Computing Systems (CHI), 2010.
40.
GuoZ., and WilsonN. H. M.Assessment of the Transfer Penalty for Transit Trips: Geographic Information System-Based Disaggregate Modeling Approach. In Transportation Research Record: Journal of the Transportation Research Board, No. 1872, Transportation Research Board of the National Academies, Washington, D.C., 2004, pp. 10–18.
