A Spatial Restricted Heuristic Algorithm of Shortest Path

Author

Liu, Ying-chun ; Yang Dong-he

Author_Institution

Inst. of Integrated Inf. Syst., ZheJiang Univ. of Technol., Hangzhou, China

Volume

2

fYear

2009

fDate

7-8 Nov. 2009

Firstpage

36

Lastpage

39

Abstract

The single-source shortest path problem based on the road network has many obvious geographic spatial characteristics. By designing the spatial data model of the road network and analyzing the geometric characteristic of the spatial trend of the path we form a spatial restricted function which can reduce the cost of searching the shortest path in the road network. The spatial restricted function is used in the heuristic algorithm as a kind of heuristic function. With this function the spatial restricted heuristic algorithm is designed and described. Experimental results show that: the cost of the spatial restricted heuristic algorithm is close to the heuristic A* algorithm, but it can obtain the optimal solution of the shortest path in real time by an iterative algorithm.

Keywords

graph theory; road traffic; roads; transportation; geographic spatial characteristics; geometric characteristics; heuristic function; road network; single-source shortest path problem; spatial data model; spatial restricted heuristic algorithm; Application software; Artificial intelligence; Cost function; Heuristic algorithms; Iterative algorithms; Logistics; Roads; Shortest path problem; Telecommunication traffic; Traffic control;

fLanguage

English

Publisher

ieee

Conference_Titel

Artificial Intelligence and Computational Intelligence, 2009. AICI '09. International Conference on

Conference_Location

Shanghai

Print_ISBN

978-1-4244-3835-8

Electronic_ISBN

978-0-7695-3816-7

Type

conf

DOI

10.1109/AICI.2009.160

Filename

5376371