在道路網絡上找尋最短路徑的問題已經被研究許多年，許多有效率的解決方法都已經被提出。從使用者角度而言，有時候使用者的需求不只單單是只從出發地到目的地這麼單純，使用者可能會一些其它的需求,例如到餐廳吃飯和去郵局寄信，因為使用者這些特殊的需求，使得那一些建立在傳統的最短路徑問題上的解決方法無法滿足使用者的需求。在此篇論文中，為了滿足使用者的需求，我們提出了三個主要的方法來解決包含使用者需求的最短路徑，前面兩個主要的不含/包含終點的基本方法是利用目前已經找到符合使用者需求的路徑來當作門檻值,利用此門檻值我們可以剔除掉那些長度已經確定比門檻值還要大的路徑，第三個方法,包含終點的修剪方法,是利用我們提出的兩個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.

Acknowledgement............................................i
Abstract..................................................ii
摘要......................................................iii
Table of Contents.........................................iv
List of Figures............................................v
1.Introduction.............................................1
2.Related Works............................................4
3.Preliminaries............................................6
4.Approaches to finding the shortest path that contains UR.9
5.Experiments.............................................25
6.Conclusions.............................................30
References................................................31

[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.
[AS12] T. Akiba, C. Sommer, & K. I. Kawarabayashi, “Shortest-path queries for complex networks: exploiting low tree-width outside the core,” Proceedings of the 15th International on Extending Database Technology (EDBT’12), pp. 144-155, 2012.
[AI13] T. Akiba, Y. Iwata, & Y. Yoshida, “Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling,” Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD’13), pp. 349-360, 2013.
[CY09] J. Cheng, & J. X. Yu, “On-line exact shortest distance query processing,” Proceedings of the 12th International on Extending Database Technology (EDBT’09), pp. 481-492, 2009.
[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.
[DK08] B. B. Dalvi, M. Kshirsagar, & S. Sudarshan, “Keyword search on external memory data graphs,” Proceedings of the 34th International Conference on Very Large Databases (VLDB’08), pp. 1189-1204, 2008.
[FH08] I. D. Felipe, V. Hristidis, and N. Rishe, “Keyword search on spatial databases,” Proceedings of the 24th International Conference on Data Engineering (ICDE’08), 2008, pp.656-665.
[GB10] A. Gubichev, S. Bedathur, S. Seufert, & G. Weikum, “Fast and accurate estimation of shortest paths in large graphs,” Proceedings of the 19th ACM International Conference on Information and Knowledge Management (CIKM’10), pp. 499-508, 2010.
[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.
[PB09] M. Potamias, F. Bonchi, C. Castillo, & A. Gionis, “Fast shortest path distance estimation in large networks,” Proceedings of the 18th ACM International Conference on Information and Knowledge Management (CIKM’09), pp. 867-876, 2009.
[PS98] Stefano Pallottino, Maria Grazia Scutellà, “Shortest Path Algorithms in Transportation Models: Classical and Innovative Aspects,” Proceedings of Equilibrium and Advanced Transportation Modelling (Centre for Research on Transportation), pp. 867-876, 1998.
[QC12] M. Qiao, H. Cheng, L. Chang, & J. X. Yu, “Approximate Shortest Distance Computing: A Query-Dependent Local Landmark Scheme,” Proceedings of the 2012 IEEE 28th International Conference on Data Engineering (ICDE’12), pp. 462-473, 2012.
[RN12] J. B. Rocha-Junior, K. Nørvåg, “Top-k spatial keyword queries on road networks,” Proceedings of the15th International Conference on Extending Database Technology (EDBT’12), 2012, pp. 168-179.
[W10] F. Wei, “TEDI: Efficient Shortest Path Query Answering on Graphs,” Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data (SIGMOD’10), 2010, pp. 99-110.
[W13] F. Wei, “Finding nearest neighbors in road networks: a tree decomposition method,” Proceedings of the 16th EDBT/ICDT workshop, 2013, pp. 233-240.
[ZC09] D. Zhang, Y. M. Chee, A. Mondal, A. K. H. Tung, and M. Kitsuregawa, “Keyword search in spatial databases: Towards searching by document,” Proceedings of the 25th International Conference on Data Engineering (ICDE’09), 2009, pp.688-699.