多品种流中特定品种在结点上的流量有要求的最大流算法设计

丁 振 寇玮华 崔皓莹

0 引 言

最大流问题是图论的核心问题之一，传统的最大流算法只能对单一品种的流量进行分配[1-4]。而对于多品种问题，虽然可以通过按品种拆分结点重构网络来求解最大流，但是，这种解法经常使得运算过程很繁琐[5,6]。多品种流交通网络中，特定品种在结点上的流量有要求的问题，类似于运输问题中的多品种问题，在实际交通网络中频繁出现，而在图论中暂时没有很好的求解方法。本文先对求解最大流的 Ford-Fulkerson算法进行改进，构造求解多品种问题最大流的算法，然后在这个基础上构造了特定品种在结点上的流量有要求的交通网络最大流算法。

1 基于多品种问题的Ford-Fulkerson算法描述

1.1 多品种流的交通网络特性分析

多品种流可以定义为在交通网络中存在的多股相互独立的流。

传统的交通网络中，只针对单一品种流进行分析，而实际的交通网络常常涉及多品种流的输送。多品种流网络具有以下几个特点：

（1）独立性。除非有特别说明，否则各品种流之间不能相互代替，具有独立性。

（2）结点的准入特性。与一般交通网络不同，多品种流交通网络上每个结点对流的进入有品种限制。

（3）发出点与接收点。多品种流交通网络有特定的一个或多个发出点与接收点。

目前求网络最大流主流的算法有 Ford-Fulkerson算法等，而为求多品种流网络的最大流势必要对原有算法进行改进。

通过对多品种流交通网络特性的分析，基于多品种问题的 Ford-Fulkerson算法与一般 Ford-Fulkerson算法的区别主要有以下几个方面：

（1）结点的标记。多品种问题中有发出点与接收点，本文用xi、yj分别表示交通网络中发出点和接收点。为了运算方便，定义一个总源点x和总汇点y，其他中间点用vi来表示。

（2）网络中边上流量的表示。一般Ford-Fulkerson算法用一个数值表示边上的流量，而基于多品种问题的Ford-Fulkerson算法用集合f(fk)=( f1, f2,…, fk, …, fq)表示该边上每一种品种的流量。

（3）在一条增流链上，基于多品种问题的Ford-Fulkerson算法只能对一个品种的流量进行调整。

（4）由于结点的准入特性，在增流时，多品种问题需要确认下一个结点是否能接收该品种的流量。

1.2 多品种流交通网络描述

根据以上描述，对基于多品种问题的Ford-Fulkerson算法可以定义如下：

（1）交通网络图用G=( X,Y, V, E,C,F)来表示。

（2）集合X={x,xi|i=1,2,…,n1}, x为图G的源，xi为发出点；集合Y={y,yj|j=1,2,…,n2}，y为图G的汇，yj为接收点；中间结点集合 V={vi|i=1,2,…,n3}。其中X、Y和V只能接收或发出特定品种的流量；边集合E={e(x,xi),e(xi,vi),e(vi,vj),e(vj,yi),e(yi,y),e(xi,yj)|x,xi∈X;vi,vj∈V;yi,y∈Y}；C为边的容量的集合；

（3）F为边的流量的集合，假设k为图G中的第k个品种（k=1,2,…,q），fkuv为边（u,v）上品种k的流量，fuv(fk)=(f1, f2,…,fq)表示边（u,v）上各品种的流量，并且f1+f2+…+fq=f(u,v)，f(u,v)为该边上所有品种流量之和。

图G中满足以下条件的一组流可以称为可行流：

①容量限制条件，对任意边e=(u,v)∈E有

其中，c为(u,v)的容量，fkuv为该边上品种k的流量。

②结点流量平衡条件：

对于结点u≠x,y，有

以上条件保证结点上每个品种的流量守恒，同时保证了结点上所有品种的流量之和的守恒。

用v(fk)表示从x到y的品种k的可行流的流量，v(f)表示从x到y的可行流流量的总和。对于结点u=x或y，有

1.3 算法步骤

基于多品种问题的Ford-Fulkerson算法步骤如下[7]：

第一步：给图 G一个初始流（一般为平凡的可行流）。给初始流的过程中要满足以下规则：

