TY - JOUR
T1 - Planning unobstructed paths in traffic-aware spatial networks
AU - Shang, Shuo
AU - Liu, Jiajun
AU - Zheng, Kai
AU - Lu, Hua
AU - Pedersen, Torben Bach
AU - Wen, Ji Rong
PY - 2015/10/1
Y1 - 2015/10/1
N2 - Route planning and recommendation have received significant attention in recent years. In this light, we study a novel problem of planning unobstructed paths in traffic-aware spatial networks (TAUP queries) to avoid potential traffic congestions. We propose two probabilistic TAUP queries: (1) a time-threshold query like “what is the path from the check-in desk to the flight SK 1217 with the minimum congestion probability to take at most 45 minutes?”, and (2) a probability-threshold query like “what is the fastest path from the check-in desk to the flight SK 1217 whose congestion probability is less than 20 %?”. These queries are mainly motivated by indoor space applications, but are also applicable in outdoor spaces. We believe that these queries are useful in some popular applications, such as planning unobstructed paths for VIP bags in airports and planning convenient routes for travelers. The TAUP queries are challenged by two difficulties: (1) how to model the traffic awareness in spatial networks practically, and (2) how to compute the TAUP queries efficiently under different query settings. To overcome these challenges, we construct a traffic-aware spatial network Gta(V, E) by analyzing uncertain trajectories of moving objects. Based on Gta(V, E), two efficient algorithms are developed to compute the TAUP queries. The performances of TAUP queries are verified by extensive experiments on real and synthetic spatial data.
AB - Route planning and recommendation have received significant attention in recent years. In this light, we study a novel problem of planning unobstructed paths in traffic-aware spatial networks (TAUP queries) to avoid potential traffic congestions. We propose two probabilistic TAUP queries: (1) a time-threshold query like “what is the path from the check-in desk to the flight SK 1217 with the minimum congestion probability to take at most 45 minutes?”, and (2) a probability-threshold query like “what is the fastest path from the check-in desk to the flight SK 1217 whose congestion probability is less than 20 %?”. These queries are mainly motivated by indoor space applications, but are also applicable in outdoor spaces. We believe that these queries are useful in some popular applications, such as planning unobstructed paths for VIP bags in airports and planning convenient routes for travelers. The TAUP queries are challenged by two difficulties: (1) how to model the traffic awareness in spatial networks practically, and (2) how to compute the TAUP queries efficiently under different query settings. To overcome these challenges, we construct a traffic-aware spatial network Gta(V, E) by analyzing uncertain trajectories of moving objects. Based on Gta(V, E), two efficient algorithms are developed to compute the TAUP queries. The performances of TAUP queries are verified by extensive experiments on real and synthetic spatial data.
KW - Efficiency
KW - Probabilistic path planning
KW - Spatio-temporal databases
KW - Traffic-aware spatial networks
UR - http://www.scopus.com/inward/record.url?scp=84943271559&partnerID=8YFLogxK
U2 - 10.1007/s10707-015-0227-9
DO - 10.1007/s10707-015-0227-9
M3 - Journal article
AN - SCOPUS:84943271559
SN - 1384-6175
VL - 19
SP - 723
EP - 746
JO - Geoinformatica
JF - Geoinformatica
IS - 4
ER -