基于重叠社团划分的大规模道路网络双层路由算法

Double Layers Routing Algorithm on Large Road Networks Based on Overlapping Communities Detecting

大规模道路网络中的最短路径快速搜索算法在交通系统的导航、交通分配等方面具有广泛的应用。现有的几种分层算法虽然在计算性能上比传统的算法有所改善,但仍存在计算量较大和计算效率较低等问题。提出了基于重叠社团划分的大规模道路网络双层路由算法,该算法在道路网络中探测基于重叠社团的分层结构,将整个网络划分为若干具有重叠节点的社团,并由此构成路网的双层结构:第一层为原始道路网络;第二层为社团连接逻辑层,其中的每一个点对应第一层的一个社团,第一层社团间的重叠节点和道路连接对应第二层节点间的连接。在此网络架构下,路由被分解为第二层社团节点间启发式的总体路由和第一层社团内部节点的局域路由。该算法提出将社团间的重叠节点作为相应两个社团之间的关键路由节点,并将其引入到基于社团的分层路由算法当中,可以有效地降低算法的搜索空间和计算复杂度,有效地提高了算法效率。几个真实城市路网的实验结果表明了本算法的有效性。

The fast searching algorithms of shortest path on large road network have wide application in navigation,transportation system,traffic assignment,etc.Although the calculated performance in several existing hierarchical algorithms has been improved,there are still some problems such as heavy computation and low calculation efficiency.By detecting the hierarchical structure based on overlapping communities,we proposed a new hierarchical routing algorithm using overlapping communities.We divided the whole network into communities containing the overlapping nodes and constituted a double-layer structure of road network.The first layer contains the original road network nodes and in the second layer the communities are regarded as nodes,the overlapping nodes and intercommunity edges are regarded as the edges.Based on the network architecture,routing is broken into two processes,the heuristic overall routing in the second layer and local routing in the communities in the first layer.We denoted the overlapping node as the key routing node and used it into the hierarchical algorithms which can reduce the searching space and computational complexity effectively.Several experimental results of the real city road networks show the effectiveness of the algorithm.