规则1：输送给结点的某品种的流量必须满足该结点对品种类别的要求。

规则2：各个品种之间的流量应该区分开来。

交通网络 G上各边对容量和流量的描述应遵从多品种流特点，用[c,( f1,f2,…,fq)]表示。同时给结点x标号。

第二步：寻找源x到汇y的增流链Q的方法：

寻找增流链首先必须满足下列规则：

规则3：一条增流链上只能对一个品种的流量进行调整。当对某个品种在增流链上进行流量调整时，不管是前向边还是后向边，在该增流链上只能对该品种的流量进行调整。

（1）与结点v相关的边上某一品种能否增流的条件：

①基于规则1，即结点v能否接收该品种的流。

当边e=(u,v)为后向边时，有边(u,v)上品种k的流量＞ 0 。

（2）对满足以上条件的结点 v进行标记（u，边的方向和调整的品种，lk(v)）。其中u为标记点v的前一个结点；v为终点时边的方向，用+表示；v为始点时边的方向，用-表示；边的方向和调整的品种表示如下：+k或者-k；lk(v)表示品种k的调整量。v为终点时lk(v)=min{lk(u),C(u,v)-f(u,v)}，v为始点时lk(v)=min{lk(u),fuvk}，其中 f(u,v)为(u,v)上所有品种流量之和。

第三步：按照标号的第一项，从汇y进行反向追踪，可得到增流链Q以及品种k的调整量lk(Q)=lk(y)。

第四步：利用修改流性质进行调整：

（1）增流链Q的前向边，品种k的流量加上调整量 lk(Q)。

（2）增流链Q的后向边，品种k的流量减去调整量 lk(Q)。

（3）非增流链Q的边的调整量不变。

第五步：返回第二步，不断循环，直到不能找到增流链为止。

为了引用方便，在这里假设用 MV-Ford-Fulkerson(G)表示基于多品种的Ford-Fulkerson算法，其中G表示交通网络图。

2 对特定品种在结点上的流量有要求的几种情况

为了描述图 G中对特定品种在结点上的流量有要求的约束条件[8]，将基于多品种流的Ford-Fulkerson算法的描述形式采用MV-Ford-Fulkerson{G,MAXFlow|(A)}来表示，其中MAXFlow|(A)表示在约束条件A下的最大流量。若A=∅，即对特定品种没有约束条件的MV-Ford-Fulkerson算法用MV-Ford-Fulkerson{G,MAXFlow|(∅)}表示。本文讨论的对特定品种的流量有要求的4种情况描述如下：

（1）某发出点发出某一品种的流量有最低限制

假设交通网络图中有 q个品种，要求发出点 xi发出品种 k的流量至少为 Z。用 MV-Ford-Fulkerson{G,MAXFlow|(Flow(xi)k≥Z,)}来描述此约束条件。

（2）某接收点接收某一品种的流量有最低限制

假设交通网络图中有 q个品种，要求接收点 yj接收品种 k的流量至少为 Z。用 MV-Ford-Fulkerson{G,MAXFlow|(Flow(yj)k≥Z,)}来描述此约束条件。

（3）某发出点发出某一品种的流量有最高限制

假设交通网络图中有 q个品种，要求发出点 xi发出品种 k的流量最多为 Z。用 MV-Ford-Fulkerson{G,MAXFlow|(Flow(xi)k≤Z,)}来描述此约束条件。

（4）某接收点接收某一品种的流量有最高限制

假设交通网络图中有 q个品种，要求接收点 yj接收品种 k的流量最多为 Z。用 MS-Ford-Fulkerson{G,MAXFlow|(Flow(yj)k≤Z,)}来描述此约束条件。

3 多品种流中对特定品种在结点上的流量有要求的最大流算法

3.1 某发出点发出的某一品种的流量有最低限制的算法

（1）算法思想[9]

由于输送流量给发出点xi的边仅有一条，因此该约束可以转换为要求边(x,xi)上的品种k的流量至少为Z。在计算过程中，先利用增流链方法将图G中在x与xi之间品种k的流量调整到限制值，在此基础上进行流量分配。但(x,xi)之间的流量须满足以下规则：

规则4：如果新的增流链包括(x,xi)，且为前向边，那么该边上的该品种的流量调整量为容量减去所有品种流量之和。

