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.