Current Visitors:


Learning to effectively estimate the travel time for fastest route recommendation

Ning Wu, Jingyuan Wang, Wayne Xin Zhao and Yang Jin

In Proceedings of the 28th ACM International Conference on Information and Knowledge Management (CIKM'19), pp. 1923–1932, 2019. Download

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.

The overall architecture of the our model. g(·)learns the cost from the source to a candidate location, called observable cost; h(·)predicts the estimated cost from a candidate location to the destination, called estimated cost.
The overall architecture of the our model. g(·)learns the cost from the source to a candidate location, called observable cost; h(·)predicts the estimated cost from a candidate location to the destination, called estimated cost.

If you find our work is helpful for your research, please kindly consider citing our paper.

 

@inproceedings{wu2019learning,

  title={Learning to Effectively Estimate the Travel Time for Fastest Route Recommendation},

  author={Wu, Ning and Wang, Jingyuan and Zhao, Wayne Xin and Jin, Yang},

  booktitle={Proceedings of the 28th ACM International Conference on Information and Knowledge Management},

  pages={1923--1932},

  year={2019}

}