婁正良

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

0 引言

編組站主要辦理貨物列車的到達、解體、集結(jié)、編組、發(fā)車等技術(shù)作業(yè)，中轉(zhuǎn)、裝卸等貨運業(yè)務(wù)以及部分客車的到達、出發(fā)等客運業(yè)務(wù)。車站行車業(yè)務(wù)主要包括接發(fā)列車作業(yè)和調(diào)車作業(yè)；在作業(yè)組織上，包括到發(fā)線運用、階段計劃編制、調(diào)車作業(yè)計劃編制、進路準備等內(nèi)容。

編組站作業(yè)是多工種、多單位協(xié)調(diào)合作的作業(yè)，所有作業(yè)都需要預(yù)先有計劃［1］。目前編組站的計劃種類有班計劃、階段計劃、調(diào)車運用計劃、本務(wù)機接續(xù)計劃。所有這些計劃都是遠期的（3～4 h），對實際作業(yè)有指導(dǎo)作用，然而并不能直接用于實際作業(yè)，在實際作業(yè)中，還需要值班員和調(diào)度員根據(jù)站場場景靈活決定每個作業(yè)使用的進路、調(diào)車、作業(yè)次序和方式。這種作業(yè)完全依賴作業(yè)人員現(xiàn)場發(fā)揮的特點正是目前計劃體系的不足。

婁正良［2］研究與機車走行關(guān)聯(lián)的局部作業(yè)優(yōu)化方式；史峰等在到發(fā)線運用方案確定的前提下，從不同角度研究進路排列優(yōu)化問題［3-5］；陳彥等對列車占用到發(fā)線和道岔進行相容性約束，以減少約束條件［6-7］；其中文獻[6]設(shè)計模擬退火算法在極大可行解范圍內(nèi)搜索，大幅縮小了求解范圍；喬瑞軍等針對客運專線列車運行圖編制階段的到發(fā)線運用問題，構(gòu)建多目標優(yōu)化模型，提出基于目標協(xié)調(diào)優(yōu)化思想的求解方法，求得到發(fā)線運用方案可以使列車站內(nèi)走行時間最少、到發(fā)線使用更均衡，從而使車站接發(fā)車作業(yè)效率更高，但沒有考慮到接發(fā)車進路有多條選擇時，如何將進路選擇與到發(fā)線運用協(xié)調(diào)優(yōu)化問題［8-9］；朱亮等［10］將到發(fā)線運用與進路選擇作為一個多層次約束條件動態(tài)規(guī)劃問題，根據(jù)運營要求約束、到發(fā)線功能約束、后效性約束和優(yōu)化條件約束，逐步縮小搜索范圍，得到局部最優(yōu)解，但此模型基于動車組假設(shè)，不能應(yīng)用于普通列車，并且不適用于上下行站場連通的情況。

在給定編組站站型結(jié)構(gòu)和階段計劃確定的前提下，充分高效地利用站內(nèi)設(shè)備，完成貨物列車運輸組織。在進路與到發(fā)線資源不相擾，并且滿足到發(fā)線使用偏好的約束條件下，以車站各項作業(yè)等待時間二階距之和最小為優(yōu)化目標，建立數(shù)學(xué)模型，可以較好地解決運輸組織優(yōu)化問題。且通過建立數(shù)學(xué)模型，利用計算機可解決模擬運輸中人工模擬的繁瑣和不準確問題。

1 編組站作業(yè)

1.1 作業(yè)描述

編組站作業(yè)主要有貨物列車的解體和編組，本務(wù)機換掛、出入段，貨物車輛的取送等業(yè)務(wù)，可作如下劃分：

（1）終到列車的列車到達、技術(shù)作業(yè)、列車解體；

（2）始發(fā)列車的集結(jié)、編組、技術(shù)作業(yè)、列車出發(fā)；

（3）通過列車的列車到達、站內(nèi)通過、列車出發(fā)；

（4）本務(wù)機入段、出段、立折；

（5）專用線、車輛段、機務(wù)段等車輛取送作業(yè)；

（6）車輛重復(fù)解體、取送交流。

