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

• 作者: 宋现锋 徐江 撖志恒 王静 芮小平 董承玮
• 来源期刊: 计算机应用研究
• 关键词: 路径规划 多层分割算法 多层递归二分算法 多层k路分割算法 分区
• 年，卷（期）: 2016,（3）
• 所属期刊栏目: 系统应用开发
• 页码范围: 779-782
• 页数: 4页
• 分类号: TP391.7|TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2016.03.031

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	宋现锋	中国科学院大学资源与环境学院	39	277	11.0	15.0
2	王静	中国科学院大学资源与环境学院	151	2547	23.0	47.0
3	芮小平	中国科学院大学资源与环境学院	62	522	14.0	20.0
4	董承玮		3	9	1.0	3.0
5	撖志恒	中国科学院大学资源与环境学院	3	9	1.0	3.0
9	徐江		4	2	1.0	1.0