A Genetic Algorithm Based Clustering Method for Optimal Route Calculation on Multilevel Networks
Feng Wen, Shingo Mabu, Kotaro Hirasawa · SICE Journal of Control Measurement and System Integration · 2011
This paper introduces a multilevel road network model to speed up the optimal route calculation on large size road networks by preprocessing and pre-computing. The multilevel road network is constructed by separating a large network into several smaller sub-networks and pushing up the boundary nodes. The new road sections on the multilevel network are decided by pre-computing the shortest path between the boundary nodes of each sub-network in a hierarchical manner. To optimize the structure of the multilevel road network, an effective genetic algorithm based clustering method is proposed, which can reduce the number of boundary nodes and road sections between boundary nodes of each sub-network greatly. Experimental results show that the proposed approach significantly reduces the search space of the route calculation algorithm over existing methods.