基于車流最佳歸屬算法的貨物列車開行方案集中編制及優(yōu)化探討

劉洪亮

（中國鐵路濟南局集團有限公司 運輸部，山東 濟南 250001)

0 引言

全路貨物列車開行方案是貨物列車編組計劃的重要組成部分，貨物列車編組計劃是全路的車流組織計劃，它統(tǒng)一安排全路的車流組織方案，是編制列車運行圖、運輸方案、日班計劃及改善站場布局的依據(jù)。

全路貨物列車開行方案的優(yōu)化是一個十分復(fù)雜的組合優(yōu)化問題，需要建立對不同方案進(jìn)行比較的統(tǒng)一計算平臺，每個列車開行方案都是一個整體，在這個方案下各支車流都應(yīng)算出用最少改編時間送達(dá)目的地的列車經(jīng)由，對各支列車去向來講，形成了車流最合理組合，對于所有車流總時間消耗最小的組合，即車流最佳歸屬。不同的列車開行方案，最合理的車流組合各不相同，需要根據(jù)列車開行方案，對每支車流確定最佳歸屬，為統(tǒng)一計算平臺的系統(tǒng)研發(fā)提供指導(dǎo)和支撐。

1 技術(shù)站車流最佳歸屬計算方法

1.1 貨物列車開行方案與車流輸送的關(guān)系

全國鐵路網(wǎng)十分復(fù)雜，首先要解決如何正確、完整地計算一個列車開行方案的經(jīng)濟指標(biāo)，以車流組合來建模優(yōu)化[1-2]。把全路車流劃分到各技術(shù)站吸引的始發(fā)車流，形成幾百乃至上千棵車流樹[3]，可以采用化整體為分散的思想，把復(fù)雜的路網(wǎng)結(jié)構(gòu)化成比較簡單的樹結(jié)構(gòu)計算，從一個技術(shù)站出發(fā)，開往全路各技術(shù)站的始發(fā)車流可以用一棵有序樹表示，包含在這棵樹里某個開行方案的直達(dá)、直通列車作為添加的弧，構(gòu)成一個無有向回路的有向圖[4]。指定了一個開行方案，就能確定車流的最合理組合(稱作車流最佳歸屬)，可結(jié)合最短徑路算法(Dijkstra算法[5])構(gòu)建優(yōu)化模型求解。

車流樹中添加弧的長度，用有向弧的箭頭所指節(jié)點的改編時間t改加上直達(dá)、直通列車沿途通過技術(shù)站的中轉(zhuǎn)時間t中來表示，有序樹中各條弧也用箭頭所指節(jié)點的t改表示弧長。無有向回路避免了繞路運輸反而消耗時間短的問題，保證了計算的正確性。全路各技術(shù)站同時計算，把全路所有車流全部計算完，匯總后可以得到一個開行方案的全部技術(shù)數(shù)據(jù)，為集中編制及選優(yōu)打下基礎(chǔ)[4]。

1.2 基于動態(tài)路由數(shù)值的Dijkstra算法

初始時，記錄車流最后發(fā)車站序號的路由數(shù)組m(i) = 0 (i= 1，2，…，n)，除起始節(jié)點外，所有節(jié)點到起始節(jié)點的通路長度d(vi)都記為足夠大的數(shù)，d(v1) = 0。p為計算起點，從1開始。

在計算過程中，對于每一個屬于待計算頂點集T內(nèi)的點vi，計算經(jīng)過vp到達(dá)該點的距離為d(vp)+lpi，若小于原有記錄的通路長度d(vi)，則更新d(vi)為d(vp)+ lpi并更新m(i)為p。

找到屬于待計算頂點集T內(nèi)的點vi且d(vi)最小，最小值相同時取小的下標(biāo)i，計算起點變量p更新為新的節(jié)點i值，將節(jié)點vi從待計算頂點集中剔除。重復(fù)上述流程，直到T中沒有待計算節(jié)點，輸出通路長度數(shù)組及路由數(shù)組，算法結(jié)束。

一個技術(shù)站始發(fā)的車流構(gòu)成車流樹，車流經(jīng)過和到達(dá)的技術(shù)站構(gòu)成樹的節(jié)點，以圖G(V，E)表示，E即邊，實邊是區(qū)段列車，虛邊是直達(dá)或直通列車，在通過的技術(shù)站不改編只進(jìn)行中轉(zhuǎn)作業(yè)。

舉一個n為15的車流樹示例如圖1所示。車流樹n=15用實線表示，相鄰節(jié)點即區(qū)段列車。邊長的箭頭所指車站改編時間，為簡化起見，均為3 h。有8支直達(dá)、直通列車，用虛線表示。跨1個技術(shù)站，改編及中轉(zhuǎn)時間為4 h；跨2個技術(shù)站，改編及中轉(zhuǎn)時間為5 h。

