LU: A Best First Search to Process Single-Origin Multiple-Destination Route Query in a Graph
Qifeng Lu · 2010
A single-origin multiple-destination route (SOMDR)query is to retrieve the minimum-cost routes, each of which starts from the same origin and ends at one of a set of destinations. The query is typically used for route assignment in transportation networks in GEOProcessing. In this paper,LU, a fundamental best first search algorithm and framework,is proposed to process SOMDR queries in a graph. It uses a heuristic, h_LU, estimated based on destinations yet-to-be reached to expedite the search process following a best first way. It is a framework that can adopt different heuristics to provide optimal and sub-optimal solutions. The paper discusses how to incorporate heuristic information obtained from the problem domain into a formal mathematical theory of graph searching and how a family of search strategies can demonstrate an optimality property in a sub graph. As an example, the Euclidean distance between two vertices is used as the basis to provide a consistent heuristic, h_LU, for LU to process SOMDR queries in network distance in a transportation network and a set of experiments is performed accordingly. The result demonstrates that LU is much more efficient than Dijkstra's algorithm when the number of destinations is relatively smaller than the total number of vertices in a graph. On average, Dijkstra's algorithm expands0.2~4.7 times more vertices and is 0.2~20.6 times slower than LU to retrieve optimal solutions when the number of destinations is up to 100. As a best first search, LU extends the capability of existing best first searches from single-destination query processing to multi-destination query processing. For SOMDR query processing, Dijkstra's algorithm is a special case of LU when no heuristic is adopted during the search process, and A* is a special case of LU when the number of destinations is one.