基于網(wǎng)絡流的多供需雙邊運輸問題模型

基于網(wǎng)絡流的多供需雙邊運輸問題模型

對于具有不同原產(chǎn)地、不同銷售場地、不同銷售渠道的產(chǎn)品運輸，大多數(shù)制造商生產(chǎn)的同一產(chǎn)品的質(zhì)量相同。對于這樣的網(wǎng)絡流問題,已經(jīng)有了成熟的求解模型和算法。但在實際問題中,不同廠家生產(chǎn)的同一產(chǎn)品,質(zhì)量并不完全相同,當因產(chǎn)品質(zhì)量問題而影響用戶使用時,用戶就會對不同廠家不同產(chǎn)品的數(shù)量提出具體要求,在這種情況下,已有的網(wǎng)絡模型及其算法不再適用?；诖?本文構(gòu)建了1種將中轉(zhuǎn)站頂點、用戶頂點拆分后與廠家頂點、產(chǎn)品頂點分別關(guān)聯(lián)的運輸問題網(wǎng)絡模型,由于同屬1個中轉(zhuǎn)站的1組中轉(zhuǎn)邊容量之和及同屬1個用戶的1組直供邊容量之和均為常數(shù),一旦其殘余容量為0,就無法在組內(nèi)調(diào)整流量,從而使該網(wǎng)絡模型的求解非常困難。文獻研究了經(jīng)濟投入最少的網(wǎng)絡容量擴張方法,但沒有涉及針對流量調(diào)整的容量擴張問題。本文提出了1種擴容切邊搜索算法,很好地解決了邊殘余容量為0條件下的流量調(diào)整問題。1同庫存放的影響設有I個工廠生產(chǎn)J種產(chǎn)品,有K個中轉(zhuǎn)站,L個用戶,并且i=1,2,…,I;j=1,2,…,J;k=1,2,…,K;l=1,2,…,L。所有生產(chǎn)廠家的產(chǎn)品既可經(jīng)由中轉(zhuǎn)站運往用戶,也可由廠家直接運往用戶。所有產(chǎn)品均為普通貨物,且性質(zhì)相近,運到中轉(zhuǎn)站和用戶后,可同庫存放。由于各廠家生產(chǎn)的同一產(chǎn)品質(zhì)量存在一定的差異,部分用戶認為這種差異對其使用有一定影響,從而對不同廠家不同產(chǎn)品的供貨數(shù)量提出具體要求。定義參數(shù)如下:ai,j為i廠可提供第j種產(chǎn)品的數(shù)量;tk為k中轉(zhuǎn)站的中轉(zhuǎn)能力;q直l為l用戶可接受廠家直接供貨的最大直供能力;dj,l為l用戶對j產(chǎn)品的需求量;oqi,j,l和uqi,j,l分別為l用戶要求獲得i廠j產(chǎn)品數(shù)量的下限和上限;p′i,j,k為從i廠將j產(chǎn)品運往k中轉(zhuǎn)站的單位運費;p中j?k為j產(chǎn)品在k中轉(zhuǎn)站的單位中轉(zhuǎn)費;p″i,j,l為從i廠將j產(chǎn)品直接運往l用戶的單位運費;pue087j,k,l為從k中轉(zhuǎn)站將j產(chǎn)品送達l用戶的單位運費。定義決策變量如下:x′i,j,k為從i廠將j產(chǎn)品運往k中轉(zhuǎn)站的單位數(shù);x″i,j,l為從i廠將j產(chǎn)品直接運往l用戶的單位數(shù);xue087j,k,l為從k中轉(zhuǎn)站將j產(chǎn)品送達l用戶的單位數(shù);xki?j?l為l用戶從k中轉(zhuǎn)站獲得的i廠j產(chǎn)品的單位數(shù)。2產(chǎn)品需求量約束方程假設供需平衡,且各用戶對i廠j產(chǎn)品需求下限之和不大于i廠j產(chǎn)品的供應量,即∑ioqi?j?l≤ai?j以總費用最小為目標函數(shù),建立上述運輸問題的線性規(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)為產(chǎn)品供應量約束方程,式(3)為用戶需求量約束方程,式(4)為中轉(zhuǎn)能力約束方程,式(5)為用戶直供能力約束方程,式(6)為用戶要求產(chǎn)品數(shù)量上下限約束方程。3求解算法3.1獲取初始解的算法3.1.1網(wǎng)絡流算法的下界算法對于上文給出的線性規(guī)劃模型,取I=2,J=2,K=3,L=2,則可以構(gòu)造出如圖1所示的運輸網(wǎng)絡G=(V,E,c,b),其中V是頂點集合,E是邊集合,c是邊容量,b是單位量費用。圖1中,頂點內(nèi)的Ai,Hj,Tk和Dl為頂點屬性,分別表示生產(chǎn)廠家、產(chǎn)品種類、中轉(zhuǎn)站和用戶;s和t分別為虛設的源和匯。中轉(zhuǎn)站是具有中轉(zhuǎn)能力和費用的頂點,因此,每個中轉(zhuǎn)站用1對頂點(Tk,T′k)表示,其中Tk為輸入頂點,T′k為輸出頂點,2個頂點間用邊關(guān)聯(lián),稱為中轉(zhuǎn)站邊。圖1中,源s至各廠家Ai的邊(v0,vr)(r=1,2)費用取0,邊容量取無窮大;廠家Ai至產(chǎn)品Hj的邊(vr,vu)(r=1,2;u=3,4,…,6)費用為0,邊容量取ai,j;產(chǎn)品Hj至中轉(zhuǎn)站輸入頂點Tk的邊(vr,vu)(r=3,4,…,6;u=7,8,…,18)費用為p′i,j,k(i為與Hj相關(guān)聯(lián)的廠家),邊容量取ai,j;中轉(zhuǎn)站邊(vr,vu)(r=7,8,…,18;u=19,20,…,30)費用取p中j?k(j為與Tk相關(guān)聯(lián)的產(chǎn)品種類),邊容量取tk;中轉(zhuǎn)站輸出頂點T′k(為便于表述,本文也將頂點用其屬性表示)至用戶Dl的邊(vr,vu)(r=19,20,…,30;u=31,32,…,38)稱為配送邊,費用取pue087j,k,l,邊容量取tk;產(chǎn)品Hj至用戶Dl的邊(vr,vu)(r=3,…,6;u=31,32,…,38)稱為直供邊,其費用取p″i,j,l,邊容量取q直l。為滿足l用戶對i廠第j種產(chǎn)品數(shù)量的上下限要求,通常需要構(gòu)建容量有上下界約束的網(wǎng)絡模型并用相應的算法求解,其求解過程比較復雜。文獻提出了通過增加平行邊將容量有上下界約束的網(wǎng)絡流問題轉(zhuǎn)化為普通網(wǎng)絡流的方法。鑒于此,圖1中增設了用戶頂點(v39—v60)和相應的邊,以便于問題的轉(zhuǎn)化和流量匯總。各增設邊參數(shù)說明如下:邊(vr,vu)(r=31,32,…,38;u=47,48,…,54)費用取0,邊容量取oqi,j,l(i,j分別為與l用戶直接或間接相關(guān)聯(lián)的廠家和產(chǎn)品種類),該邊稱為用戶要求產(chǎn)品數(shù)量下界邊;邊(vr,vu)(r=31,32,…,38;u=39,40,…,46)與用戶要求下界邊平行,費用取1個足夠大的正數(shù)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),該邊稱為用戶要求產(chǎn)品數(shù)量上界邊;邊(vr,vu)(r=39,40,…,46;u=47,48,…,54)費用取0,邊容量取dj,l,該邊稱為用戶要求上邊界輔助邊。以上3種邊將容量有上下界約束的網(wǎng)絡流問題轉(zhuǎn)化成了普通網(wǎng)絡流問題。邊(vr,vu)(r=47,48,…,54;u=55,56,57,58)稱為廠別產(chǎn)品到貨邊,費用取0,邊容量取dj,l,該邊上的流量為l用戶實際獲取的i廠第j種產(chǎn)品的數(shù)量;邊(vr,vu)(r=55,56,57,58;u=59,60)稱為產(chǎn)品需求邊,費用取0,邊容量取dj,l,該邊上的流量為l用戶從各廠獲取第j種產(chǎn)品的總量;邊(vr,vu)(r=59,60;u=61)稱為用戶總需求邊,費用取0,邊容量取∑jdj?l,該邊上的流量為l用戶從各廠獲取各種產(chǎn)品的總量。3.1.2也較高的能力為了滿足用戶對不同廠家不同產(chǎn)品的數(shù)量要求,每個中轉(zhuǎn)站被分解成了N(N=I×J)個中轉(zhuǎn)站頂點,中轉(zhuǎn)站邊也被相應地分解成了N條邊。如圖1中,T1中轉(zhuǎn)站被分解為N=2×2=4個中轉(zhuǎn)頂點,邊被分解成了(v7,v19),…,(v16,v28)共4條邊。每條中轉(zhuǎn)站邊上的流量為與之相關(guān)聯(lián)廠家經(jīng)由該中轉(zhuǎn)站中轉(zhuǎn)的j產(chǎn)品的數(shù)量,因此,在求解過程中,應使同屬1個中轉(zhuǎn)站各邊上的流量之和不大于該中轉(zhuǎn)站的中轉(zhuǎn)能力。設fr,u為邊(vr,vu)∈E上的流量,對于T1中轉(zhuǎn)站有f7,19+f10,22+f13,25+f16,28≤t1(t1為T1中轉(zhuǎn)站的中轉(zhuǎn)能力)。可以看出,1個中轉(zhuǎn)站的各條邊上,如果其中1條邊上的流量增加或減少一定數(shù)量,其他邊的容量將隨之減少或增加同樣的數(shù)量。為防止實際中轉(zhuǎn)量大于中轉(zhuǎn)站中轉(zhuǎn)能力,必須在每次調(diào)流之后,對中轉(zhuǎn)量發(fā)生變化的中轉(zhuǎn)站各條邊的容量進行修正。令Hk={(I+N+(i-1)JK+(j-1)K+k,I+N+NK+(i-1)JK+(j-1)K+k)}(7)為k中轉(zhuǎn)站所有中轉(zhuǎn)站邊的集合,則k中轉(zhuǎn)站所有邊的流量之和為Fk=∑(vr?vu)∈Ηkfr?u(8)k中轉(zhuǎn)站各條邊的容量為cr,u=tk-Fk+fr,u(vr,vu)∈Hk(9)圖1中,每1組中轉(zhuǎn)站頂點都與1組用戶頂點相關(guān)聯(lián),每個用戶頂點也被分解成了N個頂點。如圖1中,用戶D1被分解成了v31,v33,v35,v37計4個頂點。每條直供邊上的流量為與之相關(guān)聯(lián)廠家直接向該用戶供應的第j種產(chǎn)品的數(shù)量。因此,在求解過程中,應使同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網(wǎng)絡gf優(yōu)化方法由于上文所建網(wǎng)絡模型對各種產(chǎn)品經(jīng)由中轉(zhuǎn)站的流量和廠家直接向用戶供貨的流量沒有約束力,所以不能直接采用最小費用最大流的一般算法,需要對最小費用最大流的一般算法進行改進。改進后的算法步驟如下。第1步所有邊容量按上文給出的方法取初值。第2步對網(wǎng)絡G=(V,E,c,b)給出流值為0的初始流。第3步構(gòu)造1個伴隨流f的增流網(wǎng)絡Gf。第4步尋求最小費用增流鏈,在網(wǎng)絡Gf中用標號法求源s至匯t的最短路P。若存在P,轉(zhuǎn)第5步,否則算法結(jié)束。第5步取δ′=min{c′r,u,(vr,vu)∈P}。第6步在G上增流。第7步根據(jù)計算最短路時各結(jié)點的標號值P(v),按下式修正G中邊的權(quán)數(shù)b(e)P(u)-P(v)+b(e)→b(e)第8步按式(8)修正中轉(zhuǎn)站邊容量。第9步按式(10)修正直供邊容量。第10步將新流f′視為f,轉(zhuǎn)第3步。3.2優(yōu)化算法3.2.1負回路v73e邊的容量與流量之差稱為邊的殘余容量。1條邊的殘余容量決定了該邊在當前流量水平下的增流能力。由3.1.2節(jié)的討論可知,1個中轉(zhuǎn)站的1條中轉(zhuǎn)站邊流量發(fā)生變化,同屬該中轉(zhuǎn)站的其他中轉(zhuǎn)站邊的容量就會隨之變化,邊的殘余容量也相應發(fā)生變化(直供邊也存在同樣的現(xiàn)象)。因此,按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用戶的需求量已經(jīng)得到滿足,用3.1節(jié)的算法求解結(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個中轉(zhuǎn)站的各中轉(zhuǎn)站邊容量之和為1個常數(shù),當其中部分邊的流量之和達到該中轉(zhuǎn)站的中轉(zhuǎn)能力時,同屬該中轉(zhuǎn)站的各中轉(zhuǎn)站邊殘余容量均為0。因此,即使各中轉(zhuǎn)站邊流量沒有達到最優(yōu)配置,也因搜索不到滿足要求的負回路而無法調(diào)整。直供邊也存在同樣的問題。為了進一步尋求較優(yōu)解,須設法找到潛在的負回路。為此,首先擴大中轉(zhuǎn)站邊和直供邊的容量,使殘余容量為0的中轉(zhuǎn)站邊和直供邊具備增流能力,為形成包含中轉(zhuǎn)站邊和直供邊的回路創(chuàng)造條件;為了使各中轉(zhuǎn)站中轉(zhuǎn)量不大于其中轉(zhuǎn)能力和向各用戶的直供量不大于其直供能力,可使屬于同一用戶的直供邊和屬于同一中轉(zhuǎn)站的中轉(zhuǎn)站邊在負回路中成對出現(xiàn)(1條正向邊和1條反向邊同時出現(xiàn)),這樣當其中1條邊增加流量δ′時,另1條邊同時減少流量δ′,保證到達各用戶的直供量和各中轉(zhuǎn)站的中轉(zhuǎn)量不因其邊容量的擴大而增大。為了使負回路符合上述要求,需切斷部分直供邊和配送邊,從而將負回路搜索限制在直供邊間、中轉(zhuǎn)站邊間、直供邊—中轉(zhuǎn)站邊間、直供邊—所有中轉(zhuǎn)站邊間計4種范圍之內(nèi)。同時由圖1可以看出,當負回路包含虛設的匯點vt時,不能保證同一用戶的直供邊和同一中轉(zhuǎn)站的中轉(zhuǎn)站邊成對出現(xiàn)。如圖1中,若存在負回路v3-v7-v19-v31-v39-v47-v55-v59-v61-v60-v56-v48-v40-v32-v21-v9-v3,在該回路上調(diào)流后,就會導致T1中轉(zhuǎn)站的中轉(zhuǎn)量大于其中轉(zhuǎn)能力。由3.1節(jié)給出的邊容量取值方法可知,在用戶需求量不大于供貨量且不大于中轉(zhuǎn)能力與直供能力之和時,所有的產(chǎn)品需求邊和用戶總需求邊因其殘余容量為0而處于斷開狀態(tài)。當用戶需求量大于供貨量且大于中轉(zhuǎn)能力與直供能力之和時,就有可能出現(xiàn)包含匯點vt的負回路。因此,不論出現(xiàn)上述哪種情況,切斷所有用戶總需求邊,去除虛設的匯點vt,以保證在負回路上調(diào)流后,各中轉(zhuǎn)站的中轉(zhuǎn)量和到達各用戶的直供量滿足其能力約束。3.2.2.配送邊搜索方案消圈優(yōu)化根據(jù)上文分析,切斷所有用戶總需求邊,令所有直供邊的邊容量為其所屬用戶的可直供能力,令所有中轉(zhuǎn)站邊的邊容量為其所屬中轉(zhuǎn)站的中轉(zhuǎn)能力,按以下搜索過程對潛在的負回路進行消圈優(yōu)化。(1)在直供邊間搜索。切斷所有配送邊,用消圈法進行優(yōu)化。由圖1可以看出,切斷所有配送邊后,如果存在負回路,則屬于同一用戶的直供邊將會成對出現(xiàn)在負回路中,調(diào)流后,雖然相關(guān)邊的流量發(fā)生了變化,但到達同一用戶總的直供運量保持不變。(2)在中轉(zhuǎn)站邊間搜索。切斷所有直供邊和配送邊。取1個中轉(zhuǎn)站k和1個用戶l,連接所有的邊(T′k,Dl);再取1個中轉(zhuǎn)站ck(ck≠k),除Dl外,連接所有的邊(T′ck,Dcl)(cl=1,2,…,L,cl≠l),用消圈法進行優(yōu)化。經(jīng)上述切邊后的網(wǎng)絡稱為1個中轉(zhuǎn)站邊搜索方案(按搜索范圍命名,下同)。改變ck,l,k的值,重復上述過程,直到對所有的中轉(zhuǎn)站邊搜索方案進行了消圈優(yōu)化。上述配送邊的選取方法使得每次只有2個中轉(zhuǎn)站的所有中轉(zhuǎn)站邊出現(xiàn)在同一回路中。屬于同一中轉(zhuǎn)站的中轉(zhuǎn)邊成對出現(xiàn)。消圈后各中轉(zhuǎn)站的中轉(zhuǎn)量保持不變。(3)在直供邊—中轉(zhuǎn)站邊間搜索。切斷所有直供邊和配送邊,取1個用戶l,連接以Dl為終點的直供邊;取1個中轉(zhuǎn)站k,除Dl外,連接所有的邊(T′k,Dcl)(cl=1,2,…,L,cl≠l),用消圈法進行優(yōu)化。改變l和k的值,重復上述過程,直到對所有的直供邊—中轉(zhuǎn)站邊搜索方案進行了消圈優(yōu)化。上述直供邊和配送邊的選取方法使得每次只有1個用戶的直供邊和1個中轉(zhuǎn)站的中轉(zhuǎn)站邊同時出現(xiàn)在同一回路中。同屬1個用戶的直供邊和同屬同一中轉(zhuǎn)站的中轉(zhuǎn)站邊分別成對出現(xiàn)。消圈后其直供量和中轉(zhuǎn)量均保持不變。(4)在直供邊—所有中轉(zhuǎn)站邊間搜索。所有中轉(zhuǎn)站邊的容量按式(8)取值。切斷所有直供邊,連接所有的配送邊。任取1個可直供用戶l,連接以Dl為終點的直供邊;切斷所有指向該用戶的配送邊,用消圈法進行優(yōu)化。如圖1中,任取1個可直供用戶1,連接以D1為終點的直供邊(v3,v31),(v4,v33),(v5,v35),(v6,v37),切斷與D1相關(guān)聯(lián)的所有配送邊(v19,v31),(v20,v31),(v21,v31),…,(v28,v37),(v29,v37),(v30,v37),再用消圈法進行優(yōu)化。改變l的值,重復調(diào)用上述4個搜索過程,直到對所有的直供邊—中轉(zhuǎn)站邊搜索方案進行了消圈優(yōu)化。上述直供邊和配送邊的選取方法使得每次只有1個用戶的直供邊成對出現(xiàn)在回路中,所有的中轉(zhuǎn)站邊則都有可能出現(xiàn)在回路中,但由于中轉(zhuǎn)站邊容量均取正常值,消圈后,直供量不發(fā)生變化,而相關(guān)中轉(zhuǎn)