Popular route planning with travel cost estimation from trajectories

Abstract

With the increasing number of GPS-equipped vehicles, more and more trajectories are generated continuously, based on which some urban applications become feasible, such as route planning. In general, popular route that has been travelled frequently is a good choice, especially for people who are not familiar with the road networks. Moreover, accurate estimation of the travel cost (such as travel time, travel fee and fuel consumption) will benefit a wellscheduled trip plan. In this paper, we address this issue by finding the popular route with travel cost estimation. To this end, we design a system consists of three main components. First, we propose a novel structure, called popular traverse graph where each node is a popular location and each edge is a popular route between locations, to summarize historical trajectories without road network information. Second, we propose a self-adaptive method to model the travel cost on each popular route at different time interval, so that each time interval has a stable travel cost. Finally, based on the graph, given a query consists of source, destination and leaving time, we devise an efficient route planning algorithmwhich considers optimal route concatenation to search the popular route from source to destination at the leaving time with accurate travel cost estimation. Moreover, we conduct comprehensive experiments and implement our system by a mobile App, the results show that our method is both effective and efficient.

Keywords

location-based services / route planning / travel cost estimation / minimum description length / optimal road concatenation

References

[1] Kanoulas E, Du Y, Xia T, Zhang D. Finding fastest paths on a road network with speed patterns. In: Proceedings of the 22nd International Conference on Data Engineering. 2006, 1–10

[2] Ding B, Yu J, Qin L. Finding time-dependent shortest paths over large graphs. In: Proceedings of the 11th International Conference on Extending Database Technology: Advances in Database Technology. 2008, 205–216

[3] Liu H, Jin C, Yang B, Zhou A. Finding top-k shortest paths with diversity. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(3): 488–502

[4] Liu H, Jin C, Yang B, Zhou A. Finding top-k optimal sequenced routes. In: Proceedings of IEEE International Conference on Data Engineering. 2018

[5] Yuan J, Zheng Y, Zhang C, Xie W, Xie X, Sun G, Huang Y. T-drive: driving directions based on taxi trajectories. In: Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. 2010, 99–108

[6] Yuan J, Zheng Y, Xie X, Sun G. Driving with knowledge from the physical world. In: Proceedings of the 17th ACM International Conference on Knowledge Discovery and Data Mining. 2011, 316–324

[7] Guo C, Yang B, Andersen O, Jensen C S, Torp K. Ecosky: reducing vehicular environmental impact through eco-routing. In: Proceedings of the 31st IEEE International Conference on Data Engineering. 2015, 1412–1415

[8] Dai J, Yang B, Guo C, Ding Z. Personalized route recommendation using big trajectory data. In: Proceedings of the 31st IEEE International Conference on Data Engineering. 2015, 543–554

[9] Yang B, Guo C, Ma Y, Jensen C S. Toward personalized, context-aware routing. The International Journal on Very Large Data Bases, 2015, 24(2): 297–318

[10] Wang J, Chen C, Wu J, Xiong Z. No longer sleeping with a bomb: a duet system for protecting urban safety from dangerous goods. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017, 1673–1681

[11] Wang J, He X, Wang Z, Wu J, Yuan N J, Xie X, Xiong Z. CD-CNN: a partially supervised cross-domain deep learning model for urban resident recognition. 2018, arXiv preprint arXiv:1804.09901

[12] Wang J, Gu Q, Wu J, Liu G, Xiong Z. Traffic speed prediction and congestion source exploration: a deep learning method. In: Proceedings of the 16th IEEE International Conference on Data Mining. 2016, 499–508

[13] Zheng Y. Urban computing: enabling urban intelligence with big data. Frontiers of Computer Science, 2017, 11(1): 1–3

[14] Dong W, Wang Y, Yu H. An identification model of urban critical links with macroscopic fundamental diagram theory. Frontiers of Computer Science, 2017, 11(1): 27–37

[15] Chen C, Chen X, Wang Z, Wang Y, Zhang D. ScenicPlanner: planning scenic travel routes leveraging heterogeneous user-generated digital footprints. Frontiers of Computer Science, 2017, 11(1): 61–74

