交通运输网络中两个结点间有流量约束的最小费用最大流算法

对交通运输网络最小费用最大流的分配是在满足容量限制条件和流量守恒条件下,基于总费用最低的原则进行的,但在实际应用中,通常对交通运输网络中两个结点之间的流量有具体的要求和约束限制条件.针对交通运输网络中两个结点之间有流量约束的最小费用最大流问题进行了分析,总结了两个结点之间的流量不能超过限制值、不能低于限制值以及在一定范围内的3种约束条件.基于连续最短路算法中构造伴随增流网络的思路,设计了这3种约束限制条件下的最小费用最大流分配算法.利用这个算法,可以解决交通运输网络中两个结点之间有流量约束的最小费用最大流分配问题.在交通运输领域,两个结点之间有流量约束的最小费用最大流问题普遍存在,这些算法也为解决实际的运输问题提供了应用基础.

An Algorithm for the Minimum Cost Max-flow with Limited Flow Between Two Notes in the Traffic and Transportation Network

In aspect of the traffic and transportation network,the distribution of the minimum cost max-flow is based entirely on the capacity restriction,the flow conservation and the minimum cost,but in practical application,there are usually special requirements and restrictive conditions between the two notes.In this article,by describing and analyzing,three restrictive conditions are classified,between the two notes,which are the flow neither exceed the limit nor be less than the limit,and the flow must be within the confines of the limit. In addition, based on the gain-flow network of the successive shortest path algorithm and these ristrictions, three optimization algorithms of the distribution of the minimum cost max-flow are put forward on the transportation network. Thus, the distribution of maximum flow under three restrictive conditions can be solved. In the traffic and transportation field, it is ubiquitous to distribute the minimum cost maxflow under flow restrictions, so these algorithms offer the application foundation for framing the traffic and transportation network project.