編組站的作業(yè)基本上都是由以上各類作業(yè)交織在一起，形成錯綜復(fù)雜的作業(yè)網(wǎng)絡(luò)。假定車站在一個階段的作業(yè)都由階段計劃確定，以下并不討論這些作業(yè)做不做，而是討論怎么做，即關(guān)注這些作業(yè)的次序、路徑、停車點的位置等。并且主要關(guān)注這些作業(yè)對資源的獨占性，據(jù)此建立模型，如技術(shù)作業(yè)，主要考察對股道的占用，而不考慮作業(yè)人員的分派和占用。

為了便于計算機處理，將上述的所有作業(yè)切分成具有邏輯意義的獨立作業(yè)單元，以ψ來表示1個作業(yè)單元：

式中：Ψs為ψ開始前驅(qū)作業(yè)集合，即必須等Ψs都完成后ψ才可以開始；Ψe為ψ的結(jié)束前驅(qū)作業(yè)集合，即必須等Ψe都完成后ψ才可以結(jié)束；Γ為作業(yè)類型，名稱表征該作業(yè)單元的實際意義，在系統(tǒng)中用于打印和輸出；V為作業(yè)單元的作業(yè)序列，該作業(yè)序列中的元素稱為作業(yè)節(jié)點υi，每個作業(yè)序列節(jié)點可以用1個四元組來表示。

式中：tsi為作業(yè)節(jié)點的開始時間；tei為作業(yè)節(jié)點的結(jié)束時間；ri為作業(yè)路徑資源，可以認為是1 組進路的組合；ξj為需要獨占的資源，在編組站內(nèi)是指調(diào)車，但對于解體鉤計劃，并且采用雙推單溜的編組站，獨占資源還包括駝峰資源。

作業(yè)單元拆成1 個作業(yè)序列，該作業(yè)序列有2 個特殊的作業(yè)節(jié)點，分別是開始作業(yè)節(jié)點υ0和結(jié)束節(jié)點υn+1。υ0為該作業(yè)單元可以開始的標記，受制于Ψs，如果沒有限制，那么可以取一個合適的值，如班計劃開始時間，從后面的模型中看出，對于沒有限制開始的節(jié)點，取值對結(jié)果影響很小。作業(yè)節(jié)點υn+1為作業(yè)單元結(jié)束的標記，受制于Ψe。這2個特殊節(jié)點的ri和ξi為空，即ri=φ。作業(yè)單元中的作業(yè)節(jié)點必須順序執(zhí)行，每個作業(yè)節(jié)點一旦開始，就必須一次性執(zhí)行完，即作業(yè)節(jié)點是作業(yè)執(zhí)行中的不能拆分的原子操作。1個單元作業(yè)過程示意見圖1。

圖1 1個單元作業(yè)過程示意圖

車站的所有作業(yè)都可以使用上述作業(yè)單元所述模式來表達，那么編組站所有的作業(yè)可表示為：

式中：ΨE為編組站所有的作業(yè)，假定可以分割成m個作業(yè)單元。這些作業(yè)單元之間內(nèi)在的聯(lián)系是依靠每個作業(yè)單元的開始前驅(qū)作業(yè)集合Ψs和結(jié)束前驅(qū)作業(yè)集合Ψe來表達。編組站的這種內(nèi)在關(guān)系主要是由現(xiàn)車和調(diào)車等引起的，為了降低模型的復(fù)雜性，將現(xiàn)車分配作為由階段計劃確定的已知因素，而不作為模型的變量。若擴展模型，將現(xiàn)車作為模型的變量，就可用以優(yōu)化編制鉤計劃。

以編組站的入段、解體、編組為例來說明上述的模型描述：

（1）入段作業(yè)比較簡單，可以作為1個作業(yè)單元處理，該作業(yè)單元的開始前驅(qū)作業(yè)集合是接車作業(yè)單元，入段作業(yè)通常不是一次性完成的，入段的過程中可以在某個區(qū)段停留下來，為別的作業(yè)讓道，那么可以將整個入段路徑上所有可以停車的地方表示出來，以這些停車點將入段路徑分割成1個作業(yè)序列，形成入段作業(yè)單元的作業(yè)節(jié)點集合。入段徑路不需要調(diào)車，因此其ξj為空。

