多层分割算法在构建层次道路网络中的应用  

Application of multi-level algorithms in constructing hierarchical road network

作　　者：撖志恒[1,2] 芮小平[1] 董承玮[2] 宋现锋[1] 王静 徐江 

机构地区：[1]中国科学院大学资源与环境学院,北京100049 [2]北京市测绘设计研究院,北京100038 [3]北京数码汇博科技有限公司,北京100098

出　　处：《计算机应用研究》2016年第3期779-782,共4页Application Research of Computers

基　　金：国家科技支撑计划项目课题(2012BAC25B01);国家科技重大专项课题资助项目(2011ZX05039-004)

摘　　要：在大规模道路网络上使用"分层"策略构建层次道路网络能够显著降低路径规划算法的搜索空间,对分层道路网络进行分区可改进数据结构,进一步提升算法效率。现有多种网络图分割算法,介绍一类名为METIS的多层分割算法,此类算法通过概化(coarsening phase)、分割(partitioning phase)、还原(uncoarsening phase)三阶段将网络图划分为均等分区,且算法效率高。将两种典型多层分割算法:多层递归二分算法(MLRB)及多层k路分割算法(MLKP)应用于层次道路数据,以检验此类算法是否适用于强调拓扑连通性的道路网络的分区。结果分析表明,多层算法的分区结果并不适合层次道路网络构建,但多层分割的思想值得借鉴。While constructing large scale road network,the application of＂hierarchy＂strategy is attractive for its efficiency in intensively reducing the solution space. Furthermore,parting the road network into small regions would improve. Up to now,many graph partition algorithms have proposed. However,the multi-level partition algorithm called METIS hasn ＇t used in hierarchical road network. This kind of algorithms usually consisted three phases,such as coarsening phase,partitioning phase and uncoarsening phase. After partition,the graph results in a group of regions which contain roughly the same number of vertices. This paper used two multi-level algorithms as multi-level recursive bisectioning（ MLRB） and multi-level k-way partitioning（ MLKP） to partition road network,with the purpose of testing whether this kind of algorithms was suitable for applications that emphasize the connection topology of network. Result shows that the original multi-level algorithms are not suitable to road network,while the thought of ＂multi-level＂process is valuable to refer.

关 键 词：路径规划 多层分割算法 多层递归二分算法 多层k路分割算法 分区 

分 类 号：TP391.7[自动化与计算机技术—计算机应用技术] TP301.6[自动化与计算机技术—计算机科学与技术]