編組站車輛調度問題研究

劉紅英 婁正良

（北京全路通信信號研究設計院有限公司，北京 100073）

編組站的車輛調度問題可以描述為對于一系列到達列車，組織合格的出發列車，在滿足一定的約束條件下（比如線路資源，調機資源，編掛條件等），力爭實現一定的目標（如實現編組站最大的吞吐量，調機線路等資源占用最少等），為了和通常的車輛調度問題(VSP)[1]相區別，在這里稱之為鐵路車輛調度問題(RVSP)。

1 RVSP數學模型

1.1 RVSP目標

編組站比較重要的指標是中時和停時，通常編組站的主要任務是車輛的中轉，而裝卸車輛只是比較輔助的業務。因此比較注重中時，在本文的RVSP模型中，將只考慮中時。

假設采樣區間的開始時間是t0，結束時間是tE。

以一個二元組來描述車輛

公式(1)中得V表示車輛，ts表示該車輛的到達時間，te表示該車輛的離去時間。定義下列集合：

公式(2)中S1采樣區間的開始時刻t0車站內有m輛站存車。S2表示采樣區間[t0，tE]在內陸續到達的車輛n輛。S3表示在采樣區間[t0，tE]陸續發出l輛車。

很顯然這個集合滿足公式(3)的關系

則目前需要上報的班中時ΔT′按下式計算，采樣區間為一個班。

公式(4)中的ΔT′主要是根據出發車輛計算的中時。該指標不適合作為RVSP問題的優化目標。因為ΔT′采用較長時間的采樣區間長度（至少一個班）是有意義的，基本上也能反映整個編組站的車輛中轉時間。但可微的性能比較差，當取樣長度不是一個班，而是在逐漸縮小或者取樣區間移動時，該值波動比較大。比如某個取樣長度內沒有發車，則該取樣長度的中時為零。

采用下式來計算該采樣區間的中時

采用公式(5)可以比較準確反映各個采用區間的中時。同時也可以在動態過程中計算中時。

在上面的公式中，每輛車的ts是已知的。采樣區間[t0，tE]是設定的，也可以認為是已知的。但是出發車的輛數l和每輛車的te是未知的。

1.2 RVSP資源約束

在RVSP中重點考慮兩類資源，一類是線路資源，另一類是機車資源。一輛車從到達到出發，需要經歷接車、到達作業、解體、集結、編組、發車等諸多環節，有的車輛還需要重復解體，有些還需要交流，有些還需要特殊調車處理（比如有些車輛不能過峰）。還有些車輛不需要解體集結編組，直接發車。一輛車從到達，到發車，需要一系列的作業，這些作業可以用一系列的時間點來刻畫。因此將上述的二元組表達車輛用下式來表示。

根據公式(6)的車輛表達定義可以用如下集合來表示每一輛車的各個作業的時間區間。

車輛的這些時間區間肯定都需要占用線路資源，但有些區間不需要占用調機資源的，比如車輛在集結時。

因此定義集合

在占用線路或使用調車資源時，是以整個車組為單位占用的。定義車組集合

很顯然，該車組是和車輛的時間片有關系的。因為車輛在不同的時間，屬于不同的車組。不同的車輛，如果在某個時間片屬于同一個車組，則其時間片相同。如下式所示：假設Sam表示時間片（ta，ta+1）的某個車組

上式中的時間片沒有涉及線路、調機，是因為車輛的某一個時間片肯定只屬于一個調機或線路。因此該車組所表示的時間片也只能和一條線路或調機相關。

每一條線路可以用車組占用的時間片來表示

對于線路存在如下約束，就是一條線路不可以同時被兩個車組使用。即滿足下面的兩個約束

公式(12)中第一個公式表示線路在某個時間片中只能被一個車組占用。比如一條線路有一個車組時，不能再接車或作為機車轉移使用。公式(12)第二個公式表示線路最多是滿占用時間，比如在某個采樣區間中，一條線路上的車組都在占用。則第二個公式取等號。

