有运送路径限制的多品种流交通网络最小费用流算法研究

传统的交通网络最小费用流分配是针对单一品种,但在实际的交通运输应用中,交通网络中往往会出现多品种流的运送情况,而且也有可能对某些品种的运送路径进行限制.首先针对交通网络中的多品种流及其流动现象进行分析,借鉴Ford-Fulkerson算法中构造伴随增流网络的思路,建立了多品种流交通网络图的顺推重构方法,在此基础上,构造了有运送路径限制的多品种流交通网络最小费用流算法.在交通运输领域,多品种流最小费用流问题普遍存在,此算法为解决实际交通网络的相关问题提供了基础.

An Algorithm for the Minimum Cost Flow with Limited Transmission-path in Multi-species Flow Traffic Network

In aspect of the traffic and transportation network, the distribution of the minimum cost flow is for a single species,but in practical application,multi-species flow transportation usually happens in traffic network,and the transmission-path of some species may be limited. The multi-species flow in the traffic network and its flow phenomena are firstly analyzed, then the reconstruction method for the multi-species flow traffic network graph is built based on the idea of constructing the network of augmentation flow in Ford-Fulkerson algorithm. On this basis, the algorithm for the minimum cost flow of the limited transmis- sion-path in multi-species flow traffic network is constructed. In the field of transportation, multi-species flow minimum cost flow problem is widespread, and the algorithm provides the basis to solve the related is- sues in actual traffic network.