Efficient Path Routing Over Road Networks in the Presence of Ad-Hoc Obstacles

作     者：Al-Baghdadi, Ahmed Lian, Xiang Cheng, En 

作者机构：Kent State Univ Dept Comp Sci Kent OH 44242 USA Educ Al Qadisiyah Al Diwaniyah 58001 Iraq Univ Akron Dept Comp Sci Akron OH 44325 USA 

出 版 物：《INFORMATION SYSTEMS》 (信息系统)

年 卷 期：2020年第88卷

页      面：101453-000页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NSF OAC, USA Kent State University, USA University of Akron, USA Academy of Finland (AKA) Funding Source: Academy of Finland (AKA) 

主　　题：Ad-hoc weather-based obstacles Ad-hoc keyword-based obstacles Road networks Path routing query over road networks with ad-hoc obstacles 

摘      要：Nowadays, the path routing over road networks has become increasingly important, yet challenging, in many real-world applications such as location-based services (LBS), logistics and supply chain management, transportation systems, map utilities, and so on. While many prior works aimed to find a path between a source and a destination with the smallest traveling distance/time, they do not take into account the quality constraints (e.g., obstacles) of the returned paths, such as uneven roads, roads under construction, and weather conditions on roads. Inspired by this, in this paper, we consider two types of ad-hoc obstacles, keyword-based and weather-based obstacles, on road networks, which can be used for modeling roads that the returned paths should not pass through. In the presence of such ad-hoc obstacles on roads, we formulate a path routing query over road networks with ad-hoc obstacles (PRAO), which retrieves paths from source to destination on road networks that do not pass ad-hoc keyword and weather obstacles and have the smallest traveling time. In order to efficiently answer PRAO queries, we design effective pruning methods and indexing mechanism to facilitate efficient PRAO query answering. Extensive experiments have demonstrated the efficiency and effectiveness of our approaches over real/synthetic data sets. (C) 2019 Elsevier Ltd. All rights reserved.