車站調(diào)車鉤計(jì)劃算法模型及自動(dòng)編制系統(tǒng)優(yōu)化

張穎波 上海鐵路局浙江鐵道集團(tuán)

1 調(diào)車鉤計(jì)劃編制的現(xiàn)狀與問(wèn)題

統(tǒng)計(jì)資料顯示，鐵路貨車在一次周轉(zhuǎn)中，要經(jīng)過(guò)多次調(diào)車作業(yè)，并要占用大量的人員、設(shè)備，消耗大量的燃材料，其費(fèi)用約占鐵路運(yùn)營(yíng)開(kāi)支的1/4。貨車由第一次裝車至第二次裝車的周轉(zhuǎn)時(shí)間中，在裝卸站和技術(shù)站的停留時(shí)間約占70%，其中花在編組站、區(qū)段站的停時(shí)約占40%。一次貨車作業(yè)平均停時(shí)17 h 左右，有調(diào)中轉(zhuǎn)7 h。若一次貨車作業(yè)平均停時(shí)壓縮1 h，有調(diào)中轉(zhuǎn)壓縮0.5 h，可壓縮貨車周轉(zhuǎn)時(shí)間0.16天，可節(jié)省運(yùn)用車1.3 萬(wàn)多輛，直接經(jīng)濟(jì)效益達(dá)15 億元。由此可見(jiàn)，高質(zhì)量的調(diào)車作業(yè)、對(duì)加速機(jī)車車輛周轉(zhuǎn)、提高運(yùn)輸效率、增強(qiáng)運(yùn)輸能力、降低運(yùn)輸成本、保證運(yùn)輸安全具有十分重要的作用。

車站作業(yè)計(jì)劃的優(yōu)化編制一直是鐵路運(yùn)輸組織工作的重要組成部分。調(diào)車作業(yè)計(jì)劃的編制水平在很大程度上決定了運(yùn)輸效率的好壞。我國(guó)擁有80%的中間站，調(diào)車鉤計(jì)劃還靠人工編制來(lái)實(shí)現(xiàn)，車站在獲取列車確報(bào)后，由人工編制調(diào)車鉤計(jì)劃，再輸入到TMIS 系統(tǒng)中，并在執(zhí)行過(guò)程中，由人工動(dòng)態(tài)輸入和修改相關(guān)調(diào)車信息，并依賴"毛玻璃"手工更新車站現(xiàn)車的位置及狀態(tài)的變化。

造成這種現(xiàn)象的主要原因是中間站的站場(chǎng)結(jié)構(gòu)類型多，調(diào)車方式靈活，影響編制調(diào)車計(jì)劃的限制因素復(fù)雜，人工編制調(diào)車鉤計(jì)劃，單憑個(gè)人經(jīng)驗(yàn)，編制方法、質(zhì)量因人而異。而且大部分中間站的調(diào)車任務(wù)是由本務(wù)機(jī)完成，對(duì)調(diào)車計(jì)劃的編制質(zhì)量要求高，編制速度要求快，使得計(jì)算機(jī)自動(dòng)編制中間站調(diào)車鉤計(jì)劃問(wèn)題一直難以得到解決。

2 調(diào)車方法的優(yōu)選及算法模型

所謂編制車站調(diào)車鉤計(jì)劃，是指當(dāng)車站一批作業(yè)任務(wù)已確定的條件下，編制人員根據(jù)車站的線路結(jié)構(gòu)、車輛位置、各種作業(yè)時(shí)間要求等因素，編制調(diào)車作業(yè)計(jì)劃并在保證各車輛最終移動(dòng)至指定位置條件下，使整個(gè)調(diào)車過(guò)程的作業(yè)效率最高。由于不同的編制方法、不同的調(diào)車方式、不同的站場(chǎng)股道運(yùn)用，可以編出很多的調(diào)車作業(yè)方案，當(dāng)車站調(diào)車任務(wù)多，運(yùn)用車集中時(shí)，編制調(diào)車計(jì)劃的難度很大。

2.1 調(diào)車方法的優(yōu)選

按調(diào)車方法分類有統(tǒng)籌調(diào)車法、消逆法、分析計(jì)算法、基數(shù)排序調(diào)車法等都是基于統(tǒng)籌對(duì)口調(diào)車法。選編調(diào)車作業(yè)的實(shí)質(zhì)就是消除逆，最快的消逆過(guò)程，就是最優(yōu)的調(diào)車作業(yè)過(guò)程。在保證連掛鉤最少，對(duì)溜放鉤進(jìn)行優(yōu)化，并尋找各車組的有利下落位置。

調(diào)車作業(yè)計(jì)劃的編制要求盡可能提高調(diào)車作業(yè)效率，減少作業(yè)時(shí)間。而調(diào)車作業(yè)效率主要是由：作業(yè)過(guò)程中發(fā)生的連掛鉤數(shù)、溜放鉤數(shù)以及作業(yè)過(guò)程中的帶動(dòng)車輛數(shù)等因素決定。

