劉洪亮
(中國(guó)鐵路濟(jì)南局集團(tuán)有限公司 運(yùn)輸部,山東 濟(jì)南 250001)
全路貨物列車(chē)開(kāi)行方案是貨物列車(chē)編組計(jì)劃的重要組成部分,貨物列車(chē)編組計(jì)劃是全路的車(chē)流組織計(jì)劃,它統(tǒng)一安排全路的車(chē)流組織方案,是編制列車(chē)運(yùn)行圖、運(yùn)輸方案、日班計(jì)劃及改善站場(chǎng)布局的依據(jù)。
全路貨物列車(chē)開(kāi)行方案的優(yōu)化是一個(gè)十分復(fù)雜的組合優(yōu)化問(wèn)題,需要建立對(duì)不同方案進(jìn)行比較的統(tǒng)一計(jì)算平臺(tái),每個(gè)列車(chē)開(kāi)行方案都是一個(gè)整體,在這個(gè)方案下各支車(chē)流都應(yīng)算出用最少改編時(shí)間送達(dá)目的地的列車(chē)經(jīng)由,對(duì)各支列車(chē)去向來(lái)講,形成了車(chē)流最合理組合,對(duì)于所有車(chē)流總時(shí)間消耗最小的組合,即車(chē)流最佳歸屬。不同的列車(chē)開(kāi)行方案,最合理的車(chē)流組合各不相同,需要根據(jù)列車(chē)開(kāi)行方案,對(duì)每支車(chē)流確定最佳歸屬,為統(tǒng)一計(jì)算平臺(tái)的系統(tǒng)研發(fā)提供指導(dǎo)和支撐。
全國(guó)鐵路網(wǎng)十分復(fù)雜,首先要解決如何正確、完整地計(jì)算一個(gè)列車(chē)開(kāi)行方案的經(jīng)濟(jì)指標(biāo),以車(chē)流組合來(lái)建模優(yōu)化[1-2]。把全路車(chē)流劃分到各技術(shù)站吸引的始發(fā)車(chē)流,形成幾百乃至上千棵車(chē)流樹(shù)[3],可以采用化整體為分散的思想,把復(fù)雜的路網(wǎng)結(jié)構(gòu)化成比較簡(jiǎn)單的樹(shù)結(jié)構(gòu)計(jì)算,從一個(gè)技術(shù)站出發(fā),開(kāi)往全路各技術(shù)站的始發(fā)車(chē)流可以用一棵有序樹(shù)表示,包含在這棵樹(shù)里某個(gè)開(kāi)行方案的直達(dá)、直通列車(chē)作為添加的弧,構(gòu)成一個(gè)無(wú)有向回路的有向圖[4]。指定了一個(gè)開(kāi)行方案,就能確定車(chē)流的最合理組合(稱(chēng)作車(chē)流最佳歸屬),可結(jié)合最短徑路算法(Dijkstra算法[5])構(gòu)建優(yōu)化模型求解。
車(chē)流樹(shù)中添加弧的長(zhǎng)度,用有向弧的箭頭所指節(jié)點(diǎn)的改編時(shí)間t改加上直達(dá)、直通列車(chē)沿途通過(guò)技術(shù)站的中轉(zhuǎn)時(shí)間t中來(lái)表示,有序樹(shù)中各條弧也用箭頭所指節(jié)點(diǎn)的t改表示弧長(zhǎng)。無(wú)有向回路避免了繞路運(yùn)輸反而消耗時(shí)間短的問(wèn)題,保證了計(jì)算的正確性。全路各技術(shù)站同時(shí)計(jì)算,把全路所有車(chē)流全部計(jì)算完,匯總后可以得到一個(gè)開(kāi)行方案的全部技術(shù)數(shù)據(jù),為集中編制及選優(yōu)打下基礎(chǔ)[4]。
初始時(shí),記錄車(chē)流最后發(fā)車(chē)站序號(hào)的路由數(shù)組m(i) = 0 (i= 1,2,…,n),除起始節(jié)點(diǎn)外,所有節(jié)點(diǎn)到起始節(jié)點(diǎn)的通路長(zhǎng)度d(vi)都記為足夠大的數(shù),d(v1) = 0。p為計(jì)算起點(diǎn),從1開(kāi)始。
在計(jì)算過(guò)程中,對(duì)于每一個(gè)屬于待計(jì)算頂點(diǎn)集T內(nèi)的點(diǎn)vi,計(jì)算經(jīng)過(guò)vp到達(dá)該點(diǎn)的距離為d(vp)+lpi,若小于原有記錄的通路長(zhǎng)度d(vi),則更新d(vi)為d(vp)+ lpi并更新m(i)為p。
找到屬于待計(jì)算頂點(diǎn)集T內(nèi)的點(diǎn)vi且d(vi)最小,最小值相同時(shí)取小的下標(biāo)i,計(jì)算起點(diǎn)變量p更新為新的節(jié)點(diǎn)i值,將節(jié)點(diǎn)vi從待計(jì)算頂點(diǎn)集中剔除。重復(fù)上述流程,直到T中沒(méi)有待計(jì)算節(jié)點(diǎn),輸出通路長(zhǎng)度數(shù)組及路由數(shù)組,算法結(jié)束。
一個(gè)技術(shù)站始發(fā)的車(chē)流構(gòu)成車(chē)流樹(shù),車(chē)流經(jīng)過(guò)和到達(dá)的技術(shù)站構(gòu)成樹(shù)的節(jié)點(diǎn),以圖G(V,E)表示,E即邊,實(shí)邊是區(qū)段列車(chē),虛邊是直達(dá)或直通列車(chē),在通過(guò)的技術(shù)站不改編只進(jìn)行中轉(zhuǎn)作業(yè)。
舉一個(gè)n為15的車(chē)流樹(shù)示例如圖1所示。車(chē)流樹(shù)n=15用實(shí)線表示,相鄰節(jié)點(diǎn)即區(qū)段列車(chē)。邊長(zhǎng)的箭頭所指車(chē)站改編時(shí)間,為簡(jiǎn)化起見(jiàn),均為3 h。有8支直達(dá)、直通列車(chē),用虛線表示???個(gè)技術(shù)站,改編及中轉(zhuǎn)時(shí)間為4 h;跨2個(gè)技術(shù)站,改編及中轉(zhuǎn)時(shí)間為5 h。
圖1 車(chē)流樹(shù)示例Fig.1 Example of a traffic tree
對(duì)Dijkstra算法加了一個(gè)路由數(shù)組m,當(dāng)更新路長(zhǎng)數(shù)組d(vi)時(shí),把計(jì)算起點(diǎn)p計(jì)入m(i),m(i)保存了各支車(chē)流最后發(fā)車(chē)站的序號(hào),本例計(jì)算結(jié)果 如 下:m(2) =1,m(3) =1,m(4) =1,m(5) =1,m(6) =3,m(7) =1,m(8) = 4,m(9) = 2,m(10) =4,m(11) = 2,m(12) = 9,m(13) = 9,m(14) = 5,m(15) = 9,m(1) = 0無(wú)意義。
根據(jù)路由數(shù)組m反推各支車(chē)流的輸送軌跡,m(i)的值是1→i這支車(chē)流最后發(fā)車(chē)站的序號(hào),如上例中1→15這支車(chē)流,先查m(15) = 9,表示有9→15這支列車(chē),再查m(9) = 2,表示有2→9這支列車(chē),查m(2) =1,表示有1→2這支列車(chē),且已查到根節(jié)點(diǎn)。1→15這支車(chē)流軌跡為1→2→9→15。有了軌跡,不僅可以知道車(chē)流在哪些車(chē)站改編,還知道各列車(chē)(包括區(qū)段、直通、直達(dá)列車(chē))吸收了哪些車(chē)流,在反推的過(guò)程中同時(shí)更新本技術(shù)站臨時(shí)列車(chē)、車(chē)流信息,車(chē)流樹(shù)中沒(méi)有車(chē)流的通過(guò)節(jié)點(diǎn),不進(jìn)行迭代計(jì)算。由于列車(chē)與多棵樹(shù)關(guān)聯(lián),需要全路匯總后,才能得到各支列車(chē)吸引的車(chē)流量和各技術(shù)站的改編車(chē)數(shù)。
車(chē)流最佳歸屬計(jì)算奠定全路集中計(jì)算的基礎(chǔ),但開(kāi)行方案十分龐大,直接求解效率低。根據(jù)全路70多個(gè)路網(wǎng)、區(qū)域、地方性編組站的分布以及其他300多個(gè)區(qū)段站的配合,縮小選擇范圍,分出必選去向和待選去向[6-7]。抓重點(diǎn)、壓任務(wù)、多比選、求優(yōu)化。運(yùn)用計(jì)算機(jī)進(jìn)行集中編制,建立全路車(chē)流信息庫(kù),直達(dá)、直通、區(qū)段列車(chē)信息庫(kù),分“全路總?cè)蝿?wù)”“技術(shù)站任務(wù)”,大約有幾百個(gè)任務(wù)并行運(yùn)行,有上千棵車(chē)流樹(shù)同時(shí)計(jì)算。計(jì)算的方案數(shù)龐大,只能有限計(jì)算,求得較優(yōu)的開(kāi)行方案[8-9]。
主要技術(shù)參數(shù):技術(shù)站分上下行直通中轉(zhuǎn)時(shí)間t中、改編時(shí)間t改、集結(jié)車(chē)小時(shí)cm、車(chē)流量n、無(wú)改編節(jié)省時(shí)間t節(jié)、各技術(shù)站分上下行改編能力設(shè)計(jì)值N改。
車(chē)流信息庫(kù)是以各技術(shù)站來(lái)建表,1個(gè)技術(shù)站吸收的本地區(qū)車(chē)流按全路技術(shù)站劃分,1支車(chē)流為1條記錄,分上下行填記發(fā)站、經(jīng)由技術(shù)站、到站及車(chē)數(shù),并分本站作業(yè)車(chē),上行、下行摘掛車(chē)數(shù),以便計(jì)算改編工作量。經(jīng)由技術(shù)站按車(chē)流徑路逐個(gè)填記,并設(shè)改編標(biāo)記項(xiàng),折角車(chē)流另加設(shè)標(biāo)記。由于車(chē)流長(zhǎng)短不一,車(chē)流記錄是可變長(zhǎng)記錄。
直達(dá)、直通列車(chē)庫(kù)是根據(jù)待選列車(chē)方案隨時(shí)建立的,按列車(chē)分表,列車(chē)代號(hào)參照車(chē)流代號(hào)標(biāo)記,首字母加“D”“T”表示直達(dá)、直通列車(chē)。表中記錄吸引的車(chē)流代號(hào)及車(chē)數(shù)。列車(chē)總表記錄列車(chē)代號(hào),分上下行的發(fā)站、經(jīng)由站、到站、總車(chē)數(shù)?;刂边_(dá)列車(chē)庫(kù)和區(qū)段列車(chē)庫(kù)應(yīng)單獨(dú)建立,作為編組計(jì)劃的重要組成部分。
通常一個(gè)技術(shù)站按銜接方向建幾棵車(chē)流有序樹(shù),有的站可以合并成1棵樹(shù),為方便操作,可以構(gòu)建車(chē)流編號(hào)代碼,例如站名除漢字、電報(bào)碼外,采用數(shù)字代號(hào),用3位數(shù)標(biāo)識(shí)。有序樹(shù)以關(guān)聯(lián)矩陣描述,樹(shù)節(jié)點(diǎn)序號(hào)是連續(xù)的,也作為車(chē)流數(shù)組的下標(biāo)。車(chē)流代號(hào)是發(fā)到站代號(hào)拼接起來(lái)的6位數(shù),相同發(fā)到站不同徑路的車(chē)流加標(biāo)記區(qū)分。
基地直達(dá)與技術(shù)直達(dá)不同,它只吸收本基地車(chē)流,與其他車(chē)流不發(fā)生關(guān)系,當(dāng)單支車(chē)流在裝車(chē)基地開(kāi)行直達(dá)額外消耗比沿途技術(shù)站上最小的無(wú)改編節(jié)省還要小,這支車(chē)流就可單獨(dú)確定開(kāi)行直達(dá)。裝車(chē)基地都在重要的廠礦、港口、儲(chǔ)運(yùn)企業(yè),大多數(shù)具備穩(wěn)定的貨源、較強(qiáng)的裝車(chē)能力,加上整列配空,形成了規(guī)律性很強(qiáng)的骨干車(chē)流,開(kāi)行基地直達(dá)既保證了國(guó)民經(jīng)濟(jì)發(fā)展的需要,又促進(jìn)了運(yùn)輸指揮的有序可控,參考文獻(xiàn)[10-12]對(duì)基地直達(dá)列車(chē)做了深入研究,這些列車(chē)不再參與開(kāi)行方案的選擇。裝車(chē)基地還有一些車(chē)流,可歸到前方技術(shù)站?;刂边_(dá)列車(chē)中如果有需要中轉(zhuǎn)的車(chē)流,歸到基地直達(dá)列車(chē)到達(dá)技術(shù)站。
2.3.1 開(kāi)行方案的產(chǎn)生及預(yù)分
以編組站分工為主,參照上年度的列車(chē)開(kāi)行方案,根據(jù)計(jì)劃年度運(yùn)量的變化和技術(shù)設(shè)備的變化以及大型施工情況,車(chē)流徑路調(diào)整以及運(yùn)輸組織創(chuàng)新要求,來(lái)確定必選列車(chē)去向,鐵路局集團(tuán)公司確定各技術(shù)站的待選列車(chē)去向。必選列車(chē)去向占的比例小,待選列車(chē)去向要有較大冗余。先計(jì)算一個(gè)現(xiàn)行方案作為參照點(diǎn),得到初始目標(biāo)值,以便和其他方案比較。按車(chē)站等級(jí)或能力,有比例地隨機(jī)從待選列車(chē)中抽取列車(chē)與必選列車(chē)組成開(kāi)行方案。
一支直達(dá)、直通列車(chē)包含在多棵車(chē)流樹(shù)中,先建立列車(chē)與車(chē)流樹(shù)的關(guān)聯(lián)表,根據(jù)該表,把方案中的直達(dá)、直通列車(chē)預(yù)分到各車(chē)流樹(shù)中,歸各技術(shù)站任務(wù)處理。
2.3.2 開(kāi)行方案的計(jì)算及修正
各技術(shù)站任務(wù)修改樹(shù)的邊長(zhǎng)矩陣,構(gòu)成無(wú)有向回路的有向圖,進(jìn)行車(chē)流最佳歸屬計(jì)算,全路總?cè)蝿?wù)匯總,根據(jù)計(jì)算結(jié)果進(jìn)行方案修正。方案修正分去弧計(jì)算與加弧計(jì)算(區(qū)段列車(chē)不動(dòng))。
去弧計(jì)算:判斷列車(chē)方案中有無(wú)某支列車(chē)開(kāi)行不利的情況,即∑nt節(jié)<cm,去除該支列車(chē),向相關(guān)技術(shù)站任務(wù)發(fā)送重新進(jìn)行車(chē)流歸屬計(jì)算的信息,去除該支列車(chē)后的目標(biāo)值得到優(yōu)化,與該支直達(dá)列車(chē)不相關(guān)的技術(shù)站不重算。相關(guān)技術(shù)站任務(wù)計(jì)算后計(jì)算結(jié)果返回,修改數(shù)據(jù)庫(kù),全路總?cè)蝿?wù)重新匯總結(jié)果。
加弧計(jì)算:全路總?cè)蝿?wù)在車(chē)流信息庫(kù)中查找是否存在單支車(chē)流滿足充分條件而未開(kāi)行直達(dá)列車(chē),即車(chē)流表中已標(biāo)識(shí)為改編,改開(kāi)直達(dá)后的節(jié)省時(shí)間)。若有,取值最大的一支車(chē)流,補(bǔ)開(kāi)直達(dá)列車(chē),優(yōu)化目標(biāo)值。判定包含所加列車(chē)的相關(guān)樹(shù)及技術(shù)站,發(fā)送重新進(jìn)行車(chē)流歸屬計(jì)算的信息。相關(guān)技術(shù)站任務(wù)進(jìn)行加弧計(jì)算,再返回結(jié)果,全路總?cè)蝿?wù)重新匯總。自動(dòng)修正時(shí),如果加弧的去向不在待選去向中提交人工干預(yù),以后相同問(wèn)題自動(dòng)處理。
2.3.3 完成方案的修正和指標(biāo)計(jì)算后進(jìn)入下一個(gè)方案計(jì)算
加弧計(jì)算引起車(chē)流歸屬的重新分配,因?yàn)槊恐е边_(dá)列車(chē)在網(wǎng)絡(luò)中的位置及無(wú)改編節(jié)省的數(shù)值不同,與相關(guān)的直達(dá)、直通列車(chē)既協(xié)作又競(jìng)爭(zhēng),所以加弧以后,原來(lái)開(kāi)行的有些直達(dá)列車(chē)可能會(huì)出現(xiàn)開(kāi)行不利的情況,于是應(yīng)該重復(fù)去弧過(guò)程,進(jìn)一步優(yōu)化目標(biāo)。再檢查加弧條件,如果沒(méi)有加弧的可能,該過(guò)程就停止,否則重復(fù)這個(gè)過(guò)程。計(jì)算該方案目標(biāo)值,目標(biāo)值達(dá)到滿意指標(biāo)標(biāo)準(zhǔn)則留存,繼續(xù)推算其他方案。
2.3.4 技術(shù)站改編作業(yè)量的計(jì)算
在技術(shù)指標(biāo)中,技術(shù)站改編作業(yè)量十分重要,能決定方案可否采用。改編作業(yè)量按到達(dá)列車(chē)統(tǒng)計(jì)(包括區(qū)段列車(chē)),列車(chē)的到站一般已確定上行或下行,改編工作量不難計(jì)算。一般情況下折角車(chē)流要計(jì)算重復(fù)改編作業(yè)量,到達(dá)本站的摘掛車(chē)流中存在折角車(chē)。
存在通過(guò)不同的進(jìn)站線路分別到達(dá)技術(shù)站上行和下行的情況,發(fā)站車(chē)流分2個(gè)去向集結(jié),為了計(jì)算方便按1支列車(chē)計(jì)算車(chē)流歸屬,把吸引的車(chē)流分成2部分,車(chē)流庫(kù)的結(jié)構(gòu)已考慮這種情況,可以計(jì)算出上行及下行的改編工作量。這種情況無(wú)重復(fù)改編,發(fā)站的集結(jié)時(shí)間應(yīng)加倍計(jì)算。減少改編作業(yè)量可以提高車(chē)站通過(guò)能力。
2.3.5 最終開(kāi)行方案的確定
全路總?cè)蝿?wù)規(guī)定至少抽取方案數(shù),規(guī)定目標(biāo)值的最大增幅與已抽取方案數(shù)相比的閾值,當(dāng)小于閾值時(shí)結(jié)束計(jì)算。提供目標(biāo)值較優(yōu)的若干個(gè)方案的經(jīng)濟(jì)技術(shù)指標(biāo),包括目標(biāo)值(∑nt節(jié)- ∑cm),各技術(shù)站上下行改編車(chē)數(shù)、無(wú)調(diào)比重,技術(shù)直達(dá)、直通列車(chē)列數(shù)及平均通過(guò)技術(shù)站數(shù),車(chē)流平均改編次數(shù)等,在經(jīng)濟(jì)效益、能力協(xié)調(diào)和提高、直達(dá)水平、車(chē)輛運(yùn)用及可控性等方面進(jìn)行綜合分析比較。要兼顧區(qū)段內(nèi)車(chē)流輸送,相鄰技術(shù)站應(yīng)留足編開(kāi)中間站重點(diǎn)作業(yè)列車(chē)的能力,解決區(qū)段通過(guò)能力因摘掛車(chē)流過(guò)大而出現(xiàn)的緊張問(wèn)題。
經(jīng)過(guò)綜合比較分析以后,選擇一個(gè)較優(yōu)方案,適當(dāng)調(diào)整,作為最終開(kāi)行方案,遵循最終開(kāi)行方案編制各鐵路局集團(tuán)公司列車(chē)編組計(jì)劃。
(1)全路總?cè)蝿?wù)分成列車(chē)開(kāi)行方案產(chǎn)生及預(yù)分、方案計(jì)算及修正、技術(shù)指標(biāo)計(jì)算3個(gè)任務(wù),有關(guān)聯(lián)地并行運(yùn)行。方案計(jì)算及修正任務(wù)與幾百個(gè)技術(shù)站任務(wù)交替運(yùn)行,相互觸發(fā),幾百個(gè)技術(shù)站任務(wù)并行運(yùn)行,建立觸發(fā)機(jī)制確保并行任務(wù)同步,化解數(shù)據(jù)庫(kù)訪問(wèn)沖突。技術(shù)站任務(wù)又分總?cè)蝿?wù)和幾個(gè)車(chē)流樹(shù)并行計(jì)算任務(wù)。
(2)技術(shù)站編發(fā)能力可以控制,改編能力是否適應(yīng)則要看計(jì)算結(jié)果。技術(shù)指標(biāo)詳細(xì)計(jì)算任務(wù),對(duì)明顯不可行方案立即淘汰。在結(jié)束階段,對(duì)各個(gè)方案中幾百個(gè)技術(shù)站的能力協(xié)調(diào)程度作模糊綜合評(píng)判。貨物列車(chē)不固定開(kāi)行,必須考慮車(chē)流波動(dòng),列車(chē)去向吸引的車(chē)流支數(shù)多、車(chē)流量大,好控制;勉強(qiáng)夠開(kāi)行條件的列車(chē)去向,難控制。調(diào)度人員對(duì)可控性更為關(guān)切,開(kāi)行方案包括幾千支列車(chē),也采用模糊評(píng)判。
(3)全路技術(shù)站劃分車(chē)流進(jìn)行車(chē)流最佳歸屬計(jì)算,可以完成全路車(chē)流計(jì)算,實(shí)現(xiàn)集中編制。為適應(yīng)車(chē)流日常波動(dòng),鐵路局集團(tuán)公司編制列車(chē)編組計(jì)劃時(shí),既要保持開(kāi)行去向不變,又要在編組內(nèi)容上適當(dāng)調(diào)整,便于實(shí)施。同時(shí)各鐵路局集團(tuán)公司之間要在總開(kāi)行方案框架內(nèi)共同商定分組列車(chē)的組織方法,進(jìn)一步挖掘運(yùn)輸潛力。
(4)本次研究建立的信息系統(tǒng)屬于鐵路運(yùn)輸管理信息系統(tǒng),要做好系統(tǒng)整合、信息共享。尤其是十分準(zhǔn)確的貨票信息對(duì)計(jì)劃車(chē)流的推算有較大幫助,本系統(tǒng)提供的信息對(duì)全路車(chē)流組織有深遠(yuǎn)影響。
按全路技術(shù)站劃分車(chē)流進(jìn)行最佳歸屬計(jì)算,實(shí)現(xiàn)了列車(chē)開(kāi)行方案的集中編制。優(yōu)化貨物列車(chē)開(kāi)行方案是編制貨物列車(chē)編組計(jì)劃的關(guān)鍵,運(yùn)用計(jì)算機(jī)進(jìn)行集中計(jì)算,把必選列車(chē)去向和隨機(jī)抽取的待選列車(chē)去向,組成大量的開(kāi)行方案進(jìn)行比選,以經(jīng)由節(jié)點(diǎn)標(biāo)識(shí)法構(gòu)建車(chē)流及列車(chē)數(shù)據(jù)庫(kù),為詳細(xì)計(jì)算提供依據(jù)。運(yùn)用直達(dá)列車(chē)開(kāi)行的充分和必要條件檢查修正每個(gè)方案,實(shí)行多目標(biāo)綜合評(píng)價(jià),尋找較優(yōu)方案,尊重經(jīng)驗(yàn)又不囿于經(jīng)驗(yàn),具有可實(shí)施性;采用車(chē)流樹(shù)并行計(jì)算,當(dāng)鐵路網(wǎng)增加線路、增減技術(shù)站、調(diào)整重車(chē)流徑路時(shí),只需要修改相關(guān)車(chē)流樹(shù),具有靈便性。全路集中優(yōu)化涉及許多方面,這里僅作了初步探討,還有許多不足之處,有待于不斷改進(jìn)和完善。