鐵路客運過站徑路優化模型研究

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