Show simple item record

dc.contributor.authorLu, Qifengen_US
dc.date.accessioned2014-03-14T20:08:15Z
dc.date.available2014-03-14T20:08:15Z
dc.date.issued2009-02-25en_US
dc.identifier.otheretd-03162009-210052en_US
dc.identifier.urihttp://hdl.handle.net/10919/26444
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_US
dc.publisherVirginia Techen_US
dc.relation.haspartETD_QifengLU_Patented.pdfen_US
dc.rightsI hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to Virginia Tech or its agents the non-exclusive license to archive and make accessible, under the conditions specified below, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report.en_US
dc.subjectstate graph spaceen_US
dc.subjectO*-MSTen_US
dc.subjectGeographic Information Scienceen_US
dc.subjectC*- Dijkstraen_US
dc.subjectO*-Greedyen_US
dc.subjectO*-Dijkstraen_US
dc.subjectO*-SCDMSTen_US
dc.subjecttrip planningen_US
dc.subjectcategory based queriesen_US
dc.subjectO*en_US
dc.subjectGeographic Information Systemen_US
dc.subjectadmissibleen_US
dc.subjectL#en_US
dc.subjecttransportation networken_US
dc.subjectlogisticsen_US
dc.subjectmultivariateen_US
dc.subjectBivariateen_US
dc.subjectbest first searchen_US
dc.subjectCSTQen_US
dc.subjectC*en_US
dc.subjectconsistenten_US
dc.subjectpathen_US
dc.subjectheuristicen_US
dc.subjectoptimizationen_US
dc.subjectstate graphen_US
dc.subjectgraphen_US
dc.subjectOSTQen_US
dc.subjectC*-Pen_US
dc.titleBivariate Best First Searches to Process Category Based Queries in a Graph for Trip Planning Applications in Transportationen_US
dc.typeDissertationen_US
dc.contributor.departmentCivil Engineeringen_US
dc.description.degreePh. D.en_US
thesis.degree.namePh. D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen_US
thesis.degree.disciplineCivil Engineeringen_US
dc.contributor.committeechairHancock, Kathleen L.en_US
dc.contributor.committeememberMidkiff, Scott F.en_US
dc.contributor.committeememberLu, Chang-Tienen_US
dc.contributor.committeememberKikuchi, Shinyaen_US
dc.contributor.committeememberDymond, Randel L.en_US
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-03162009-210052/en_US
dc.date.sdate2009-03-16en_US
dc.date.rdate2012-03-30
dc.date.adate2009-04-22en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record