（2）解體作業(yè)比較復(fù)雜，可以分為預(yù)推和推峰2個部分，因此1 個單純的解體作業(yè)可以劃分為2 個作業(yè)單元，而預(yù)推是一次性完成，中間沒有停頓，因此預(yù)推作業(yè)單元的作業(yè)節(jié)點有3 個，分別是預(yù)推開始，預(yù)推，預(yù)推結(jié)束。而解體作業(yè)的鉤計劃比較復(fù)雜，有的解體有30 多鉤，但可以將解體計劃視作1 個作業(yè)單元，解體動作一旦開始，中間不能停頓，而且獨占駝峰資源（雙推單溜），因此同樣解體作業(yè)單元也包括3 個節(jié)點，分別是解體開始、解體、解體結(jié)束3個作業(yè)節(jié)點。

（3）對于平面調(diào)車的鉤計劃，如編組，通常每一勾都是1個作業(yè)單元，在調(diào)車運行過程中，空程時可以隨時停車，而帶車則須一次性走完整條路徑，因此帶車的作業(yè)節(jié)點較少，而空程的作業(yè)節(jié)點較多。

1.2 決策內(nèi)容

建立模型主要解決以下決策內(nèi)容：

（1）作業(yè)單元的次序。

（2）作業(yè)節(jié)點的節(jié)奏。每個作業(yè)單元可能不是一次性完成的，如本務(wù)機入段，可能走走停停以避開相擾（讓行其他調(diào)車作業(yè)和列車運行），或者等待關(guān)聯(lián)作業(yè)完成。

（3）作業(yè)單元的獨占資源。獨占資源主要指駝峰（雙推單溜）、調(diào)車、存車線等。若為了降低模型的復(fù)雜度和搜索規(guī)模，也可去掉其中的某些獨占資源決策，而采納階段計劃中的輸入。以下假定獨占資源只有調(diào)車，加入其他獨占資源的處理方式與之類似。

（4）徑路資源。模型中徑路資源屬于部分決策變量，很多作業(yè)有固定走法，如下行編組，不可能走到上行去。在作業(yè)單元中，隨著獨占資源、本區(qū)域前后作業(yè)確定，其徑路也大體確定，選擇1條干擾最小，距離最短的徑路即可。模型的徑路決策是指當徑路必然要與其他作業(yè)造成干擾時需要對具體徑路進行選擇。選擇不同徑路，造成的干擾范圍、干擾程度不同，進而模型計算出的目標值不同。

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

2.1 作業(yè)時間

編組站多數(shù)作業(yè)是有先后次序的，但是也有很多作業(yè)是可以平行作業(yè)的，在實際工作中也會盡量創(chuàng)造平行作業(yè)機會以提高作業(yè)效率。數(shù)學(xué)模型建立的單元作業(yè)首先要滿足時間要求。

（1）由于作業(yè)節(jié)點需要一次性執(zhí)行完，因此tei是僅依賴于tsi的變量：

式中：c(ri，Γ)為常量，其值隨著作業(yè)類型和徑路確定，屬于字典類數(shù)據(jù)，以下將其定義為受作業(yè)類型和徑路等字典類數(shù)據(jù)影響的變量。

（2）在1個作業(yè)單元內(nèi)部，作業(yè)序列是嚴格按照順序來執(zhí)行的，因此需要滿足如下關(guān)系：

（3）任意1個作業(yè)單元ψ的開始和結(jié)束節(jié)點需要滿足其前驅(qū)作業(yè)集合的限制：

2.2 作業(yè)徑路

作業(yè)徑路是整個模型重要決策變量。很多作業(yè)執(zhí)行次序、執(zhí)行方式的改變都是因為作業(yè)徑路的干擾。以下作業(yè)徑路不僅指路徑，還包括股道，如技術(shù)作業(yè)，其作業(yè)徑路就是列車的停留股道。

