With the technological advancement in computer science, Geographic Information Science (GIScience), and transportation, more and more complex path finding queries including category based queries are proposed and studied across diverse disciplines. A category based query, such as Optimal Sequenced Routing (OSR) queries and Trip Planning Queries (TPQ), asks for a minimum-cost path that traverses a set of categories with or without a predefined order in a graph. Due to the extensive computing time required to process these complex queries in a large scale environment, efficient algorithms are highly desirable whenever processing time is a consideration. In Artificial Intelligence (AI), a best first search is an informed heuristic path finding algorithm that uses domain knowledge as heuristics to expedite the search process. Traditional best first searches are single-variate in terms of the number of variables to describe a state, and thus not appropriate to process these queries in a graph. In this dissertation, 1) two new types of category based queries, Category Sequence Traversal Query (CSTQ) and Optimal Sequence Traversal Query (OSTQ), are proposed; 2) the existing single-variate best first searches are extended to multivariate best first searches in terms of the state specified, and a class of new concepts--state graph, sub state graph, sub state graph space, local heuristic, local admissibility, local consistency, global heuristic, global admissibility, and global consistency--is introduced into best first searches; 3) two bivariate best first search algorithms, C* and O*, are developed to process CSTQ and OSTQ in a graph, respectively; 4) for each of C* and O*, theorems on optimality and optimal efficiency in a sub state graph space are developed and identified; 5) a family of algorithms including C*-P, C-Dijkstra, O*-MST, O*-SCDMST, O*- Dijkstra, and O*-Greedy is identified, and case studies are performed on path finding in transportation networks, and/or fully connected graphs, either directed or undirected; and 6) O*- SCDMST is adopted to efficiently retrieve optimal solutions for OSTQ using network distance metric in a large transportation network. / Ph. D.

Indiana University-Purdue University Indianapolis (IUPUI) / Over the past two decades, northern parts of the United States have experienced extreme heat conditions. Some of the notable heat wave impacts have occurred in Chicago in 1995 with over 600 reported deaths and in Philadelphia in 1993 with over 180 reported deaths. The distribution of extreme heat events in Indianapolis has varied since the year 2000. The Urban Heat Island effect has caused the temperatures to rise unusually high during the summer months. Although the number of reported deaths in Indianapolis is smaller when compared to Chicago and Philadelphia, the heat wave in the year 2010 affected primarily the vulnerable population comprised of the elderly and the lower socio-economic groups. Studying the spatial distribution of high temperatures in the vulnerable areas helps determine not only the extent of the heat affected areas, but also to devise strategies and methods to plan, mitigate, and tackle extreme heat. In addition, examining spatial patterns of vulnerability can aid in development of a heat warning system to alert the populations at risk during extreme heat events. This study focuses on the qualitative and quantitative methods used to measure extreme heat events. Land surface temperatures obtained from the Landsat TM images provide useful means by which the spatial distribution of temperatures can be studied in relation to the temporal changes and socioeconomic vulnerability. The percentile method used, helps to determine the vulnerable areas and their extents. The maximum temperatures measured using LST conversion of the original digital number values of the Landsat TM images is reliable in terms of identifying the heat-affected regions.