C*: A Bivariate Best First Search Framework, and C*-P and C*-Dijkstra, to Process Category Sequence Traversal Query in a Graph for Trip Planning

A Category Sequence Traversal Query (CSTQ) is a new type of category based query that determines the minimum-cost path with a predefined origin-destination pair, traversing at least a single selection from each of a set of categories in a specified order. To process CSTQ in a graph corresponds to trip planning in a transportation network where a priority to visit a set of categories is imposed whenever a work flow or time constraint exists. Due to the extensive computing time required to process this query in a large scale environment such as large set of candidate points in each of categories of interest to be traversed in a dense urban transportation network, efficient optimal algorithms are necessary whenever processing time is a consideration, and C*, a family algorithm of best first searches that incorporate heuristics from a problem domain to expedite the search process, was developed. C* can provide sub-optimal, optimal, and optimally efficient algorithms based on different heuristics adopted. C*-P and C*-Dijkstra are all special cases of O*, and C*-P is more efficient than C*-Dijkstra to retrieve optimal solutions in a large dense urban transporation network.

Inventors

• Qifeng (Luke) Lu (2 technologies)
• Kathleen Hancock (2 technologies)

Intellectual Property

Contact commercialization manager for patent and/or copyright information.

Commercialization Opportunity

For more information about this technology, please contact John Geikler at Virginia Tech Intellectual Properties.

John Geikler (166 technologies)

Senior Licensing Associate

Office:(540) 443-9228
Fax:(540) 951-5292
 jgeikler@vtip.org