基于网络流的多供需双边运输问题模型

基于网络流的多供需双边运输问题模型

对于具有不同原产地、不同销售场地、不同销售渠道的产品运输，大多数制造商生产的同一产品的质量相同。对于这样的网络流问题,已经有了成熟的求解模型和算法。但在实际问题中,不同厂家生产的同一产品,质量并不完全相同,当因产品质量问题而影响用户使用时,用户就会对不同厂家不同产品的数量提出具体要求,在这种情况下,已有的网络模型及其算法不再适用。基于此,本文构建了1种将中转站顶点、用户顶点拆分后与厂家顶点、产品顶点分别关联的运输问题网络模型,由于同属1个中转站的1组中转边容量之和及同属1个用户的1组直供边容量之和均为常数,一旦其残余容量为0,就无法在组内调整流量,从而使该网络模型的求解非常困难。文献研究了经济投入最少的网络容量扩张方法,但没有涉及针对流量调整的容量扩张问题。本文提出了1种扩容切边搜索算法,很好地解决了边残余容量为0条件下的流量调整问题。1同库存放的影响设有I个工厂生产J种产品,有K个中转站,L个用户,并且i=1,2,…,I;j=1,2,…,J;k=1,2,…,K;l=1,2,…,L。所有生产厂家的产品既可经由中转站运往用户,也可由厂家直接运往用户。所有产品均为普通货物,且性质相近,运到中转站和用户后,可同库存放。由于各厂家生产的同一产品质量存在一定的差异,部分用户认为这种差异对其使用有一定影响,从而对不同厂家不同产品的供货数量提出具体要求。定义参数如下:ai,j为i厂可提供第j种产品的数量;tk为k中转站的中转能力;q直l为l用户可接受厂家直接供货的最大直供能力;dj,l为l用户对j产品的需求量;oqi,j,l和uqi,j,l分别为l用户要求获得i厂j产品数量的下限和上限;p′i,j,k为从i厂将j产品运往k中转站的单位运费;p中j‚k为j产品在k中转站的单位中转费;p″i,j,l为从i厂将j产品直接运往l用户的单位运费;pue087j,k,l为从k中转站将j产品送达l用户的单位运费。定义决策变量如下:x′i,j,k为从i厂将j产品运往k中转站的单位数;x″i,j,l为从i厂将j产品直接运往l用户的单位数;xue087j,k,l为从k中转站将j产品送达l用户的单位数;xki‚j‚l为l用户从k中转站获得的i厂j产品的单位数。2产品需求量约束方程假设供需平衡,且各用户对i厂j产品需求下限之和不大于i厂j产品的供应量,即∑ioqi‚j‚l≤ai‚j以总费用最小为目标函数,建立上述运输问题的线性规划模型如下:minz=∑i∑j∑k(p´i‚j‚k+p中j‚k)x′i‚j‚k+∑i∑j∑lp″i‚j‚lx″i‚j‚l+∑j∑k∑lp‴j‚k‚lx‴j‚k‚l(1)s.t.∑kx′i‚j‚k+∑lx″i‚j‚l=ai‚j(2)∑ix″i‚j‚l+∑kx‴j‚k‚l=dj‚l(3)∑i∑jx′i‚j‚k≤tk(4)∑i∑jx″i‚j‚l≤q直l(5)oqi‚j‚l≤∑kxki‚j‚l+x″i‚j‚l≤uqi‚j‚l(6)模型中式(2)为产品供应量约束方程,式(3)为用户需求量约束方程,式(4)为中转能力约束方程,式(5)为用户直供能力约束方程,式(6)为用户要求产品数量上下限约束方程。3求解算法3.1获取初始解的算法3.1.1网络流算法的下界算法对于上文给出的线性规划模型,取I=2,J=2,K=3,L=2,则可以构造出如图1所示的运输网络G=(V,E,c,b),其中V是顶点集合,E是边集合,c是边容量,b是单位量费用。图1中,顶点内的Ai,Hj,Tk和Dl为顶点属性,分别表示生产厂家、产品种类、中转站和用户;s和t分别为虚设的源和汇。中转站是具有中转能力和费用的顶点,因此,每个中转站用1对顶点(Tk,T′k)表示,其中Tk为输入顶点,T′k为输出顶点,2个顶点间用边关联,称为中转站边。图1中,源s至各厂家Ai的边(v0,vr)(r=1,2)费用取0,边容量取无穷大;厂家Ai至产品Hj的边(vr,vu)(r=1,2;u=3,4,…,6)费用为0,边容量取ai,j;产品Hj至中转站输入顶点Tk的边(vr,vu)(r=3,4,…,6;u=7,8,…,18)费用为p′i,j,k(i为与Hj相关联的厂家),边容量取ai,j;中转站边(vr,vu)(r=7,8,…,18;u=19,20,…,30)费用取p中j‚k(j为与Tk相关联的产品种类),边容量取tk;中转站输出顶点T′k(为便于表述,本文也将顶点用其属性表示)至用户Dl的边(vr,vu)(r=19,20,…,30;u=31,32,…,38)称为配送边,费用取pue087j,k,l,边容量取tk;产品Hj至用户Dl的边(vr,vu)(r=3,…,6;u=31,32,…,38)称为直供边,其费用取p″i,j,l,边容量取q直l。为满足l用户对i厂第j种产品数量的上下限要求,通常需要构建容量有上下界约束的网络模型并用相应的算法求解,其求解过程比较复杂。文献提出了通过增加平行边将容量有上下界约束的网络流问题转化为普通网络流的方法。鉴于此,图1中增设了用户顶点(v39—v60)和相应的边,以便于问题的转化和流量汇总。各增设边参数说明如下:边(vr,vu)(r=31,32,…,38;u=47,48,…,54)费用取0,边容量取oqi,j,l(i,j分别为与l用户直接或间接相关联的厂家和产品种类),该边称为用户要求产品数量下界边;边(vr,vu)(r=31,32,…,38;u=39,40,…,46)与用户要求下界边平行,费用取1个足够大的正数M(例如Μ=maxi‚j‚k‚l{p′i‚j‚k+p″i‚j‚l+p中j,k+pue087j,k,l}),边容量取uqi,j,l-oqi,j,l(无上限要求时取dj,l-oqi,j,l),该边称为用户要求产品数量上界边;边(vr,vu)(r=39,40,…,46;u=47,48,…,54)费用取0,边容量取dj,l,该边称为用户要求上边界辅助边。以上3种边将容量有上下界约束的网络流问题转化成了普通网络流问题。边(vr,vu)(r=47,48,…,54;u=55,56,57,58)称为厂别产品到货边,费用取0,边容量取dj,l,该边上的流量为l用户实际获取的i厂第j种产品的数量;边(vr,vu)(r=55,56,57,58;u=59,60)称为产品需求边,费用取0,边容量取dj,l,该边上的流量为l用户从各厂获取第j种产品的总量;边(vr,vu)(r=59,60;u=61)称为用户总需求边,费用取0,边容量取∑jdj‚l,该边上的流量为l用户从各厂获取各种产品的总量。3.1.2也较高的能力为了满足用户对不同厂家不同产品的数量要求,每个中转站被分解成了N(N=I×J)个中转站顶点,中转站边也被相应地分解成了N条边。如图1中,T1中转站被分解为N=2×2=4个中转顶点,边被分解成了(v7,v19),…,(v16,v28)共4条边。每条中转站边上的流量为与之相关联厂家经由该中转站中转的j产品的数量,因此,在求解过程中,应使同属1个中转站各边上的流量之和不大于该中转站的中转能力。设fr,u为边(vr,vu)∈E上的流量,对于T1中转站有f7,19+f10,22+f13,25+f16,28≤t1(t1为T1中转站的中转能力)。可以看出,1个中转站的各条边上,如果其中1条边上的流量增加或减少一定数量,其他边的容量将随之减少或增加同样的数量。为防止实际中转量大于中转站中转能力,必须在每次调流之后,对中转量发生变化的中转站各条边的容量进行修正。令Hk={(I+N+(i-1)JK+(j-1)K+k,I+N+NK+(i-1)JK+(j-1)K+k)}(7)为k中转站所有中转站边的集合,则k中转站所有边的流量之和为Fk=∑(vr‚vu)∈Ηkfr‚u(8)k中转站各条边的容量为cr,u=tk-Fk+fr,u(vr,vu)∈Hk(9)图1中,每1组中转站顶点都与1组用户顶点相关联,每个用户顶点也被分解成了N个顶点。如图1中,用户D1被分解成了v31,v33,v35,v37计4个顶点。每条直供边上的流量为与之相关联厂家直接向该用户供应的第j种产品的数量。因此,在求解过程中,应使同1个用户的各直供边上的流量之和不大于该用户的直供能力。令Hl={(I+(i-1)J+j,I+N+2NK+(i-1)JL+(j-1)L+l)}(10)为l用户所有直供边的集合,则l用户所有直供边的流量之和为Wl=∑(vr‚vu)∈Ηl(11)l用户所有直供边的容量为cr,u=q直l-Wl+fr,u(vr,vu)∈Hl(12)3.1.3网络gf优化方法由于上文所建网络模型对各种产品经由中转站的流量和厂家直接向用户供货的流量没有约束力,所以不能直接采用最小费用最大流的一般算法,需要对最小费用最大流的一般算法进行改进。改进后的算法步骤如下。第1步所有边容量按上文给出的方法取初值。第2步对网络G=(V,E,c,b)给出流值为0的初始流。第3步构造1个伴随流f的增流网络Gf。第4步寻求最小费用增流链,在网络Gf中用标号法求源s至汇t的最短路P。若存在P,转第5步,否则算法结束。第5步取δ′=min{c′r,u,(vr,vu)∈P}。第6步在G上增流。第7步根据计算最短路时各结点的标号值P(v),按下式修正G中边的权数b(e)P(u)-P(v)+b(e)→b(e)第8步按式(8)修正中转站边容量。第9步按式(10)修正直供边容量。第10步将新流f′视为f,转第3步。3.2优化算法3.2.1负回路v73e边的容量与流量之差称为边的残余容量。1条边的残余容量决定了该边在当前流量水平下的增流能力。由3.1.2节的讨论可知,1个中转站的1条中转站边流量发生变化,同属该中转站的其他中转站边的容量就会随之变化,边的残余容量也相应发生变化(直供边也存在同样的现象)。因此,按3.1节的算法求得的初始解中,就有可能存在负回路。如图1中,在直供边(v3,v31)上的残余容量为0的条件下,又搜索到1条增流链v0-v1-v3-v7-v19-v31-v39-v47-v55-v51-v43-v35-v5-v36-v44-v52-v56-v60-v61,沿该链增流δ′后,使直供边(v5,v35)上的流量减少δ′,从而使直供边(v3,v31)上的残余容量由0变为δ′。如果此时D1用户的需求量已经得到满足,用3.1节的算法求解结束后,在边(v3,v7),(v7,v19)和(v19,v31)的费用之和小于边(v3,v31)费用的条件下,就会形成负回路v3-v31-v19-v7-v3。该回路是求解过程中自然形成的负回路,即已存在的负回路,对该类负回路直接用消圈法进行消圈优化。3.2.2消圈优化用于潜在负电路3.2.2.负回路vt由于同1个中转站的各中转站边容量之和为1个常数,当其中部分边的流量之和达到该中转站的中转能力时,同属该中转站的各中转站边残余容量均为0。因此,即使各中转站边流量没有达到最优配置,也因搜索不到满足要求的负回路而无法调整。直供边也存在同样的问题。为了进一步寻求较优解,须设法找到潜在的负回路。为此,首先扩大中转站边和直供边的容量,使残余容量为0的中转站边和直供边具备增流能力,为形成包含中转站边和直供边的回路创造条件;为了使各中转站中转量不大于其中转能力和向各用户的直供量不大于其直供能力,可使属于同一用户的直供边和属于同一中转站的中转站边在负回路中成对出现(1条正向边和1条反向边同时出现),这样当其中1条边增加流量δ′时,另1条边同时减少流量δ′,保证到达各用户的直供量和各中转站的中转量不因其边容量的扩大而增大。为了使负回路符合上述要求,需切断部分直供边和配送边,从而将负回路搜索限制在直供边间、中转站边间、直供边—中转站边间、直供边—所有中转站边间计4种范围之内。同时由图1可以看出,当负回路包含虚设的汇点vt时,不能保证同一用户的直供边和同一中转站的中转站边成对出现。如图1中,若存在负回路v3-v7-v19-v31-v39-v47-v55-v59-v61-v60-v56-v48-v40-v32-v21-v9-v3,在该回路上调流后,就会导致T1中转站的中转量大于其中转能力。由3.1节给出的边容量取值方法可知,在用户需求量不大于供货量且不大于中转能力与直供能力之和时,所有的产品需求边和用户总需求边因其残余容量为0而处于断开状态。当用户需求量大于供货量且大于中转能力与直供能力之和时,就有可能出现包含汇点vt的负回路。因此,不论出现上述哪种情况,切断所有用户总需求边,去除虚设的汇点vt,以保证在负回路上调流后,各中转站的中转量和到达各用户的直供量满足其能力约束。3.2.2.配送边搜索方案消圈优化根据上文分析,切断所有用户总需求边,令所有直供边的边容量为其所属用户的可直供能力,令所有中转站边的边容量为其所属中转站的中转能力,按以下搜索过程对潜在的负回路进行消圈优化。(1)在直供边间搜索。切断所有配送边,用消圈法进行优化。由图1可以看出,切断所有配送边后,如果存在负回路,则属于同一用户的直供边将会成对出现在负回路中,调流后,虽然相关边的流量发生了变化,但到达同一用户总的直供运量保持不变。(2)在中转站边间搜索。切断所有直供边和配送边。取1个中转站k和1个用户l,连接所有的边(T′k,Dl);再取1个中转站ck(ck≠k),除Dl外,连接所有的边(T′ck,Dcl)(cl=1,2,…,L,cl≠l),用消圈法进行优化。经上述切边后的网络称为1个中转站边搜索方案(按搜索范围命名,下同)。改变ck,l,k的值,重复上述过程,直到对所有的中转站边搜索方案进行了消圈优化。上述配送边的选取方法使得每次只有2个中转站的所有中转站边出现在同一回路中。属于同一中转站的中转边成对出现。消圈后各中转站的中转量保持不变。(3)在直供边—中转站边间搜索。切断所有直供边和配送边,取1个用户l,连接以Dl为终点的直供边;取1个中转站k,除Dl外,连接所有的边(T′k,Dcl)(cl=1,2,…,L,cl≠l),用消圈法进行优化。改变l和k的值,重复上述过程,直到对所有的直供边—中转站边搜索方案进行了消圈优化。上述直供边和配送边的选取方法使得每次只有1个用户的直供边和1个中转站的中转站边同时出现在同一回路中。同属1个用户的直供边和同属同一中转站的中转站边分别成对出现。消圈后其直供量和中转量均保持不变。(4)在直供边—所有中转站边间搜索。所有中转站边的容量按式(8)取值。切断所有直供边,连接所有的配送边。任取1个可直供用户l,连接以Dl为终点的直供边;切断所有指向该用户的配送边,用消圈法进行优化。如图1中,任取1个可直供用户1,连接以D1为终点的直供边(v3,v31),(v4,v33),(v5,v35),(v6,v37),切断与D1相关联的所有配送边(v19,v31),(v20,v31),(v21,v31),…,(v28,v37),(v29,v37),(v30,v37),再用消圈法进行优化。改变l的值,重复调用上述4个搜索过程,直到对所有的直供边—中转站边搜索方案进行了消圈优化。上述直供边和配送边的选取方法使得每次只有1个用户的直供边成对出现在回路中,所有的中转站边则都有可能出现在回路中,但由于中转站边容量均取正常值,消圈后,直供量不发生变化,而相关中转