編組站車輛調(diào)度問題研究

劉紅英 婁正良

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

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

1 RVSP數(shù)學(xué)模型

1.1 RVSP目標

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

假設(shè)采樣區(qū)間的開始時間是t0，結(jié)束時間是tE。

以一個二元組來描述車輛

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

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

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

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

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

采用下式來計算該采樣區(qū)間的中時

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

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

1.2 RVSP資源約束

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

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

車輛的這些時間區(qū)間肯定都需要占用線路資源，但有些區(qū)間不需要占用調(diào)機資源的，比如車輛在集結(jié)時。

因此定義集合

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

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

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

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

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

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

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

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

根據(jù)以上定義用下列的等式將線路資源和車輛作業(yè)聯(lián)系起來。

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

同樣可以用下列等式說明車輛作業(yè)和調(diào)機資源的關(guān)系。

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

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

1.3 RVSP出發(fā)列車對車輛要求的約束

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

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

假定在給定的采樣區(qū)間內(nèi)發(fā)出w輛車。

所有出發(fā)列車的關(guān)系集合：

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

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

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

1.4 數(shù)學(xué)模型

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

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

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

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

2 算法與實現(xiàn)

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

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

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

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

2.1 技術(shù)作業(yè)圖表鋪畫法

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

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

2.2 MAS在管理系統(tǒng)設(shè)計與實現(xiàn)中的應(yīng)用[2]

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

對編組站業(yè)務(wù)的分析，以仿真的方式，采用多A gen t[3]系統(tǒng)[4]仿真來組織和實現(xiàn)編組站計劃的自動編排、鋪畫和動態(tài)調(diào)整。

系統(tǒng)通過各個A gen t模擬編組站現(xiàn)場執(zhí)行情況，迭代調(diào)整各項作業(yè)優(yōu)先次序和使用資源，不斷優(yōu)化目標值，最后生成的任務(wù)執(zhí)行次序和資源使用狀況可以通過技術(shù)作業(yè)圖表顯示和調(diào)整。

3 實踐和結(jié)論

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

1）動態(tài)性

由于在建模的過程中充分考慮了采樣區(qū)間的微分和移動的性能。因此，系統(tǒng)能夠根據(jù)車站作業(yè)實時執(zhí)行的過程和用戶參與實時調(diào)整采樣區(qū)間[t0，tE]，并且在新的采樣區(qū)間上重新優(yōu)化，迭代調(diào)整。從而使系統(tǒng)動態(tài)地根據(jù)實際作業(yè)進度和用戶參與調(diào)整后繼的作業(yè)次序和資源分配。

2）實時性

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

因為采用A gen t迭代循環(huán)仿真車站作業(yè)，因此無法保證能夠?qū)崟r地給出最優(yōu)解。因此設(shè)計的Agent會保證每一個解都是可行解，可以執(zhí)行的解。在時間允許的情況下，再用后繼的較優(yōu)解來替代前面的解。

3）可控性

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

用戶也可以很容易操縱后繼的任務(wù)，系統(tǒng)會根據(jù)用戶的參與動態(tài)地重新計算、優(yōu)化。

4）優(yōu)化性

系統(tǒng)在設(shè)計的時候充分考慮到系統(tǒng)的可擴展性和可優(yōu)化型。

可以通過增加、變換A gen t模具的啟發(fā)學(xué)習(xí)的算法來實現(xiàn)業(yè)務(wù)的變遷和增添新業(yè)務(wù)。比如在編組選擇尾部調(diào)機時，目前采用非均衡的尾部調(diào)機算法?？梢愿鶕?jù)需要采用均衡的尾部調(diào)機算法來替代當前算法而實現(xiàn)車站的特殊要求。

隨著系統(tǒng)運行時間的增長，積累歷史數(shù)據(jù)。通過對歷史數(shù)據(jù)的挖掘和分析來優(yōu)化系統(tǒng)運行的參數(shù)矩陣，提高系統(tǒng)的優(yōu)化速度和性能，從而實現(xiàn)系統(tǒng)的離線自學(xué)習(xí)功能。

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

[2]婁正良．編組站CIPS系統(tǒng)的調(diào)度計劃管理[J]．鐵路通信信號工程技術(shù)，2006（4）：8-9

[3]陳森發(fā)．復(fù)雜系統(tǒng)建模理論和方法[M]．南京：東南大學(xué)出版社，2005.

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