鐵路客運(yùn)過站徑路優(yōu)化模型研究

鐵路客運(yùn)過站徑路優(yōu)化模型研究

列車經(jīng)過的路線是鐵路的入口業(yè)務(wù)，列車占用的路線是出發(fā)業(yè)務(wù)的起點(diǎn)。列車通過的路徑優(yōu)化是連接客運(yùn)和貨運(yùn)的綜合優(yōu)化問題。旅客列車過站徑路優(yōu)化克服了接車進(jìn)路排列、到發(fā)線運(yùn)用、發(fā)車進(jìn)路排列等3個(gè)單項(xiàng)優(yōu)化的不足,突出了優(yōu)化方案的整體性。文獻(xiàn)對(duì)旅客列車過站進(jìn)路優(yōu)化進(jìn)行了研究。文獻(xiàn)將旅客列車過站徑路選擇劃分為接車作業(yè)進(jìn)路、占用到發(fā)線和發(fā)車作業(yè)進(jìn)路的分項(xiàng)選擇,對(duì)任意2列列車的各種接發(fā)車作業(yè)進(jìn)路和到發(fā)線選擇進(jìn)行相容性約束,以接發(fā)車作業(yè)進(jìn)路和到發(fā)線運(yùn)用效用最大為優(yōu)化目標(biāo),建立旅客列車過站徑路優(yōu)化的0-1規(guī)劃模型,求解時(shí)首先將問題轉(zhuǎn)化為最大權(quán)和獨(dú)立集,并設(shè)法剔除一些變量以縮小問題規(guī)模,然后利用分枝切割法進(jìn)行求解。文獻(xiàn)注意到旅客列車接發(fā)車作業(yè)進(jìn)路唯一確定旅客列車占用的到發(fā)線,以接發(fā)車作業(yè)進(jìn)路為決策,到發(fā)線和道岔占用相容性為約束,建立到發(fā)線運(yùn)用和一端咽喉接發(fā)車作業(yè)進(jìn)路綜合優(yōu)化的0-1規(guī)劃模型,針對(duì)該問題的特征,提出極大列車進(jìn)路方案及其剔除鄰域系概念,依此設(shè)計(jì)模擬退火算法。相比之下,文獻(xiàn)中模型的決策變量數(shù)明顯少于文獻(xiàn),其模擬退火算法比文獻(xiàn)的分枝定界法具有更強(qiáng)的求解能力。在文獻(xiàn)綜合優(yōu)化一端咽喉接發(fā)車作業(yè)進(jìn)路排列與到發(fā)線運(yùn)用的基礎(chǔ)上,本文進(jìn)一步綜合優(yōu)化全站的接發(fā)車作業(yè)進(jìn)路排列與到發(fā)線運(yùn)用問題,即旅客列車過站徑路優(yōu)化問題。在給定鐵路客運(yùn)站站形布局和列車運(yùn)行圖的前提下,以旅客列車接發(fā)車作業(yè)進(jìn)路為決策,以道岔和到發(fā)線占用相容性為約束,在盡可能多地為相對(duì)重要的旅客列車安排過站徑路的條件下,以旅客列車過站徑路方案的接發(fā)車作業(yè)進(jìn)路和到發(fā)線運(yùn)用效用最大為優(yōu)化目標(biāo),建立旅客列車過站徑路優(yōu)化的0-1規(guī)劃模型,并設(shè)計(jì)了基于極大列車過站徑路方案剔除鄰域系的模擬退火算法,求解旅客列車過站徑路優(yōu)化問題。1道岔占用及過站徑路由于旅客列車過站徑路優(yōu)化問題是接發(fā)車作業(yè)進(jìn)路排列和到發(fā)線運(yùn)用的綜合優(yōu)化問題,而接發(fā)車作業(yè)進(jìn)路唯一確定旅客列車占用的到發(fā)線,所以只需要確定旅客列車的接發(fā)車作業(yè)進(jìn)路,便可確定旅客列車過站徑路。所有旅客列車過站徑路必須彼此相容。這種相容性體現(xiàn)為2個(gè)方面:首先是道岔占用相容性,即同一道岔在同一時(shí)刻最多只能被1項(xiàng)作業(yè)占用;其次是到發(fā)線占用相容性,即同一條到發(fā)線在同一時(shí)刻最多只能被1列列車占用。描述道岔占用相容性時(shí),需要確定作業(yè)占用的道岔及占用時(shí)間。作業(yè)占用的道岔由作業(yè)所選進(jìn)路決定,而作業(yè)占用道岔時(shí)間則需要根據(jù)列車起始位置、運(yùn)行速度、列車長(zhǎng)度、作業(yè)起始時(shí)刻、進(jìn)路解鎖方式、道岔所處軌道電路區(qū)段位置等來綜合確定,具體計(jì)算方法參見文獻(xiàn)。描述到發(fā)線占用相容性時(shí),需要確定列車占用的到發(fā)線及占用時(shí)間。列車占用的到發(fā)線由接發(fā)車作業(yè)進(jìn)路決定,而列車占用到發(fā)線的時(shí)間由列車運(yùn)行圖確定。在滿足道岔和到發(fā)線占用相容性的基礎(chǔ)上,確定旅客列車過站徑路時(shí),應(yīng)盡量排列長(zhǎng)度短、道岔少的接發(fā)車作業(yè)進(jìn)路,所占用的到發(fā)線應(yīng)符合到發(fā)線的使用要求,方便旅客乘降。值得注意的是,旅客列車過站徑路方案與列車運(yùn)行圖是配套的。當(dāng)調(diào)整列車運(yùn)行圖時(shí),相應(yīng)地也要調(diào)整旅客列車過站方案,如果列車到達(dá)強(qiáng)度超過車站接發(fā)車能力,無法為全部列車排列過站徑路,則應(yīng)盡可能多地為相對(duì)重要的列車安排過站徑路,以減少運(yùn)行圖的調(diào)整工作量。綜上所述,旅客列車過站徑路優(yōu)化問題是在滿足道岔和到發(fā)線占用相容性的基礎(chǔ)上,盡可能多地為相對(duì)重要的列車排列長(zhǎng)度短、道岔少的接發(fā)車作業(yè)進(jìn)路,所占用的到發(fā)線符合到發(fā)線的使用要求、方便旅客乘降。2列車占用到發(fā)線方案的確定記列車集為I,到發(fā)線集為W,列車i(i∈I)的進(jìn)站端為o(i),出站端為d(i),o(i)與到發(fā)線w(w∈W)之間的第k條進(jìn)路為Rko(i)wko(i)w,k=1,2,…,n(o(i),w),到發(fā)線w與d(i)之間的第k條進(jìn)路為Rkd(i)w,k=1,2,…,n(w,d(i))。記列車i的接車作業(yè)為i(0),發(fā)車作業(yè)為i(1);對(duì)于b=0,1,記作業(yè)i(b)所在咽喉區(qū)的道岔集為V(i(b))。對(duì)于列車i,在辦理接車作業(yè)i(0)時(shí),必須選擇進(jìn)站端i(i)至某條發(fā)線之間的1條進(jìn)路,即對(duì)于i∈I,有∑w∈Wn(o(i)?w)∑k=1xki(0)w=1(1)∑w∈W∑k=1n(o(i)?w)xki(0)w=1(1)式中:xki(0)w為0-1變量,若作業(yè)i(0)選擇進(jìn)路Rko(i)w,則其值為1,否則為0。相應(yīng)地,在辦理發(fā)車作業(yè)i(1)時(shí),必須選擇某條到發(fā)線至出站端d(i)之間的1條進(jìn)路,即對(duì)于i∈I,有式中:xki(1)w為0-1變量,若作業(yè)i(1)選擇進(jìn)路Rkd(i)w,則其值為1,否則為0。作業(yè)i(0)與i(1)選擇的進(jìn)路唯一確定列車i占用的到發(fā)線。引入0-1變量ziw,若列車i占用到發(fā)線w,則其值為1,否則為0,則對(duì)于i∈I,w∈W,有列車占用到發(fā)線時(shí)必須滿足到發(fā)線占用相容性約束,即同一條到發(fā)線在同一時(shí)刻最多只能被1列列車占用,因此需要在列車、到發(fā)線、時(shí)間3維空間進(jìn)行約束。注意到只有列車進(jìn)入到發(fā)線的時(shí)刻才可能破壞相容性,所以只需要在列車進(jìn)入到發(fā)線的時(shí)刻檢查到發(fā)線占用相容性約束,將約束限制在列車和到發(fā)線2維空間范圍內(nèi)。記列車i占用到發(fā)線的時(shí)間為[ti,t′i],對(duì)于i∈I,w∈W,則到發(fā)線占用相容性約束可表示為排列接發(fā)車作業(yè)進(jìn)路時(shí)必須滿足道岔占用相容性約束,即同一道岔在同一時(shí)刻最多只能被1項(xiàng)作業(yè)占用。對(duì)于列車i,記其作業(yè)i(b)占用道岔v的時(shí)間為[ti(b)v,t′i(b)v],與到發(fā)線占用相容性約束類似,對(duì)于i∈I,v∈V(i(b)),進(jìn)路相容性約束可表示為式中:yi(b)v為0-1變量,若作業(yè)i(b)占用道岔v,則其值為1,否則為0。yi(b)v的取值由作業(yè)i(b)選擇的進(jìn)路決定,對(duì)于i∈I,v∈V(i(0)),有相應(yīng)地,對(duì)于i∈I,v∈V(i(1)),有yi(1)v=∑k?w∶v∈Rkd(i)wxki(1)w(7)在滿足到發(fā)線占用相容性約束的條件下,列車占用到發(fā)線應(yīng)盡量符合到發(fā)線固定使用方案,并且乘降人數(shù)較多的列車應(yīng)盡量?？吭卩徑囌境鋈肟诘牡桨l(fā)線上,以方便旅客乘降。記列車i占用到發(fā)線w的效用為ciw,若列車i滿足到發(fā)線w的使用要求,則ciw>0,否則,ciw=0。在滿足符合到發(fā)線使用要求的基礎(chǔ)上:到發(fā)線w越靠近出入口ciw的值越大;列車i的乘降人數(shù)越多ciw的值越大;列車i占用到發(fā)線w越符合到發(fā)線固定使用方案ciw的值越大。將到發(fā)線運(yùn)用效用最大作為第1優(yōu)化目標(biāo),即maxE=∑i∈Ι∑w∈Wciwziw(8)在滿足道岔占用相容性約束的條件下,接發(fā)車作業(yè)應(yīng)盡量選擇長(zhǎng)度短、道岔少的進(jìn)路,以提高作業(yè)效率。對(duì)于列車i,記進(jìn)站端o(i)至到發(fā)線w的第k條進(jìn)路的效用為cko(i)w,到發(fā)線w至出站端d(i)的第k條進(jìn)路的效用為ckd(i)w,進(jìn)路長(zhǎng)度越短、經(jīng)過道岔越少則效用越大,反之效用越小。將接發(fā)車作業(yè)進(jìn)路效用最大作為第2優(yōu)化目標(biāo),即將上述目標(biāo)函數(shù)式(8)和式(9)歸一化,得到新的目標(biāo)函數(shù)其中0≤α1,α2≤1,α1+α2=1。由此可得旅客列車過站徑路優(yōu)化的0-1規(guī)劃模型M1:式(10);式(1)—式(7)。值得注意的是,模型M1并不一定總是有解的,當(dāng)某一時(shí)段列車密集到達(dá)強(qiáng)度超過車站能力時(shí),車站無法為所有列車安排過站徑路,只能盡可能多地為相對(duì)重要的列車安排過站徑路。為此,對(duì)于i∈I,松弛約束條件式(1)和式(2)如下∑w∈Wn(o(i)?w)∑k=1xki(0)w≤1(11)∑w∈Wn(w?d(i))∑k=1xki(1)w≤1(12)引入列車i的等級(jí)權(quán)重ei(列車i的等級(jí)越高,ei越大),足夠大的罰因子β和γ,將目標(biāo)函數(shù)式(10)擴(kuò)展如下maxΗ=∑i∈Ι∑w∈W[α1ciwziw+α2(n(o(i)?w)∑k=1cko(i)wxki(0)w+n(w?d(i))∑k=1ckd(i)wxki(1)w)]-∑i∈Ιei[β(1-∑w∈Wn(o(i)?w)∑k=1xki(0)w)+γ(1-∑w∈Wn(o(i)?w)∑k=1xki(0)w)](13)由此可將模型式M1擴(kuò)展成為模型M2:式(13);式(3)—式(7),式(11),式(12)。當(dāng)模型M1可行時(shí),模型M2與之等價(jià),并且目標(biāo)函數(shù)值相等;當(dāng)模型式(M1)不可行時(shí),模型M2也可行,由于β和γ為足夠大的罰因子,最優(yōu)解為列車等級(jí)總權(quán)重最大前提下,接發(fā)車作業(yè)進(jìn)路和到發(fā)線運(yùn)用效用最大的過站徑路方案。3極大列車過站徑路方案由于模型M2是0-1線性整數(shù)規(guī)劃問題,約束條件與變量數(shù)較多,特此選擇模擬退火算法求解。這里省略模擬退火算法的通用框架,借鑒文獻(xiàn)的思想構(gòu)造模擬退火算法的鄰域系,模擬退火計(jì)劃表將在算例中給出。模型M2的1個(gè)可行解對(duì)應(yīng)1個(gè)列車集及其相容過站徑路方案(其他列車不安排過站徑路),其中列車集可表示為J?I,相容過站徑路方案可表示為在i∈J范圍內(nèi)滿足約束條件式(1)—式(7)的X(J)={xk′i(0)w,xk″i(1)w:k′=1,2,…,n(o(i),w),k″=1,2,…,n(w,d(i)),i∈J,w∈W}為了縮小搜索范圍引入極大可行解的概念:對(duì)于模型M2的可行解(J,X(J)),如果X(J)不存在可行性擴(kuò)展,即對(duì)于任何j?J,均使得X(J)∪{xk′j(0)w,xk″j(1)w:k′=1,2,…,n(o(j),w),k″=1,2,…,n(w,d(j)),w∈W}不滿足約束條件式(1)—式(7),則稱(J,X(J))為極大可行解,也稱為極大列車過站徑路方案。借助于極大列車過站徑路方案的概念,構(gòu)造極大列車過站徑路方案(J,X(J))的k剔除鄰域。首先從J中任意剔除k列列車得J′,然后對(duì)J′進(jìn)行極大化擴(kuò)展,即尋找列車集J″?I-J′,使(J′∪J″,X(J′∪J″))構(gòu)成極大列車過站徑路方案,其中X(J′∪J″)=X(J′)∪{xk′j(0)w,xk″j(1)w:k′=1,2,…,n(o(j),w),k″=1,2,…,n(w,d(i)),j∈J″,w∈W}滿足上述條件的所有(J′∪J″,X(J′∪J″))構(gòu)成極大列車過站徑路方案(J,X(J))的k剔除鄰域系。值得注意的是,對(duì)J′進(jìn)行極大化擴(kuò)展過程中,是在完全保持J′的過站徑路方案X(J′)不變的基礎(chǔ)上進(jìn)行的。J″可以通過對(duì)列車j∈I-J′按照隨機(jī)順序進(jìn)行極大化擴(kuò)展,相應(yīng)的過站徑路只需在已占用到發(fā)線和道岔的剩余網(wǎng)絡(luò)中求解即可。不滿足極大化擴(kuò)展條件的列車及其過站徑路方案不需重復(fù)嘗試。之所以選擇極大列車過站徑路方案作為搜索對(duì)象,一方面在于極大列車過站徑路方案比它的任何子方案因安排了更多列車的過站徑路而優(yōu)越;另一方面在于按照上述極大化方法,很容易從當(dāng)前極大列車過站徑路方案的鄰域中求出新的極大列車過站徑路方案。4到發(fā)線運(yùn)用效用以某客運(yùn)站為例,運(yùn)用上述模型和算法為18:00—0:00時(shí)段的旅客列車安排過站徑路。該客運(yùn)站的站形布局如圖1所示,其中Ⅰ,3,5道用于接發(fā)下行列車,Ⅱ,4,6,10道用于接發(fā)上行列車,Ⅰ和Ⅱ道為正線,8道為機(jī)走線。10道為接近車站出入口的到發(fā)線。該客運(yùn)站18:00—0:00時(shí)段到發(fā)列車見表1(單、雙數(shù)編號(hào)的列車分別為下、上行列車)。根據(jù)列車性質(zhì)、到發(fā)線使用要求和位置,確定的到發(fā)線運(yùn)用效用見表2。簡(jiǎn)便起見,僅考慮到發(fā)線運(yùn)用效用最大,不考慮進(jìn)路效用,進(jìn)路采用1次解鎖,左端咽喉作業(yè)占用道岔時(shí)間為1min,右端咽喉為2min,平衡因子α1取1,α2取0;懲罰因子β,γ均取10000.0,始發(fā)和終到列車列車等級(jí)權(quán)重取10.0,其他列車等級(jí)權(quán)重取5.0,鄰域系采用2剔除鄰域系。模擬退火計(jì)劃為:初始溫度取20000.0,溫度下降比例取0.9,溫度低于10時(shí)采用等步長(zhǎng)下降,步長(zhǎng)取0.5,同一溫度的迭代次數(shù)取200,溫度低于0.5或接受概率在20次迭代無改變時(shí)算法終止。通過計(jì)算所得的過站徑路方案效用為27720,具體方案見表3。過站徑路方案對(duì)應(yīng)的到發(fā)線運(yùn)用方案如圖2所示。由圖2所示的到發(fā)線運(yùn)用方案可見,上行方向列車均安排在用于上行列車接發(fā)作業(yè)的4,6,10道,由于20:00—23:00時(shí)段下行旅客列車到達(dá)強(qiáng)度超過下行方向到發(fā)線數(shù),使得下行方向列車T19和T39被迫分別占用6道和4道。注意到列車T39被安排在4道,而沒有安排在更靠近出入口的6道,這是由于T20的發(fā)車作業(yè)與T39的接車作業(yè)在時(shí)間上沖突,只有將T39安排在4道才能為2項(xiàng)作業(yè)排列平行進(jìn)路,這正體現(xiàn)出到發(fā)線運(yùn)用與接發(fā)車作業(yè)進(jìn)路之間的密切聯(lián)系,也反映了綜合優(yōu)化到發(fā)線運(yùn)用與接發(fā)車作業(yè)進(jìn)路的必要性。另外,本文未考慮到發(fā)線運(yùn)用的均衡性。5列車過站徑