同樣對于調機也可以用車組占用的時間片來表示

同樣上面的公式表示機車在某個時間片中只能被一個車組占用。比如機車不可能同時解體兩列車。

根據以上定義用下列的等式將線路資源和車輛作業聯系起來。

LNUM表示編組站的所有線路資源的數量。上式表明所有的車輛在任何狀態下都需要占用線路資源，包括車輛在機車上，也需要占用線路資源。

同樣可以用下列等式說明車輛作業和調機資源的關系。

MNUM表示編組站的所有機車資源的數量。調機和線路不同，車輛只有需要移動時，才需要調機資源。而這些活動需要機車資源可以作為已知量輸入。

實際上機車和線路自身會有一些時間片用于自身的活動。比如線路停用，那么該條線路在停用期間，是和車輛的時間片沒有直接關系。機車也會有一些機車作業，如機車上油等作業。在RVSP模型中，也可以加上這些活動約束。在本文的數學建模中，忽略這些作業。但在實現時，沒有忽略。

1.3 RVSP出發列車對車輛要求的約束

從編組站發出的列車首先要符合下達的階段計劃要求，另外還要符合編掛條件約束。這一點反映車輛的時間片序列上，有的車輛多，有的車輛少。另外，也是產生所有鉤計劃的約束條件。

在前面描述RVSP目標時，定義列車是一系列車輛的集合。但實際上車輛在列車上是有次序的。需要增加一個關系R來表達這種車輛在列車上的前后次序。

假定在給定的采樣區間內發出w輛車。

所有出發列車的關系集合：

假定Ri表示附加在第i輛出發列車上的關系，第i輛車的編掛要求是Ψi，則Ri必須符合給定的編掛要求Ψi，即

每一列出發列車的編掛要求是已知的。而到達列車的關系是已知的。如何從已知的關系中進行拆分、組合成新的關系，并且新的關系滿足編掛條件的約束。這是編組站所有活動的依據和根本目標。

目前沒有將該目標作為RVSP的目標。因為該目標首先必須滿足，其次它的彈性僅僅表現在滿足編掛要求的前提下，選擇一個比較好的關系。實際上是編組高質列車，減輕后繼的車站作業負擔，但這種彈性通常會和車站本身的中時相矛盾。因此在本文中不將它列為RVSP的目標。

1.4 數學模型

根據前面對目標和約束的討論，RVSP的數學模型可以描述如下：假定給定的采樣區間是[t0，tE]。

公式(20)中字符的含義參見前文。

實際上編組站的資源還包括一大類資源，即人力資源。在該模型中假設這類資源無窮大，不予考慮。

站形分布、車輛占線規則、調機使用規則、本務機接續、調度命令等也可以算作約束。該模型為了簡化起見，也沒有包含這些規則約束。

2 算法與實現

如果以車輛為單位，基本上一輛車進站后經過接車、到達作業、解體、集結、編組、發車這些作業。但不是每一輛車都是這樣，有些需要重復解體，而有些可能需要站修。因此有些車輛可能會經歷重復解體，交流等作業。

圖1簡單地表達接4輛車，發四輛車的經過。圓圈表示列車的作業節點(到、解、集、編、發)，黑色線條表示車輛流動的方向，虛線條表示機車使用接續，即因為使用機車資源而使這些節點發生次序關系。淺黑色線條表示峰位或正線使用接續。這些連接線中還不包括停車線，走行線等關系。

中間的黑色粗黑線表示到達列車和出發列車的車輛對應關系。實際上到達列車和出發列車的車輛是多對多的關系，一輛到達列車的車輛需要解體到多列出發列車中去，而一輛出發列車則是由多個到達列車解體形成的。如果忽略虛線、淺黑色線條，可以將上圖看成是一個二部圖。

實際上編組站不斷有到達列車和出發列車。并且作業節點也遠比圖1所示的多。因此，所有的節點構成的圖是比圖1復雜得多的無始無終的圖。RVSP的問題復雜性大，沒有好的多項式算法。目前現狀是在這個大問題下有很多子問題的算法。比如車輛選編算法，調機任務分配算法等。