圖1 車流樹示例Fig.1 Example of a traffic tree

對Dijkstra算法加了一個路由數(shù)組m，當(dāng)更新路長數(shù)組d(vi)時，把計算起點p計入m(i)，m(i)保存了各支車流最后發(fā)車站的序號，本例計算結(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無意義。

1.3 車流更新迭代算法

根據(jù)路由數(shù)組m反推各支車流的輸送軌跡，m(i)的值是1→i這支車流最后發(fā)車站的序號，如上例中1→15這支車流，先查m(15) = 9，表示有9→15這支列車，再查m(9) = 2，表示有2→9這支列車，查m(2) =1，表示有1→2這支列車，且已查到根節(jié)點。1→15這支車流軌跡為1→2→9→15。有了軌跡，不僅可以知道車流在哪些車站改編，還知道各列車(包括區(qū)段、直通、直達(dá)列車)吸收了哪些車流，在反推的過程中同時更新本技術(shù)站臨時列車、車流信息，車流樹中沒有車流的通過節(jié)點，不進(jìn)行迭代計算。由于列車與多棵樹關(guān)聯(lián)，需要全路匯總后，才能得到各支列車吸引的車流量和各技術(shù)站的改編車數(shù)。

2 全路列車開行方案集中編制及優(yōu)化

車流最佳歸屬計算奠定全路集中計算的基礎(chǔ)，但開行方案十分龐大，直接求解效率低。根據(jù)全路70多個路網(wǎng)、區(qū)域、地方性編組站的分布以及其他300多個區(qū)段站的配合，縮小選擇范圍，分出必選去向和待選去向[6-7]。抓重點、壓任務(wù)、多比選、求優(yōu)化。運用計算機進(jìn)行集中編制，建立全路車流信息庫，直達(dá)、直通、區(qū)段列車信息庫，分“全路總?cè)蝿?wù)”“技術(shù)站任務(wù)”，大約有幾百個任務(wù)并行運行，有上千棵車流樹同時計算。計算的方案數(shù)龐大，只能有限計算，求得較優(yōu)的開行方案[8-9]。

2.1 數(shù)據(jù)結(jié)構(gòu)及主要參數(shù)

主要技術(shù)參數(shù)：技術(shù)站分上下行直通中轉(zhuǎn)時間t中、改編時間t改、集結(jié)車小時cm、車流量n、無改編節(jié)省時間t節(jié)、各技術(shù)站分上下行改編能力設(shè)計值N改。

車流信息庫是以各技術(shù)站來建表，1個技術(shù)站吸收的本地區(qū)車流按全路技術(shù)站劃分，1支車流為1條記錄，分上下行填記發(fā)站、經(jīng)由技術(shù)站、到站及車數(shù)，并分本站作業(yè)車，上行、下行摘掛車數(shù)，以便計算改編工作量。經(jīng)由技術(shù)站按車流徑路逐個填記，并設(shè)改編標(biāo)記項，折角車流另加設(shè)標(biāo)記。由于車流長短不一，車流記錄是可變長記錄。

直達(dá)、直通列車庫是根據(jù)待選列車方案隨時建立的，按列車分表，列車代號參照車流代號標(biāo)記，首字母加“D”“T”表示直達(dá)、直通列車。表中記錄吸引的車流代號及車數(shù)。列車總表記錄列車代號，分上下行的發(fā)站、經(jīng)由站、到站、總車數(shù)?；刂边_(dá)列車庫和區(qū)段列車庫應(yīng)單獨建立，作為編組計劃的重要組成部分。

通常一個技術(shù)站按銜接方向建幾棵車流有序樹，有的站可以合并成1棵樹，為方便操作，可以構(gòu)建車流編號代碼，例如站名除漢字、電報碼外，采用數(shù)字代號，用3位數(shù)標(biāo)識。有序樹以關(guān)聯(lián)矩陣描述，樹節(jié)點序號是連續(xù)的，也作為車流數(shù)組的下標(biāo)。車流代號是發(fā)到站代號拼接起來的6位數(shù)，相同發(fā)到站不同徑路的車流加標(biāo)記區(qū)分。

2.2 裝車基地直達(dá)列車開行方案的確定

基地直達(dá)與技術(shù)直達(dá)不同，它只吸收本基地車流，與其他車流不發(fā)生關(guān)系，當(dāng)單支車流在裝車基地開行直達(dá)額外消耗比沿途技術(shù)站上最小的無改編節(jié)省還要小，這支車流就可單獨確定開行直達(dá)。裝車基地都在重要的廠礦、港口、儲運企業(yè)，大多數(shù)具備穩(wěn)定的貨源、較強的裝車能力，加上整列配空，形成了規(guī)律性很強的骨干車流，開行基地直達(dá)既保證了國民經(jīng)濟發(fā)展的需要，又促進(jìn)了運輸指揮的有序可控，參考文獻(xiàn)[10-12]對基地直達(dá)列車做了深入研究，這些列車不再參與開行方案的選擇。裝車基地還有一些車流，可歸到前方技術(shù)站?；刂边_(dá)列車中如果有需要中轉(zhuǎn)的車流，歸到基地直達(dá)列車到達(dá)技術(shù)站。