规则5：如果新的增流链包括(x,xi)，且为后向边，那么该边上的该品种的流量调整量为该品种的流量减去最低限值Z。

（2）算法过程

发出点xi发出品种k的流量不能低于限制值Z，步骤如下：

第一步：如果边(x,xi)上的品种k的流量fkxxi小于限制值Z，进行以下过程：

（1）按照标记法先找从发出点xi到汇y品种k的不饱和链Q1，寻找增流链的时候必须满足规则1、2和3。

（2）确定增流链(x,xi)+Q1上的品种k的调整量：lk((x,xi)+Q1)=min{lk(Q1),C(x,xi)-f(x,xi)}。

（3）对增流链(x,xi)+Q1按照修改流性质进行流量调整，如果(x,xi)之间fkxxi大于等于限制值Z，停止。否则，返回第（1）个过程。

第二步：对图G调用MV-Ford-Fulkerson(G)，寻找增流链。如果增流链 Q包括(x,xi)，并对品种 k进行流量调整，根据规则4和5，增流链的调整量如下所示：

当边(x,xi)为前向边时，lk(Q)=min{lk(Q1),C(x,xi)-f(x,xi)}；当边(x,xi)为后向边时，lk(Q)=min{lk(Q1),fkxxi-Z}；第三步：返回第二步，不断循环，直到不能找到增流链为止。

在以上的算法中，边(x,xi)是不可能出现后向边的，本文写出后向边的目的是为了能够拓展到对多品种问题任意一条边的流量有限制的情况。本文的算法对多品种网络上任意一条边上某品种的流量有限制的情况同样适用。

3.2 某接收点接收某一品种的流量有最低限制的算法

（1）算法思想

同理，该约束可以转换为要求边(yj,y)上的品种k的流量至少为Z。在计算过程中，先利用增流链方法将图G中在yj与y之间品种k的流量调整到最低限制值，在此基础上进行流量分配。规则与前述相似。

（2）算法过程与3.1相似。

3.3 某发出点发出某一品种的流量有最高限制的算法

（1）算法思想

限制边(x,xi)上的品种k的流量最高为Z。只需在进行流量分配和流量调整时，使边(x,xi)上的品种k的流量不要超过限制值即可。

（2）算法步骤

调用MV-Ford-Fulkerson(G)。

第一步：给图G一个初始流。若(x,xi)上fkxxi≤Z，则进行下一步，否则重新分配流量。

第二步：寻找源x到汇y的增流链Q。

（1）检查增流链上是否包含边(x,xi)，并且对品种k进行了流量调整。否则，进行第三步。

（2）当增流链 Q上有边(x,xi)，并且调整的是品种k的流量，则确认调整后fkxxi是否小于等于Z，若是则进行下一步，否则重新调整 lk(Q)的值或者重新寻找增流链。

第三步：返回第二步，不断循环，直到不能找到增流链为止。

3.4 某接收点接收某一品种的流量有最高限制的算法

（1）算法思想

限制边(yj,y)上的品种 k的流量最高为 Z。只需在进行流量分配和流量调整时，使边(yj,y)上的品种k的流量不要超过限制值即可。

（2）算法步骤

算法过程与3.3相似。

4 示 例

已知某交通网络有3个品种Ⅰ、Ⅱ和Ⅲ的货物需要输送，各结点关系如图1所示，图中数值表示边的容量。表 1表示各结点所能接收的品种。要求结点x1发出品种Ⅱ的数量至少为4，y2接收品种Ⅰ的数量至少为 5，x3发出品种Ⅱ的数量最多为 3，y3接收品种Ⅱ的数量最多为4，请分配最大流。

图1 运输网络结构Fig.1 Configuration of traffic network

表1 各结点所能接收的品种类型Tab.1 Types of the varieties each node can receive

该题是多品种流的问题，同时对特定的品种有条件要求，因此不能直接采用Ford-Fulkerson算法。针对题中的约束条件，可以采用本文相关的一些算法。由于篇幅限制，省略掉寻找增流链的过程，解题过程如下：

给定初始流为零流，如图2所示。

图2 初始化的运输网络结构Fig.2 Initialization of the transportation network configuration

