成利剛(五邑大學(xué) 軌道交通學(xué)院,廣東 江門 529020)
鐵路客運(yùn)車站股道運(yùn)用優(yōu)化模型及算法研究
成利剛
(五邑大學(xué) 軌道交通學(xué)院,廣東 江門 529020)
為了提高鐵路客運(yùn)車站的生產(chǎn)作業(yè)效率和自動(dòng)化水平,本文通過對(duì)客運(yùn)車站作業(yè)特點(diǎn)及股道運(yùn)用計(jì)劃的調(diào)查分析,以有效利用車站設(shè)備、提高車站接發(fā)車對(duì)數(shù)為目的,考慮車站接發(fā)車作業(yè)過程中的交叉干擾以及進(jìn)路建立過程中的技術(shù)作業(yè)時(shí)間差,分別以股道占用時(shí)間和空費(fèi)時(shí)間的方差來衡量股道運(yùn)用的均衡性,建立了股道運(yùn)用均衡的多目標(biāo)模型,并用布谷鳥算法求解模型,以實(shí)際車站數(shù)據(jù)進(jìn)行驗(yàn)證,結(jié)果證明了模型的可行性及優(yōu)越性.
鐵路客運(yùn)站;股道運(yùn)用均衡;交叉干擾;布谷鳥算法
隨著鐵路事業(yè)的發(fā)展,依靠通信技術(shù)、計(jì)算機(jī)技術(shù)等,鐵路調(diào)度指揮自動(dòng)化在一定程度上得以實(shí)現(xiàn),列車嚴(yán)格按照運(yùn)行圖的規(guī)定在線路上運(yùn)行.但對(duì)于鐵路客運(yùn)車站來說,運(yùn)行圖僅規(guī)定了列車在車站到達(dá)、出發(fā)、通過的時(shí)刻和停站時(shí)分,列車選擇什么樣的進(jìn)路進(jìn)站、在哪條股道停車、選擇怎樣的發(fā)車進(jìn)路等只能由車站調(diào)度人員憑借自身經(jīng)驗(yàn)安排,若趕上節(jié)假日車站的日接發(fā)車數(shù)量突然增大,調(diào)度人員將無法始終根據(jù)運(yùn)行圖和車站站場(chǎng)的時(shí)空約束來保證車站進(jìn)路及股道的最優(yōu)化配置,尤其是列車晚點(diǎn)時(shí),車站股道不能按照原有計(jì)劃進(jìn)行安排,直接影響車站的接發(fā)車效率和服務(wù)質(zhì)量.鐵路客運(yùn)車站如何制定合理的股道運(yùn)用計(jì)劃最大限度地提高接發(fā)車對(duì)數(shù),成為亟待解決的問題.
車站股道運(yùn)用不僅要得到列車在車站的到發(fā)時(shí)刻,還要得到列車在車站占用的股道.合理科學(xué)地解決鐵路車站股道運(yùn)用中存在的問題,不僅可以減少調(diào)度人員的工作量,提高進(jìn)路安排的合理性,保證各設(shè)備的均衡使用,而且可以增加車站股道運(yùn)用的抗干擾能力,提高車站服務(wù)質(zhì)量.國內(nèi)外學(xué)者對(duì)股道運(yùn)用問題做了大量的研究.如Carey和Carville[1]以成本最小為目標(biāo),以最小時(shí)間間隔、多站臺(tái)車站的站臺(tái)占用以及進(jìn)路交叉為約束條件的排序模型;雷定猷等[2]以車站設(shè)備的均衡使用、旅客乘降方便為目標(biāo)的建模;謝楚農(nóng)等[3]以方便旅客乘降和提升車站技術(shù)作業(yè)設(shè)備使用效率構(gòu)建的多目標(biāo)優(yōu)化模型與分枝定界法的求解模型;Partha Chakroborty等[4]建立混合線性整數(shù)規(guī)劃模型描述在列車到達(dá)不準(zhǔn)時(shí)的條件下股道運(yùn)用問題;喬瑞軍等[5]以列車站內(nèi)走行時(shí)間之和最小以及股道運(yùn)用均衡為目標(biāo)建模優(yōu)化客運(yùn)站股道運(yùn)用;史峰等[6]以列車等級(jí)總權(quán)重最大化和到發(fā)線運(yùn)用效用最大化為優(yōu)化目標(biāo),對(duì)列車占用到發(fā)線和道岔進(jìn)行相容性約束,建立了到發(fā)線運(yùn)用和一端咽喉接發(fā)車進(jìn)路排列方案綜合優(yōu)化的0-1規(guī)劃模型.
本文主要從股道的均衡使用、提高設(shè)備利用率、減少列車在站內(nèi)的走行時(shí)間、提高接發(fā)車的效率的角度,對(duì)車站股道運(yùn)用進(jìn)行優(yōu)化.
車站股道的總數(shù)量為M,該站開行的列車總數(shù)為N. xij( i∈ N, j∈ M )表示第i列列車對(duì)第j條股道的占用情況,若 xij= 1,則表示第 j條股道被列車i占用,占用的總時(shí)間為 tij,否則 xij= 0.表示列車i尾部越過股道 j相應(yīng)方向出站信號(hào)機(jī)的時(shí)間,即列車i在 t時(shí)刻從股道 j出清;在列車i之后的任意列車k( k ∈ N )占用股道j的時(shí)間為t.則列車在車站的接發(fā)車及其他作業(yè)必須滿足以下約束:
1)列車編組長(zhǎng)度 li必須受到所占用股道有效長(zhǎng)度的限制 Lj,即 Lj> li;
4)同一股道接發(fā)相鄰列車的時(shí)間間隔要滿足最小安全時(shí)間間隔要求,即其中, Δj為前行車i出清股道 j、后行車k準(zhǔn)備并進(jìn)入股道 j的最小時(shí)間;
5)任一列車在進(jìn)行接發(fā)車作業(yè)占用咽喉區(qū)段時(shí),應(yīng)避免與其他列車的接發(fā)形成沖突[7].如果列車i辦理股道j的接發(fā)車作業(yè)與列車k辦理股道h的接發(fā)車作業(yè)存在交叉,則 Aik=1,否則 Aik=0;如果列車i辦理股道 j接發(fā)車作業(yè)的進(jìn)路與列車k辦理股道h接發(fā)車作業(yè)的進(jìn)路是平行作業(yè),則Bijkh=1,否則 Bijkh= 0;因此,為了避免兩列列車的進(jìn)路存在時(shí)間交叉,則兩列列車應(yīng)安排平行進(jìn)路,即必須滿足:
股道運(yùn)用均衡主要指列車對(duì)每條股道的占用總時(shí)間的均衡和股道空費(fèi)時(shí)間的均衡.通過均衡,最大限度提升車站的接發(fā)車能力以及股道運(yùn)用方案的抗干擾性能.
以每條股道被占用時(shí)間的方差來衡量股道被占用總時(shí)間的均衡性,目標(biāo)函數(shù)1f的函數(shù)值越小,表明每條股道的占用時(shí)間越均衡:
以進(jìn)入同一股道的相鄰列車間隔時(shí)間的平方和衡量股道占用間隔時(shí)間均衡.目標(biāo)函數(shù)2f的函數(shù)值越小,表明同一股道的相鄰列車間隔時(shí)間越小,這有利于提高股道的利用率,即提高車站的接發(fā)車能力.
目標(biāo)函數(shù):
其中, θ1,θ2分別為目標(biāo)函數(shù) f1和 f2的權(quán)重系數(shù),本文令 θ1=θ2= 0 .5; Tij為進(jìn)入股道j的相鄰兩列列車的時(shí)間間隔.
布谷鳥算法是劍橋大學(xué)學(xué)者Xin-She Yang和Suash Deb提出的一種啟發(fā)式智能優(yōu)化算法[8].該算法基于布谷鳥尋找鳥窩放置鳥蛋,并融入了鳥類的Lévy飛行行為,很好結(jié)合了局部隨機(jī)過程和全局隨機(jī)過程.與遺傳算法、粒子群算法等相比,布谷鳥算法有更好的尋優(yōu)速度和更高的精度[9-11],其局部隨機(jī)過程可描述如下:
全局隨機(jī)過程按Lévy進(jìn)行,可表示為:
其中, s ? s0>0,1 < λ ≤3.
2.1 初始化種群
為縮短計(jì)算時(shí)間,本文求解時(shí)采用整數(shù)編碼:按照列車占用股道的時(shí)間順序?qū)⒘熊嚲幪?hào)為1,2,3,…, N,車站股道編號(hào)為1,2,3,…, M.初始化種群數(shù)量只需包含所有列車,因此隨機(jī)產(chǎn)生N個(gè)鳥窩位置 xi( i = 1,2,…,N ).
2.2 適應(yīng)度函數(shù)選取
對(duì)于股道運(yùn)用優(yōu)化問題,以股道分配的均衡值最小作為其優(yōu)化目標(biāo),本文以目標(biāo)函數(shù)作為算法的適應(yīng)度函數(shù),即:
2.3 算法流程
布谷鳥算法的具體步驟如下:
步驟1 初始化m個(gè)鳥窩位置 xi( i = 1,2,…, m ),選出全局最優(yōu)的鳥窩位置,并將其保留到下一代;
步驟2 用式(3)、式(4)進(jìn)行鳥窩位置的更新,將適應(yīng)度函數(shù)值與更新前進(jìn)行對(duì)比,保留較好的鳥窩位置;
步驟3 拋棄較差的鳥窩.產(chǎn)生服從均勻分布的隨機(jī)數(shù) r ∈ ( 0,1),并與發(fā)現(xiàn)概率 pa= 0.25進(jìn)行比較,如果 r > pa,則將改變,通過與步驟2得到的鳥窩位置對(duì)比,保留較好的鳥窩位置,并選出當(dāng)代全局最優(yōu)位置 X;
本文以實(shí)際鐵路客運(yùn)樞紐站N站Z場(chǎng)進(jìn)行驗(yàn)證,其平面布置圖如圖1所示,Z場(chǎng)中包括20~28 共9條股道,出站開行的方向主要有A、B和C 3個(gè)動(dòng)車所.
目前,N站日均辦理列車364.5對(duì),其中營業(yè)列車283.5對(duì),動(dòng)車組出入庫84.5對(duì),上水列車54組,上水吸污列車19組,發(fā)送旅客117 567人,到達(dá)旅客107 955人;高峰期辦理列車386對(duì),其中營業(yè)列車294.5對(duì),動(dòng)車組出入庫96.5對(duì),上水列車61組,上水吸污列車23組,發(fā)送旅客130 195人,到達(dá)旅客134 723人.其中Z場(chǎng)每日開行列車69.5對(duì),選取某日下午14:00到凌晨00:12這段時(shí)間進(jìn)行研究,N站Z場(chǎng)的股道分配優(yōu)化前方案如表1所示,可計(jì)算其股道均衡值 Z = 643.316 7.
根據(jù)模型的目標(biāo)函數(shù)和約束條件,計(jì)算得到如表1所示的N站Z場(chǎng)的股道運(yùn)用優(yōu)化后方案,其運(yùn)用均衡值 Z = 76.817 8,明顯優(yōu)于原方案.
圖1 N站Z場(chǎng)平面圖
表1 優(yōu)化前后,N站Z場(chǎng)的股道分配方案
為了提高鐵路客運(yùn)車站股道運(yùn)用計(jì)劃編制的科學(xué)性和自動(dòng)化水平,本文以股道運(yùn)用均衡為目標(biāo)建模,能夠提高車站設(shè)備利用率和車站接發(fā)車能力;同時(shí)對(duì)于車站股道運(yùn)用計(jì)劃的抗干擾能力也有所改善;由于考慮了進(jìn)路間的交叉干擾,使得模型更加符合實(shí)際.本文結(jié)果對(duì)于鐵路客(貨)運(yùn)車站、鐵路編組場(chǎng)以及城市軌道交通停車場(chǎng)股道運(yùn)用計(jì)劃的編制都有一定的借鑒意義.但在建模過程中,沒有考慮車站的調(diào)車作業(yè),也沒有詳細(xì)論述股道運(yùn)用計(jì)劃抗干擾能力的大小以及影響因素,無法對(duì)模型的實(shí)用性作出科學(xué)的評(píng)價(jià),因此,本方案的使用有一定的局限性,只能應(yīng)用于行車密度不是特別高的客運(yùn)車站.
[1]CRAEY M,CRAVILLE S.Scheduling and platforming trains at busy complex stations[J].Transportation Research Part A,2003,37(3):195-224.
[2]雷定猷,王棟,劉明翔.客運(yùn)站股道運(yùn)用優(yōu)化模型及算法[J].交通運(yùn)輸工程學(xué)報(bào),2007,7(5):84-87.
[3]謝楚農(nóng),黎新華.鐵路客運(yùn)站到發(fā)線運(yùn)用優(yōu)化研究[J].中國鐵道科學(xué),2004,25(5):130-133.
[4]CHAKROBORTY P,VIKRAM D.Optimum assignment of trains to platforms under partial schedule compliance [J].Transportation Research Part B,2008,42:169-184.
[5]喬瑞軍,朱曉寧,張?zhí)靷?,?客運(yùn)專線車站接發(fā)車進(jìn)路選擇與調(diào)整問題研究[J].北京交通大學(xué)學(xué)報(bào),2012,36(3):57-64.
[6]史峰,陳彥,秦進(jìn),等.鐵路客運(yùn)站到發(fā)線運(yùn)用和接發(fā)車進(jìn)路排列方案綜合優(yōu)化[J].中國鐵道科學(xué),2009,30(6):108-113.
[7]郭莉,呂紅霞,陳煥云.基于遺傳算法的鐵路車站到發(fā)線運(yùn)用優(yōu)化研究[J].西南民族大學(xué)學(xué)報(bào)(自然科學(xué)版),2005,31(1):28-31.
[8]YANG Xinshe,DEB S.Cuckoo search via Lévy flights[C]//World Congress on Nature&Biologically Inspired Computing.Piscataway:IEEE Publications,2009:210-214.
[9]青學(xué)江,馬國忠.遺傳算法在區(qū)段站到發(fā)線的應(yīng)用研究[J].西南交通大學(xué)學(xué)報(bào),1998,33(4):30-40.
[10]李煜,馬良.新型元啟發(fā)式布谷鳥搜索算法[J].系統(tǒng)工程,2012,30(8):64-69.
[11]姚遠(yuǎn)遠(yuǎn),葉春明.作業(yè)車間調(diào)度問題的布谷鳥搜索算法求解[J].計(jì)算機(jī)工程與應(yīng)用,2015,51(5):255-260.
[責(zé)任編輯:熊玉濤]
A Study of the Optimization Model and Algorithm for Track Application in Railway Passenger Stations
CHENG Li-gang
(School of Railway Tracks and Transportation,Wuyi University,Jiangmen 529020,China)
In order to improve railway passenger stations’production efficiency and automation level, this paper,through an investigative analysis of passenger stations’operation characteristics and track use plans,with the efficient use of railway stations’equipment and increasing train departures and arrivals as the object,and taking into consideration the cross interference by arrivals and departures and the technical operation time difference in the approach process,measures the equilibriumof track use using the variance of the hold-up time and time unoccupied respectively,establishes a balanced multi-purpose model for track use,adopts a cuckoo algorithm,and validates the model against actual station data.The results prove the feasibility and superiority of the model.
railway passenger stations;track use equilibrium;cross interference;the cuckooalgorithm
U293.2
A
1006-7302(2016)03-0014-05
2016-03-18
江門市基礎(chǔ)與理論科學(xué)研究類項(xiàng)目(20150030004128)
成利剛(1987—),男,甘肅天水人,助教,碩士,研究方向?yàn)榻煌ㄐ畔⒐こ碳翱刂?