吴 立 新，刘 纪 平，江 锦 成

(1.东北大学测绘遥感与数字矿山研究所，辽宁 沈阳 110819；2.中国矿业大学环境与测绘学院，江苏 徐州 221116；3.中国测绘科学研究院，北京 100830；4.北京师范大学减灾与应急管理研究院，北京 100875)

基于MPI的最小费用流网络单纯形并行算法设计与实验

吴 立 新1，2，刘 纪 平3，江 锦 成4

(1.东北大学测绘遥感与数字矿山研究所，辽宁 沈阳 110819；2.中国矿业大学环境与测绘学院，江苏 徐州 221116；3.中国测绘科学研究院，北京 100830；4.北京师范大学减灾与应急管理研究院，北京 100875)

网络最小费用流算法常用来解决资源流最优分配问题，传统的串行算法因时间复杂度高而不能满足大规模网络对计算效率的要求。该文用时间复杂度低的网络单纯形算法(NSA)的并行化求解大规模网络的最小费用流问题。通过分析NSA的可并行性，使用MPI分布式并行技术，设计了NSA并行算法；分析了3种常用流网络的拓扑结构特征及其与地理网络的关系；在并行环境下对计算效率进行实验测试，结果表明该算法具有显著的加速效果，峰值可达5.4。NSA并行算法应用面宽，可为区域及全国性大规模网络流资源分配方案的快速制定与政务决策提供有力支持。

网络最小费用流；并行计算；资源分配；网络单纯形算法(NSA)； MPI

0 引言

网络最小费用流问题旨在将交通网络上的资源以最小的总代价从供应点运输至需求点,已被广泛应用于工业生产、通讯及GIS网络分析领域，在全国性物流规划与资源调配中有着重要意义。目前，针对……