尋找一條符合使用者需求的最短路徑

Finding Shortest Paths Considering the Requirements of Users

呂其錞

指導教授 ： 陳良弼

國立清華大學/電機資訊學院/資訊工程學系/碩士(2014年)

摘要

在道路網絡上找尋最短路徑的問題已經被研究許多年，許多有效率的解決方法都已經被提出。從使用者角度而言，有時候使用者的需求不只單單是只從出發地到目的地這麼單純，使用者可能會一些其它的需求,例如到餐廳吃飯和去郵局寄信，因為使用者這些特殊的需求，使得那一些建立在傳統的最短路徑問題上的解決方法無法滿足使用者的需求。在此篇論文中，為了滿足使用者的需求，我們提出了三個主要的方法來解決包含使用者需求的最短路徑，前面兩個主要的不含/包含終點的基本方法是利用目前已經找到符合使用者需求的路徑來當作門檻值,利用此門檻值我們可以剔除掉那些長度已經確定比門檻值還要大的路徑，第三個方法,包含終點的修剪方法,是利用我們提出的兩個lemma 和一條已符合使用者需求的路徑來規劃出的一個膠囊形狀的範圍，只有落在此膠囊形狀內的那些點所形成的路徑我們才需要考慮。我們的實驗結果顯示我們提出的方法有不錯的表現，修剪方法更是大大的加速了我們的計算效率。

關鍵字

道路網絡 ； 最短路徑 ； 使用者需求

並列摘要

Finding the shortest paths in road networks has been studied for years. However, from the perspective of a user, finding the shortest path from a start location to a destination is only a basic requirement. Other demands may also be involved, such as asking for dining or mailing on the way to the destination. In this paper, we consider a novel problem of finding the shortest path which satisfies the user requirement represented as a set of points of interest such as a shopping center or a restaurant. Three main approaches are proposed to deal with this problem. The first two basic approaches answer the queries without and with a destination by using the BFS and DFS based algorithms, respectively. Moreover, we design some pruning strategies for reducing the search space of the paths and then propose another advanced approach. The experiment results show that the advanced approach has great performance in terms of executing time.

並列關鍵字

road network ； shortest ； distance ； path ； user requirement

參考文獻

[D59]E. W. Dijkstra, “A note on two problems in connexion with graphs,” In Proc. Numerische Mathematik, 1959, vol. 1, no. 1, pp. 269-271.

[NZ02] T. E. Ng, & H. Zhang, “Predicting internet network distance with coordinates-based approaches,” Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’02), pp. 170-179, 2002.

[W13] F. Wei, “Finding nearest neighbors in road networks: a tree decomposition method,” Proceedings of the 16th EDBT/ICDT workshop, 2013, pp. 233-240.

[AD11] I. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck, “A hub-based labeling algorithm for shortest paths in road networks,” Proceedings of the 10thInternational Symposium on Experimental Algorithm (SEA2011), pp. 230-241, 2011.

[AD12] I. Abraham, D. Delling, A. V. Goldberg, & R. F. Werneck, “Hierarchical hub labelings for shortest paths,” Proceedings of the 11th International Symposium on Experimental Algorithm (ESA’12), pp. 24-35, 2012.