交通运输网络中有流量约束的最小费用最大流分配

交通运输网络中有流量约束的最小费用最大流分配

交通网络的最小成本效益最大化是图论的核心问题之一。常用的算法包括网络简单算法（graph简单算法）、连续最短缺陷算法（sucssie检验尔gori提名算法）、减速算法（抗皱算法）、离散算法（cyboricalgori提名算法）、序列算法（迭代算法）、基本迭代算法（矩阵算法）和缺陷算法（矩阵算法）等。例如，在实际应用中，大多数应用的流量都不受限制，因此，最小成本效益最大化的问题是，这两个关联节点之间的流量没有限制，并且最小成本效益最大化的问题是没有限制的。这意味着在大多数情况下，基于对流量没有限制的情况下分配流量，即对两个相关节点之间的流量没有限制限制。在大多数情况下，最小成本效益最大化的问题有着许多实际的应用背景。同时，在实践中，对交通网络上两个相关节点之间的流量通常有具体的要求和限制。使用传统算法不能很好地解决由于传统算法而导致的最小成本最大化问题。因此，有必要根据传统算法的基础，研究网络中两个相关节点之间的流量限制限制下的最小成本最大流，并建立具有约束力的最小成本分布算法。本文对交通运输网络中最小费用最大流的分配要求两个结点之间的流量不能超过限制值、不能低于限制值以及在一定范围之内这3种约束条件进行了分析和分类,基于连续最短路算法的思路,结合两个结点之间的流量有具体的要求和约束限制条件,构造了约束限制条件下的最小费用最大流分配算法.1连续最短路算法为了对连续最短路算法(SuccessiveShortestPathAlgorithm,SSPA)引用方便,在这里假设用SSPA(G)表示该算法,其中G表示交通运输网络图,同时为了描述图G中两个结点之间的流量有约束条件,将连续最短路算法的描述形式采用SSPA{G,maxFlow|(A)}来表示,其中maxFlow|(A)表示在约束条件A下的最小费用最大流.针对连续最短路算法,约束条件A=Ø,即对两个结点之间的流量没有约束条件的连续最短路算法用SSPA{G,maxFlow|(Ø)}表示.对两个结点之间流量有约束限制条件的3种情况如下描述:1)两个结点之间流量不能超过限制值.假设结点vi和结点vj之间流量不能超过限制值Z,用SSPA{G,maxFlow|(Flow(vi,vj)≤Z)}来描述此约束条件.2)两个结点之间流量不能低于限制值.假设结点vi和结点vj之间流量不能低于限制值Z,用SSPA{G,maxFlow|(Flow(vi,vj)≥Z)}来描述此约束条件.3)两个结点之间流量在一定范围之内.假设结点vi和结点vj之间流量在限制值Z1和Z2之间,用SSPA{G,maxFlow|(Z1≤Flow(vi,vj)≤Z2)}来描述此约束条件.2在两个节点之间的流量限制下，有条件的算法尽管两个结点之间流量约束限制有3种情况,但只针对3)两个结点之间流量在一定范围内的情况进行算法设计即可.2.1设置流量调整量在计算过程中,先利用增流链方法将图G中两个限制结点之间的流量调整到限制值,但调整过程中必须满足以下规则:规则1新的增流链必须包含两个限制结点并且尽可能是从源到汇的最短路径.规则2如果新增流链中两个限制结点的边为前向边,那么该边流量调整量为最大限制值减去流量.规则3如果新增流链中两个限制结点的边为后向边,那么该边流量调整量为流量减去最小限制值.规则1是在满足费用最小情况下将两个限制结点之间流量调整在最小限制值和最大限制值之间的前提,规则2是使两个限制结点之间流量在最大限制值之内进行流量增加,规则3是使两个限制结点之间流量的减少不低于最小限制值.2.2基于流量网络的增流算法假设结点vi和结点vj之间流量限制的最小值为Z1,最大值为Z2,即Z1≤Flow(vi,vj)≤Z2),这里用SSPA{G,maxFlow|Z1≤Flow(vi,vj)≤Z2)}表示该算法,算法过程如下:第1步因为流量的分配必须满足容量限制条件,所以首先将限制结点之间的容量值用最大限制值Z2做新的容量,即C(vi,vj)=Z2.第2步如果边(vi,vj)的流量小于最小限制值Z1,为了满足规则1,进行以下过程:1)在图G中找从起点x到结点vi的关于费用W尽可能最短并且不饱和的链路Q1.2)在图G中找从结点vj到终点y的关于费用W尽可能最短并且不饱和的链路Q2.3)设不饱和链路Q1的调整量为l(Q1),不饱和链路Q2的调整量为l(Q2),则增流链Q1+(vi,vj)+Q2的调整量l(Q1+(vi,vj)+Q2)=min{l(Q1),C(vi,vj)-f(vi,vj),l(Q2)}.4)对增流链Q1+(vi,vj)+Q2按照修改流性质进行流量调整,如果两个限制结点之间流量在限制值Z1和Z2之间,停止,否则,返回第1)个过程.第3步构造图G的伴随流量f的增流网络Gf=(V′,E′,C′,W′,X′,Y′),Gf中顶点同G中顶点一样,即V′=V;X′=X;Y′=Y,但E′,C′,W′的规则如下:1)针对边(vi,vj)①若f(vi,vj)<C(vi,vj)且f(vi,vj)>Z1,则在Gf中构造两条边e1=(vi,vj)和e2=(vj,vi),其中针对e1有C′(vi,vj)=C(vi,vj)-f(vi,vj),W′(vi,vj)=W(vi,vj);针对e2有C′(vj,vi)=f(vj,vi)-Z1,W′(vj,vi)=-W(vi,vj).②若f(vi,vj)<C(vi,vj)且f(vi,vj)=Z1,则在Gf中构造一条边e=(vi,vj),其中针对e有C′(vi,vj)=C(vi,vj)-f(vi,vj),W′(vi,vj)=W(vi,vj).③若f(vi,vj)=C(vi,vj),则在Gf中构造一条边e=(vj,vi),其中针对e有C′(vj,vi)=C(vi,vj)-Z1,W′(vj,vi)=-W(vi,vj).2)针对边(vi,vj)以外的边①若G中f(u,v)<C(u,v)且f(u,v)>0,则在Gf中构造两条边e1=(u,v)和e2=(v,u),其中针对e1有C′(u,v)=C(u,v)-f(u,v),W′(u,v)=W(u,v);针对e2有C′(v,u)=f(u,v),W′(v,u)=-W(u,v).②若f(u,v)=0,则在Gf中构造一条边e=(u,v),其中C′(u,v)=C(u,v)-f(u,v),W′(u,v)=W(u,v).③若G中f(u,v)=C(u,v),则在Gf中构造一条边e=(v,u),其中C′(v,u)=f(u,v),W′(v,u)=-W(u,v).第4步从增流网络Gf中找x到y的路径f,若不存在,则G的流即为最小费用最大流,算法终止,否则找出由x到y关于费用W的最短路径P,W(P*)=min{W(P)}.第5步求流的增加量δ,δ=min{C′(e),e∈P*}.第6步找出G中与最短路径P*对应的边,它是一条由源x到汇y的增流链,对所有前向边的流量加上δ,后向边的流量减去δ,其它边的流量不变.第7步网络的流值Valf*=Valf+δ,视f*为f,转第3步继续构造图G的伴随流量f的增流网络并继续调整.3利用修改流性质进行调整假设某交通运输网络如图1所示,图中线路数据表示(容量,费用),请分配代价最低的最大流量,要求结点v6到结点v5之间的流量在8和12之间.如果不考虑结点v6到结点v5之间的流量要求条件,直接调用连续最短路算法即可,但针对约束条件,需要利用本文涉及的算法,分配代价最低的最大流量过程如下:第1步将结点v6到结点v5之间的流量限制值用Z1和Z2表示,即Z1=8,Z2=12,给图一个初始流,同时用限制值Z2代替运输网络图中的C(v6,v5),即C(v6,v5)=Z2=12,如图2所示.第2步边(v6,v5)的流量不小于限制值Z1,先寻找从起点v1到结点v6的最短路径并且是不饱和的链路,假设寻找到不饱和的最短链路Q1为v1→v4→v6,那么调整量为l(Q1)=min{l(v1,v4),l(v4,v6)}=min{C(v1,v4)-f(v1,v4),C(v4,v6)-f(v4,v6)}=min{6-0,9-0}=6.再寻找从结点v5到终点v7不饱和的最短链路Q2为v5→v7,那么调整量为l(Q2)=min{l(v5,v7)}=min{C(v5,v7)-f(v5,v7)}=min{13-0}=13.增流链Q1+(v6,v5)+Q2的调整量:l(Q1+(v6,v5)+Q2)=min{l(Q1),Z1-f(v6,v5),l(Q2)}=min{6,8-0,13}=6.利用修改流性质进行调整,结果如图3所示.第3步边(v6,v5)的流量仍然小于限制值Z1,再寻找从起点v1到结点v6的不饱和的最短链路,假设寻找到的Q1为v1→v3→v6,那么调整量为l(Q1)=min{l(v1,v3),l(v3,v6)}=min{C(v1,v3)-f(v1,v3),C(v3,v6)-f(v3,v6)}=min{11-0,10-0}=10.再寻找从结点v5到终点v7不饱和的最短链路Q2为v5→v7,那么调整量为l(Q2)=min{l(v5,v7)}=min{C(v5,v7)-f(v5,v7)}=min{13-6}=7.增流链Q1+(v6,v5)+Q2的调整量:l(Q1+(v6,v5)+Q2)=min{l(Q1),Z1-f(v6,v5),l(Q2)}=min{10,8-6,7}=2.利用修改流性质进行调整,结果如图4所示.第4步边(v6,v5)的流量已经满足限制值Z1的要求,对图4做增流网络,因为边(v6,v5)的流量不能小于8,所以在增流网络中不能构造边(v5,v6),结果如图5所示.第5步在图5中找出从起点v1到终点v7的最短路径为v1→v2→v5→v7,流的调整量:δ=min{C′(e),e∈P*}={9,4,5}=4对图4进行流量调整,如图6所示.第6步对图6做增流网络,因为边(v6,v5)的流量不能小于8,所以在增流网络中不能构造边(v5,v6),结果如图7所示.第7步在图7中找出从起点v1到终点v7的最短路径为v1→v3→v6→v5→v7,流的调整量δ=min{C′(e),e∈P*}={9,8,4,1}=1,对图6进行流量调整,如图8所示.第8步对图8继续做增流网络并调整,结果如图9所示.第9步对图9做增流网络,因为边(v6,v5)的流量不能小于8,所以在增流网络中构造边(v5,v6)的容量只能是C′(v5,v6)=f(v5,v6)-Z=9-8=1,结果如图10所示.图10中不能找到从起点v1到终点v7的最短路径,而且图9中结点v6到结点v5之间的发送列车数也在8和12之间,所以开行列车