Home // GEOProcessing 2011, The Third International Conference on Advanced Geographic Information Systems, Applications, and Services // View article

O*: A Bivariate Best First Search Algorithm to Process Optimal Sequence Traversal Query in a Graph

Authors:
Qifeng Lu
Kathleen Hancock

Keywords: Bivariate Best First Search, Heuristic, Optimal Sequence Traversal Query, O*, O*-SCDMST

Abstract:
An Optimal Sequence Traversal Query is a new query in a graph typically representing a transportation network that determines the minimum-cost path with a predefined origin-destination pair, traversing a set of non-ordered points of interest, at least once for each point. It has distinctive applications in the GoeProcessing domain in transportation where a user may query a shortest route to start from his/her office, traverse a set of consumer destinations, and then go home. Optimal Sequence Traversal Query generalizes TSP in the sense that the origin and the destination may be different in the former. This paper proposes a bivariate best first search, O*, to process such a query within a graph. Two special cases of O*, O*-SCDMST and O*-Dijkstra, are provided, their performance in a fully connected directed graph are studied through a set of experiments, and the result demonstrates that, on average, O*-SCDMST reduces computation time by one order of magnitude when compared to O*-Dijkstra.

Pages: 53 to 61

Copyright: Copyright (c) IARIA, 2011

Publication date: February 23, 2011

Published in: conference

ISSN: 2308-393X

ISBN: 978-1-61208-118-2

Location: Gosier, Guadeloupe, France

Dates: from February 23, 2011 to February 28, 2011