劉紅英 婁正良

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

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

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

1.1 RVSP目標(biāo)

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

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

以一個(gè)二元組來描述車輛

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

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

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

則目前需要上報(bào)的班中時(shí)ΔT′按下式計(jì)算，采樣區(qū)間為一個(gè)班。

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

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

采用公式(5)可以比較準(zhǔn)確反映各個(gè)采用區(qū)間的中時(shí)。同時(shí)也可以在動(dòng)態(tài)過程中計(jì)算中時(shí)。

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

1.2 RVSP資源約束

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

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

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

因此定義集合

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

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

上式中的時(shí)間片沒有涉及線路、調(diào)機(jī)，是因?yàn)檐囕v的某一個(gè)時(shí)間片肯定只屬于一個(gè)調(diào)機(jī)或線路。因此該車組所表示的時(shí)間片也只能和一條線路或調(diào)機(jī)相關(guān)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 算法與實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)踐和結(jié)論

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

1）動(dòng)態(tài)性

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

2）實(shí)時(shí)性

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

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

3）可控性

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

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

4）優(yōu)化性

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

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

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

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

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

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

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