在以往編制調(diào)車作業(yè)計(jì)劃時(shí)，首先要進(jìn)行的就是"車組下落"，即為了調(diào)整順序，把待編車列中的反順序車組分解到不同線路上，而后根據(jù)車組下落的情況進(jìn)行"合并下落列"等步驟來(lái)得到調(diào)車方案。不同的車組下落方案對(duì)應(yīng)著不同的調(diào)車方案。因此，車組下落情況，對(duì)調(diào)車方案的優(yōu)劣有重要的影響。采用分析計(jì)算法依據(jù)合列有利性原理，對(duì)各種下落列數(shù)的全部調(diào)車方案按對(duì)口子系統(tǒng)進(jìn)行優(yōu)化組合，產(chǎn)生各方案組的待選方案集，刪除其中的必然不利方案，由各方案組的最優(yōu)變異方案組成經(jīng)過(guò)優(yōu)化的比選方案集，然后綜合考慮調(diào)車鉤數(shù)和帶動(dòng)輛數(shù)對(duì)調(diào)車作業(yè)時(shí)間的影響，計(jì)算出各比選方案的換算溜放鉤數(shù)，從而獲得最佳方案。

2.2 最優(yōu)車組排序的圖論模型

求一個(gè)有向圖的最小Hamiltom 路是一個(gè)NP 困難問(wèn)題，當(dāng)車組數(shù)較大時(shí)，一般很難求最大優(yōu)解。但是，待編車列生成的有向圖具有一定的特殊性，由于編組有站順要求，因此所求的Hamiltom 路具有如下特征：只有當(dāng)同一個(gè)到達(dá)站的車組節(jié)點(diǎn)全部經(jīng)過(guò)后，才能進(jìn)入下一個(gè)到達(dá)站的車組節(jié)點(diǎn)；而當(dāng)同一個(gè)到達(dá)站的車組節(jié)點(diǎn)的進(jìn)入節(jié)點(diǎn)和離開(kāi)節(jié)點(diǎn)確定后，根據(jù)生成圖的弧長(zhǎng)取值可知，通過(guò)所有該到達(dá)站節(jié)點(diǎn)的最小Hamiltom 路的次序必定是第一個(gè)點(diǎn)為進(jìn)入節(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn)為離開(kāi)節(jié)點(diǎn)。而其它節(jié)點(diǎn)的次序與在原車列中的排列次序相同。按照此 方法即可將問(wèn)題轉(zhuǎn)化為最短路問(wèn)題，而最短路問(wèn)題則很容易求解。

例如：原車組排列為3 .4 .1.2 .1.2 .3.4, 即第一站的次序?yàn)?，5；第二站的次序?yàn)?，6；第三站的次序?yàn)?，7；第四站的位置為2，8。構(gòu)造最短路圖見(jiàn)圖1。從節(jié)點(diǎn)0 到節(jié)點(diǎn)9 的最短路為5, 3, 4, 6, 7, 1, 2, 8?？偮烽L(zhǎng)為（3,4），即為3 掛鉤4 摘鉤。

圖1 構(gòu)造最短路圖

2.3 最優(yōu)解的判定

為解決動(dòng)態(tài)規(guī)劃中每一階段各種狀態(tài)的最優(yōu)指標(biāo)函數(shù)值必須通過(guò)遞歸計(jì)算得到，并且需要有足夠的空間存儲(chǔ)這些值的困難，以及克服位勢(shì)法容易陷入局部最優(yōu)解和沒(méi)有考慮階段轉(zhuǎn)移費(fèi)用等問(wèn)題。將位勢(shì)法與動(dòng)態(tài)規(guī)劃法相結(jié)合，設(shè)計(jì)一種求最優(yōu)調(diào)車鉤計(jì)劃的隱枚舉搜索算法。由于在求調(diào)車鉤計(jì)劃隱枚舉搜索算法中，每次循環(huán)都是找當(dāng)前狀態(tài)集中綜合指標(biāo)最小的車組布局進(jìn)行下一步的移動(dòng)，而且狀態(tài)集和比選方案集的規(guī)模都不會(huì)超過(guò)枚舉規(guī)則M，因此算法的復(fù)雜度是Mn2，其中n 是本批調(diào)車任務(wù)需移動(dòng)車組數(shù)。該方法是一個(gè)高效的算法，不僅速度快，而且當(dāng)M 足夠大時(shí)，能保證求得在綜合意義上的最優(yōu)解。

3 調(diào)車鉤計(jì)劃編制優(yōu)化功能

調(diào)車鉤計(jì)劃優(yōu)化編制系統(tǒng)主要完成對(duì)車站調(diào)車作業(yè)的管理（包括車站圖形顯示、接發(fā)列車、編制調(diào)車計(jì)劃、執(zhí)行和回放調(diào)車作業(yè)、數(shù)據(jù)統(tǒng)計(jì)分析），各種相關(guān)信息的錄入和查詢。

