基于網絡流的多供需雙邊運輸問題模型

基于網絡流的多供需雙邊運輸問題模型

對于具有不同原產地、不同銷售場地、不同銷售渠道的產品運輸，大多數制造商生產的同一產品的質量相同。對于這樣的網絡流問題,已經有了成熟的求解模型和算法。但在實際問題中,不同廠家生產的同一產品,質量并不完全相同,當因產品質量問題而影響用戶使用時,用戶就會對不同廠家不同產品的數量提出具體要求,在這種情況下,已有的網絡模型及其算法不再適用。基于此,本文構建了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以總費用最小為目標函數,建立上述運輸問題的線性規(guī)劃模型如下: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網絡流算法的下界算法對于上文給出的線性規(guī)劃模型,取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條邊上的流量增加或減少一定數量,其他邊的容量將隨之減少或增加同樣的數量。為防止實際中轉量大于中轉站中轉能力,必須在每次調流之后,對中轉量發(fā)生變化的中轉站各條邊的容量進行修正。令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優(yōu)化方法由于上文所建網絡模型對各種產品經由中轉站的流量和廠家直接向用戶供貨的流量沒有約束力,所以不能直接采用最小費用最大流的一般算法,需要對最小費用最大流的一般算法進行改進。改進后的算法步驟如下。第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優(yōu)化算法3.2.1負回路v73e邊的容量與流量之差稱為邊的殘余容量。1條邊的殘余容量決定了該邊在當前流量水平下的增流能力。由3.1.2節(jié)的討論可知,1個中轉站的1條中轉站邊流量發(fā)生變化,同屬該中轉站的其他中轉站邊的容量就會隨之變化,邊的殘余容量也相應發(fā)生變化(直供邊也存在同樣的現象)。因此,按3.1節(jié)的算法求得的初始解中,就有可能存在負回路。如圖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變?yōu)棣摹?。如果此時D1用戶的需求量已經得到滿足,用3.1節(jié)的算法求解結束后,在邊(v3,v7),(v7,v19)和(v19,v31)的費用之和小于邊(v3,v31)費用的條件下,就會形成負回路v3-v31-v19-v7-v3。該回路是求解過程中自然形成的負回路,即已存在的負回路,對該類負回路直接用消圈法進行消圈優(yōu)化。3.2.2消圈優(yōu)化用于潛在負電路3.2.2.負回路vt由于同1個中轉站的各中轉站邊容量之和為1個常數,當其中部分邊的流量之和達到該中轉站的中轉能力時,同屬該中轉站的各中轉站邊殘余容量均為0。因此,即使各中轉站邊流量沒有達到最優(yōu)配置,也因搜索不到滿足要求的負回路而無法調整。直供邊也存在同樣的問題。為了進一步尋求較優(yōu)解,須設法找到潛在的負回路。為此,首先擴大中轉站邊和直供邊的容量,使殘余容量為0的中轉站邊和直供邊具備增流能力,為形成包含中轉站邊和直供邊的回路創(chuàng)造條件;為了使各中轉站中轉量不大于其中轉能力和向各用戶的直供量不大于其直供能力,可使屬于同一用戶的直供邊和屬于同一中轉站的中轉站邊在負回路中成對出現(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節(jié)給出的邊容量取值方法可知,在用戶需求量不大于供貨量且不大于中轉能力與直供能力之和時,所有的產品需求邊和用戶總需求邊因其殘余容量為0而處于斷開狀態(tài)。當用戶需求量大于供貨量且大于中轉能力與直供能力之和時,就有可能出現包含匯點vt的負回路。因此,不論出現上述哪種情況,切斷所有用戶總需求邊,去除虛設的匯點vt,以保證在負回路上調流后,各中轉站的中轉量和到達各用戶的直供量滿足其能力約束。3.2.2.配送邊搜索方案消圈優(yōu)化根據上文分析,切斷所有用戶總需求邊,令所有直供邊的邊容量為其所屬用戶的可直供能力,令所有中轉站邊的邊容量為其所屬中轉站的中轉能力,按以下搜索過程對潛在的負回路進行消圈優(yōu)化。(1)在直供邊間搜索。切斷所有配送邊,用消圈法進行優(yōu)化。由圖1可以看出,切斷所有配送邊后,如果存在負回路,則屬于同一用戶的直供邊將會成對出現在負回路中,調流后,雖然相關邊的流量發(fā)生了變化,但到達同一用戶總的直供運量保持不變。(2)在中轉站邊間搜索。切斷所有直供邊和配送邊。取1個中轉站k和1個用戶l,連接所有的邊(T′k,Dl);再取1個中轉站ck(ck≠k),除Dl外,連接所有的邊(T′ck,Dcl)(cl=1,2,…,L,cl≠l),用消圈法進行優(yōu)化。經上述切邊后的網絡稱為1個中轉站邊搜索方案(按搜索范圍命名,下同)。改變ck,l,k的值,重復上述過程,直到對所有的中轉站邊搜索方案進行了消圈優(yōu)化。上述配送邊的選取方法使得每次只有2個中轉站的所有中轉站邊出現在同一回路中。屬于同一中轉站的中轉邊成對出現。消圈后各中轉站的中轉量保持不變。(3)在直供邊—中轉站邊間搜索。切斷所有直供邊和配送邊,取1個用戶l,連接以Dl為終點的直供邊;取1個中轉站k,除Dl外,連接所有的邊(T′k,Dcl)(cl=1,2,…,L,cl≠l),用消圈法進行優(yōu)化。改變l和k的值,重復上述過程,直到對所有的直供邊—中轉站邊搜索方案進行了消圈優(yōu)化。上述直供邊和配送邊的選取方法使得每次只有1個用戶的直供邊和1個中轉站的中轉站邊同時出現在同一回路中。同屬1個用戶的直供邊和同屬同一中轉站的中轉站邊分別成對出現。消圈后其直供量和中轉量均保持不變。(4)在直供邊—所有中轉站邊間搜索。所有中轉站邊的容量按式(8)取值。切斷所有直供邊,連接所有的配送邊。任取1個可直供用戶l,連接以Dl為終點的直供邊;切斷所有指向該用戶的配送邊,用消圈法進行優(yōu)化。如圖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),再用消圈法進行優(yōu)化。改變l的值,重復調用上述4個搜索過程,直到對所有的直供邊—中轉站邊搜索方案進行了消圈優(yōu)化。上述直供邊和配送邊的選取方法使得每次只有1個用戶的直供邊成對出現在回路中,所有的中轉站邊則都有可能出現在回路中,但由于中轉站邊容量均取正常值,消圈后,直供量不發(fā)生變化,而相關中轉