滿足時空查詢之最佳旅遊軌跡

Optimal Traveling Trajectory Satisfying Spatio-temporal Query

呂維源(Lu-Wei-Yuan)

指導教授 ： 吳宜鴻

中原大學/電機資訊學院/資訊工程研究所/碩士(2016年)

https://doi.org/10.6840/cycu201600886

摘要

在資訊科技的時代下，各式各樣的資通訊軟體引領了許多應用的蓬勃發展，也實質改變了人們的生活，旅遊正是其中之一，然而人們仍須耗費許多時間在旅程規劃上，大多數現有軟體也只提供手動介面，因此本論文研究在總體時間限制下如何自動規劃旅程，我們提出新穎的兩階段演算法處理由一系列景點類型所構成的查詢，在時間和景點類型的雙重限制下，目標是透過分析使用者軌跡找出符合限制的最長旅遊路線。在實驗中，資料量的成長大幅影響查詢處理的時間，相較於對照用的深度優先走訪方法，所提出的演算法可以在最佳化和效率之間達到比較好的折衷。

關鍵字

旅程規劃，序列查詢，時間限制，最長路線

並列摘要

In the era of information technology, a variety of communication and computing tools result in the rapid development of many applications and substantially change people's life. Traveling is one of such applications. However, people still need to spend a lot of time on creating a nice plan for traveling. Most of the current tools simply provide manual interfaces for users. Consequently, this thesis studies the automatic ways of travel planning under the constraint of total traveling time. Specifically, a novel two-phase algorithm is proposed to process the queries composed by an ordered list of user-specified types of scenic spots. Under both the constraints, the goal is to find the longest path after the analysis of user trajectories. In the experiments, the growth of data amount has a huge impact on the query processing time. Compared with a baseline method, i.e., depth-first search algorithm, the proposed algorithm can achieve a better tradeoff between optimization and efficiency.

並列關鍵字

travel planning, sequence query, time constraint, longest path

參考文獻

[1] 余泉慶，「共乘系統之轉乘路徑規劃方法」，碩士論文，中原大學資訊工程所，2011。

[2] Zhijun Yin and Liangliang Cao And Jiawei Han .,“Diversified Trajectory Pattern Ranking in Geo-Tagged Social Media.”In Proc SDM, pp.980-991,2011.

[3] Yu-Ting Wen, Kae-Jer Cho, Wen-Chih Peng, Jinyoung Yeo and Seung-won Hwang.: “KSTR: Keyword-aware Skyline Travel Route Recommendation.” In Proc ICDM, 2015.

[4] Ugur Demiryurek1., Farnoush Banaei-Kashani1., Cyrus Shahabi1.,Anand Ranganathan.: “Online Computation of Fastest Path in Time-Dependent Spatial Networks ,” In Proc SSTD,92-111,2011.

[5] Bolin Ding, Jeffrey Xu Yu and Lu Qin..:”Finding Time-Dependent Shortest Paths over Large Graphs,” In Proc EDBT,2008