3.1 系統(tǒng)設(shè)計(jì)思路

系統(tǒng)啟動(dòng)后，自動(dòng)連接遠(yuǎn)程TMIS 系統(tǒng)數(shù)據(jù)庫(kù)，并實(shí)時(shí)讀取數(shù)據(jù)用于初始化本地?cái)?shù)據(jù)庫(kù)，使本地與遠(yuǎn)程數(shù)據(jù)庫(kù)信息同步。初始化完成后，在系統(tǒng)主界面顯示車站的當(dāng)前車輛分布情況，列車的編組信息在到達(dá)本站前已發(fā)送到本站，本系統(tǒng)根據(jù)到確報(bào)信息安排接車作業(yè)，出發(fā)列車要安排發(fā)車作業(yè)，車列在本站逗留期間可能要進(jìn)行多項(xiàng)作業(yè)，根據(jù)列車的不同去向，將車列按照一定要求分組，再編組調(diào)車鉤計(jì)劃，打印下達(dá)調(diào)車作業(yè)任務(wù)，現(xiàn)場(chǎng)依據(jù)調(diào)車計(jì)劃通知單，按順序?qū)④囕v送到指定股道，并且在系統(tǒng)中完成對(duì)調(diào)車作業(yè)過(guò)程模擬和執(zhí)行過(guò)程的回放，同時(shí)對(duì)于系統(tǒng)中的數(shù)據(jù)提供查詢和管理功能。

3.2 系統(tǒng)功能模塊

中間站調(diào)車鉤計(jì)劃自動(dòng)優(yōu)化編制系統(tǒng)主要涵蓋七大功能。

3.2.1 現(xiàn)車信息動(dòng)態(tài)查詢和統(tǒng)計(jì)功能

本系統(tǒng)能夠?qū)崿F(xiàn)與TMIS 系統(tǒng)的連接，自動(dòng)實(shí)時(shí)讀取數(shù)據(jù)庫(kù)數(shù)據(jù)，并可以根據(jù)需要顯示不同的詳細(xì)信息。如現(xiàn)在車狀態(tài)的信息查詢與屏幕顯示、超時(shí)停留車、關(guān)門(mén)車信息查詢與顯示等，可顯示現(xiàn)場(chǎng)的防溜措施，股道現(xiàn)車查詢完全替代"毛玻璃"功能，還可以按要求顯示各車輛的重量、車種、品名、噸位、收貨人等詳細(xì)信息，并有現(xiàn)在車進(jìn)行車輛數(shù)和停留時(shí)間統(tǒng)計(jì)。

3.2.2 鉤計(jì)劃自動(dòng)編制功能

系統(tǒng)內(nèi)置鉤計(jì)劃編制的優(yōu)化模型與算法，可自動(dòng)讀取TMIS 系統(tǒng)的相關(guān)數(shù)據(jù)，根據(jù)設(shè)定的優(yōu)化限制條件自動(dòng)編制調(diào)車鉤計(jì)劃，并可根據(jù)實(shí)際需要對(duì)鉤計(jì)劃施行人工調(diào)整，并智能添加備注欄信息。

3.2.3 圖形編制鉤計(jì)劃（人機(jī)對(duì)話式編制）功能

操作人員可以通過(guò)系統(tǒng)所顯示的股道現(xiàn)車圖形，通過(guò)鼠標(biāo)拖動(dòng)車組位置來(lái)編制鉤計(jì)劃，使編制調(diào)車計(jì)劃過(guò)程直觀化。

3.2.4 調(diào)車作業(yè)動(dòng)態(tài)模擬功能

系統(tǒng)可模擬站內(nèi)發(fā)生的調(diào)車和接發(fā)列車作業(yè)情況并可觀察各時(shí)段、各操作所引起的站場(chǎng)內(nèi)現(xiàn)車情況的變化，在作業(yè)之前對(duì)作業(yè)有直觀的了解。

3.2.5 大屏顯示功能

系統(tǒng)可以實(shí)現(xiàn)全屏顯示。并能用鼠標(biāo)拖拉來(lái)實(shí)現(xiàn)畫(huà)面的放大縮小，解決"毛玻璃"不能實(shí)現(xiàn)的效果，同時(shí)也可以根據(jù)需要對(duì)顏色設(shè)置。

3.2.6 作業(yè)回顧和歷史操作回放功能

系統(tǒng)能對(duì)本班操作已執(zhí)行的鉤計(jì)劃進(jìn)行回推操作。同時(shí)對(duì)已完成鉤計(jì)劃進(jìn)行回放顯示每鉤操作前后站場(chǎng)的現(xiàn)車情況，對(duì)歷史操作進(jìn)行跟蹤。

3.2.7 作業(yè)計(jì)劃單打印輸出功能

智能打印鉤計(jì)劃作業(yè)通知單，可根據(jù)打印紙張大小自動(dòng)排版，并自動(dòng)插入調(diào)車作業(yè)期間通過(guò)本站的旅客列車信息。