多品种流交通网络的最大流算法研究

Study of Maximum Flow Algorithm for Multicommodity Flow Traffic Network

基于Ford-Fulkerson算法在单一品种网络中最大流量分配的思路,通过对多品种交通网络的网络特性进行分析,作者将多源多汇的交通网络构建成单源单汇的形式。在保证符合流量约束的条件下,设计了适用于多品种交通网络的最大流分配算法。在交通网络的实际应用领域里,多品种交通网络的问题普遍存在,因此该算法为解决实际交通网络的相关问题提供了基础。

Based on Ford-Fulkerson algorithm’s idea about the maximum flow of a single commodity’s traffic network, this paper first analyzed the flow constraints of a multi-species traffic network, then, a multi-source and multi-sink transportation network was constructed for a single-source and single-sink transportation network. In accordance with the flow constraints, this paper built an algorithm which worked for the maximum flow distribution. This algorithm provided some contribution to solve the practical problems. This algrithm could be used to the similar problems in a practical traffic network.