2.3 優(yōu)化方法的實現(xiàn)過程

2.3.1 開行方案的產(chǎn)生及預(yù)分

以編組站分工為主，參照上年度的列車開行方案，根據(jù)計劃年度運量的變化和技術(shù)設(shè)備的變化以及大型施工情況，車流徑路調(diào)整以及運輸組織創(chuàng)新要求，來確定必選列車去向，鐵路局集團公司確定各技術(shù)站的待選列車去向。必選列車去向占的比例小，待選列車去向要有較大冗余。先計算一個現(xiàn)行方案作為參照點，得到初始目標(biāo)值，以便和其他方案比較。按車站等級或能力，有比例地隨機從待選列車中抽取列車與必選列車組成開行方案。

一支直達(dá)、直通列車包含在多棵車流樹中，先建立列車與車流樹的關(guān)聯(lián)表，根據(jù)該表，把方案中的直達(dá)、直通列車預(yù)分到各車流樹中，歸各技術(shù)站任務(wù)處理。

2.3.2 開行方案的計算及修正

各技術(shù)站任務(wù)修改樹的邊長矩陣，構(gòu)成無有向回路的有向圖，進(jìn)行車流最佳歸屬計算，全路總?cè)蝿?wù)匯總，根據(jù)計算結(jié)果進(jìn)行方案修正。方案修正分去弧計算與加弧計算(區(qū)段列車不動)。

去弧計算：判斷列車方案中有無某支列車開行不利的情況，即∑nt節(jié)＜cm，去除該支列車，向相關(guān)技術(shù)站任務(wù)發(fā)送重新進(jìn)行車流歸屬計算的信息，去除該支列車后的目標(biāo)值得到優(yōu)化，與該支直達(dá)列車不相關(guān)的技術(shù)站不重算。相關(guān)技術(shù)站任務(wù)計算后計算結(jié)果返回，修改數(shù)據(jù)庫，全路總?cè)蝿?wù)重新匯總結(jié)果。

加弧計算：全路總?cè)蝿?wù)在車流信息庫中查找是否存在單支車流滿足充分條件而未開行直達(dá)列車，即車流表中已標(biāo)識為改編，改開直達(dá)后的節(jié)省時間)。若有，取值最大的一支車流，補開直達(dá)列車，優(yōu)化目標(biāo)值。判定包含所加列車的相關(guān)樹及技術(shù)站，發(fā)送重新進(jìn)行車流歸屬計算的信息。相關(guān)技術(shù)站任務(wù)進(jìn)行加弧計算，再返回結(jié)果，全路總?cè)蝿?wù)重新匯總。自動修正時，如果加弧的去向不在待選去向中提交人工干預(yù)，以后相同問題自動處理。

2.3.3 完成方案的修正和指標(biāo)計算后進(jìn)入下一個方案計算

加弧計算引起車流歸屬的重新分配，因為每支直達(dá)列車在網(wǎng)絡(luò)中的位置及無改編節(jié)省的數(shù)值不同，與相關(guān)的直達(dá)、直通列車既協(xié)作又競爭，所以加弧以后，原來開行的有些直達(dá)列車可能會出現(xiàn)開行不利的情況，于是應(yīng)該重復(fù)去弧過程，進(jìn)一步優(yōu)化目標(biāo)。再檢查加弧條件，如果沒有加弧的可能，該過程就停止，否則重復(fù)這個過程。計算該方案目標(biāo)值，目標(biāo)值達(dá)到滿意指標(biāo)標(biāo)準(zhǔn)則留存，繼續(xù)推算其他方案。

2.3.4 技術(shù)站改編作業(yè)量的計算

在技術(shù)指標(biāo)中，技術(shù)站改編作業(yè)量十分重要，能決定方案可否采用。改編作業(yè)量按到達(dá)列車統(tǒng)計(包括區(qū)段列車)，列車的到站一般已確定上行或下行，改編工作量不難計算。一般情況下折角車流要計算重復(fù)改編作業(yè)量，到達(dá)本站的摘掛車流中存在折角車。

存在通過不同的進(jìn)站線路分別到達(dá)技術(shù)站上行和下行的情況，發(fā)站車流分2個去向集結(jié)，為了計算方便按1支列車計算車流歸屬，把吸引的車流分成2部分，車流庫的結(jié)構(gòu)已考慮這種情況，可以計算出上行及下行的改編工作量。這種情況無重復(fù)改編，發(fā)站的集結(jié)時間應(yīng)加倍計算。減少改編作業(yè)量可以提高車站通過能力。