作業(yè)徑路是一種獨占資源，因此要求所有的徑路都不能相擾，否則必須通過時間錯開達到不相擾。

為了不失一般性，假設(shè)任意2 個作業(yè)單元ψm和ψn的任意2個作業(yè)節(jié)點υmi和υnj為：

如果時間上存在重疊，即：

那么，徑路上就不能相擾：

2.3 獨占資源

作業(yè)單元中需要使用獨占資源，調(diào)車作業(yè)的獨占資源是機車，駝峰解體的獨占資源還包括駝峰（雙推單溜），接發(fā)列車和本務(wù)機作業(yè)單元沒有獨占資源。獨占資源的限制和作業(yè)徑路類似，其實作業(yè)徑路也是一種獨占資源。

為了不失一般性，假設(shè)任意2 個作業(yè)單元ψm和ψn的任意2個作業(yè)節(jié)點υmi和υnj為：

如果時間上存在重疊：

那么對于獨占資源ξmi和ξnj就不能相擾：

2.4 模擬運輸目標

編組站的模擬運輸目標是充分高效地利用站內(nèi)設(shè)備，完成車站各項作業(yè)。上述目標很難量化，也無法將上述目標作為模型的目標。因此，從作業(yè)的角度來考察模擬運輸?shù)男剩贫〝?shù)學(xué)模型的目標是均衡、緊湊地完成車站各項作業(yè)。

首先以接車和發(fā)車為參照，為車站的每個作業(yè)制定1個作業(yè)時間的參照，以到解列車為例，接車作業(yè)單元的開始時間就是計劃接車時間，而解體的開始時間就是接車時間加上技術(shù)作業(yè)時間，也就是解體最早可能開始的時間。然后根據(jù)作業(yè)時間與參照時間的差值來計算作業(yè)方案的優(yōu)劣。

（1）對于1 個作業(yè)單元ψm，其作業(yè)節(jié)點中開始節(jié)點υ0表示這單作業(yè)可以開始的時間，實際上是最早開始時間。如果該作業(yè)從能夠開始的時候就進行，并且一直到結(jié)束，中間沒有延誤，那么認為該作業(yè)是最理想的作業(yè)方式。

1個作業(yè)單元延誤的時間就是這個作業(yè)單元每個作業(yè)節(jié)點的延誤時間：

那么所有作業(yè)單元的延誤時間：

在實際作業(yè)中，每個作業(yè)由于其他作業(yè)的影響，都或多或少有些延誤，而考察作業(yè)效率的高低，可以考察作業(yè)的延誤時間。如果車站只進行1個作業(yè)，那么無論怎么安排計劃，都不會延誤，即無論如何做，效率都是最高的，而如果有很多計劃交織在一起，那么組織這些作業(yè)的方式、次序?qū)π视绊懞艽蟆?/p>

上式中，所有作業(yè)對延誤時間δΨE的“貢獻”都是相同的，但用戶可能會認為一些作業(yè)重要，一些作業(yè)不重要，因此定義一個權(quán)值，僅和作業(yè)類型相關(guān)的常量，表示為ω(Γ)，那么上式改為：

（2）模擬運輸目標是盡可能減少整個作業(yè)的延誤時間，也就是緊湊目標，但這樣會出現(xiàn)某項作業(yè)延誤很長時間，而其余作業(yè)延誤時間較短的情況。因此δΨE反映了整個作業(yè)的緊湊度，還不能反映整個作業(yè)的均衡度。

修改上述的作業(yè)的δΨE，改用每個作業(yè)單元的延誤時間二階距ΔΨE作為衡量整個作業(yè)的均衡、緊湊的指標。

通過對編組站的所有作業(yè)建立數(shù)學(xué)模型，將模擬運輸?shù)膬?yōu)化轉(zhuǎn)為通過計算機的手段來尋找最優(yōu)指標的ΔΨE搜索過程。

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

根據(jù)以上對目標和約束的討論，建立編組站作業(yè)組織優(yōu)化運輸模型為：

