罗文, 袁林旺, 易琳, 闾国年. 多条件约束最大流分析的几何代数方法[J]. 武汉大学学报 ( 信息科学版), 2013, 38(7): 862-868.
引用本文: 罗文, 袁林旺, 易琳, 闾国年. 多条件约束最大流分析的几何代数方法[J]. 武汉大学学报 ( 信息科学版), 2013, 38(7): 862-868.
LUO Wen, YUAN Linwang, YI Lin, LV Guonian. Geometric Algebra-based Multi-criteria Constrained Maximal Flow Analysis[J]. Geomatics and Information Science of Wuhan University, 2013, 38(7): 862-868.
Citation: LUO Wen, YUAN Linwang, YI Lin, LV Guonian. Geometric Algebra-based Multi-criteria Constrained Maximal Flow Analysis[J]. Geomatics and Information Science of Wuhan University, 2013, 38(7): 862-868.

多条件约束最大流分析的几何代数方法

Geometric Algebra-based Multi-criteria Constrained Maximal Flow Analysis

  • 摘要: 针对多约束变容量条件下的应急物资调度问题,构建了基于几何代数的条件约束最大流分析模型。基于几何基编码法和几何积运算进行网络图表达、网络连通性判定与路径搜索,进而建立了基于贪心算法思想的几何代数最大流分析方法。利用几何代数运算的独立性及其与布尔逻辑运算间的内蕴联系,探讨了基于约束矩阵的多约束集成方法,实现了外部约束及权重变化条件下的网络最大流的快速计算与更新。污染物扩散条件下最大流分析的案例分析结果显示,基于几何代数的网络分析算法在网络表达、算法构造以及权重更新等方面表现出较好的优势,可有效支撑多约束下的物资调度分析。

     

    Abstract: Network analysis is a fundamental basis for community resources scheduling applications.Discussed in this paper is a multi-criteria-constrained maximal flow problem with route capacity changing over time.Geometric algebra unit based coding is used to obtain a geometric algebra expression for a network diagram.Network connectivity and path search are implemented based on this geometric product.Using independent computation the inner linkage between Boolean operations in geometric algebra computation are exploited,multi- criteria are integrated based on a constrained matrix.A multi-criteria-constrained maximal flow analysis algorithm with changing route capacity is proposed.The algorithm was implemented and validated by maximum flow analysis dealing with pollutant dispersion cases.The results show that,under the constraints imposed by a materials scheduling analysis,the geometric algebra based network algorithm can effectively support multi-dimensional community networks.The algorithm also supports rapid computing and updating of the weight of external constraints as well as changes in the conditions of maximum flow problems.

     

/

返回文章
返回