[16] Yuan J, Zheng Y, Xie X, Sun G. T-drive: enhancing driving directions with taxi drivers. IEEE Transactions on Knowledge and Data Engineering, 2012, 25(1): 220–232

[17] Wang Y, Zheng Y, Xue Y. Travel time estimation of a path using sparse trajectories. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2014, 25–34

[18] Grnwald P D, Myung I J, Pitt M A. Advances in Minimum Description Length: Theory and Applications (Neural Information Processing). Massachusetts: The MIT Press, 2005

[19] Liu H, Jin C, Zhou A. Popular route planning with travel cost estimation. In: Proceedings of International Conference on Database Systems for Advanced Applications. 2016, 403–418

[20] Dijkstra E W. A note on two problems in connexion with graphs. Numerische Mathematik, 1959, 1(1): 269–271

[21] Hart P E, Nilsson N J, Raphael B. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 2007, 4(2): 100–107

[22] Cooke K L, Halsey E. The shortest route through a network with timedependent internodal transit times. Journal of Mathematical Analysis and Applications, 1997, 14(3): 493–498

[23] Gonzalez H, Han J, Li X, Myslinska M, Sondag J P. Adaptive fastest path computation on a road network: a traffic mining approach. In: Proceedings of the 23rd International Conference on Very Large Data Bases. 2007, 794–805

[24] Zheng K, Zheng Y, Xie X, Zhou X. Reducing uncertainty of lowsampling-rate trajectories. In: Proceedings of the 28th IEEE International Conference on Data Engineering. 2012, 1144–1155

[25] Wei L Y, Zheng Y, Peng W C. Constructing popular routes from uncertain trajectories. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2012, 195–203

[26] Chen Z, Shen H T, Zhou X. Discovering popular routes from trajectories. In: Proceedings of the 27th IEEE International Conference on Data Engineering. 2011, 900–911

[27] Luo W, Tan H, Chen L, Ni L M. Finding time period-based most frequent path in big trajectory data. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. 2013, 713–724

[28] Zheng J, Ni L M. Time-dependent trajectory regression on road networks via multi-task learning. In: Proceedings of the 27th AAAI Conference on Artificial Intelligence. 2013, 1048–1055

[29] Yang B, Kaul M, Jensen C S. Using incomplete information for complete weight annotation of road networks. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(5): 1267–1279

[30] Yang B, Guo C, Jensen C S, Kaul M, Shang S. Stochastic skyline route planning under time-varying uncertainty. In: Proceedings of the 30th IEEE International Conference on Data Engineering. 2014, 136–147

[31] Dai J, Yang B, Guo C, Jensen C S, Hu J. Path cost distribution estimation using trajectory data. In: Proceedings of the 42nd International Conference on Very Large Data Bases. 2016, 85–96

[32] Ester M, Kriegel H P, Xu X. A density-based algorithm for discovering clusters in large spatial databases with noise. In: Proceedings of International Conference on Knowledge Discovery and Data Mining. 1996, 226–231

[33] Ranu S, Deepak P, Telang A D, Deshpande P. Indexing and matching trajectories under inconsistent sampling rates. In: Proceedings of the 31st IEEE International Conference on Data Engineering. 2015, 999–1010

[34] Lee J G, Han J, Whang K Y. Trajectory clustering: a partition-andgroup framework. In: Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. 2007, 593–604

[35] Mao J, Wang T, Jin C, Zhou A. Feature grouping-based outlier detection upon streaming trajectories. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(12): 2696–2709

[36] Balan R K, Nguyen K X, Jiang L. Real-time trip information service for a large taxi fleet. In: Proceedings of the 9th International Conference on Mobile Systems, Applications, and Services. 2011, 99–112

[37] Ding B, Yu J X, Qin L. Finding time-dependent shortest paths over large graphs. In: Proceedings of the 11th International Conference on Extending Database Technology: Advances in Database Technology. 2008, 205–216

[38] Fredman M L. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 1987, 34(3): 596–615

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature