運(yùn)用學(xué)習(xí)規(guī)則求解編組站靜態(tài)配流問題的研究

景 云，王慈光，王如義，唐建橋

（西南交通大學(xué) 交通運(yùn)輸學(xué)院，四川 成都 610031）

編組站配流問題研究如何合理地安排列車的解編方案和配流方案，使車流在車站停留時間最短，同時使編組站各項(xiàng)工作平穩(wěn)、有序地進(jìn)行，以保證整個路網(wǎng)的暢通[1]。配流問題分為動態(tài)配流和靜態(tài)配流兩個階段。動態(tài)配流通過制定列車的解編方案，確定列車解編順序，初步確定出發(fā)列車的車流來源；靜態(tài)配流則通過確定出發(fā)列車具體的編組內(nèi)容和車流來源得到最終配流方案。由于出發(fā)列車編組去向的多樣性與交錯性，即便列車的解編方案已經(jīng)確定，車流的接續(xù)關(guān)系基本明朗，仍然存在多種配流方案，需要進(jìn)行合理的優(yōu)化選擇[2]。本文將在文獻(xiàn)[1]的基礎(chǔ)上，設(shè)計(jì)一種新型網(wǎng)絡(luò)算法求解靜態(tài)配流問題。

1 靜態(tài)配流模型

1.1 目標(biāo)函數(shù)

編組站編制階段計(jì)劃的主要目的是為了保證編組站工作的穩(wěn)定有序，在銜接線路能力足夠的情況下盡可能向區(qū)間多發(fā)列車[3-6]。所以，配流問題的目標(biāo)函數(shù)應(yīng)為階段內(nèi)出發(fā)列車所配車輛總數(shù)最大，即：

式中：xij表示到達(dá)列車 di向出發(fā)列車 fj配入的車輛數(shù)。

按調(diào)度計(jì)劃，出發(fā)列車分為可欠軸列車與不可欠軸列車。對不可欠軸列車，當(dāng)列車發(fā)車時刻沒有足夠的車流令其滿軸，該次列車將停運(yùn)，線路能力將浪費(fèi)；對可欠軸列車，在出發(fā)時刻應(yīng)盡可能湊齊滿軸[7]。這樣配流問題就由較復(fù)雜的目標(biāo)分解為兩個較簡單的目標(biāo)，即在保證不可欠軸列車滿軸的情況下，使可欠軸列車所配車數(shù)最多。

1.2 約束條件

通常情況下，一個階段內(nèi)總車流量供求是不平衡的。靜態(tài)配流問題除了要考慮簡單配流問題的約束條件外[2]，還需要考慮以下3個約束條件。

（1）接續(xù)時間約束。以D = {d0,d1,d2,…,dn}記為本階段廣義到達(dá)列車集合，包括調(diào)車場現(xiàn)車、到達(dá)場待解列車、本階段陸續(xù)到達(dá)的列車、交換場等待轉(zhuǎn)場分解的車組和從專用線取回待分解車組等；以F = { f1,f2,…,fm} 記為本階段出發(fā)列車集合。只有符合接續(xù)時間要求的 di才能夠提供給 fj所需的車輛。

（2）編組內(nèi)容約束。到達(dá)列車 di中只有與出發(fā)列車 fj編組去向相符的車流才能成為 fj的車流來源。

（3）滿軸約束。對可欠軸列車，其編成輛數(shù)可小于滿軸車數(shù)；對不可欠軸列車其編成輛數(shù)應(yīng)等于滿軸車數(shù)。

將靜態(tài)配流模型看作有時間約束、銷量不確定的產(chǎn)銷不平衡運(yùn)輸問題，可建立該問題的網(wǎng)絡(luò)模型。

1.3 靜態(tài)配流網(wǎng)絡(luò)模型

由于接續(xù)時間約束條件的限制，到發(fā)列車之間并不一定能夠建立一一對應(yīng)的關(guān)系。將滿足接續(xù)時間約束條件的到、發(fā)列車用弧連接起來，表示 di可以提供給 fj車流，弧的容量即為 di的車輛數(shù)，沒有用弧連接的到、發(fā)列車表示不滿足接續(xù)時間約束條件。

到達(dá)列車中的車流往往不止一個編組去向，將 di中每個組號作為一個中間節(jié)點(diǎn)，相當(dāng)于一列單去向的到達(dá)列車，將其與去向相符的出發(fā)列車用弧連接起來，沒有用弧連接的到、發(fā)列車表示不滿足編組內(nèi)容約束條件。

只將符合約束條件的到、發(fā)列車之間以弧相連，可以減小問題的規(guī)模，在求解的過程中暫不考慮運(yùn)輸費(fèi)用。由于靜態(tài)配流所要解決的關(guān)鍵問題是確定出發(fā)列車的編組內(nèi)容(包括編組去向和各去向車數(shù))，至于具體而精確的車流來源并無需明確，故利用文獻(xiàn)[8]的化簡方法進(jìn)一步的化簡，減小問題的規(guī)模，將經(jīng)過整理后的到達(dá)列車重新排列得到 di'。

靜態(tài)配流問題是產(chǎn)銷不平衡的運(yùn)輸問題，為化為平衡運(yùn)輸問題，增加一個虛發(fā)點(diǎn)dn'+1。將該發(fā)點(diǎn)與可欠軸出發(fā)列車用弧連接；增加一個虛收點(diǎn) fm+1，將該收點(diǎn)與所有到達(dá)列車用弧連接。除從 dn'+1吸收的車輛外，fm+1其實(shí)就是下一階段的d0。由此，一個固定費(fèi)用、產(chǎn)銷平衡的運(yùn)輸網(wǎng)絡(luò)模型就建成了。

2 算法的學(xué)習(xí)規(guī)則

由于大型編組站涉及的變量較多，使用傳統(tǒng)的最大流算法較難在合理的時間內(nèi)求得網(wǎng)絡(luò)模型的最優(yōu)解。學(xué)習(xí)規(guī)則是一種用來計(jì)算給定 dn'+1時配流方案的方法。通過在 dn'+1每次減小的過程中調(diào)用學(xué)習(xí)規(guī)則以判斷配流方案的可行性，最終得到虛擬到達(dá)列車車輛數(shù)最小的配流方案，以求解靜態(tài)配流問題的網(wǎng)絡(luò)模型。

2.1 初始化權(quán)數(shù)

在運(yùn)輸問題的網(wǎng)絡(luò)模型(圖1)中，di'為輸入層， fj為輸出層，源 s 表示本階段到達(dá)車輛總數(shù)，匯 t 表示出發(fā)車輛總數(shù)，層內(nèi)元素?zé)o弧相連。

圖1 靜態(tài)配流網(wǎng)絡(luò)模型示例圖

聯(lián)通系數(shù) ρi'j表示輸入層與輸出層之間是否有弧相連，若有，則 ρi'j=1；若無，則ρi'j=0。權(quán)數(shù)wi'j表示將 di'分配到 fj的車輛占 di'總車輛的百分比，故如果輸入層與輸出層之間是聯(lián)通的，應(yīng)當(dāng)滿足：

2.2 誤差函數(shù)

假設(shè)輸入為(x0,x1,x2,…,xi',…,xn'+1)；期望輸出為(r1,r2,…,rj,…,rm+1)，表示出發(fā)列車的滿軸輛數(shù)；實(shí)際輸出為(y1,y2,…,yj,…,ym+1)，則：

誤差函數(shù)表示實(shí)際輸出與期望輸出之差，為：

函數(shù)值的大小表示出發(fā)列車所配車數(shù)與滿軸車數(shù)的偏離程度，如果E(w)= 0，表示所有出發(fā)列車都滿軸。虛擬出發(fā)列車 fm+1起調(diào)節(jié)車流的作用，吸收本階段不能編入出發(fā)列車的車流，計(jì)算誤差函數(shù)時不考慮 fm+1。

2.3 權(quán)值的計(jì)算

從一個隨機(jī)選取的初始權(quán)值wi'j開始，在經(jīng)過每次的學(xué)習(xí)過程中，沿E(w)下降最快的方向?qū)?quán)值移動一個很小的距離Δwi'j，最終確定權(quán)值w使誤差函數(shù)值達(dá)到最小。若學(xué)習(xí)次數(shù)為t，每次學(xué)習(xí)后權(quán)值為wi'j(t)，則：

為實(shí)現(xiàn)梯度下降法，需要誤差函數(shù)關(guān)于權(quán)重導(dǎo)數(shù)的顯式表達(dá)，單層網(wǎng)絡(luò)中，權(quán)值w為一系列線性方程組，梯度向量為：

導(dǎo)數(shù)的計(jì)算就網(wǎng)絡(luò)圖而言關(guān)于權(quán)重wi'j是局部的，基于導(dǎo)數(shù)的這一表示，權(quán)向量的移動距離為:

