Discovering historic traffic-tolerant paths in road networks

详细信息    查看全文

• 作者：Pui Hang Li ; Man Lung Yiu ; Kyriakos Mouratidis
• 关键词：Road networks ; Road traffic
• 刊名：GeoInformatica
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：21
• 期：1
• 页码：1-32
• 全文大小：
• 刊物类别：Earth and Environmental Science
• 刊物主题：Geographical Information Systems/Cartography; Data Structures, Cryptology and Information Theory; Computer Science, general; Information Storage and Retrieval; Multimedia Information Systems;
• 出版者：Springer US
• ISSN：1573-7624
• 卷排序：21

文摘

Historic traffic information is valuable in transportation analysis and planning, e.g., evaluating the reliability of routes for representative source-destination pairs. Also, it can be utilized to provide efficient and effective route-search services. In view of these applications, we propose the k traffic-tolerant paths (TTP) problem on road networks, which takes a source-destination pair and historic traffic information as input, and returns k paths that minimize the aggregate (historic) travel time. Unlike the shortest path problem, the TTP problem has a combinatorial search space that renders the optimal solution expensive to find. First, we propose an exact algorithm with effective pruning rules to reduce the search time. Second, we develop an anytime heuristic algorithm that makes ‘best-effort’ to find a low-cost solution within a given time limit. Extensive experiments on real and synthetic traffic data demonstrate the effectiveness of TTP and the efficiency of our proposed algorithms.