Title page for ETD etd-03162009-210052

Type of Document

Dissertation

Author

Lu, Qifeng

URN

etd-03162009-210052

Title

Bivariate Best First Searches to Process Category Based Queries in a Graph for Trip Planning Applications in Transportation

Degree

PhD

Department

Civil Engineering

Advisory Committee

Advisor Name	Title
Hancock, Kathleen L.	Committee Chair
Dymond, Randel L.	Committee Member
Kikuchi, Shinya	Committee Member
Lu, Chang-Tien	Committee Member
Midkiff, Scott F.	Committee Member

Keywords

state graph space
O*-MST
Geographic Information Science
C*- Dijkstra
O*-Greedy
O*-Dijkstra
O*-SCDMST
trip planning
category based queries
O*
Geographic Information System
admissible
L#
transportation network
logistics
multivariate
Bivariate
best first search
CSTQ
C*
consistent
path
heuristic
optimization
state graph
graph
OSTQ
C*-P

Date of Defense

2009-02-25

Availability

unrestricted

Abstract

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.

Files

Filename		Size	Approximate Download Time (Hours:Minutes:Seconds)
Filename		Size	28.8 Modem	56K Modem	ISDN (64 Kb)	ISDN (128 Kb)	Higher-speed Access
	ETD_QifengLU_Patented.pdf	1.13 Mb	00:05:12	00:02:40	00:02:20	00:01:10	00:00:06