O*: A Bivariate Best First Search Framework, and O*-SCDMST to Process Optimal Sequence Traversal Query in a Graph for Trip Planning

Optimal Sequence Traversal Query (OSTQ) asks for a minimum-cost path between a given origin and a given destination, traversing a set of points of interest without a predefined order. The traveling salesman problem is a special case of OSTQ. Due to the extensive computing time required to process this query in a large scale environment such as a large set of points of interest to be traversed in a dense urban transportation network, efficient algorithms, either optimal or sub-optimal, are necessary whenever procesing time is a consideraiton, and O*, a family algorithm of best first searches that incorporate heuristics from a problem domain to expedite the search process, was developed. O* can provide sub-optimal, optimal, and optimally efficient algorithms based on different heuristics adopted. O*-SCDMST, and O*-Dijkstra are all special cases of O*. The optimal algorithm O*-SCDMST can be used to efficiently retrieve optimal solutions in a directed graph and applied to corresponding transportation trip planning.

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