This content is not included in
your SAE MOBILUS subscription, or you are not logged in.
Evaluation of Shortest Path Algorithms in a Distributed Traffic Assignment Environment
Technical Paper
2003-01-0536
ISSN: 0148-7191, e-ISSN: 2688-3627
Annotation ability available
Sector:
Language:
English
Abstract
The increasing linkage of route guidance servers within the recent years leads to numerous efforts to split traffic assignment algorithms in an efficient way on these distributed computers. Especially in the field of intermodal services, i.e. calculating the fastest paths of certain origin-destination pairs with respect to different individual and public traffic services, solutions are required to implement the routing models in a fast, reliable way. Unfortunately, analysis of different realizations is commonly done by comparing the amount of necessary instructions O(·) in different net topologies. However, as computing power is in the meanwhile at a fairly high level, delay in a distributed environment can mainly be expected due to communication time. Dynamic calculations demand to transmit actual traffic conditions during several time periods, thus this paper examines the different routing strategies by evaluating the occuring message transmission time in common graph classes. It will be shown that possessing a star topology (one central server) Label-Setting algorithms can be proved to be superior in regard to Label-Correcting algorithms. In addition, considerable improvements will be achieved by parallel message transfer for possible next link investigations. Here, the paper proposes solutions with a profit in delays by a factor of O′(n), where n denotes the number of nodes in a network.
Authors
Citation
Kriesten, R. and Kiencke, U., "Evaluation of Shortest Path Algorithms in a Distributed Traffic Assignment Environment," SAE Technical Paper 2003-01-0536, 2003, https://doi.org/10.4271/2003-01-0536.Also In
References
- Baccelli, F. Cohen, G. 1992 Synchronization and Linearity. An Algebra for Discrete Event Systems Wiley & Son New York
- Cherkassky, B. Goldberg, A. Radzik, K. 1993 Shortest Paths Algorithms: Theory and Experimental Evaluation ACM-SIAM Symposium on Discrete Algorithms (SODA) Texas
- Christofides, N. 1975 Graph Theory: An Algorithmic Approach Academic Press San Diego
- Domschke, W. 1995 Logistik: Transport Oldenbourg Verlag München (Germany)
- 2001 Das Programm Marco Polo Brüssel
- Halbritter, G. et al 2001 Verkehr in Ballungsräumen. Optionen für eine effizientere und umweltverträglichere Gestaltung Germany
- Kiencke, U. 1997 Ereignisdiskrete Systeme Oldenbourg Verlag München Germany
- Stuttgart Stadt 2002 Mobilist. Mobilität im Ballungsraum Stuttgart http://www.mobilist.de
- Rembold. U. 1999 Einführung in die Informatik für Naturwissenschaftler und Ingenieure Carl Hanser Verlag Munich (Germany)
- Scott, K. et al. 1997 Finding alternatives to the best path Proceedings of the 76 th annual meeting of The Transportation Research Board, paper number 970682 Washington
- Sun, W. 1996 Optimale Steuerung verteilter, ereignisdiskreter Systeme University of Karlsruhe Germany