Fastest Path Search Algorithm Fused With Deep Neural Networks

Given the road network and corresponding traffic condition information,fastest route recommendation aims to generate a fastest route based on the query that consists of an origin point,a destination point and a departure time.FRR is an important location-based service for urban computing.Accurate FRR can boost the efficiency of the transportation system,reduce the travel cost for users,and reduce the energy consumption to avoid pollution.Therefore,in order to better facilitate user travel,the research on the fastest route recommendation is very meaningful.However,FRR is a challenging issue due to the huge size of road network and its corresponding time-varying traffic condition.Existi ng methods used to solve this problem include statistical methods and learning-based methods.The authors model the road network as time dependent graphs,so that they can transform FRR into a shortest path query on a time dependent graph and solve this task via heuristic search,e.g.,Dijkstra and A*algorithms.However,a fixed time-dependent graph based on history traffic condition can not truly reflect the real-time road network.Recently,state-of-the-art method first extends the classic A*algorithm for the FRR task by modeling complex traffic information with neural networks.This method is effective to some extent,they suffer from inaccuracy of travel time estimation and admissibility of model,resulting sub-optimal results accordingly.In this paper,we propose an ASNN-FRR model to achieve accurate and efficient fastest path search.In this paper,we propose an ASNN-FRR model that contains two powerful predictors for g(·)and h(·)functions of A*algorithm respectively.Specifically,an adaptive graph convolutional recurrent network is used to accurately estimate the travel time of the observed path in g(·).We propose two adaptive modules for enhancing Graph Convolutional Network(GCN),which can capture node-specific patterns and infer the inter-dependencies among different traffic series automatically.Toward h(·),the model adopts a multi-task representation learning method to support origin-destination(OD)based travel time estimation,which can achieve high accuracy without the actual path information.Besides,we further consider the admissibility of A*algorithm,and utilize a rational setting of the loss function for h(·)estimator,which is likely to return a lower bound value without overestimation.At last,the two predictors are fused into the A*algorithm in a seamlessly way to help us find the realtime fastest route.We conduct extensive experiments on two real-world large scale trip datasets.The proposed approach clearly outperforms state-of-the-art methods for FRR task.