基于几何代数的多类型约束路网最优路径分析算法

发布时间：2018-02-13 05:48

本文关键词： 交通路径规划多约束最优路径几何代数 GIS　出处：《地理与地理信息科学》2014年02期 　论文类型：期刊论文

【摘要】：针对现有交通规划中最优路径算法难以同时集成多种不同类型约束的不足,提出了一种多类型约束下最优路径统一求解的几何代数算法。基于几何基编码的网络表达模型,实现了对节点、边、路径等网络对象及权重和约束条件的统一表达。建立了基于几何邻接矩阵外积的路径延拓、遍历与筛选机制,实现了路径延拓过程中网络拓扑关系和权重结构的同步计算。在此基础上,构建多约束条件下最优路径生成算法。最后,以江苏道路网络为例对算法的正确性进行验证,结果显示,该算法可较好地支撑同时包含数值型、节点型及结构型约束条件下最优路径的计算,可为复杂GIS网络分析提供理论与方法支撑。
[Abstract]:In order to solve the problem that it is difficult for the existing optimal path algorithms to integrate many different types of constraints simultaneously, a geometric algebraic algorithm for solving the optimal path under multiple types of constraints is proposed. A network representation model based on geometric basis coding is proposed. The unified representation of network objects such as nodes, edges, paths, weights and constraints is realized, and a path extension, traversal and screening mechanism based on the outer product of geometric adjacency matrix is established. The synchronous calculation of network topology and weight structure in the course of path continuation is realized. On this basis, the optimal path generation algorithm under multi-constraint conditions is constructed. Finally, the correctness of the algorithm is verified by taking Jiangsu road network as an example. The results show that the algorithm can support the calculation of the optimal path under the constraints of numerical, node and structural types at the same time, and can provide theoretical and methodological support for the analysis of complex GIS networks.
【作者单位】：虚拟地理环境教育部重点实验室/南京师范大学;江苏省大规模复杂系统数值模拟重点实验室/南京师范大学;南京师范大学计算机科学与技术学院;
【基金】：国家自然科学重点基金项目“基于几何代数的时空统一数据模型构建理论与方法”(41231173) 江苏省自然科学基金项目“复杂场景中空间关系动态计算的几何代数方法”(BK2012454)
【分类号】：U116.2;P208

【参考文献】