A new bidirectional search algorithm with shortened postprocessing

Abstract

For finding a shortest path in a network bidirectional A^∗ is a widely known algorithm. This algorithm distinguishes between the main phase and the postprocessing phase. The version of bidirectional A^∗ that is considered the most appropriate in literature hitherto, uses a so-called balanced heuristic estimate. This type of heuristic is chosen, as it accounts for a short postprocessing phase. In this paper, we do not restrict ourselves any longer to balanced heuristics. First, we introduce an algorithm containing a new method for the postprocessing phase, reducing this phase considerably for non-balanced heuristics. For a balanced heuristic the new algorithm is nearly equivalent to the existing versions of bidirectional A^∗. An obvious choice for a non-balanced heuristic turns out to be superior in terms of storage space and computation time. Second, we show that the main phase on its own, when using this non-balanced heuristic estimate, is a useful algorithm, which provides us quickly with a feasible approximation.

Introduction

In the past few years large digital road maps have become available, to be used in car navigators. This has given rise to a revival of shortest path algorithms. Digital road maps contain millions of nodes and edges, whereas previous experiments used small artificial networks. We consider the point-to-point instance of the shortest path problem. The best-known algorithms in Operations Research are Bellman-Ford [1], [5] and Dijkstra [3]. In Artificial Intelligence the A^∗ algorithm [8], which assumes the availability of a heuristic estimate, is widely known. Both Dijkstra’s algorithm and A^∗ start from the origin point and continue their search process until the destination is reached. A new approach, bidirectional search, was introduced by Nicholson [16], who proposed two simultaneous search processes starting from either endpoint. Pohl [19] applied this idea to Dijkstra and A^∗. Several variants of Pohl’s approach were discussed in [2], [10], [13]. The two search spaces meet somewhere in the middle between the endpoints. Before a meeting point is obtained, we are in the so-called main phase. After the processes have met, the remaining steps of bidirectional search are called the postprocessing phase or briefly the post-phase.

For the A^∗ algorithm one needs to define some heuristic function estimating the remaining distance from a node to the target. Since there are two processes, two estimates h and $\tilde{h}$ are used, each belonging to one process. The heuristic is called balanced if $h(u)+\tilde{h}(u)$ equals a constant value for any node u.

The algorithm that is considered the most efficient of all shortest path solutions hitherto is bidirectional A^∗ with a balanced heuristic, cf. [7], [9], [11]. The efficiency of this algorithm is due to a short post-phase. We found that this benefit of a balanced heuristic can be carried over to arbitrary heuristics. A new version of A^∗ including new statements for the post-phase is proposed. As a result of the new statements, the post-phase is shortened considerably. Now, for any heuristic a relatively short post-phase is enabled. Using an obvious choice for the heuristic estimate, the new version outperforms the versions with the balanced heuristics. An experimental comparison on a digital road map of the Netherlands is presented.

Moreover, we discovered that the post-phase needs not to be executed at all. Applying the obvious estimate, the main phase on it own provides a tight approximation with a deviation of less 0.2%. This result is also demonstrated by experiments on a real road network.

The outline of this paper is as follows. In Section 2.1 we recall the classical A^∗ algorithm along with some properties relevant to bidirectional versions discussed later on. In Section 2.2 the old bidirectional version is treated and a new proof is given for the fact that the post-phase is short for balanced heuristics. Section 3 presents the new bidirectional algorithm. The properties of the search space, also implying the correctness of the algorithm, are studied in Section 4. Section 5 elaborates on the different instances to be used in Section 6, which section presents experimental results comparing old and new methods. In Section 7 we show that the main phase on its own is a feasible method of great practical use. Concluding remarks are given in Section 8.