Learning to Effectively Estimate the Travel Time for Fastest Route Recommendation

Fastest Route Recommendation (FRR) aims to find the fastest path in response to user's queries in a large complex road network. Early studies cast the FRR task as a pathfinding problem on graphs and adopt heuristic algorithms as the major solution due to the efficiency and robustness. A major problem of heuristic algorithms is that the heuristic function is usually empirically set with simple methods, which is difficult to model other useful factors. In this paper, we extend the classic A* algorithm for the FRR task by modeling complex traffic information with neural networks. Specially, we identify an important factor that is important to improve the FRR task, i.e. the estimation of travel time. For this purpose, we first develop a module for predicting the time-varying traffic speed for a road segment, which is the foundation for estimating the travel time. Conditioned on this module, we further design another module to estimate the fastest travel time between two locations connected by routes. We adopt neural networks to implement both modules for enabling the capacity of modeling complex traffic characteristics and dynamics. In this way, the original two cost functions of A* algorithm have been set in a more principled way with neural networks. To our knowledge, we are the first to use neural networks for improving A* algorithm in the FRR task. It elegantly combines the merits of A* algorithm and the powerful modeling capacities of neural networks for the FRR task. Extensive results on the three real-world datasets have shown the effectiveness and robustness of the proposed model.