Popular route planning with travel cost estimation from trajectories

doi:10.1007/s11704-018-7249-z

Front. Comput. Sci.

2020, Vol. 14

Issue (1) : 191-207 https://doi.org/10.1007/s11704-018-7249-z

RESEARCH ARTICLE

Popular route planning with travel cost estimation from trajectories

Huiping LIU, Cheqing JIN(

), Aoying ZHOU

School of Data Science and Engineering, School of Computer Science and Software Engineering, East China Normal University, Shanghai 200062, China

Download: PDF(1322 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Cheqing JIN

Just Accepted Date: 09 February 2018 Online First Date: 03 December 2018 Issue Date: 24 September 2019

Cite this article:

Huiping LIU,Cheqing JIN,Aoying ZHOU. Popular route planning with travel cost estimation from trajectories[J]. Front. Comput. Sci., 2020, 14(1): 191-207.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-018-7249-z
https://academic.hep.com.cn/fcs/EN/Y2020/V14/I1/191

1	E Kanoulas, Y Du, T Xia, D Zhang. Finding fastest paths on a road network with speed patterns. In: Proceedings of the 22nd International Conference on Data Engineering. 2006, 1–10 https://doi.org/10.1109/ICDE.2006.71
2	B Ding, J Yu, L Qin. 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 https://doi.org/10.1145/1353343.1353371
3	H Liu, C Jin, B Yang, A Zhou. Finding top-k shortest paths with diversity. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(3): 488–502 https://doi.org/10.1109/TKDE.2017.2773492
4	H Liu, C Jin, B Yang, A Zhou. Finding top-k optimal sequenced routes. In: Proceedings of IEEE International Conference on Data Engineering. 2018 https://doi.org/10.1109/ICDE.2018.00058
5	J Yuan, Y Zheng, C Zhang, W Xie, X Xie, G Sun, Y Huang. 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 https://doi.org/10.1145/1869790.1869807
6	J Yuan, Y Zheng, X Xie, G Sun. Driving with knowledge from the physical world. In: Proceedings of the 17th ACM International Conference on Knowledge Discovery and Data Mining. 2011, 316–324 https://doi.org/10.1145/2020408.2020462
7	C Guo, B Yang, O Andersen, C S Jensen, K Torp. Ecosky: reducing vehicular environmental impact through eco-routing. In: Proceedings of the 31st IEEE International Conference on Data Engineering. 2015, 1412–1415 https://doi.org/10.1109/ICDE.2015.7113389
8	J Dai, B Yang, C Guo, Z Ding. Personalized route recommendation using big trajectory data. In: Proceedings of the 31st IEEE International Conference on Data Engineering. 2015, 543–554 https://doi.org/10.1109/ICDE.2015.7113313
9	B Yang, C Guo, Y Ma, C S Jensen. Toward personalized, context-aware routing. The International Journal on Very Large Data Bases, 2015, 24(2): 297–318 https://doi.org/10.1007/s00778-015-0378-1
10	J Wang, C Chen, J Wu, Z Xiong. 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 https://doi.org/10.1145/3097983.3097985
11	J Wang, X He, Z Wang, J Wu, N J Yuan, X Xie, Z Xiong. CD-CNN: a partially supervised cross-domain deep learning model for urban resident recognition. 2018, arXiv preprint arXiv:1804.09901
12	J Wang, Q Gu, J Wu, G Liu, Z Xiong. 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 https://doi.org/10.1109/ICDM.2016.0061
13	Y Zheng. Urban computing: enabling urban intelligence with big data. Frontiers of Computer Science, 2017, 11(1): 1–3 https://doi.org/10.1007/s11704-016-6907-2
14	W Dong, Y Wang, H Yu. An identification model of urban critical links with macroscopic fundamental diagram theory. Frontiers of Computer Science, 2017, 11(1): 27–37 https://doi.org/10.1007/s11704-016-6080-7
15	C Chen, X Chen, Z Wang, Y Wang, D Zhang. ScenicPlanner: planning scenic travel routes leveraging heterogeneous user-generated digital footprints. Frontiers of Computer Science, 2017, 11(1): 61–74 https://doi.org/10.1007/s11704-016-5550-2
16	J Yuan, Y Zheng, X Xie, G Sun. T-drive: enhancing driving directions with taxi drivers. IEEE Transactions on Knowledge and Data Engineering, 2012, 25(1): 220–232 https://doi.org/10.1109/TKDE.2011.200
17	Y Wang, Y Zheng, Y Xue. 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 https://doi.org/10.1145/2623330.2623656
18	P D Grnwald, I J Myung, M A Pitt. Advances in Minimum Description Length: Theory and Applications (Neural Information Processing). Massachusetts: The MIT Press, 2005
19	H Liu, C Jin, A Zhou. Popular route planning with travel cost estimation. In: Proceedings of International Conference on Database Systems for Advanced Applications. 2016, 403–418 https://doi.org/10.1007/978-3-319-32049-6_25
20	E W Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1959, 1(1): 269–271 https://doi.org/10.1007/BF01386390
21	P E Hart, N J Nilsson, B Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 2007, 4(2): 100–107 https://doi.org/10.1109/TSSC.1968.300136
22	K L Cooke, E Halsey. The shortest route through a network with timedependent internodal transit times. Journal of Mathematical Analysis and Applications, 1997, 14(3): 493–498 https://doi.org/10.1016/0022-247X(66)90009-6
23	H Gonzalez, J Han, X Li, M Myslinska, J P Sondag. 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	K Zheng, Y Zheng, X Xie, X Zhou. Reducing uncertainty of lowsampling-rate trajectories. In: Proceedings of the 28th IEEE International Conference on Data Engineering. 2012, 1144–1155
25	L Y Wei, Y Zheng, W C Peng. Constructing popular routes from uncertain trajectories. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2012, 195–203 https://doi.org/10.1145/2339530.2339562
26	Z Chen, H T Shen, X Zhou. Discovering popular routes from trajectories. In: Proceedings of the 27th IEEE International Conference on Data Engineering. 2011, 900–911 https://doi.org/10.1109/ICDE.2011.5767890
27	W Luo, H Tan, L Chen, L M Ni. 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 https://doi.org/10.1145/2463676.2465287
28	J Zheng, L M Ni. 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	B Yang, M Kaul, C S Jensen. Using incomplete information for complete weight annotation of road networks. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(5): 1267–1279 https://doi.org/10.1109/TKDE.2013.89
30	B Yang, C Guo, C S Jensen, M Kaul, S Shang. Stochastic skyline route planning under time-varying uncertainty. In: Proceedings of the 30th IEEE International Conference on Data Engineering. 2014, 136–147 https://doi.org/10.1109/ICDE.2014.6816646
31	J Dai, B Yang, C Guo, C S Jensen, J Hu. Path cost distribution estimation using trajectory data. In: Proceedings of the 42nd International Conference on Very Large Data Bases. 2016, 85–96 https://doi.org/10.14778/3021924.3021926
32	M Ester, H P Kriegel, X Xu. 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	S Ranu, P Deepak, A D Telang, P Deshpande. Indexing and matching trajectories under inconsistent sampling rates. In: Proceedings of the 31st IEEE International Conference on Data Engineering. 2015, 999–1010 https://doi.org/10.1109/ICDE.2015.7113351
34	J G Lee, J Han, K Y Whang. Trajectory clustering: a partition-andgroup framework. In: Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. 2007, 593–604 https://doi.org/10.1145/1247480.1247546
35	J Mao, T Wang, C Jin, A Zhou. Feature grouping-based outlier detection upon streaming trajectories. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(12): 2696–2709 https://doi.org/10.1109/TKDE.2017.2744619
36	R K Balan, K X Nguyen, L Jiang. 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 https://doi.org/10.1145/1999995.2000006
37	B Ding, J X Yu, L Qin. 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 https://doi.org/10.1145/1353343.1353371
38	M L Fredman. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 1987, 34(3): 596–615 https://doi.org/10.1145/28869.28874

[1]

Download

[1]	Jingwei ZHANG, Chao YANG, Qing YANG, Yuming LIN, Yanchun ZHANG. HGeoHashBase: an optimized storage model of spatial objects for location-based services[J]. Front. Comput. Sci., 2020, 14(1): 208-218.
[2]	Zhefan ZHONG, Xin LIN, Liang HE, Jing YANG. Answering why-not questions on KNN queries[J]. Front. Comput. Sci., 2019, 13(5): 1062-1071.
[3]	Chao CHEN,Xia CHEN,Zhu WANG,Yasha WANG,Daqing ZHANG. ScenicPlanner: planning scenic travel routes leveraging heterogeneous user-generated digital footprints[J]. Front. Comput. Sci., 2017, 11(1): 61-74.
[4]	Xiao PAN, Xiaofeng MENG. Preserving location privacy without exact locations in mobile services[J]. Front Comput Sci, 2013, 7(3): 317-340.

Viewed

Full text

Abstract

Cited

Shared

Discussed