Browse Publications Technical Papers 2003-01-0536

Evaluation of Shortest Path Algorithms in a Distributed Traffic Assignment Environment 2003-01-0536

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.


Subscribers can view annotate, and download all of SAE's content. Learn More »


Members save up to 40% off list price.
Login to see discount.
Special Offer: With TechSelect, you decide what SAE Technical Papers you need, when you need them, and how much you want to pay.