Finding Traffic-Aware Fastest Paths in Spatial Networks

Route planning and recommendation have received significant attention in recent years. In this light, we propose and investigate the novel problem of finding traffic-aware fastest paths (TAFP query) in spatial networks by considering the related traffic conditions. Given a sequence of user specified intended places O q and a departure time t, TAFP finds the fastest path connecting O q in order to guarantee that moving objects (e.g., travelers and bags) can arrive at the destination in time. This type of query is mainly motivated by indoor space applications, but is also applicable in outdoor space, and we believe that it may bring important benefits to users in many popular applications, such as tracking VIP bags in airports and recommending convenient routes to travelers. TAFP is challenged by two difficulties: (i) how to model the traffic awareness practically, and (ii) how to evaluate TAFP efficiently under different query settings. To overcome these challenges, we construct a traffic-aware spatial network G ta (V,E) by analysing uncertain trajectory data of moving objects. Based on G ta (V,E), two efficient algorithms are developed based on best-first and heuristic search strategies to evaluate TAFP query. The performance of TAFP has been verified by extensive experiments on real and synthetic spatial datasets