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

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