將車站作業(yè)抽象成模型描述的方式，在滿足約束條件下尋找最小的ΔΨE，在最小的ΔΨE下，編組站作業(yè)方式是最小的，是最緊湊、均衡的組織方式，同時也是在既有作業(yè)量下，設(shè)備利用效率最高的方式。

2.6 模型求解討論

2.6.1 建立模型

按照上述編組站業(yè)務(wù)描述，將階段計劃內(nèi)所有即將進行的作業(yè)抽象為作業(yè)單元的集合ΨE，然后根據(jù)計劃類型和現(xiàn)車關(guān)系，設(shè)置為每個作業(yè)單元的Ψs和Ψe。計算每個作業(yè)單元的開始節(jié)點時間和結(jié)束節(jié)點時間。

2.6.2 設(shè)定常量

模型中有2類常量需在模型求解前預(yù)先設(shè)定：

（1）作業(yè)節(jié)點執(zhí)行時間c(ri，Γ)。作業(yè)節(jié)點的開始節(jié)點和結(jié)束節(jié)點只是一個標記，其執(zhí)行時間為0，即ts0=te0和ts(n+1)=te(n+1)，而其余節(jié)點的執(zhí)行時間主要和路徑的長度有關(guān)系，所以需要對站場進行測繪。根據(jù)每個設(shè)備的長度，以及路徑經(jīng)由的設(shè)備，計算路徑長度，由作業(yè)類型設(shè)定其運行速度曲線，并計算作業(yè)節(jié)點執(zhí)行時間。

（2）延誤時間權(quán)值ω(Γm)。延誤時間權(quán)值用于表示作業(yè)重要程度，如編組站的非重要作業(yè)（站修線取車等）的作業(yè)權(quán)重可以小一點。延誤時間權(quán)值是主觀性比較強的參數(shù)，需要參考車站作業(yè)人員的意見，也可用于模型輸出的調(diào)整。

對于那些沒有明確開始時間的作業(yè)，延誤時間權(quán)值可以定得小一點，開始時間則可定義得早一點。

2.6.3 最優(yōu)解

公式（14）編組站作業(yè)模型是個典型的完全多項式非確定問題（NPC），即模型的解需要去嘗試和猜測，但每個解都可以很容易地去求解其模型目標值，然后依據(jù)目標值判斷解的好壞。以下僅討論采用窮舉法，將滿足約束的所有可能解一一枚舉出來。采用式（8）計算每個解對應(yīng)的緊湊、均衡度，并選出最優(yōu)解。

2.6.4 解空間

根據(jù)式（2），每個作業(yè)單元ψ的作業(yè)節(jié)點的個數(shù)記做|ψ|，而對于所有的作業(yè)單元ΨE，其含有的所有作業(yè)節(jié)點數(shù)為|ΨE|：

那么，作業(yè)節(jié)點的全排序的解空間為Ω 就是|ΨE|的階乘，記做：

考慮到同一個作業(yè)單元內(nèi)部的作業(yè)節(jié)點有序，則：

式（17）表示編組站作業(yè)最大可能性的組合，由于作業(yè)開始和作業(yè)結(jié)束約束、調(diào)車約束、站形約束等會大大降低解空間的規(guī)模。以下討論具有代表性的機車資源對解空間的影響。

假定編組站內(nèi)有u臺調(diào)車，那么這些作業(yè)單元根據(jù)所使用調(diào)車分割成u+1 個集合。其中每臺調(diào)車對應(yīng)1 個作業(yè)單元集合ΨLi，把不需要調(diào)車的所有作業(yè)單元合并到1 個集合ΨL(u+1)。假定ΨL(u+1)單元作業(yè)的個數(shù)是m′，則解空間為：

2.6.5 求解模型

采用窮舉法，通過剪枝、降低問題規(guī)模等來達到快速求解的目的。

（1）劃分子集。編組站很多作業(yè)單元可以根據(jù)作業(yè)區(qū)域和作業(yè)時間來劃分成互不關(guān)聯(lián)的作業(yè)集合，如在車站1個班內(nèi)，到達列車有密集到達的，也有空閑到達的，這樣有可能在時間上將ΨE分成幾個集合；同時有些作業(yè)在解體區(qū)域，有些作業(yè)在編組區(qū)域，也可以劃分成不同的集合。假定可以劃分成μ個結(jié)合。那么可以將解空間降為：

