[1] Zhang Xiaoguo, Wang Qing, Gong Fuxiang,. Optimal path finding algorithms based on SLSD road network model [J]. Journal of Southeast University (English Edition), 2010, 26 (4): 558-562. [doi:10.3969/j.issn.1003-7985.2010.04.012]

Copy

Optimal path finding algorithms based on SLSD road network model()

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

26

Issue:

2010 4

Page:

558-562

Research Field:

Automation

Publishing date:

2010-12-30

Info

Title:

Optimal path finding algorithms based on SLSD road network model

Author(s):

Zhang Xiaoguo;  Wang Qing;  Gong Fuxiang

School of Instrument Science and Engineering, Southeast University, Nanjing 210096, China

Keywords:

optimal path finding;  road network model;  conceptual model;  digital map;  vehicle navigation system;  A^* algorithm;  Dijkstra algorithm

PACS:

TP208;U666.1

DOI:

10.3969/j.issn.1003-7985.2010.04.012

Abstract:

A solution to compute the optimal path based on a single-line-single-directional(SLSD)road network model is proposed. Unlike the traditional road network model, in the SLSD conceptual model, being single-directional and single-line style, a road is no longer a linkage of road nodes but abstracted as a network node. Similarly, a road node is abstracted as the linkage of two ordered single-directional roads. This model can describe turn restrictions, circular roads, and other real scenarios usually described using a super-graph. Then a computing framework for optimal path finding(OPF)is presented. It is proved that classical Dijkstra and A^* algorithms can be directly used for OPF computing of any real-world road networks by transferring a super-graph to an SLSD network. Finally, using Singapore road network data, the proposed conceptual model and its corresponding optimal path finding algorithms are validated using a two-step optimal path finding algorithm with a pre-computing strategy based on the SLSD road network.

References:

[1] Zhan F B, Noon C E. Shortest path algorithms: an evaluation using real road networks [J]. Transportation Science, 1998, 32(1): 65-73.
[2] Zhao Y L. Vehicle location and navigation system [M]. London: Artech House, Inc, 1999.
[3] Zhang X G. The theory and application of vehicle navigation oriented GIS and its map-matching techniques[D]. Nanjing: School of Instrument Science and Engineering of Southeast University, 2001.(in Chinese)
[4] Ness S, Lee T. Single line street network: the foundation of mobile GIS[C]//Proc of IEEE-IEE Vehicle Navigation & Information Systems Conference. Ottawa, Canada, 1993:34-37.
[5] Christopher K H. The potential of precision maps in intelligent vehicles[C]//Proc of IEEE International Conference on Inteilligent Vehicles. Stuttgart, Germany, 1998: 419-422.
[6] Car A, Taylor G, Brunsdon C. An analysis of the performance of a hierarchical wayfinding computational model using synthetic graphs [J]. Computers, Environment and Urban Systems, 2001, 25(1): 69-88.
[7] Hisao N, Yuuji Y, Teruo F. Path finding algorithms based on the hierarchical representation of a road map and its application to a map information system [J]. IPSJ Journal Contents, 2001, 31(5): 659-665.
[8] Holzer M. Hierarchical speed-up techniques for shortest-path algorithms[D]. Konstanz, Germany: University of Konstanz, 2003.
[9] Li Q Q, Zeng Z, Yang B S. Hierarchical model of road network for route planning in vehicle navigation systems [J]. IEEE Intelligent Transportation Systems Magazine, 2009, 1(2): 20-24.
[10] Jing N, Huang Y W, Rundensteiner E A. Hierarchical encoded path views for path query processing: an optimal model and its performance evaluation [J]. IEEE Transactions on Knowledge and Data Engineering, 1998, 10(3): 371-388.
[11] Thorup M. Undirected single-source shortest paths with positive integer weights in linear time [J]. Journal of the Association for Computing Machinery, 1999, 46(3): 362-394.
[12] Muhammad A A. Integrating OO road network database, cases and knowledge for route finding[C]//Proc of the 2001 ACM Symposium on Applied Computing. Las Vegas, Nevada, USA, 2001:215-219.
[13] Wagner D, Willhalm T. Geometric speed-up techniques for finding shortest paths in large sparse graphs[C]//Proc of European Symposium on Algorithms. Budapest, Hungary, 2003:776-787.
[14] Möhring R H, Schilling H, Schütz B, et al. Partitioning graphs to speed up Dijkstra’s algorithm [J]. The ACM Journal of Experimental Algorithm, 2006, 11: 1-29.
[15] Morris J. Data structures and algorithms: Dijkstra algorithm [EB/OL].(1998-12-30)[2010-09-25]. http://www.cs.auckland.ac.nz/software/AlgAnim/dijkstra.html.

Memo

Memo:

Biography: Zhang Xiaoguo(1973—), male, doctor, lecturer, zxg519@sina.com.
Foundation item: The National Key Technology R& D Program of China during the 11th Five Year Plan Period(No.2008BAJ11B01).
Citation: Zhang Xiaoguo, Wang Qing, Gong Fuxiang. Optimal path finding algorithms based on SLSD road network model [J].Journal of Southeast University(English Edition), 2010, 26(4):558-562.

Common functions