在本篇論文，我們探討在路徑網路上搜尋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.

[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.