Dynamic graph research is an essential subject in Computer Science. The shortest path problem is still the central in this field; moreover there is a variety of applications in practical projects. In this paper, we select the transportation activity as a paradigm to study. Of course there exists the most clear and appealing practical application over the intelligent navigation, also which is an important part in intelligent transportation system (ITS). Totally speaking, this activity is fairly simple and well-behavior under our consideration, for which, there is a lot of sophisticated theories and techniques to motivate our researches although this problem relates to interdisciplinary; so that we can be dedicated to computing aspect. Below, a host of practical problems will by the way be discussed in theory and empiricism including correctness, sampling, accuracy, compatibility, quick query and the application into other research; therein some have been scarcely argued intentionally or not in literatures before. Through these contents, we are able to have a smart system built which easy to incorporate other modules to realize a sophisticated industrial system.
The development of intelligent transportation systems (ITS) and the resulting need for the solution of a variety of dynamic traffic network models and management problems require faster-than-real-time computation of shortest path problems in dynamic networks. Recently, a sequential algorithm was developed to compute shortest paths in discrete time dynamic networks from all nodes and all departure times to one destination node. The algorithm is known as algorithm DOT and has an optimal worst-case running-time complexity. This implies that no algorithm with a better worst-case computational complexity can be discovered. Consequently, in order to derive algorithms to solve all-to-one shortest path problems in dynamic networks, one would need to explore avenues other than the design of sequential solution algorithms only. The use of commercially-available high-performance computing platforms to develop parallel implementations of sequential algorithms is an example of such avenue. This paper reports on the design, implementation, and computational testing of parallel dynamic shortest path algorithms. We develop two shared-memory and two message-passing dynamic shortest path algorithm implementations, which are derived from algorithm DOT using the following parallelization strategies: decomposition by destination and decomposition by transportation network topology. The algorithms are coded using two types of parallel computing environments: a message-passing environment based on the parallel virtual machine (PVM) library and a multi-threading environment based on the SUN Microsystems Multi-Threads (MT) library. We also develop a time-based parallel version of algorithm DOT for the case of minimum time paths in FIFO networks, and a theoretical parallelization of algorithm DOT on an ‘ideal’ theoretical parallel machine. Performances of the implementations are analyzed and evaluated using large transportation networks, and two types of parallel computing platforms: a distributed network of Unix workstations and a SUN shared-memory machine containing eight processors. Satisfactory speed-ups in the running time of sequential algorithms are achieved, in particular for shared-memory machines. Numerical results indicate that shared-memory computers constitute the most appropriate type of parallel computing platforms for the computation of dynamic shortest paths for real-time ITS applications.