進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-2008201512310000
論文名稱(中文) 道路網路上之K條相異路徑搜尋技術
論文名稱(英文) Search of K-Discriminative Paths on Road Networks
校院名稱 成功大學
系所名稱(中) 資訊工程學系
系所名稱(英) Institute of Computer Science and Information Engineering
學年度 103
學期 2
出版年 104
研究生(中文) 陳楚狄
研究生(英文) Chu-Di Chen
學號 P76014698
學位類別 碩士
語文別 英文
論文頁數 47頁
口試委員 指導教授-莊坤達
口試委員-謝孫源
口試委員-高宏宇
口試委員-黃仁暐
口試委員-黃春融
中文關鍵字 路徑搜尋  多起點與多終點  緊急避難  多目標最佳化  演化式計算 
英文關鍵字 Path search  multiple sources and destinations  emergency evacuation  multi-objective optimization  evolutionary computing 
學科別分類
中文摘要 在本篇論文,我們探討在路徑網路上搜尋K條相異路徑的技術,給定單一起點與單一終點,我們搜尋從起點到終點間的K條相異路徑。這些路徑必須滿足一些條件來符合使用者的需求,條件與條件間可能會互相衝突,因此多目標問題中的柏拉圖曲線概念就被提出,但是搜尋柏拉圖曲線是相當耗費記憶體與時間的操作,並不能滿足在緊急的情況當中,同時單一起點與單一終點也不符合在一些情境當中,如區域避難,因此在本篇論文我們針對搜尋K條相異路徑提出三種不同的查詢方式,分別為緊急查詢、柏拉圖曲線查詢以及多起點與多終點查詢,在真實的路徑網路上我們驗證演算法的準確性以及效率性。
英文摘要 In this thesis, we study the problem of searching k discriminative paths on road networks. Given a source node src and a destination node dest on a road network, we aim to search k discriminative paths from src to dest. The paths have to satisfy some criteria to make these paths be suitable for the user. The criteria may conflict with each other. Therefore, the concept of skyline or Pareto curve are proposed. However, finding Pareto curve consumes tremendous resources in terms of memory and execution time. That is infeasible in emergency circumstances. Single source and destination are not sufficient in many situations such as regional evacuation. Therefore, we proposed three query types for the k discriminate paths problem, namely, emergency query, Pareto-based query and multiple sources and destinations query for different scenarios. Evaluation results show the effectiveness and efficiency of the proposed algorithms. We also compare with state-of-the-art approaches and discuss the experimental results on real road networks.
論文目次 中文摘要................i
Abstract ...............ii
Contents ...............iii
List of Tables ..............v
List of Figures ...............vi
1 Introduction ...............1
2 Preliminaries ..............6
2.1 Problem Statements ...........6
2.2 Related Works .............10
2.3 Application Design ............14
3 Query Frameworks .............16
3.1 The Weighted Sum Technique ..........16
3.2 Emergence Query and Pareto-based Query .......18
4 Algorithms ..............20
4.1 Ant Colony Optimization ...........20
4.2 Emergency Query .............21
4.3 Pareto-based Query ............24
4.4 Time Complexity Analysis ..........25
5 Multiple Sources and Destinations ...........26
6 Experimental Results ............29
6.1 Determination of Pheromone Decay Coefficient .......29
6.2 Determination of Ant Threshold .........30
6.3 Determination of Iterations ...........30
6.4 Evaluation on Execution Time under Different Iterations .....31
6.5 Evaluation on Execution Time under Different Distance of Emergency Query on
OL ...............32
6.6 Evaluation on Execution Time under Different Distance of Pareto-based Query
on OL ...............33
6.7 Evaluation on Approximate Pareto Curve of OL ......33
6.8 Evaluation on Criteria under Different Iterations on OL ......35
6.9 Evaluation on Execution Time under Different Distance of Pareto-based query
on CAL ..............35
6.10 Evaluation on Approximate Pareto Curve of CAL .......36
6.11 Evaluation on Execution Time on NY ........37
6.12 Evaluation on multiple sources and destinations on OL ......38
6.13 Visualization on OL Map ...........39
7 Conclusions ...............43
Bibliography ..............44
參考文獻 [1] Y. Dean, "Coping with disaster: The impact of hurricanes on international financial flows,
1970-2002," The B.E. Journal of Economic Analysis & Policy, 2008.
[2] Y. Zheng, L. Capra, O. Wolfson, and H. Yang, "Urban computing: Concepts, methodologies,
and applications," ACM Trans. Intell. Syst. Technol., 2014.
[3] J. Eskovitz, "Evacuation planning in texas: Before and after hurricane rita. interim news,"
2006.
[4] Q. B. F. J. Carpender SK, Campbell PH and A. JJ, "Urban evacuations and rural america:
Lessons learned from hurricane rita," Public Health Reports, 2006.
[5] L. Miller and K. Douglas, "Collective thinking keeps us safe: Lessons from hurricanes
katrina, rita and ike," 2009.
[6] L. Soomaroo and V. Murray, "Disasters at mass gatherings: Lessons from history," PLoS
Currents, 2012.
[7] S. Borzsony, D. Kossmann, and K. Stocker, "The skyline operator," in Data Engineering,
2001. Proceedings. 17th International Conference on, 2001.
[8] D. P. Caramia, Massimiliano, "Chapter 2 multi-objective optimization," in Multi-objective
Management in Freight Logistics. Springer-Verlag London, 2008.
[9] J. Brumbaugh-Smith and D. Shier, "An empirical investigation of some bicriterion shortest
path algorithms," European Journal of Operational Research, 1989.
[10] F. Guerriero and R. Musmanno, "Label correcting methods to solve multicriteria shortest
path problems," Journal of Optimization Theory and Applications, 2001.
[11] E. Q. V. Martins, "On a multicriteria shortest path problem," European Journal of Operational
Research, 1984.
[12] M. Hribar, V. E. Taylor, and D. E. Boyce, "Choosing a shortest path algorithm," EECS
Department, Northwestern University, Tech. Rep., 1995.
[13] J. Chomicki, P. Godfrey, J. Gryz, and D. Liang, "Skyline with presorting," in Data Engineering,
2003. Proceedings. 19th International Conference on, 2003.
[14] P. Dell’Olmo, M. Gentili, and A. Scozzari, "On finding dissimilar pareto-optimal paths,"
European Journal of Operational Research, 2005.
[15] R. Mart´ı, J. L. G. Velarde, and A. Duarte, "Heuristics for the bi-objective path dissimilarity
problem," Computers & OR, 2009.
[16] J. Y. Yen, "Finding the k shortest loopless paths in a network," Management Science,
1971.
[17] C. D. Johnson PE, Joy DS, "Highway3.01, an enhancement routing model: program,
description, methodology and revised user’s manual." CSE-95-004, Tech. Rep., 1992.
[18] V. Akgun, E. Erkut, and R. Batta, "On finding dissimilar paths," European Journal of
Operational Research, 2000.
[19] C. R. Lombard K, "The gateway shortest path problem: generation of alternative routes
for a corridor location problem," Geographical Systems, 1993.
[20] M. Kuby, X. Zhongyi, and X. Xiaodong, "A minimax method for finding the k best differentiated
paths," Geographical Analysis, 1997.
[21] F. Glover, C.-C. Kuo, and K. S.Dhir, "Heuristic algorithms for the maximum diversity
problem," Journal of Information and Optimization Sciences, 1998.
[22] P. Carotenuto, S. Giordani, and S. Ricciardelli, "Finding minimum and equitable risk
routes for hazmat shipments," Computers & Operations Research, 2007.
[23] D. Pisinger, "Exact solution of p-dispersion problems," DIKU, University of Copenhagen,
Denmark, Tech. Rep., 1999.
[24] I. Bomze, M. Budinich, P. Pardalos, and M. Pelillo, "The maximum clique problem," in
Handbook of Combinatorial Optimization. Springer US, 1999.
[25] Y. Tian, K. C. K. Lee, and W.-C. Lee, "Finding skyline paths in road networks," in
Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic
Information Systems, 2009.
[26] P. Modesti and A. Sciomachen, "A utility measure for finding multiobjective shortest
paths in urban multimodal transportation networks1," European Journal of Operational
Research, 1998.
[27] R. L. Carraway, T. L. Morin, and H. Moskowitz, "Generalized dynamic programming for
multicriteria optimization," European Journal of Operational Research, 1990.
[28] J. R. Current, C. S. Revelle, and J. L. Cohon, "An interactive approach to identify the best
compromise solution for two objective shortest path problems," Computers & Operations
Research, 1990.
[29] J. Granat and F. Guerriero, "The interactive analysis of the multicriteria shortest path
problem by the reference point method," European Journal of Operational Research, 2003.
[30] W. Li, J. Guan, and S. Zhou, "Efficiently evaluating range-constrained spatial keyword
query on road networks," in Database Systems for Advanced Applications. Springer Berlin
Heidelberg, 2014.
[31] X. Kuang, P. Zhao, V. Sheng, J.Wu, Z. Li, G. Liu, and Z. Cui, "Tk-sk: Textual-restricted k
spatial keyword query on road networks," in Databases Theory and Applications. Springer
International Publishing, 2015.
[32] H. Fang, P. Zhao, V. Sheng, J. Wu, J. Xu, A. Liu, and Z. Cui, "Effective spatial keyword
query processing on road networks," in Databases Theory and Applications. Springer
International Publishing, 2015.
[33] X. Liu, D.-N. Yang, M. Ye, and W.-C. Lee, "U-skyline: A new skyline query for uncertain
databases," Knowledge and Data Engineering, IEEE Transactions on, 2013.
[34] K. Deng, X. Zhou, and H. T. Shen, "Multi-source skyline query processing in road networks,"
in Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on,
2007.
[35] S. M. Jang and J. S. Yoo, "Processing continuous skyline queries in road networks," in
Computer Science and its Applications, 2008. CSA ’08. International Symposium on, 2008.
[36] W. T. Hsu, Y. T. Wen, L. Y. Wei, and W. C. Peng, "Skyline travel routes: Exploring skyline
for trip planning," in Mobile Data Management (MDM), 2014 IEEE 15th International
Conference on, 2014.
[37] I. Kim and O. de Weck, "Adaptive weighted-sum method for bi-objective optimization:
Pareto front generation," Structural and Multidisciplinary Optimization, 2005.
[38] R. Marler and J. Arora, "The weighted sum method for multi-objective optimization: new
insights," Structural and Multidisciplinary Optimization, 2010.
[39] M. Dorigo and C. Blum, "Ant colony optimization theory: A survey," Theoretical Computer
Science, 2005.
[40] M. Dorigo, M. Birattari, and T. Stutzle, "Ant colony optimization - artificial ants as a
computational intelligence technique," IEEE COMPUT. INTELL. MAG, 2006.
[41] J. M. Tiwari, "Ant colony algorithm: Its emergence and applications in soft computing,"
Discovery Publication, 2014.
[42] S. Gilmour and M. Dras, "Understanding the pheromone system within ant colony optimization,"
in AI 2005: Advances in Artificial Intelligence, 18th Australian Joint Conference
on Artificial Intelligence, Sydney, Australia, December 5-9, 2005, Proceedings, 2005.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2020-08-25起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw