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

Simple item page
dc.contributor.authorLu, Qifengen
dc.contributor.committeechairHancock, Kathleen L.en
dc.contributor.committeememberMidkiff, Scott F.en
dc.contributor.committeememberLu, Chang-Tienen
dc.contributor.committeememberKikuchi, Shinyaen
dc.contributor.committeememberDymond, Randel L.en
dc.contributor.departmentCivil Engineeringen
dc.date.accessioned2014-03-14T20:08:15Zen
dc.date.adate2009-04-22en
dc.date.available2014-03-14T20:08:15Zen
dc.date.issued2009-02-25en
dc.date.rdate2012-03-30en
dc.date.sdate2009-03-16en
dc.description.abstractWith 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.en
dc.description.degreePh. D.en
dc.identifier.otheretd-03162009-210052en
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-03162009-210052/en
dc.identifier.urihttp://hdl.handle.net/10919/26444en
dc.publisherVirginia Techen
dc.relation.haspartETD_QifengLU_Patented.pdfen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectstate graph spaceen
dc.subjectO*-MSTen
dc.subjectGeographic Information Scienceen
dc.subjectC*- Dijkstraen
dc.subjectO*-Greedyen
dc.subjectO*-Dijkstraen
dc.subjectO*-SCDMSTen
dc.subjecttrip planningen
dc.subjectcategory based queriesen
dc.subjectO*en
dc.subjectGeographic Information Systemen
dc.subjectadmissibleen
dc.subjectL#en
dc.subjecttransportation networken
dc.subjectlogisticsen
dc.subjectmultivariateen
dc.subjectBivariateen
dc.subjectbest first searchen
dc.subjectCSTQen
dc.subjectC*en
dc.subjectconsistenten
dc.subjectpathen
dc.subjectheuristicen
dc.subjectoptimizationen
dc.subjectstate graphen
dc.subjectgraphen
dc.subjectOSTQen
dc.subjectC*-Pen
dc.titleBivariate Best First Searches to Process Category Based Queries in a Graph for Trip Planning Applications in Transportationen
dc.typeDissertationen
thesis.degree.disciplineCivil Engineeringen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.leveldoctoralen
thesis.degree.namePh. D.en

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
ETD_QifengLU_Patented.pdf
Size:
1.07 MB
Format:
Adobe Portable Document Format
Download

Collections

Doctoral Dissertations