LU: A Best First Search to Process Single-Origin Multiple-Destination Route Query in a Graph

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.