車站調車鉤計劃算法模型及自動編制系統優化

張穎波 上海鐵路局浙江鐵道集團

1 調車鉤計劃編制的現狀與問題

統計資料顯示，鐵路貨車在一次周轉中，要經過多次調車作業，并要占用大量的人員、設備，消耗大量的燃材料，其費用約占鐵路運營開支的1/4。貨車由第一次裝車至第二次裝車的周轉時間中，在裝卸站和技術站的停留時間約占70%，其中花在編組站、區段站的停時約占40%。一次貨車作業平均停時17 h 左右，有調中轉7 h。若一次貨車作業平均停時壓縮1 h，有調中轉壓縮0.5 h，可壓縮貨車周轉時間0.16天，可節省運用車1.3 萬多輛，直接經濟效益達15 億元。由此可見，高質量的調車作業、對加速機車車輛周轉、提高運輸效率、增強運輸能力、降低運輸成本、保證運輸安全具有十分重要的作用。

車站作業計劃的優化編制一直是鐵路運輸組織工作的重要組成部分。調車作業計劃的編制水平在很大程度上決定了運輸效率的好壞。我國擁有80%的中間站，調車鉤計劃還靠人工編制來實現，車站在獲取列車確報后，由人工編制調車鉤計劃，再輸入到TMIS 系統中，并在執行過程中，由人工動態輸入和修改相關調車信息，并依賴"毛玻璃"手工更新車站現車的位置及狀態的變化。

造成這種現象的主要原因是中間站的站場結構類型多，調車方式靈活，影響編制調車計劃的限制因素復雜，人工編制調車鉤計劃，單憑個人經驗，編制方法、質量因人而異。而且大部分中間站的調車任務是由本務機完成，對調車計劃的編制質量要求高，編制速度要求快，使得計算機自動編制中間站調車鉤計劃問題一直難以得到解決。

2 調車方法的優選及算法模型

所謂編制車站調車鉤計劃，是指當車站一批作業任務已確定的條件下，編制人員根據車站的線路結構、車輛位置、各種作業時間要求等因素，編制調車作業計劃并在保證各車輛最終移動至指定位置條件下，使整個調車過程的作業效率最高。由于不同的編制方法、不同的調車方式、不同的站場股道運用，可以編出很多的調車作業方案，當車站調車任務多，運用車集中時，編制調車計劃的難度很大。

2.1 調車方法的優選

按調車方法分類有統籌調車法、消逆法、分析計算法、基數排序調車法等都是基于統籌對口調車法。選編調車作業的實質就是消除逆，最快的消逆過程，就是最優的調車作業過程。在保證連掛鉤最少，對溜放鉤進行優化，并尋找各車組的有利下落位置。

調車作業計劃的編制要求盡可能提高調車作業效率，減少作業時間。而調車作業效率主要是由：作業過程中發生的連掛鉤數、溜放鉤數以及作業過程中的帶動車輛數等因素決定。

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

2.2 最優車組排序的圖論模型

求一個有向圖的最小Hamiltom 路是一個NP 困難問題，當車組數較大時，一般很難求最大優解。但是，待編車列生成的有向圖具有一定的特殊性，由于編組有站順要求，因此所求的Hamiltom 路具有如下特征：只有當同一個到達站的車組節點全部經過后，才能進入下一個到達站的車組節點；而當同一個到達站的車組節點的進入節點和離開節點確定后，根據生成圖的弧長取值可知，通過所有該到達站節點的最小Hamiltom 路的次序必定是第一個點為進入節點，最后一個節點為離開節點。而其它節點的次序與在原車列中的排列次序相同。按照此 方法即可將問題轉化為最短路問題，而最短路問題則很容易求解。

例如：原車組排列為3 .4 .1.2 .1.2 .3.4, 即第一站的次序為3，5；第二站的次序為4，6；第三站的次序為1，7；第四站的位置為2，8。構造最短路圖見圖1。從節點0 到節點9 的最短路為5, 3, 4, 6, 7, 1, 2, 8。總路長為（3,4），即為3 掛鉤4 摘鉤。

圖1 構造最短路圖

2.3 最優解的判定

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

3 調車鉤計劃編制優化功能

調車鉤計劃優化編制系統主要完成對車站調車作業的管理（包括車站圖形顯示、接發列車、編制調車計劃、執行和回放調車作業、數據統計分析），各種相關信息的錄入和查詢。

3.1 系統設計思路

系統啟動后，自動連接遠程TMIS 系統數據庫，并實時讀取數據用于初始化本地數據庫，使本地與遠程數據庫信息同步。初始化完成后，在系統主界面顯示車站的當前車輛分布情況，列車的編組信息在到達本站前已發送到本站，本系統根據到確報信息安排接車作業，出發列車要安排發車作業，車列在本站逗留期間可能要進行多項作業，根據列車的不同去向，將車列按照一定要求分組，再編組調車鉤計劃，打印下達調車作業任務，現場依據調車計劃通知單，按順序將車輛送到指定股道，并且在系統中完成對調車作業過程模擬和執行過程的回放，同時對于系統中的數據提供查詢和管理功能。

3.2 系統功能模塊

中間站調車鉤計劃自動優化編制系統主要涵蓋七大功能。

3.2.1 現車信息動態查詢和統計功能

本系統能夠實現與TMIS 系統的連接，自動實時讀取數據庫數據，并可以根據需要顯示不同的詳細信息。如現在車狀態的信息查詢與屏幕顯示、超時停留車、關門車信息查詢與顯示等，可顯示現場的防溜措施，股道現車查詢完全替代"毛玻璃"功能，還可以按要求顯示各車輛的重量、車種、品名、噸位、收貨人等詳細信息，并有現在車進行車輛數和停留時間統計。

3.2.2 鉤計劃自動編制功能

系統內置鉤計劃編制的優化模型與算法，可自動讀取TMIS 系統的相關數據，根據設定的優化限制條件自動編制調車鉤計劃，并可根據實際需要對鉤計劃施行人工調整，并智能添加備注欄信息。

3.2.3 圖形編制鉤計劃（人機對話式編制）功能

操作人員可以通過系統所顯示的股道現車圖形，通過鼠標拖動車組位置來編制鉤計劃，使編制調車計劃過程直觀化。

3.2.4 調車作業動態模擬功能

系統可模擬站內發生的調車和接發列車作業情況并可觀察各時段、各操作所引起的站場內現車情況的變化，在作業之前對作業有直觀的了解。

3.2.5 大屏顯示功能

系統可以實現全屏顯示。并能用鼠標拖拉來實現畫面的放大縮小，解決"毛玻璃"不能實現的效果，同時也可以根據需要對顏色設置。

3.2.6 作業回顧和歷史操作回放功能

系統能對本班操作已執行的鉤計劃進行回推操作。同時對已完成鉤計劃進行回放顯示每鉤操作前后站場的現車情況，對歷史操作進行跟蹤。

3.2.7 作業計劃單打印輸出功能

智能打印鉤計劃作業通知單，可根據打印紙張大小自動排版，并自動插入調車作業期間通過本站的旅客列車信息。