||Search of K-Discriminative Paths on Road Networks
||Institute of Computer Science and Information Engineering
multiple sources and destinations
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.
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
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
 Y. Dean, "Coping with disaster: The impact of hurricanes on international financial flows,
1970-2002," The B.E. Journal of Economic Analysis & Policy, 2008.
 Y. Zheng, L. Capra, O. Wolfson, and H. Yang, "Urban computing: Concepts, methodologies,
and applications," ACM Trans. Intell. Syst. Technol., 2014.
 J. Eskovitz, "Evacuation planning in texas: Before and after hurricane rita. interim news,"
 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.
 L. Miller and K. Douglas, "Collective thinking keeps us safe: Lessons from hurricanes
katrina, rita and ike," 2009.
 L. Soomaroo and V. Murray, "Disasters at mass gatherings: Lessons from history," PLoS
 S. Borzsony, D. Kossmann, and K. Stocker, "The skyline operator," in Data Engineering,
2001. Proceedings. 17th International Conference on, 2001.
 D. P. Caramia, Massimiliano, "Chapter 2 multi-objective optimization," in Multi-objective
Management in Freight Logistics. Springer-Verlag London, 2008.
 J. Brumbaugh-Smith and D. Shier, "An empirical investigation of some bicriterion shortest
path algorithms," European Journal of Operational Research, 1989.
 F. Guerriero and R. Musmanno, "Label correcting methods to solve multicriteria shortest
path problems," Journal of Optimization Theory and Applications, 2001.
 E. Q. V. Martins, "On a multicriteria shortest path problem," European Journal of Operational
 M. Hribar, V. E. Taylor, and D. E. Boyce, "Choosing a shortest path algorithm," EECS
Department, Northwestern University, Tech. Rep., 1995.
 J. Chomicki, P. Godfrey, J. Gryz, and D. Liang, "Skyline with presorting," in Data Engineering,
2003. Proceedings. 19th International Conference on, 2003.
 P. Dell’Olmo, M. Gentili, and A. Scozzari, "On finding dissimilar pareto-optimal paths,"
European Journal of Operational Research, 2005.
 R. Mart´ı, J. L. G. Velarde, and A. Duarte, "Heuristics for the bi-objective path dissimilarity
problem," Computers & OR, 2009.
 J. Y. Yen, "Finding the k shortest loopless paths in a network," Management Science,
 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.
 V. Akgun, E. Erkut, and R. Batta, "On finding dissimilar paths," European Journal of
Operational Research, 2000.
 C. R. Lombard K, "The gateway shortest path problem: generation of alternative routes
for a corridor location problem," Geographical Systems, 1993.
 M. Kuby, X. Zhongyi, and X. Xiaodong, "A minimax method for finding the k best differentiated
paths," Geographical Analysis, 1997.
 F. Glover, C.-C. Kuo, and K. S.Dhir, "Heuristic algorithms for the maximum diversity
problem," Journal of Information and Optimization Sciences, 1998.
 P. Carotenuto, S. Giordani, and S. Ricciardelli, "Finding minimum and equitable risk
routes for hazmat shipments," Computers & Operations Research, 2007.
 D. Pisinger, "Exact solution of p-dispersion problems," DIKU, University of Copenhagen,
Denmark, Tech. Rep., 1999.
 I. Bomze, M. Budinich, P. Pardalos, and M. Pelillo, "The maximum clique problem," in
Handbook of Combinatorial Optimization. Springer US, 1999.
 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.
 P. Modesti and A. Sciomachen, "A utility measure for finding multiobjective shortest
paths in urban multimodal transportation networks1," European Journal of Operational
 R. L. Carraway, T. L. Morin, and H. Moskowitz, "Generalized dynamic programming for
multicriteria optimization," European Journal of Operational Research, 1990.
 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
 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.
 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
 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.
 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.
 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.
 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,
 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.
 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.
 I. Kim and O. de Weck, "Adaptive weighted-sum method for bi-objective optimization:
Pareto front generation," Structural and Multidisciplinary Optimization, 2005.
 R. Marler and J. Arora, "The weighted sum method for multi-objective optimization: new
insights," Structural and Multidisciplinary Optimization, 2010.
 M. Dorigo and C. Blum, "Ant colony optimization theory: A survey," Theoretical Computer
 M. Dorigo, M. Birattari, and T. Stutzle, "Ant colony optimization - artificial ants as a
computational intelligence technique," IEEE COMPUT. INTELL. MAG, 2006.
 J. M. Tiwari, "Ant colony algorithm: Its emergence and applications in soft computing,"
Discovery Publication, 2014.
 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.