Probabilistic Time-Constrained Paths Search over Uncertain Road Networks

With the proliferation of positioning technologies and GPS-enabled mobile devices, it has become very important to search for optimal paths to cover required points of interest(POIs, e.g., banks and restaurants) over road networks in many location-based services. In practice, however, traffic condit...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on services computing 2018-03, Vol.11 (2), p.399-414
Main Authors: Li, Wengen, Guan, Jihong, Lian, Xiang, Zhou, Shuigeng, Cao, Jiannong
Format: Article
Language:English
Subjects:
Computational modeling
Computer science
Location-based service
path search
Probabilistic logic
Reliability
Roads
service time-constrained POI
Time factors
uncertain road network
Uncertainty
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:With the proliferation of positioning technologies and GPS-enabled mobile devices, it has become very important to search for optimal paths to cover required points of interest(POIs, e.g., banks and restaurants) over road networks in many location-based services. In practice, however, traffic conditions are inherently uncertain and dynamically changing overtime, which makes it rather challenging to provide accurate results for path queries based on travelling time. Inspired by this, we considerthe practical settings of road networks and model them by uncertain road networks (URNs) on which the travelling time of each road is uncertain and captured by a set of travelling time samples. Then, we formalize the probabilistic time-constrained path (PTP) query over uncertain road networks to retrieve those paths that not only cover required POIs with constrained service time but also have the minimum travelling times in high confidence. We prove that PTPquery problem is NP-hard. In orderto answer PTPqueries efficiently, we propose an efficient PTPquery approach with effective pruning strategies regarding the time constraints on POIs and the probabilistic/rank requirements of queries. Extensive experiments on real road networks validate the efficiency and effectiveness of our PTPquery approach.
ISSN:1939-1374
2372-0204
DOI:10.1109/TSC.2016.2582692