2.3.5 最終開行方案的確定

全路總?cè)蝿?wù)規(guī)定至少抽取方案數(shù)，規(guī)定目標(biāo)值的最大增幅與已抽取方案數(shù)相比的閾值，當(dāng)小于閾值時結(jié)束計算。提供目標(biāo)值較優(yōu)的若干個方案的經(jīng)濟技術(shù)指標(biāo)，包括目標(biāo)值(∑nt節(jié)- ∑cm)，各技術(shù)站上下行改編車數(shù)、無調(diào)比重，技術(shù)直達(dá)、直通列車列數(shù)及平均通過技術(shù)站數(shù)，車流平均改編次數(shù)等，在經(jīng)濟效益、能力協(xié)調(diào)和提高、直達(dá)水平、車輛運用及可控性等方面進(jìn)行綜合分析比較。要兼顧區(qū)段內(nèi)車流輸送，相鄰技術(shù)站應(yīng)留足編開中間站重點作業(yè)列車的能力，解決區(qū)段通過能力因摘掛車流過大而出現(xiàn)的緊張問題。

經(jīng)過綜合比較分析以后，選擇一個較優(yōu)方案，適當(dāng)調(diào)整，作為最終開行方案，遵循最終開行方案編制各鐵路局集團公司列車編組計劃。

3 貨物列車編組計劃優(yōu)化方法有關(guān)問題說明

（1）全路總?cè)蝿?wù)分成列車開行方案產(chǎn)生及預(yù)分、方案計算及修正、技術(shù)指標(biāo)計算3個任務(wù)，有關(guān)聯(lián)地并行運行。方案計算及修正任務(wù)與幾百個技術(shù)站任務(wù)交替運行，相互觸發(fā)，幾百個技術(shù)站任務(wù)并行運行，建立觸發(fā)機制確保并行任務(wù)同步，化解數(shù)據(jù)庫訪問沖突。技術(shù)站任務(wù)又分總?cè)蝿?wù)和幾個車流樹并行計算任務(wù)。

（2）技術(shù)站編發(fā)能力可以控制，改編能力是否適應(yīng)則要看計算結(jié)果。技術(shù)指標(biāo)詳細(xì)計算任務(wù)，對明顯不可行方案立即淘汰。在結(jié)束階段，對各個方案中幾百個技術(shù)站的能力協(xié)調(diào)程度作模糊綜合評判。貨物列車不固定開行，必須考慮車流波動，列車去向吸引的車流支數(shù)多、車流量大，好控制；勉強夠開行條件的列車去向，難控制。調(diào)度人員對可控性更為關(guān)切，開行方案包括幾千支列車，也采用模糊評判。

（3）全路技術(shù)站劃分車流進(jìn)行車流最佳歸屬計算，可以完成全路車流計算，實現(xiàn)集中編制。為適應(yīng)車流日常波動，鐵路局集團公司編制列車編組計劃時，既要保持開行去向不變，又要在編組內(nèi)容上適當(dāng)調(diào)整，便于實施。同時各鐵路局集團公司之間要在總開行方案框架內(nèi)共同商定分組列車的組織方法，進(jìn)一步挖掘運輸潛力。

（4）本次研究建立的信息系統(tǒng)屬于鐵路運輸管理信息系統(tǒng)，要做好系統(tǒng)整合、信息共享。尤其是十分準(zhǔn)確的貨票信息對計劃車流的推算有較大幫助，本系統(tǒng)提供的信息對全路車流組織有深遠(yuǎn)影響。

4 結(jié)束語

按全路技術(shù)站劃分車流進(jìn)行最佳歸屬計算，實現(xiàn)了列車開行方案的集中編制。優(yōu)化貨物列車開行方案是編制貨物列車編組計劃的關(guān)鍵，運用計算機進(jìn)行集中計算，把必選列車去向和隨機抽取的待選列車去向，組成大量的開行方案進(jìn)行比選，以經(jīng)由節(jié)點標(biāo)識法構(gòu)建車流及列車數(shù)據(jù)庫，為詳細(xì)計算提供依據(jù)。運用直達(dá)列車開行的充分和必要條件檢查修正每個方案，實行多目標(biāo)綜合評價，尋找較優(yōu)方案，尊重經(jīng)驗又不囿于經(jīng)驗，具有可實施性；采用車流樹并行計算，當(dāng)鐵路網(wǎng)增加線路、增減技術(shù)站、調(diào)整重車流徑路時，只需要修改相關(guān)車流樹，具有靈便性。全路集中優(yōu)化涉及許多方面，這里僅作了初步探討，還有許多不足之處，有待于不斷改進(jìn)和完善。