成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	李晟維 Lee, Cheng-Wei
論文名稱：	利用大軌跡資料在動態道路上進行個人化路線推薦 Personalize Path Recommendation in Dynamic Networks Based on Big Trajectory Data
指導教授：	李強 Lee, Chiang
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering
論文出版年：	2017
畢業學年度：	105
語文別：	英文
論文頁數：	58
中文關鍵詞：	路網、個人化、動態、軌跡、大資料處理、查詢處理
外文關鍵詞：	road networks, personalize, dynamic, trajectory, route planning, query processing, mining, big data
相關次數：	點閱：109 下載：2
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

路線規劃一直以來都是我們生活中不可或缺的一部份, 現今相關的路線規劃服務, 例如:Google Map、Bing Map、GPS 導航等都提供使用者一條或數條最快或最短的路徑。然而這些服務往往不能滿足駕駛人的需求, 因為對於不同的駕駛人來說, 儘管起點與終點相同, 可能會因為不同的駕駛習慣而選擇不一樣的路線; 再者, 考量到了同條道路在不同時間下的交通變化, 同樣的起點終點在不同時間下也應該有不同的結果, 而這些正是目前的服務或研究所缺少的。因此我們提出了一個新的路徑規劃方法, 除了考量每個使用者的駕駛行為外, 亦參考了大量車
輛的歷史軌跡資料, 並模擬出隨著時間而變化的道路交通狀況, 我們希望最終推薦的路徑從任何方面來看都是最適合該駕駛人的。由於此研究需要針對大量的車輛歷史軌跡資料做資料挖掘的動作, 因此我們一開始將收集車輛的原始GPS數據, 並根據此數據挖掘出每個駕駛人的駕駛習慣, 例如偏好的速度、偏好的距離、對每條路的熟悉度等, 建立獨特的駕駛行為模型。同樣依據大量的車輛歷史軌跡, 我們可以準確的分析每條道路在每個時段下的交通狀況, 並提出Baseline algorithm、Advancing algorithm、Improve algorithm和Hierarchy algorithm來評估每條道路與駕駛人的適合程度。 Baseline利用貪婪的概念搜尋兩點間所有路徑配合配上一
些剪枝的機制, 來找出最佳解; 後面三個算法分別不同的方式, 找出近似解, 在確保精準度的前提下, 大幅增快了查詢時間。最後我們提出了一系列的實驗來評測各個演算法的成效。

Route planning has an irreplaceable role in our life for a long time. Nowadays, all of the route planning service, ex: Google Map、Bing Map、GPS navigation, provide multiple effective routes for their users. However, these cannot satisfy all of the demands which drivers ask for. In spite of having the same destination, every driver have their own habit when driving, affecting the route they choose. Furthermore, due to the timing variation
of the traffic condition, we should give different suggestions for users in every single time, and it’s what we lack. This work proposes a new way of route planning, which not only consider the driving behavior of every user, but also refer to considerable historical
trajectory data, in order to simulate the traffic condition changing continuously. Finding out the most appropriate choice for every user in every aspect is the final goal of our work. In our work, we study the problem of recommendation of personalized routes to drivers based on big trajectory data. First, we collect huge trajectory data and mine time-variant traffic information for every road. Then we propose a model that capable of leaning driver’s driving preference from driver’s historical trajectories. We propose Baseline algorithm, Advancing algorithm, Improve algorithm, and Hierarchy algorithm
to retrieve a best route according to a driver’s preference and many time-variant travel costs. The first one uses the concept of greedy to search the best answer between the two vertices, and the remaining three approximation algorithms improve the time efficiency.
Finally, we presented a series of experiments to evaluate the efficiency and effectiveness of each algorithm.

Table of Contents iv
Table of Figures vi
Table of Tables viii
Introduction 1
Related Work 7
1 Traditional route planning . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Historical trajectory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 Personalized route recommendation . . . . . . . . . . . . . . . . . . . . . 9
4 Dynamic networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Preliminary and Problem Definition 12
1 Explanation of Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Preference function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1 Speed score . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Familiarity score . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Distance score . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Algorithm 21
1 Offline Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.1 Raw GPS Data and Road Networks . . . . . . . . . . . . . . . . . 22
1.2 Map Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.3 Personalized preference function . . . . . . . . . . . . . . . . . . . 23
1.4 Calculate historical average speed for each road . . . . . . . . . . 23
1.5 Road information . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2 Baseline Algorithm & Advancing Algorithm . . . . . . . . . . . . . . . . 24
2.1 Baseline Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2 Advancing Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 26
3 The Improve Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4 The Hierarchy Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Experimental Study 38
1 Experimental Environment . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.1 Processing time with varying query length . . . . . . . . . . . . . 38
2.2 Experiment results of Improve algorithm with varying k on large
scale maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.3 Experiment results of Hierarchy algorithm with varying dis . . . . 42
2.4 Accuracy rate with varying query length . . . . . . . . . . . . . . 43
2.5 Processing time with varying α, β, γ . . . . . . . . . . . . . . . . . 45
2.6 Accuracy rate with varying α, β, γ . . . . . . . . . . . . . . . . . . 47
2.7 Experiment results with varying Avg rate(di). . . . . . . . . . . . 49
2.8 Experiment results with varying σ(di) . . . . . . . . . . . . . . . . 50
Conclusions 55
Reference 56
                                    

