Abstract
The numerous amount of existing Route Guidance Systems (RGS) leads to increasing efforts to integrate these stand-alone tools into an overall solution, possessing the ability to process information of all the individual systems. Especially in the fields of intermodal services and in order to combine RGS of neighboured regions, enhanced developments can be regarded. As representatives of intermodal services, i.e. calculating the best ways of certain origin-demand matrices with respect to the simultaneous use of different Public Transportation Means (PTM) and Individual Transportation (IT), the European project Marco Polo [EK01] can be named as well as the German projects Mobilist [MOB02] or Wayflow [WAY02], mainly trying to implement shortest path models under a star topology with distributed information storage. In addition, Personal Digital Assistents (PDA) with integrated GPS modul are curently available [PTV 02], thus being able to perform intermodal navigation within the vehicle as well as by the use of PTM and for pedestrians.
Unfortunately, analysis of different path search algorithms is commonly done by comparing the amount of necessary instructions O(·). However, delay in a distributed environment can mainly be expected due to communication time, as computing power is in the meanwhile at a fairly high level. 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 performing route determination) Label-Setting (LS) algorithms can be proved to be superior in regard to Label-Correcting (LC) 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 , where n denotes the number of nodes in a network.