式中：η為學(xué)習(xí)速率參數(shù)，η∈( 0,1)。η的取值相當(dāng)重要，因?yàn)棣侨〉锰。瑒t誤差下降會非常緩慢，而η取得太大，則會導(dǎo)致發(fā)散振蕩。

2.4 歸一化處理

通過對權(quán)值的迭代，新產(chǎn)生的權(quán)值并不一定滿足約束條件⑵，利用公式:

進(jìn)行歸一化處理，使式⑵成立。

2.5 學(xué)習(xí)步驟

步驟2：利用式⑶計(jì)算yi；利用式⑷計(jì)算E(wi'j( t ))。

步驟3：根據(jù)式⑺計(jì)算權(quán)值的改變量Δwi'j；根據(jù)式⑸更新權(quán)值wi'j( t + 1 )。

步驟4：根據(jù)式⑻對wi'j(t +1)進(jìn)行歸一化處理以滿足式⑵。

步驟5：若誤差函數(shù)E(wi'j( t + 1)) ≠ 0，轉(zhuǎn)入步驟2；否則，停止學(xué)習(xí)，得出權(quán)值wi'j。

3 算法過程

在 dn'+1每次減小的過程中都調(diào)用學(xué)習(xí)規(guī)則得到一個配流方案，最終求得一個使虛擬到達(dá)列車車輛數(shù)最小，即出發(fā)列車所配車輛總數(shù)最大的配流方案，從而求解靜態(tài)配流問題的網(wǎng)絡(luò)模型。

3.1 虛擬到達(dá)列車初始值

在配流方案中，不可欠軸列車必須滿軸，所以虛擬到達(dá)列車的車流不必提供給這些列車，dn'+1僅與可欠軸列車以弧相連。由于并非每一對到、發(fā)列車都能夠建立對應(yīng)關(guān)系，即便是到達(dá)列車總輛數(shù)大于出發(fā)列車總輛數(shù)，可欠軸出發(fā)列車依然可能欠軸。為使可欠軸出發(fā)列車能夠滿軸，虛擬列車的初始值應(yīng)當(dāng)?shù)扔诳汕份S列車的最大配車數(shù)：式中：qj表示 fj能否欠軸，不可欠軸為1，可欠軸為 0。

3.2 配流方案的計(jì)算

調(diào)用學(xué)習(xí)規(guī)則計(jì)算后，若E(w) ≠ 0，表示有不可欠軸列車不滿軸，無法得到可行的配流方案，需要回到動態(tài)配流階段重新選擇解編方案；若E(w) = 0，表示解編方案是可行解。對于一個可行的解編方案，不可欠軸列車的配車數(shù)是一定的，目標(biāo)函數(shù)值的大小取決于可欠軸列車的配車數(shù)。在網(wǎng)絡(luò)模型中，可欠軸列車也要等于滿軸輛數(shù)，不足的車輛由虛擬到達(dá)列車提供，所以虛擬到達(dá)列車輛數(shù)越大，表示出發(fā)列車實(shí)際配車數(shù)越小。算法就是在調(diào)用學(xué)習(xí)規(guī)則保證所有列車都達(dá)到滿軸的基礎(chǔ)上，逐步尋找xn'+1的最小值。將經(jīng)過第c次迭代后的 xn'+1記為：

式中： δ為迭代步長參數(shù)，δ∈( 0,1)。

若在第c次迭代時，誤差函數(shù) E(w) ≠ 0，表示 xn'+1下降的過多，有出發(fā)列車不滿軸，應(yīng)當(dāng)增加 xn'+1。

當(dāng)再次得到E(w) = 0，表示網(wǎng)絡(luò)模型達(dá)到了平衡，所有出發(fā)列車都已滿軸，且 dn'+1的車輛數(shù)最小，目標(biāo)函數(shù)達(dá)到最優(yōu)。此時，配流方案為：

最大配流輛數(shù)為：

3.3 算法步驟

步驟1：通過由動態(tài)配流得到的解編方案構(gòu)建靜態(tài)配流網(wǎng)絡(luò)模型。

步驟2：建立虛發(fā)點(diǎn)與虛收點(diǎn)，對虛擬到達(dá)列車 xn'+1賦初值。

步驟3：調(diào)用學(xué)習(xí)規(guī)則，判斷解編方案的可行性，若不可行則返回動態(tài)配流階段重新尋找解編方案。

步驟4：若誤差值E(w) = 0利用公式⑽計(jì)算虛擬到達(dá)列車輛數(shù)，若誤差值E(w) ≠ 0利用公式⑾ 計(jì)算虛擬到達(dá)列車輛數(shù)。

步驟5：當(dāng)重新滿足E(w) = 0 時停止迭代，得出權(quán)值wi'j。

步驟6：利用式⑿計(jì)算列車配流方案，根據(jù)式⒀求出最多配流輛數(shù)。

4 算例

假設(shè)在某編組站一個階段的配流問題中僅討論4個去向: a,b,c,d，則到達(dá)列車 di與出發(fā)列車 fj共有4個組號l ={a,b,c,d}，記表示到達(dá)列車 d的l去向i的車組數(shù)量；為出發(fā)列車 fj的l去向的車組數(shù)量。表示第 i 列到達(dá)列車到達(dá)時刻；表示第 j 列出發(fā)列車出發(fā)時刻；T解表示解體時間；T編表示編組時間。按照先發(fā)先編的原則，經(jīng)動態(tài)配流得到的解體方案為g ={11,32,23,44,55,76,87,68,99,109,1110}；除 f2, f6, f10為摘掛列車可欠軸外，其他列車均不得欠軸；到發(fā)列車的信息如表1、表2所示。

經(jīng)簡化后的靜態(tài)配流網(wǎng)絡(luò)模型如圖2所示，輸入層共有16列單去向到達(dá)列車和虛擬到達(dá)列車 d17，輸入層內(nèi)的字母和數(shù)字表示該列列車的編組去向和車輛數(shù)；輸出層共有10列出發(fā)列車和虛擬出發(fā)列車f11。

表1 到達(dá)列車信息表

表2 出發(fā)列車信息表

圖2 靜態(tài)配流網(wǎng)絡(luò)模型

當(dāng)r = 40，η = 0.1，δ = 0.05 時，經(jīng)計(jì)算得到的配流方案如下表所示。

表3 出發(fā)列車配流方案

該配流方案可使不可欠軸列車均滿軸，可欠軸列車配車數(shù)最大，階段內(nèi)最大發(fā)車輛數(shù)為392輛，為最優(yōu)方案。

5 結(jié)束語

本文提出的算法利用學(xué)習(xí)規(guī)則使配流方案滿足滿軸約束條件，通過設(shè)立虛擬到達(dá)列車將目標(biāo)函數(shù)轉(zhuǎn)化為求虛擬到達(dá)列車車輛數(shù)最小，以簡化網(wǎng)絡(luò)模型，從而避免利用最大流的方法求解大規(guī)模網(wǎng)絡(luò)模型。算法能夠快速、有效地解決大型編組站多列到發(fā)列車的靜態(tài)配流問題，制定配流方案，對帶有時間約束、銷量不確定的產(chǎn)銷不平衡運(yùn)輸問題也是有益的探索。

[1] 王慈光. 運(yùn)輸模型及優(yōu)化[M]. 北京：中國鐵道出版社，2004.

[2] 王慈光. 用表上作業(yè)法求解編組站配流問題的研究[J]. 鐵道學(xué)報，2002，24 (4)：1-5.

[3] 王明慧，趙 強(qiáng). 編組站智能調(diào)度系統(tǒng)階段計(jì)劃優(yōu)化模型及算法研究[J]. 鐵道學(xué)報，2005，27 (6)：1-9.

[4] 何世偉，宋 瑞，朱松年. 編組站階段計(jì)劃解編作業(yè)優(yōu)化模型及算法[J]. 鐵道學(xué)報，1997，19 (3)：1-8.

[5] 何世偉，宋 瑞，胡安洲. 編組站階段計(jì)劃剛性與柔性優(yōu)化的協(xié)調(diào)研究[J]. 鐵道學(xué)報，1999，21 (4)：1-8.

[6] ?；菝瘢仓? 雙向編組站車流接續(xù)的綜合優(yōu)化[J]. 鐵道學(xué)報，1998，20 (6)：16-21.

[7] 薛 鋒. 編組站調(diào)度系統(tǒng)配流協(xié)同優(yōu)化理論與方法研究[D].成都：西南交通大學(xué)，2009.

[8] 王慈光. 編組站靜態(tài)配流網(wǎng)絡(luò)模型[J]. 交通運(yùn)輸工程與信息學(xué)報，2003，1 (2)：67-71.