针对约束条件，结点 x1发出品种Ⅱ的数量至少为4，即要求（x,x1）上的品种Ⅱ的流量至少为4。寻找 x1到 y，品种Ⅱ不饱和链 Q1：x1→v1→v2→y3→y，调整量：

增流链(x,x1)+Q1品种Ⅱ的调整量：lⅡ((x,x1)+Q1)=min{C(x,x1)-f(x,x1), lⅡ(Q2)}=min{8-0,4}=4。利用修改流性质进行调整，fkxx1=4。同时，由于限制了y3接收品种Ⅱ的数量最多为4，增流链上有边(y3,y)，并对品种Ⅱ增流，检查(y3,y)上流量。品种Ⅱ流量小于等于4，该结果是满足限制条件的，结果如图3所示。

图3 基于修改流的分配方案1Fig.3 Scheme 1 of flow distribution based on modification

同理，针对约束条件 y2接收品种Ⅰ的数量至少为5，即要求(y2,y)上的品种Ⅰ的流量至少为5。寻找x到 y2，品种Ⅰ不饱和链 Q2：x→x2→v1→y2，调整量：lⅠ(Q2)=6。增流链 Q2+(y2,y)品种Ⅰ的调整量：lⅠ(Q2+(y2,y))=6。利用修改流性质进行调整，结果如图4所示。

图4 基于修改流的分配方案2Fig.4 Scheme 2 of flow distribution based on modification

第三步：寻找增流链。Q3：x→x1→y1→y，对品种Ⅰ进行流量调整，lⅠ(Q3)=4，结果如图5所示。同理，寻找增流链 Q4：x→x2→v2→y3→y，对品种Ⅲ进行流量调整，lⅢ(Q4)=4，结果如图6所示。寻找增流链 Q5：x→x3→v2→v1→y2→y，对品种Ⅱ进行流量调整，lⅡ(Q5)=3，结果如图 7所示。寻找增流链 Q6：x→x3→v2→y3→y，对品种Ⅲ进行流量调整，lⅢ(Q6)=4，结果如图8所示。

在图4中再无法寻找到增流链，最终方案如图8所示。

图5 基于修改流的分配方案3Fig.5 Scheme 3 of flow distribution based on modification

图6 基于修改流的分配方案4Fig.6 Scheme 4 of flow distributing based on modification

图8 基于修改流的最终方案Fig.8 Scheme of flow distribution based on modification

5 结束语

本文研究的算法，是在Ford-Fulkerson算法基础上，解决多品种流中结点上对特定品种的流量有要求的交通网络最大流问题，本文的算法对多品种网络上任意一条边的某品种的流量有限制的情况同样适用。对于特别复杂的情况，本文的标号方法和各品种流量表示不是很明晰，应加以改进。本文研究对象针对的是发出点与接收点，而针对其他中间结点某品种流量的限制还没有研究，应继续研究相应的算法。

[1] 寇玮华.运筹学[M].成都：西南交通大学出版社，2013.

[2] 徐周波,古天龙,赵岭忠.网络最大流问题求解的符号ADD 增广路径算法[J].计算机科学，2005,32(10)∶38-54.

[3] 寇玮华,李宗平. 运输网络中有流量需求的转运结点最大流分配算法[J]. 西南交通大学学报，2009,44(1)∶118-121

[4] Daiheng Ni. Determining Traffic-Flow Characteristics by Definition for Application in ITS [J]. IEEE Transactions on Intelligent Transportation Systems,2007, 8(2)∶ 181-187.

[5] 焦永兰.管理运筹学[M].北京∶中国铁道出版社,2005.

[6] 甘爱英等. 运筹学[M].北京∶清华大学出版社,2002.

[7] 孙泽宇,丁国强,程志谦. 网络最大流求解算法的研究[J]. 微计算机信息, 2010,(03)∶143-145.

[8] 寇玮华,董雪,吕林剑.交通运输网络中两个结点间有流量约束的最小费用最大流算法[J].兰州交通大学学报, 2009,28(6)∶104-109

[9] 寇玮华,朱雪丽,张聪聪. 交通网络两个相邻结点之间有流量约束的最大流分配算法[J].交通运输工程与信息学报, 2010,8(1)∶7-13.