[1] Ove Andersen, Christian S. Jensen, Kristian Torp, and Bin Yang, “Ecotour: Reducing the environmental footprint of vehicles using eco-routes,” in Mobile Data Management, pages 338-340, 2013.
[2] Vaida Ceikute, and Christian S. Jensen, “Routing service quality-local driver behavior versus routing services,” in Mobile Data Management, pages 97-106, 2013.
[3] Kai-Ping Chang, Ling-Yin Wei, Mi-Yeh Yeh, and Wen-Chih Peng, “Discovering personalized routes from trajectories,” in ACM SIGSPATIAL International Workshop
on Location-Based Social Networks, 2011.
[4] Zaiben Chen, Heng Tao Shen, and Xiaofang Zhou, “Discovering popular routes from trajectories,” in International Conference on Data Engineering, pages 900-
911, 2011.
[5] Jian Dai, Bin Yang, Chenjuan Guo, Zhiming Ding, “Personalized Route Recommendation using Big Trajectory Data,” in International Conference on Data Engineering,
pages 543-554, 2015.
[6] Edsger W. Dijkstra, “A note on two problems in connexion with graphs,” in Numerische Mathematik, 1959.
[7] Peter E. Hart, Nils J. Nilsson, Bertram Raphael, “A formal basis for the heuristic determination of minimum cost paths,” in IEEE transactions on Systems Science
and Cybernetics, pages 100-107, 1968.
[8] Ming Hua and Jian Pei, “Probabilistic path queries in road networks: traffic uncertainty aware path selection,” in Proceedings of the 13th International Conference
on Extending Database Technology, pages 347-358, 2010
[9] Evangelos Kanoulas, Yang Du, Tian Xia, and Donghui Zhang, “Finding fastest paths on a road network with speed patterns,” in International Conference on Data
Engineering, 2006.
[10] Hans-Peter Kriegel, Matthias Renz, and Matthias Schubert, “Route skyline queries: A multi-preference path planning approach,” in International Conference on Data
Engineering, pages 261-272, 2010
[11] Julia Letchner, John Krumm, and Eric Horvitz, “Trip router with individualized preferences(trip),” in Proceedings of the National Conference on Artificial Intelligence, 2006.
[12] Wuman Luo, Haoyu Tan, Lei Chen, and Lionel 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.
[13] N. Malviya, S. Madden, and A. Bhattacharya, “A continuous query system for dynamic route planning,” in International Conference on Data Engineering, pages
792-803, 2011
[14] Stephan B¨orzs¨onyi, Donald Kossmann, and Konrad Stocker, “The skyline operator,” in Proceedings of 17th International Conference on Data Engineering, pages
421-430, 2001.
[15] Leslie G. Valiant, “The complexity of enumeration and reliability problems,” in Society for Industrial and Applied Mathematics, pages 410-421, 1979.
[16] Jiajie Xu, Limin Guo, Zhiming Ding, Xiling Sun, Chengfei Liu, “Traffic aware route planning in dynamic road networks,” in International Conference on Database
Systems for Advanced Applications, pages 576-591, 2012
[17] Bin Yang, Chenjuan Guo , and Christian S. Jensen, “Travel cost inference from sparse, spatio temporally correlated time series using markov models,” in Proceedings of the VLDB Endowment, pages 769-780, 2013.
[18] Bin Yang, Chenjuan Guo, Christian S. Jensen, Manohar Kaul, and Shuo Shang, “Stochastic skyline route planning under time-varying uncertainty,” in International
Conference on Data Engineering, pages 136-147, 2014.
[19] Bin Yang, Manohar Kaul, and Christian S. Jensen, “Using incomplete information for complete weight annotation of road networks,” in IEEE Transactions on
Knowledge and Data Engineering, pages 1267-1279, 2014.
[20] Jing Yuan, Yu Zheng, Chengyang Zhang, Wenlei Xie, Xing Xie, Guangzhong Sun, and Yan Huang, “T-drive: driving directions based on taxi trajectories,” in Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 99-108, 2010.
[21] Xiaoxiao Yu, Huasha Zhao, Lin Zhang, Shining Wu, Bhaskar Krishnamachari,and Victor O.K. Li, “Cooperative sensing and compression in vehicular sensor networks
for urban monitoring,” in International Conference on Communications, pages 1-5, 2010.
[22] http://siwa-umh.cs.umn.edu/app/webroot/osme/.
[23] http://sensor.ee.tsinghua.edu.cn/datasets.html.

校內：2022-08-23公開
校外：2022-08-23公開

簡易檢索 / 詳目顯示

相關論文