A Strategy for Solving Static Multiple-Optimal-Path Transit Network Problems
Publication: Journal of Transportation Engineering
Volume 122, Issue 3
Abstract
The trip making process using transit versus private automobile differs in the use of time schedules, walking paths, transfer stops, plus issues such as fare and safety. Due to these factors, many of the standard shortest path algorithms do not apply. The purpose of this study is to develop an algorithm and strategy for transit providers to find best alternatives for the user, and to demonstrate how a geographic information system can be used in the development of transit advanced traveler information system (TATIS) to meet these needs. This paper presents a short introduction to TATIS systems, some commonly used algorithms in determining the shortest and multiple paths, and a new strategy that was developed in this study which differs from standard network algorithms. The major features of this proposed algorithm are: (1) Capability of handling multiple modes of transit; (2) providing paths that include walking distances from and to the transit path as well as between transfer points; and (3) provision of multiple optimal paths to allow the user flexibility in choosing a path.
Get full access to this article
View all available purchase options and get full access to this article.
References
1.
Bellman, R.(1958). “On a routing problem.”Quarterly J. Appl. Math., 16(1), 87–90.
2.
Dijkstra, E.(1959). “A note on two problems in connexion with graphs.”Numerische Mathemalik, 1, 269–271.
3.
Dreyfus, S.(1969). “An appraisal of some shortest-path algorithms.”Operations Res., 17(3), 395–412.
4.
Eiger, A., Mirchandani, P., and Soroush, H.(1985). “Path preferences and optimal paths in probabilistic networks.”Transp. Sci., 19(1), 75–84.
5.
Frank, H.(1969). “Shortest paths in probabilistic graphs.”Operations Res., 17(4), 583–599.
6.
Hall, R.(1986). “The fastest path through a network with random timedependent travel times.”Transp. Sci., 20(3), 182–188.
7.
Hoffman, W., and Pavley, R.(1959). “A method for the solution of the n-th best path problem.”J. Assoc. for Comp. Machinery, 6, 506–514.
8.
Kaufman, D., and Smith, R.(1993). “Fastest paths in time-dependent networks for intelligent vehicle-highway systems application.”IVHS J., 1(1), 1–11.
9.
Koncz, N. (1994). “A GIS-based multi-modal multiple optimal path transit advanced traveler information system,” MSc thesis, New Jersey Inst. of Technol., Newark, N.J.
10.
Laporte, G., Louveaux, F., and Mercure, H.(1992). “The vehicle routing problem with stochastic travel times.”Transp. Sci., 26(3), 161–169.
11.
Lawler, E.(1972). “A procedure for computing the K best solutions to discrete optimization problems and its application to the shortest path problem.”Mgmt. Sci., 18(7), 401–405.
12.
Moore, E. (1957). “The shortest path through a maze.”Proc., Int. Symp. on the Theory of Switching, Part II, Harvard University Press, Cambridge, Mass.
13.
Perko, A.(1986). “Implementation of algorithms for K shortest loopless paths.”Networks, 16(2), 149–160.
14.
Schweiger, C. (1992). “Current use of geographic information systems in transit planning.”Transp. Res. Rec. 1349, Transp. Res. Board, Washington, D.C., 93–106.
15.
Yen, J.(1971). “Finding the K shortest loopless paths in a network.”Mgmt. Sci., 17(11), 712–716.
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 122 • Issue 3 • May 1996
Pages: 218 - 225
Copyright
Copyright © 1996 American Society of Civil Engineers.
History
Published online: May 1, 1996
Published in print: May 1996
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.