（2）剪枝。在搜索的過程中，可以隨時拋棄明顯不合理的解，即剪枝。在實際應(yīng)用中，剪枝對搜索速度的影響極大。剪枝的權(quán)值設(shè)定可以根據(jù)經(jīng)驗設(shè)定，也可以估算。由于只需要搜索模型的1個最優(yōu)解，如果估算權(quán)值越接近最優(yōu)解的權(quán)值，則剪枝的效果就越明顯。

如果估算目標值，則首先假定平均每個作業(yè)單元延時30 min，然后根據(jù)平均值計算模型的目標值ΔΨω。在搜索的過程，隨時檢查最優(yōu)解的目標值，如果超過ΔΨω，則直接剪掉。估算的目標值對搜索范圍影響很大，通?？梢試L試定一個比較優(yōu)的目標值，如果搜不到解，則逐步放開目標值。目標估計值設(shè)定流程見圖2。

（3）縮小問題規(guī)模。模型的解空間隨著作業(yè)節(jié)點的個數(shù)成指數(shù)級地增長，因此為了提高搜索最優(yōu)解的速度，可以減少作業(yè)節(jié)點個數(shù)。在工程實際應(yīng)用中，通過減少求解問題的時間寬度解決，即只對最近1 h 的編組站作業(yè)進行優(yōu)化求解。

圖2 目標估計值設(shè)定流程

整個模型求解過程見圖3。

圖3 模型求解過程

3 實驗驗證

編組站作業(yè)組織優(yōu)化是一個很難定量分析的值，對于1 個車站，每天的作業(yè)都在變化，即使同樣的作業(yè)，不同作業(yè)人員的作業(yè)方式也不同。主要通過兌現(xiàn)率和模型目標函數(shù)值（均衡緊湊度）2個指標評價模型的優(yōu)劣。選擇某車站4 月份3 個日班，上午、下午、晚上各1 個時間段作為驗證時間。選擇的標準是：3 個時間段的作業(yè)比較有普遍性，沒有交班、施工等異常情況的干擾，且作業(yè)比較飽滿。

兌現(xiàn)率是指模型決策內(nèi)容與車站實際作業(yè)情況進行比較的結(jié)果。從模型中求解出來的作業(yè)，如果其作業(yè)單元次序、作業(yè)節(jié)奏、獨占資源、走行徑路等和實際作業(yè)一致，則認為該作業(yè)兌現(xiàn)了。兌現(xiàn)率反映模型的最優(yōu)解與實際作業(yè)過程的貼合度。選擇模型驗證時間的兌現(xiàn)率見表1。

表1 驗證時間的兌現(xiàn)率

模型計算出的這些作業(yè)節(jié)點的均衡、緊湊度之和見表2。

表2 作業(yè)節(jié)點均衡緊湊度之和

從上述的數(shù)據(jù)可以看出，模型產(chǎn)生的作業(yè)序列兌現(xiàn)率是72.6%，而從均衡、緊湊度上看，模型所安排的作業(yè)組織明顯優(yōu)于車站的實際作業(yè)組織。由此可見，車站的作業(yè)組織還有優(yōu)化空間。

4 結(jié)束語

建立的編組站作業(yè)組織優(yōu)化運輸模擬推演模型綜合考慮了到發(fā)線路，接發(fā)車進路，單機轉(zhuǎn)移、調(diào)車、出入段、立折、轉(zhuǎn)頭等編組站所有的作業(yè)，并對這些作業(yè)的作業(yè)次序、作業(yè)所使用資源進行了優(yōu)化。模型貼近于實際作業(yè)，具有很高的實用性。從實驗結(jié)果可以看出，模型較好地擬合現(xiàn)場作業(yè)，其作業(yè)的均衡度和緊湊度都明顯優(yōu)于實際現(xiàn)場作業(yè)。