基于網(wǎng)絡(luò)流技術(shù)的雙向編組站調(diào)度優(yōu)化問題研究

基于網(wǎng)絡(luò)流技術(shù)的雙向編組站調(diào)度優(yōu)化問題研究

雙向列車站系統(tǒng)的工作分工方案規(guī)定了連接系統(tǒng)和出發(fā)徑向列車的出發(fā)系統(tǒng)。然而，由于鐵路運(yùn)輸工人的特殊性，在下一種情況下，需要調(diào)整出發(fā)站的操作地點(diǎn)。(1)由于列車到發(fā)不均衡,導(dǎo)致一段時間雙向編組站各系統(tǒng)的作業(yè)負(fù)荷差異較大,即一個系統(tǒng)能力緊張,而另一個系統(tǒng)相對空閑,此時需要對到達(dá)列車的接入地點(diǎn)和出發(fā)列車的編組地點(diǎn)進(jìn)行調(diào)整。(2)由于車流結(jié)構(gòu)的動態(tài)隨機(jī)性,對于輸送同一支到達(dá)車流的列車,其編組內(nèi)容也會有較大的差異,將這些列車全部接入同一個系統(tǒng),可能會對接續(xù)出發(fā)列車不利,或產(chǎn)生過多的折角車流,有必要對這些到達(dá)列車的接入地點(diǎn)進(jìn)行調(diào)整。(3)當(dāng)某些出發(fā)車流可以在2個系統(tǒng)同時集結(jié)時,以這些車流組號為編組內(nèi)容的出發(fā)列車有必要選擇最有利的編組地點(diǎn)。(4)當(dāng)某些出發(fā)列車的集結(jié)過程接近結(jié)束時,需要將接續(xù)這些出發(fā)列車的個別到達(dá)列車改變接入地點(diǎn),以及時實(shí)現(xiàn)列車編組的滿重或滿軸要求。故此,雙向編組站除了每個系統(tǒng)各自配備1名站調(diào)負(fù)責(zé)本系統(tǒng)的作業(yè)組織外,還專門配備1名總站調(diào)協(xié)調(diào)2個系統(tǒng)之間的工作,實(shí)時調(diào)度到達(dá)列車的接入系統(tǒng)和出發(fā)列車的編組系統(tǒng),協(xié)調(diào)的質(zhì)量主要依賴于總站調(diào)的經(jīng)驗(yàn)和對系統(tǒng)的了解程度。由于系統(tǒng)的復(fù)雜性和個人能力的局限性,總站調(diào)無法憑個人能力做出非常科學(xué)的調(diào)度決策。文獻(xiàn)運(yùn)用矩陣方法檢查接續(xù)組號、接續(xù)時間和交換車數(shù),實(shí)時確定到達(dá)列車的接入系統(tǒng),但前提是出發(fā)列車的編組系統(tǒng)固定不變,這一假定不符合實(shí)際,因?yàn)樵诂F(xiàn)實(shí)作業(yè)組織中,恰好存在著出發(fā)列車可以在2個系統(tǒng)編組出發(fā)的情況?；诖?本文對雙向編組站到發(fā)列車的調(diào)度調(diào)整問題做深入研究。1虛擬出發(fā)列車隨到達(dá)列車進(jìn)入編組站解體的車輛,要經(jīng)過一段時間的技術(shù)作業(yè)后方能接續(xù)出發(fā)列車,那些在計(jì)劃末期到達(dá)車站的列車實(shí)際上用來接續(xù)下一個調(diào)度時段的出發(fā)列車,而與本時段的出發(fā)列車無直接的車流接續(xù)關(guān)系。對于這些到達(dá)列車,盡管可以通過走行距離、能力負(fù)荷等來判斷列車的接入系統(tǒng),但這樣做會影響下一時段出發(fā)列車的編組,因?yàn)檐嚵鹘永m(xù)合理應(yīng)該是判斷列車接入系統(tǒng)的首要條件。為此,本研究將出發(fā)列車的離開時段向后平移一段時間,以保證到發(fā)列車之間能夠發(fā)生有效的車流接續(xù)關(guān)系。移動幅度一般取為雙向編組站列車的平均接續(xù)時間,由于調(diào)度時段的不斷向前滾動,可以基本消除移動幅度的偏差對模型求解結(jié)果的影響。另外,在計(jì)劃開始時刻,車站2個系統(tǒng)的編組場留有上一時段沒有用完的殘存車,本文將它們視為虛擬到達(dá)列車,其到達(dá)時刻為本時段的開始時刻;在計(jì)劃結(jié)束時刻,2個系統(tǒng)的編組場留有該時段沒有用完的殘存車,將它視為虛擬出發(fā)列車。顯然,當(dāng)前時段的虛擬出發(fā)列車即為下一時段的虛擬到達(dá)列車。定義符號和參數(shù)如下:[T1,T2]表示列車到達(dá)時段;[T1⊕T0,T2⊕T0]表示列車離開時段,其中T0表示離開時段向后平移的幅度,⊕表示以24為模(mod24)的加法運(yùn)算符;k是雙向編組站上、下行系統(tǒng)的標(biāo)志,k=0表示上行系統(tǒng),k=1表示下行系統(tǒng);B為雙向編組站集結(jié)車流組號的集合;Q為時段[T1,T2]內(nèi)到達(dá)編組站的列車集合,其中包括小運(yùn)轉(zhuǎn)列車;ˉQ為虛擬到達(dá)列車的集合,ˉQ={q0?q1},其中qk表示T1時刻k系統(tǒng)從上時段遺留下來的存車;R為時段[T1⊕T0,T2⊕T0]內(nèi)從編組站出發(fā)的列車集合;ˉR為虛擬出發(fā)列車的集合,ˉR={r0?r1},其中rk表示T2⊕T0時刻k系統(tǒng)沒有用完的殘存車;Mj,mj表示出發(fā)列車j(j∈R)編成輛數(shù)的上、下界;Dki表示到達(dá)列車i(i∈Q)進(jìn)入k系統(tǒng)到達(dá)場的時刻;Fkj表示出發(fā)列車j在k系統(tǒng)出發(fā)場的離開時刻;Jk表示k系統(tǒng)列車的接續(xù)時間標(biāo)準(zhǔn),指該系統(tǒng)到達(dá)技術(shù)作業(yè)時間、解體時間、編組時間、出發(fā)技術(shù)作業(yè)時間及必要的等待作業(yè)時間之和;ˉJk表示k′(k′=0,1;k+k′=1)系統(tǒng)的到達(dá)列車接續(xù)k系統(tǒng)出發(fā)列車的時間標(biāo)準(zhǔn),ˉJk除了包含Jk的作業(yè)時間外,還包括轉(zhuǎn)場交換作業(yè)需要的時間;Hib為到達(dá)列車i(i∈Q∪ˉQ)中含車流組號b(b∈B)的車數(shù)。定義邏輯常數(shù)如下:λkb表示已知的編組站作業(yè)分工方案,若車流組號b在系統(tǒng)k集結(jié)則取值為1,否則為0,滿足∑k∈{0?1}λkb≥1;ηjb表示出發(fā)列車的編組要求,若出發(fā)列車j含車流組號b,則取值為1,否則為0;Jkij表示同一系統(tǒng)的到發(fā)列車是否滿足接續(xù)時間要求,若Fkj-Dki≥Jk,則取值為1,否則為0,(i∈Q∪ˉQ?j∈R∪ˉR);ˉJkij表示不同系統(tǒng)的到發(fā)列車是否滿足接續(xù)時間要求,若Fkj-Dk′i≥ˉJk,則取值為1,否則為0。定義決策變量如下:Xki為0-1變量,如果到達(dá)列車i接入k系統(tǒng),則取值為1,否則為0;Ykj為0-1變量,如果出發(fā)列車j在k系統(tǒng)編組出發(fā),則取值為1,否則為0;Ubij為整數(shù)變量,表示到達(dá)列車i(i∈Q∪ˉQ)中b車流組號接續(xù)出發(fā)列車j(j∈R∪)的車數(shù)。在變量Ubij的定義中,如果i∈ˉQ,則Ubij表示虛擬到達(dá)列車的相應(yīng)組號接續(xù)出發(fā)列車j(j∈R∪ˉR)的車數(shù);如果j∈ˉR,則Ubij表示到達(dá)列車i(i∈Q∪ˉQ)中的相應(yīng)組號殘存到下一時段的車數(shù)。2數(shù)學(xué)模型2.1合同規(guī)定2.1.1列車交叉口平衡條件∑k∈{0?1}Xki=1i∈Q(1)∑k∈{0?1}Ykj=1j∈R(2)∑j∈R∪ˉRUbij=Ηibb∈B?i∈Q∪ˉQ(3)式(1)表示到達(dá)列車i只能接入1個系統(tǒng),式(2)表示出發(fā)列車j只能在1個系統(tǒng)編組出發(fā),式(3)表示到達(dá)列車所滿足的車流平衡條件。2.1.2組成車輛數(shù)限制mj≤∑i∈Q∪ˉQ∑b∈BUbij≤Μjj∈R(4)2.1.3正數(shù)為相當(dāng)大的正數(shù)∑i∈Q∪QˉUijb≤Μηjbb∈B?j∈R(5)其中,M為相當(dāng)大的正數(shù)。式(5)表示當(dāng)ηjb=0,即出發(fā)列車j不包含車流組號b時,其相應(yīng)的變量應(yīng)滿足:Uijb=0(i∈Q∪Qˉ)。2.1.4xki型∑b∈BUijb≤Μ{Jijk[1-δ(Xik-Yjk)]+Jˉijkδ(Xik-Yjk)}i∈Q∪Qˉ(6)其中,M為相當(dāng)大的正數(shù);δ(x)為符號函數(shù),定義為δ(x)={1(如果x≠0)0(否則)對于本問題,δ(x)可取為δ(Xik-Yjk)=Xik+Yjk-2XkiYjk。當(dāng)Xik=Yjk=1,即到達(dá)列車i和出發(fā)列車j在同一系統(tǒng)k時,δ(Xik-Yjk)=0,此時式(6)變?yōu)椤芺∈BUijb≤ΜJijk。這表明當(dāng)Jijk=0,即在同一系統(tǒng)k中的到達(dá)列車i和出發(fā)列車j之間的接續(xù)時間不夠時,其相應(yīng)的變量Uijb應(yīng)等于0。當(dāng)Xik≠Yjk,即到達(dá)列車i和出發(fā)列車j不在同一系統(tǒng)k時,δ(Xki-Yjk)=1,此時式(6)變?yōu)椤芺∈BUijb≤ΜJˉijk。這表明當(dāng)Jˉijk=0,即不在同一系統(tǒng)k中的到達(dá)列車i和出發(fā)列車j之間的接續(xù)時間不夠時,其相應(yīng)的變量Uijb應(yīng)等于0。2.1.5bbk+2Yjk≥1-Μ∑b∈Bηjb{λb1-k+(1-λbk)}j∈R;k=0,1(7)其中,若∑b∈Bηjb{λb1-k+(1-λbk)}=0,于是對任意的車流組號b,如果ηjb=1,則必有λb1-k+(1-λbk)=0;也就是說,當(dāng)出發(fā)列車j包含車流組號b時,該車流組號必須滿足λb1-k+(1-λbk)=0。故有λbk=1,λb1-k=0。這表明車流組號b僅在1個系統(tǒng)k集結(jié),再由式(7)可知,此時必有Yjk=1。綜上所述,式(7)表示如果某個出發(fā)列車所包含的車流組號都在同一系統(tǒng)集結(jié)時,則該出發(fā)列車的編組也只能在該系統(tǒng)中進(jìn)行。2.1.6車數(shù)計(jì)作業(yè)能力情感值的計(jì)算∑i∈QXik≤CD(k)(8)∑i∈Q∪Qˉ∑b∈BXikΗib+∑i∈Q∪Qˉ∑b∈B∑j∈R∪RˉUijbYjk(1-Xik)≤CJ(k)(9)∑k∈{0?1}∑i∈Q∪Qˉ∑b∈B∑j∈R∪RˉUijbYjk(1-Xik)≤CΗ(10)∑j∈RYjk≤CF(k)(11)其中CD(k),CF(k)表示k系統(tǒng)在調(diào)度時段內(nèi)以列數(shù)計(jì)的到達(dá)及出發(fā)作業(yè)能力,CJ(k)為k系統(tǒng)在調(diào)度時段內(nèi)以車數(shù)計(jì)的解體作業(yè)能力,CH為在調(diào)度時段內(nèi)以車數(shù)計(jì)的交換作業(yè)能力;式(8)表示到達(dá)能力約束,式(9)表示解體能力約束,式(10)表示交換能力約束,式(11)表示出發(fā)能力約束。2.2流接續(xù)費(fèi)用edim到發(fā)列車在雙向編組站選擇不同的接入系統(tǒng)和出發(fā)系統(tǒng)會導(dǎo)致走行距離、交換車數(shù)各異,綜合優(yōu)化目標(biāo)應(yīng)是在現(xiàn)有能力支持系統(tǒng)下,滿足車流接續(xù)要求,使其在雙向編組站消耗的總費(fèi)用最小,即minΖ=∑k∈{0?1}{∑i∈QXikEDik+∑j∈RYjkEFjk+∑i∈Q∪Qˉ∑j∈R∪Rˉ∑b∈BUijbYjk(1-Xik)EJ}(12)式中:EDik為到達(dá)列車i進(jìn)入k系統(tǒng)所花費(fèi)的費(fèi)用,元/列車;EFjk為出發(fā)列車j從k系統(tǒng)編組出發(fā)所花費(fèi)的費(fèi)用,元/列車;EJ為折角車比一般有調(diào)中轉(zhuǎn)車多花費(fèi)的費(fèi)用,元/車。3列車頂出設(shè)備的推動上文構(gòu)造的雙向編組站列車調(diào)度調(diào)整模型有以下特點(diǎn):①混合性——模型中既有0-1變量,也有整數(shù)變量;②非線性性——約束條件和優(yōu)化目標(biāo)中都出現(xiàn)了非線性函數(shù);③相關(guān)性——模型中的0-1變量和整數(shù)變量密切相關(guān),約束條件中的編組內(nèi)容、編成輛數(shù)、接續(xù)時間和集結(jié)地點(diǎn)等約束都從不同側(cè)面反映了這種關(guān)聯(lián)關(guān)系。特點(diǎn)①與②決定了普通的求解算法難于得到模型的解,為此可利用搜索能力很高的遺傳算法求解模型;而特點(diǎn)③注定了常規(guī)遺傳算法的求解效率也非常有限,因?yàn)樽兞康母叨认嚓P(guān)性表明,要找到1個滿足所有約束條件的可行解,也是件非常困難的事情。為此,本文采用1種特殊設(shè)計(jì)的遺傳算法,主要思想是在假定0-1變量Xik和Yjk已經(jīng)確定的條件下,將整數(shù)變量Uijb的確定歸結(jié)為求解1個網(wǎng)絡(luò)最小費(fèi)用流問題,構(gòu)造時空網(wǎng)絡(luò)如圖1所示。將圖1中網(wǎng)絡(luò)表示為(V,t(v);A,c(a),M(a),m(a);v∈V,a∈A)。其中V是頂點(diǎn)的集合;A是弧的集合;t(v)是頂點(diǎn)權(quán)重,表示頂點(diǎn)v所處的時刻;c(a),M(a),m(a)是弧權(quán)重,分別表示弧a的單位費(fèi)用、流量上界和流量下界。頂點(diǎn)集合V包括:頂點(diǎn)Ii對應(yīng)到達(dá)列車(包括虛擬到達(dá)列車)i(i=1,2,…,N);頂點(diǎn)權(quán)重t(Ii)為列車i進(jìn)入相應(yīng)系統(tǒng)的時刻,即t(Ιi)=∑k∈{0?1}XikDik;頂點(diǎn)Bib對應(yīng)到達(dá)列車i所含的車流組號b(b=1,2,…,si);頂點(diǎn)權(quán)重t(Bib)與Ii的頂點(diǎn)權(quán)重t(Ii)相同;頂點(diǎn)Jj(j=1,2,…,M)對應(yīng)出發(fā)列車j;頂點(diǎn)權(quán)重t(Jj)為列車j離開相應(yīng)系統(tǒng)的時刻,即t(Jj)=∑k∈{0?1}YjkFjk;頂點(diǎn)J0和J1對應(yīng)虛擬出發(fā)列車r0和r1,頂點(diǎn)權(quán)重為出發(fā)時段的結(jié)束時刻,即t(J0)=t(J1)=T2⊕T0;頂點(diǎn)L為虛擬頂點(diǎn),表示列車離開編組站?；〖螦包括:如果到達(dá)列車i包含si個車流組號b(b=1,2,…,si),則在頂點(diǎn)Ii和頂點(diǎn)Bib之間連si條弧(Ii,Bib),費(fèi)用權(quán)重c(Ii,Bib)=t(Bib)-t(Ii)=0,上界權(quán)重M(Ii,Bib)=Hib,下界權(quán)重為零;如果出發(fā)列車j可將到達(dá)列車i中的車流組號b納入其接續(xù)車流,即滿足編組內(nèi)容約束ηjb=1和接續(xù)時間約束Jijk=1或Jˉijk=1時,則在頂點(diǎn)Bib和Jj之間連1條弧(Bib,Jj),費(fèi)用權(quán)重為終點(diǎn)權(quán)重與起點(diǎn)權(quán)重的差,即c(Bib,Jj)=t(Jj)-t(Bib),下界權(quán)重為零,上界權(quán)重為相應(yīng)車流組號所含的車數(shù),即M(Bib,Jj)=Hib;如果到達(dá)列車i接入k系統(tǒng),則在頂點(diǎn)Bib與虛擬出發(fā)頂點(diǎn)Jk之間連si條弧(Bib,Jk);費(fèi)用權(quán)重為終點(diǎn)權(quán)重與起點(diǎn)權(quán)重的差,即c(Bib,Jk)=t(Jk)-t(Bib),上界權(quán)重為無窮大,下界權(quán)重為零;任意出發(fā)頂點(diǎn)Jj與虛擬頂點(diǎn)L之間連1條弧(Jj,F),費(fèi)用權(quán)重為c(Jj,F)=0,上界權(quán)重為相應(yīng)出發(fā)列車編成輛數(shù)的上界,即M(Jj,F)=Mj,下界權(quán)重為列車編成輛數(shù)的下界,即m(Jj,F)=mj;虛擬出發(fā)頂點(diǎn)J0和J1與虛擬頂點(diǎn)L之間分別連1條弧(J0,F)和(J1,F),費(fèi)用權(quán)重為零,上界權(quán)重為無窮大,下界權(quán)重為零。利用以上時空網(wǎng)絡(luò),設(shè)計(jì)1種基于問題特點(diǎn)的混合遺傳算法如下:(1)用0-1變量Xi0和Yj0作為二進(jìn)制編碼的字節(jié),全體字節(jié)按一定順序構(gòu)成種群中的染色體,非獨(dú)立變量Xi1和Yj1由約束條件(1),(2)求得;(2)在已知Xik和Yjk的條件下,按上文方法構(gòu)造時空網(wǎng)絡(luò),并求解最小費(fèi)用網(wǎng)路流,將(Bib,Jj)上的流量f(Bib,Jj)作為整數(shù)變量Uijb(i∈Q∪Qˉ?j∈R)的取值,這樣構(gòu)造的變量集合自然滿足式(3)—式(7);(3)將式(8)—式(11)按照罰函數(shù)法構(gòu)造新的目標(biāo)函數(shù),原模型轉(zhuǎn)化成1個無約束的最優(yōu)化問題;(4)按照文獻(xiàn)的方法計(jì)算適應(yīng)度,并在遺傳迭代過程中,對選擇算子進(jìn)行模擬退火拉伸,對交叉、變異算子進(jìn)行動態(tài)變化。4接收點(diǎn)計(jì)劃方案以鄭州北站為例,利用上述模型和算法確定到發(fā)列車調(diào)度調(diào)整計(jì)劃。到達(dá)(出發(fā))列車進(jìn)入編組站2個到達(dá)場(或從2個出發(fā)場離開)的走行距離見文獻(xiàn)。此外,列車走行公里費(fèi)用及其他相關(guān)參數(shù)取為:大運(yùn)轉(zhuǎn)列車4.55元/列公里,小運(yùn)轉(zhuǎn)列車2.95元/列公里;轉(zhuǎn)場交換車費(fèi)用0.78元/車;以4h作為計(jì)劃期間的時間長度,出發(fā)列車時間段向后平移的幅度為2h,上、下行系統(tǒng)車流接續(xù)時間分別為110,120min,交換作業(yè)時間為40min;計(jì)劃期間內(nèi)上行系統(tǒng)的到達(dá)和出發(fā)能力都是17列,下行系統(tǒng)的到達(dá)和出發(fā)能力分別為18和16列,交換作業(yè)能力為600車。車流組號及編組作業(yè)地點(diǎn)見表1;計(jì)劃開始時上、下行系統(tǒng)的編組場內(nèi)殘存各組號的車流量見表2;計(jì)劃期間7:00—11:00到達(dá)編組站的列