Pruning high-level network using genetic algorithm for efficient hierarchical route planning in road networks

This paper proposes a pruning method to improve the computational efficiency of the hierarchical route search using Q Value-based Dynamic Programming. In the hierarchical route search, the road network is divided into several subnetworks and the high-level network built with origin, destination and border intersections is used for the route search. In the previous work, it was shown that the hierarchical route search is efficient compared to the non-hierarchical method. To further improve the computational efficiency of the hierarchical route search, an offline pruning method for the high-level network is proposed in which the border intersections are selected using Genetic Algorithm in order to include them in the high-level network. But, pruning the high-level network leads to the loss of accuracy of the routes. Therefore, the border intersections are selected considering the traveling time of the routes and time required to do the route search during the pruning process. The proposed method is evaluated using the Kitakyushu city road network and the simulation results show that the proposed method improves the computational efficiency of the route search with small loss of accuracy on average.