标题：Accurate and Fast Path Computation in Urban Environments Using Region Pruning Strategies
作者：Song, Qing; Li, Meng; Li, Xiaolei
作者机构：[Song, Qing; Li, Meng] Univ Jinan, Sch Elect Engn, Jinan 250022, Shandong, Peoples R China.; [Li, Xiaolei] Shandong Univ, Sch Control Sci & Engn, Ji 更多
会议名称：36th Chinese Control Conference (CCC)
会议日期：JUL 26-28, 2017
来源：PROCEEDINGS OF THE 36TH CHINESE CONTROL CONFERENCE (CCC 2017)
关键词：Path computation; heuristics; hierarchical; urban road network
摘要：Accurate and fast path computation is essential for applications such as onboard navigation systems and traffic network routing. While a number of heuristic algorithms have been developed in the past few years for faster path queries, the accuracy of them are always far below satisfying. To facilitate accurate and fast routing applications, a three-level graph model is presented for structuring the urban road network, and a hierarchical path computation algorithm is then proposed, which benefits from the hierarchical graph model and utilizes a region pruning strategy to significantly reduce the search space without compromising the accuracy. The experimental evaluation on the real urban road network of New York City demonstrates the effectiveness of the proposed approach to generate optimal fast paths and to facilitate real-time routing applications.