论文研究 多层分割算法在构建层次道路网络中的应用.pdf

在大规模道路网络上使用“分层”策略构建层次道路网络能够显著降低路径规划算法的搜索空间，对分层道路网络进行分区可改进数据结构，进一步提升算法效率。现有多种网络图分割算法，介绍一类名为METIS的多层分割算法，此类算法通过概化（coarsening phase）、分割（partitioning phase）、还原（uncoarsening phase）三阶段将网络图划分为均等分区，且算法效率高。将两种典型多层分割算法：多层递归二分算法（MLRB）及多层k路分割算法（MLKP）应用于层次道路数据，以检验此类算法是否适用于强调拓扑连通性的道路网络的分区。结果分析表明，多层算法的分区结果并不适合层次道路