2.1 技術作業圖表鋪畫法

眾所周知，運輸問題的作業圖表法是一種有效的標準算法。目前所有的手工編制計劃的方式都是通過作業圖表的鋪畫完成。

各種作業以圖形的方式反映在圖表上，比較直觀。圖2是成都北技術作業圖表。各個站會因為站形和具體業務的差異而有所不同。圖中橫坐標是時間軸。縱向是機車和線路資源。在這張圖表上比較直接地反映各項作業對線路和機車的占用。也可以間接地反映車輛流動方向。沿著技術作業圖表鋪畫，可以自然地保證機車，線路分時復用，不重疊，即滿足公式(15)和公式(16)。

2.2 MAS在管理系統設計與實現中的應用[2]

RVSP問題涉及面寬，關系錯綜復雜。很難用算法來一次性解決所有問題。在本文中，首先嘗試將問題分解成一個個的個體。通過分層，分批地解決個體問題，進而解決全局的問題。

對編組站業務的分析，以仿真的方式，采用多A gen t[3]系統[4]仿真來組織和實現編組站計劃的自動編排、鋪畫和動態調整。

系統通過各個A gen t模擬編組站現場執行情況，迭代調整各項作業優先次序和使用資源，不斷優化目標值，最后生成的任務執行次序和資源使用狀況可以通過技術作業圖表顯示和調整。

3 實踐和結論

目前基于M A S仿真的啟發式算法解決的RVSP問題的系統在成都北編組站正式運行，運行效果良好。系統通過單個智能A gen t的相對簡單的決策和調整，從整體上實現整個RVSP問題的解決。具有以下特點。

1）動態性

由于在建模的過程中充分考慮了采樣區間的微分和移動的性能。因此，系統能夠根據車站作業實時執行的過程和用戶參與實時調整采樣區間[t0，tE]，并且在新的采樣區間上重新優化，迭代調整。從而使系統動態地根據實際作業進度和用戶參與調整后繼的作業次序和資源分配。

2）實時性

由于成都北C IPS系統中有計劃直接指揮下層的控制系統，因此需要有很強的實時性。由于前述的動態性，使得實時性具有可能。

因為采用A gen t迭代循環仿真車站作業，因此無法保證能夠實時地給出最優解。因此設計的Agent會保證每一個解都是可行解，可以執行的解。在時間允許的情況下，再用后繼的較優解來替代前面的解。

3）可控性

系統通過多種方式自動求解，將結果反映給客戶，視覺上的有技術作業圖表、列車表、毛玻璃、鉤計劃和站場表示等，聽覺上語音提示和語音報警等。用戶很容易得到系統后面的任務進展情況。

用戶也可以很容易操縱后繼的任務，系統會根據用戶的參與動態地重新計算、優化。

4）優化性

系統在設計的時候充分考慮到系統的可擴展性和可優化型。

可以通過增加、變換A gen t模具的啟發學習的算法來實現業務的變遷和增添新業務。比如在編組選擇尾部調機時，目前采用非均衡的尾部調機算法。可以根據需要采用均衡的尾部調機算法來替代當前算法而實現車站的特殊要求。

隨著系統運行時間的增長，積累歷史數據。通過對歷史數據的挖掘和分析來優化系統運行的參數矩陣，提高系統的優化速度和性能，從而實現系統的離線自學習功能。

[1]教材編寫組．運籌學[M]．3版．北京：清華大學出版社，2005.

[2]婁正良．編組站CIPS系統的調度計劃管理[J]．鐵路通信信號工程技術，2006（4）：8-9

[3]陳森發．復雜系統建模理論和方法[M]．南京：東南大學出版社，2005.

[4]馮珊，唐超，閔君，等．用于復雜系統建模與仿真的面向智能體技術[J]．管理科學學報，1999，2（2）：71-76.