Parallel Route Optimization Algorithm of Central Guidance

Abstract:

To solve the problem that the central guidance system takes too long time to calculate the shortest routes between all node pairs of network which can not meet the real-time demand of central guidance, this paper presents a central guidance parallel route optimization method based on parallel computing technique involving both route optimization time and travelers preferences by means of researching three parts: network data storage based on an array, multi-level network decomposition with travelers preferences considered and parallel shortest route computing of deque based on messages transfer. And based on the actual traffic network data of Guangzhou city, the suggested method is verified on three parallel computing platforms including ordinary PC cluster, Lenovo server cluster and HP workstations cluster. The results show that above three clusters finish the optimization of 21.4 million routes between 5631 nodes of Guangzhou city traffic network in 215, 189 and 177 seconds with the presented method respectively, which can completely meet the real-time demand of the central guidance.

• Periodical: Applied Mechanics and Materials (Volumes 380-384)
• Pages: 1571-1575
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.380-384.1571
• Online since: August 2013
• Authors: Hong Chen, Hu Xing Zhou, Juan Meng
• Keywords: Central Guidance, Deque, Message Transfer, Multi-Level Network Decomposition, Shortest Route, Travelers Preferences

References

[1] Zhang He, Yang Zhao-sheng, Wang Wei. Research on vehicle route optimization of central dynamic route guidance systems based on real-time traffic flow information[J]. Journal of Highway and Transportation Research and Development, 2004, 21(9): 91-94.

[2] Tomkewitsch R V. Dynamic route guidance and interactive transport management with ALI-SCOUT [J]. IEEE Transactions on Vehicular Technology, 1991, 40(1): 45-50.

DOI: 10.1109/25.69971

[3] O'Cearbhaill E A, O'Mahony M. Parallel implementation of a transportation network model[J]. Parallel and Distributed Computing, 2005, 65(1): 1-14.

[4] Henning M, Burkhard M, Thomas S. A new diffusion-based multilevel algorithm for computing graph partitions[J]. Journal of Parallel and Distributed Computing, 2009, 69(9): 750-761.

DOI: 10.1016/j.jpdc.2009.04.005

[5] Yang Zhaosheng, Zhou Huxing, Gao Xueying, Liu Songnan. Multiobjective Model for Emergency Resources Allocation [J]. Mathematical Problems in Engineering, (2013).

[6] Yang Zhaosheng, Zhou Huxing, Gao Peng, Chen Hong, Zhang Nan. The Topological Analysis of Urban Transit System as a Small-World Network [J]. International Journal of Computational Intelligence Systems, 2011, 4(6): 1216-1223.

DOI: 10.1080/18756891.2011.9727870

[7] Karypis G, Kumar V. Multilevel k-way Hypergraph Partitioning[J], VLSI Design, 2000, 11(3): 343 – 348.

DOI: 10.1155/2000/19436