Efficient Path Routing Over Road Networks in the Presence of Ad-Hoc Obstacles. (February 2020)

• Record Type: Journal Article
• Authors: Al-Baghdadi, Ahmed; Lian, Xiang; Cheng, En
• Is Part Of: Information systems. Volume 88(2020)
• Publication Date: 2020-02
• Subjects: Ad-hoc weather-based obstacles -- Ad-hoc keyword-based obstacles -- Road networks -- Path routing query over road networks with ad-hoc obstacles; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2019.101453
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: 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. Highlights: Formally define path routing query over road networks with ad-hoc obstacles (PRAO). Design effective pruning strategies to reduce the search space of the PRAO problem. Devise an effective indexing mechanism to support the PRAO query processing. Develop efficient and effective PRAO query answering algorithm. Conduct extensive experiment to confirm the PRAO performance on real/synthetic data.