技術(shù)站列車編組計劃的綜合優(yōu)化方法

肖　杰，林柏梁，王家喜，劉　暢，李　建

(北京交通大學(xué) 交通運輸學(xué)院，北京　100044)

優(yōu)化技術(shù)站的列車編組計劃能夠充分發(fā)揮技術(shù)站作業(yè)能力，提高車流組織效率。根據(jù)車流組織形式，技術(shù)站列車編組計劃包括單組列車編組計劃和分組列車編組計劃。

既有的研究成果中，針對單組列車編組計劃的主要有：林柏梁[1]等人構(gòu)建了基于最遠站法則的列車編組計劃的雙層模型，上層確定列車到發(fā)站，下層根據(jù)流量平衡確定車流改編方案，并采用模擬退火算法對模型進行了求解；許紅[2]等人綜合車站改編能力、調(diào)車線容車數(shù)等限制條件構(gòu)建單組列車編組計劃，使所耗費的總車小時最少。張震[3]研究了技術(shù)直達列車編組計劃優(yōu)化方法，提出了基于車流無改編通過支點站的最大次數(shù)及有利性判別條件式。

針對分組列車編組計劃的主要有：李夏苗[4]等人利用分組列車組織快運貨物運輸，同時考慮了牽引條件和發(fā)車時間間隔限制的條件，以運輸收入最大為目標(biāo)，確定了經(jīng)濟有效的組織方式。梁棟[5]等人根據(jù)分組列車的組織特點，提出了帶有階躍函數(shù)的技術(shù)站分組列車編組計劃的0-1規(guī)劃模型。這些研究均沒有在編組計劃編制過程中同時考慮單組列車和分組列車，進行綜合優(yōu)化。

單組列車是貨物列車最基本的組織形式，分組列車是單組列車的一種輔助或附屬形式。相比于單組列車，分組列車可以減少沿途技術(shù)站的調(diào)車作業(yè)量，但卻需要技術(shù)站具有更多的調(diào)車線和較大的改編能力。因此，在優(yōu)化技術(shù)站列車編組計劃時應(yīng)綜合考慮單組列車和分組列車，發(fā)揮各自優(yōu)勢，從而提高運輸效率。本文基于這種情況，首先在給定技術(shù)站的技術(shù)參數(shù)、車流量和車流徑路的條件下，構(gòu)建單組列車編組計劃優(yōu)化模型；在此基礎(chǔ)上，分別計算合并式分組列車和銜接式分組列車的車小時消耗；以最大限度地降低技術(shù)站總的車小時消耗為目標(biāo)，引入階躍函數(shù)設(shè)置開行分組列車的條件，建立包括單組列車和分組列車的編組計劃綜合優(yōu)化模型。采用遺傳算法求解單組列車編組計劃優(yōu)化模型，并將計算結(jié)果作為已知條件，采用遍歷算法求解技術(shù)站編組計劃綜合優(yōu)化模型，得到綜合效益更佳的技術(shù)站列車編組計劃。并用實例證明本文所建立模型和算法的合理性和有效性。

1　單組列車編組計劃優(yōu)化模型

構(gòu)建技術(shù)站單組列車編組計劃需要考慮技術(shù)站的改編能力和調(diào)車線數(shù)量等約束條件，確定列車開行方案，實現(xiàn)車流組織總成本最小。

1.1　模型前提假設(shè)

首先做如下設(shè)定：任意2個技術(shù)站之間的運量均為已知；所有車流徑路以《全國鐵路貨物運輸特定計費徑路》為準(zhǔn)，即所有車流徑路均為已知[6]；去向相同的各支車流在某站合并之后，就被視作1股車流，在運送的過程中不能被拆散；相鄰車站之間的車流以小運轉(zhuǎn)列車或者直通方式運送，即所有相鄰車站均存在直達去向。

1.2　單組列車編組計劃優(yōu)化模型

定義S為路網(wǎng)上車站的集合；i，j，k，e，y等泛指路網(wǎng)上任一車站。以i，j，k為例定義如下變量：Yi為i站后方車站的集合；Ei為i站前方車站的集合；Ci為i站的集結(jié)參數(shù)，Hi為i站調(diào)車線的數(shù)量；Dij為i站到j(luò)站所經(jīng)過的技術(shù)站集合；aij為i站到j(luò)站的始發(fā)直達車流量；mij為i站到j(luò)站的列車平均編成輛數(shù)；fij為i站到j(luò)站的實際車流量，不僅包括從i站到j(luò)站的固有的車流量aij，還有來自i站后方且經(jīng)i站改編的車流量；gij為i站到j(luò)站去向吸引的車流強度；Fk為技術(shù)站k的改編車流量；τk為技術(shù)站k進行車輛改編的時間消耗；Mk為技術(shù)站k的最大改編能力；γk為技術(shù)站k改編能力利用系數(shù)。

根據(jù)車流不可分割原則，一股車流在某技術(shù)站要么無改編通過，要么全部改編，不存在部分改編情況，即從i站到j(luò)站的車流必須滿足車流不可分割約束條件，即

(1)

若i站到j(luò)站的車流在途中k站進行改編，則必須滿足i站到j(luò)站存在近程直達去向的限制條件，即

(2)

技術(shù)站k的改編車流量Fk必須滿足其改編能力限制條件[7]，即

Fk≤Mkγk?k∈S

(3)

其中，

編發(fā)列車占用的調(diào)車線數(shù)量應(yīng)滿足該站的調(diào)車線數(shù)量約束條件[8]，即

φ(gij)≤Hi?i∈S

(4)

其中，

式中：φ(gij)為1個階躍函數(shù)，反映調(diào)車線使用情況，本文假設(shè)1條調(diào)車線1晝夜可容納200車，因此每1個編組去向中每增加200車就需要增加1條調(diào)車線。

以編組去向消耗的技術(shù)站總車小時最小為目標(biāo)函數(shù)，構(gòu)建的單組列車編組計劃優(yōu)化模型為

s.t. 式(1)—式(4)

(5)

2　分組列車的技術(shù)效益分析

2.1　分組列車的利弊分析

分組列車由2個及其以上不同到站的車組組成，并且要在沿途技術(shù)站至少進行1次換掛作業(yè)。分組列車包括基本組和補軸組，其中到達列車終點站及其以遠的車組為基本組，到達沿途技術(shù)站換下和掛上的車組為補軸組。

與單組列車相比，分組列車具有以下優(yōu)勢[8]。①減少貨物列車在編成站的集結(jié)時間。分組列車集結(jié)時，基本組和補軸組都不需達到列車編成輛數(shù)就可以結(jié)束，壓縮了集結(jié)時間。②減輕沿途技術(shù)站調(diào)車作業(yè)負荷。分組列車只需對摘掛車組進行改編，并不需要對整個列車改編。③加速車輛運行。分組列車免除基本組在沿途技術(shù)站的改編作業(yè)，加速列車中轉(zhuǎn)。

但分組列車的組織方式較為復(fù)雜，對技術(shù)站作業(yè)要求也比較嚴(yán)格，主要表現(xiàn)在以下4個方面。①編成站設(shè)備要求高。分組列車的基本組和補軸組分線集結(jié)時需要占用較多的調(diào)車線路，同時不能混編，故編成站需要有較大的改編能力。②換掛站車流穩(wěn)定。為防止列車欠軸運行甚至提前解體，要求換掛站的補軸車流穩(wěn)定可靠。③要求選擇換掛站時應(yīng)避免縱列式且無直通場的編組站。④換掛站需要及時準(zhǔn)備好換掛車組，以保證分組列車在站停留時間內(nèi)完成換掛作業(yè)。

隨著車組數(shù)量的增加，因基本組和補軸組之間的相互等待而消耗的車小時也隨之增加，考慮到目前大多數(shù)編組站調(diào)車線不足等因素，分組列車的組數(shù)不應(yīng)過多，并且分3組的分組列車極其罕見，因此本文僅針對雙組分組列車展開研究。

2.2　分組列車分類

根據(jù)分組列車的組成方式，可分為合并式和銜接式2種分組列車，如圖1和圖2所示，NAC，NAB，NBC為任意2個車站之間的車流，合并式分組列車是將2支或者多支單組列車合并為1支分組列車，而銜接式分組列車是將2支或者多支單組列車連接為1支分組列車。這2種情形都是分組列車代替單組列車，可以減少單組列車改編方案中列車到達站數(shù)目，但是代替是否有利，還需通過技術(shù)經(jīng)濟比較確定。

圖1　合并式分組列車

圖2　銜接式分組列車

根據(jù)分組列車基本組和補軸組重量是否固定可分為不固定車組重量和固定車組重量。這里重量均以車輛數(shù)進行描述，如圖3和圖4所示，當(dāng)摘解車流不大于補掛車流，即方向上車流量遞增NBC≥NAB時，采用不固定車組重量的分組列車，將換掛站多出的補軸車流NBC-NAB開行單組列車；反之將開行固定車組重量的分組列車，將編成站多出的補軸車流NAB-NBC開行單組列車，這種形式的分組列車可以避免基本車組在換掛站因等待補軸車組集結(jié)而產(chǎn)生延誤，或者無車流補軸而提前解體[9]。

圖3　不固定車組重量的分組列車

圖4　固定車組重量的分組列車

2.3　分組列車車小時消耗的計算

本文針對車組重量固定和不固定的合并式分組列車和銜接式分組列車分別計算其車小時的消耗。為了敘述簡便，上圖中遠程車流NAC作為分組列車的基本車組用NJ表示，短程車流NAB和NBC作為分組列車的補軸車組，分別用NZ和NG表示。

2.3.1合并式分組列車車小時消耗的計算

2.3.1.1不固定車組重量(即NG≥NZ)

1)編成站

不固定車組重量的合并式分組列車在編成站的車小時消耗主要包括車輛集結(jié)車小時和編組作業(yè)車小時。

(6)

式中：CA為A站的集結(jié)系數(shù)；m為列車平均編成輛數(shù)。

(7)

2)換掛站

不固定車組重量的合并式分組列車在換掛站的車小時消耗包括集結(jié)車小時消耗、車組等待車小時消耗、調(diào)車作業(yè)車小時消耗和直通車流額外停留車小時消耗4部分。

(8)

式中：CB為B站集結(jié)系數(shù)；mB為補軸車組平均編成輛數(shù)。

(9)

(10)

式中：mJ為基本車組平均編成輛數(shù)。

(11)

①當(dāng)NG=NZ時，

(12)

②當(dāng)NG>NZ時，

(13)

(14)

(4)直通車流額外停留車小時消耗ΔTZT。分組列車在換掛站的停留時間要比無改編中轉(zhuǎn)列車停站時間長，所以分組列車內(nèi)的直通車流NZT在換掛站1晝夜的額外停留車小時消耗ΔTZT為

ΔTZT=NZTΔtZT

(15)

式中：ΔtZT為分組列車較無改編中轉(zhuǎn)列車額外停留時間。

2.3.1.2固定車組重量(即NG

1)編成站

固定車組重量的分組列車在編成站的車小時消耗包含車輛集結(jié)車小時消耗、車組互相等待車小時消耗和編組作業(yè)車小時消耗。

(16)

(17)

(18)

(19)

(20)

2)換掛站

在列車換掛站，固定車組重量的分組列車的車小時消耗包括車輛集結(jié)車小時消耗、車組等待車小時消耗、調(diào)車作業(yè)車小時消耗和直通車流額外停留4部分。

(21)

(22)

(23)

(24)

(25)

(4)直通車流額外停留車小時消耗ΔTZT。分組列車內(nèi)的直通車流NZT在換掛站1晝夜產(chǎn)生的額外停留車小時消耗ΔTZT為

ΔTZT=NZTΔtZT

(26)

2.3.1.3合并式分組列車1晝夜總的車小時消耗

綜上，對于合并式分組列車，1晝夜總的車小時消耗TH可分為以下3種情況進行計算。

(1)當(dāng)NG=NZ時，

(27)

(2)當(dāng)NG>NZ時，

(28)

(3)當(dāng)NG

(29)

2.3.1.4合并式分組列車較單組列車的車小時節(jié)省

根據(jù)合并式分組列車1晝夜總的車小時消耗，分以下3種情況計算合并式分組列車較單組列車的車小時節(jié)省ΔTH。

(1)當(dāng)NG=NZ時，

(30)

(2)當(dāng)NG>NZ時，

(31)

(3)當(dāng)NG

(32)

2.3.2銜接式分組列車的車小時計算

銜接式分組列車與合并式相比，1晝夜增加的車小時消耗ΔTS為

(33)

再根據(jù)合并式分組列車1晝夜總的車小時消耗，可得到銜接式分組列車1晝夜總的車小時消耗TX為

TX=TH+ΔTS

(34)

根據(jù)合并式分組列車較單組列車的車小時節(jié)省，得到銜接式分組列車較單組列車的車小時節(jié)省ΔTX為

ΔTX=ΔTH+ΔTS

(35)

3　技術(shù)站列車編組計劃綜合優(yōu)化模型

1)約束條件

(1)只有單組列車去向i站到k站與k站到j(luò)站同時存在，且與單組列車對比有車小時消耗節(jié)省，才有可能開行i站到j(luò)站去向的分組列車，則有

(36)

式中：I(x)為階躍函數(shù)。

(2)任何1個單組去向的車流只能選擇1種分組列車方案，可以是分組列車基本車組，也可以作為分組列車的補軸車組，但只能選擇其中1種，則有

(37)

(3)分組列車的換掛站應(yīng)該避免選擇沒有直通場的縱列式編組站，設(shè)集合W是不能作為換掛站的技術(shù)站集合，則有

(38)

此外，分組列車換掛站應(yīng)該避免選擇車站能力限制的編組站,但由于分組列車方案是在最優(yōu)單組列車編組方案的基礎(chǔ)上建立起來的，此處不再考慮車站能力限制。

2)綜合優(yōu)化模型

綜上，以列車集結(jié)和車流改編的總車小時消耗最小為目標(biāo)函數(shù)，綜合考慮單組列車和分組列車，在滿足路網(wǎng)上車站設(shè)備能力和組織要求條件下，得到技術(shù)站列車編組計劃綜合優(yōu)化模型為

(1-Xij)TX]}

(39)

s.t. 式(36)—式(38)

4　求解算法

技術(shù)站列車編組計劃優(yōu)化問題是一個典型的NP難題，需要采用現(xiàn)代優(yōu)化算法進行求解。本文首先采用遺傳算法求解式(1)—式(5)所示的單組列車編組方案模型，得到單獨開行單組列車的編組計劃；在此基礎(chǔ)上，采用遍歷算法求解式(36)—式(39)所示的技術(shù)站編組計劃綜合優(yōu)化模型，得到適合開行分組列車的方案，計算分組列車替代單組列車后車小時消耗節(jié)省情況，以是否有益于優(yōu)化路網(wǎng)總的技術(shù)站車小時消耗為原則，確定是否開行分組列車；最終得到同時開行單組列車和分組列車的綜合編組計劃。由于遍歷算法較為基本和簡單，下面主要對遺傳算法進行闡述。

遺傳算法將1組隨機產(chǎn)生的解作為初始解，為第1代種群，種群中的每個個體為1個解，稱之為染色體，染色體通過選擇、交叉、變異不斷迭代進化生成下一代，經(jīng)過若干代迭代，最后收斂于最優(yōu)解。

首先確定計算參數(shù)：種群大小為D，最大代數(shù)為N，交叉概率為Pc，變異概率為Pm，隨機生成初始種群Q(0)，計算種群中個體適應(yīng)度函數(shù)，按照遺傳策略，對種群進行選擇、交叉和變異，形成下一代種群，最后判斷是否停止。遺傳算法中使用適應(yīng)度函數(shù)來度量每個解達到的優(yōu)良程度。

1)編碼

任意2個技術(shù)站去向變量的取值具有獨立性，采用分塊編碼。

符號||之間是2個編碼塊，代表了2個技術(shù)站之間開行直達以及途中改編站。

2)種群大小及初始種群

種群大小決定了最終求得的解是否是全局最優(yōu)解，如果規(guī)模太小，容易陷入局部最優(yōu)，但種群規(guī)模太大，計算量將顯著增加。經(jīng)過試算，總?cè)阂?guī)模為20時能夠滿足計算的要求。初始種群按照編碼塊進行隨機賦值產(chǎn)生，且賦值時滿足式(1)的要求，保證初始種群都是有意義的取值。

3)適應(yīng)度函數(shù)的選擇

適應(yīng)度函數(shù)根據(jù)目標(biāo)函數(shù)選擇，本文的目標(biāo)函數(shù)Z為恒大于0的正數(shù)，因此適應(yīng)度函數(shù)f可選擇為

(40)

4)算子的確定

選擇算子：遺傳算法使用選擇算子來對種群中的個體進行優(yōu)勝劣汰操作，本文采用輪盤賭選擇，根據(jù)個體的適應(yīng)度函數(shù)值，并使適應(yīng)度較高的個體遺傳到一下代種群中的概率較大。第a代第b個個體被選擇的概率Pb為

(41)

交叉算子：交叉運算使用單點交叉算子。只有1個交叉點位置，隨機進行個體間兩兩組合，隨機產(chǎn)生1個交叉點位置，2個個體在交叉點位置互換部分基因碼，形成2個子個體。

變異概率：變異概率一般取為0.000 1～0.1，如果變異概率過大，遺傳算法將變?yōu)殡S機搜索。本文使用的變異概率為0.001。

5)罰函數(shù)的設(shè)置

目標(biāo)函數(shù)的限制條件中存在不等式條件，需要將其轉(zhuǎn)化為等式約束條件，需要在目標(biāo)函數(shù)中設(shè)置罰函數(shù)。罰數(shù)值應(yīng)充分大，因此選擇值為100 000。

6)終止規(guī)則

算法通過遺傳代數(shù)控制終止操作，這也是遺傳算法的通用終止規(guī)則。

5　算例分析

以我國東北地區(qū)局部鐵路網(wǎng)絡(luò)為例，圖5中有14個車站[11]，對提出的技術(shù)站單組列車編組方案和分組列車開行方案優(yōu)化模型及算法進行驗證。各技術(shù)站之間的原始車流數(shù)據(jù)及各技術(shù)站的改編參數(shù)見表1和表2，分組列車相關(guān)參數(shù)見表3。

圖5　路網(wǎng)結(jié)構(gòu)示意圖

表1　技術(shù)站間車流量

利用遺傳算法求解單組列車編組計劃優(yōu)化模型，遺傳算法運行50～150代時，每代最小值和每代平均值均在一個相對小的區(qū)間內(nèi)變動，且目標(biāo)函數(shù)值遠小于罰數(shù)，因此運行到150代停止時，認(rèn)為結(jié)果已經(jīng)收斂到最優(yōu)，得到單組列車編組方案車小時消耗最小值為157 651.84車小時。以優(yōu)化得到的單組列車編組方案為已知變量，采用遍歷算法，求解技術(shù)站編組計劃綜合優(yōu)化模型，得到共需開行18組分組列車，最終得到同時開行單組列車和分組列車時，技術(shù)站列車編組計劃的車小時消耗為155 743.479車小時，比僅開行單組列車時節(jié)約1 908.361車小時。

表2　各技術(shù)站改編參數(shù)

表3　分組列車相關(guān)參數(shù)

6　結(jié)　論

分組列車作為一種高級的車流組織形式，以編成站集結(jié)車小時消耗較少增加為代價，換取換掛站車小時消耗的較多節(jié)省，從而實現(xiàn)更好的技術(shù)經(jīng)濟效益。但開行分組列車較為復(fù)雜，相應(yīng)的技術(shù)作業(yè)條件要求也較為嚴(yán)格，需與單組列車相互配合才能實現(xiàn)最大經(jīng)濟效益。鑒于此，本文提出了1種同時開行單組列車和分組列車的技術(shù)站列車編組計劃綜合優(yōu)化方法。首先只考慮開行單組列車情況，以技術(shù)站的總車小時消耗最小為目標(biāo)，建立單組列車編組計劃規(guī)劃模型。然后分別分析合并式分組列車和銜接式分組列車的車小時消耗，并對其相對于單組列車節(jié)省的車小時消耗進行計算。以最大限度地降低技術(shù)的站總車小時消耗為目標(biāo)，引入階躍函數(shù)設(shè)置開行分組列車的條件，建立同時開行單組列車和分組列車的技術(shù)站編組計劃綜合優(yōu)化模型。采用遺傳算法求解單組列車編組計劃優(yōu)化模型，然后以計算結(jié)果為已知條件，采用遍歷算法求解綜合優(yōu)化模型，得到綜合效益更佳的技術(shù)站列車編組計劃。最后通過1個實例計算證明，采用本文提出的模型和算法能夠快速、便捷地獲得1個同時開行單組列車和分組列車的技術(shù)站綜合列車編組計劃，且綜合列車編組計劃能有效降低技術(shù)站的總車小時消耗。

[1]林柏梁, 田亞明, 王志美. 基于最遠站法則的列車編組計劃優(yōu)化雙層規(guī)劃模型[J]. 中國鐵道科學(xué), 2011, 32(5)：108-113.

(LIN Boliang, TIAN Yaming, WANG Zhimei. The Bi-Level Programming Model for Optimizing Train Formation Plan and Technical Station Load Distribution Based on the Remote Reclassification Rule [J]. China Railway Science, 2011, 32(5)：108-113. in Chinese)

[2]許紅, 馬建軍, 龍昭, 等. 技術(shù)站單組列車編組方案模型與計算方法的研究[J]. 鐵道學(xué)報, 2006, 28(3)：12-17.

(XU Hong, MA Jianjun, LONG Zhao, et al. Study on the Model and Algorithm of the Formation Plan of Single Group Trains at Technical Service Stations [J]. Journal of the China Railway Society, 2006, 28(3)：12-17. in Chinese)

[3]張震. 單組技術(shù)直達列車編組方案的最優(yōu)化理論和方法[J]. 鐵道運輸與經(jīng)濟, 1979(1)：43-53.

(ZHANG Zhen. The Optimization Theory and Method for One-Block Train Formation Plan [J]. Railway Transport and Economy, 1979(1)：43-53. in Chinese)

[4]李夏苗, 盧紅巖. 快運貨物列車編組方案的優(yōu)化[J]. 中國鐵道科學(xué), 2004, 25(2)：117-120.

(LI Xiamiao, LU Hongyan. Optimization of Train Formation Diagram of Express Freight [J]. China Railway Science, 2004, 25(2)：117-120. in Chinese)

[5]梁棟, 林柏梁. 技術(shù)站分組列車編組計劃的優(yōu)化理論及模型研究[J]. 鐵道學(xué)報, 2006, 28(3)：1-5.

(LIANG Dong, LIN Boliang. Study on the Theory Model of the Optimal Train Formation Plan of Multi-Block Trains at Technical Service Stations [J]. Journal of the China Railway Society, 2006, 28(3)：1-5. in Chinese)

[6]田亞明. 鐵路網(wǎng)編組站改編能力配置優(yōu)化研究[D]. 北京：北京交通大學(xué), 2012:28-29.

(TIAN Yamin. Railway Marshalling Yards Reclassifying Capability Configuration Optimization [D]. Beijing: Beijing Jiaotong University, 2012:28-29. in Chinese)

[7]LIN Boliang, WANG Zhimei. Optimizing the Freight Train Connection Service Network of a Large-Scale Rail System[J]. Transportation Research Part B, 2012(46)：649-667.

[8]陳崇雙, 王慈光, 楊運貴, 等. 不確定條件下開行固定車組重量分組列車適用條件研究[J]. 鐵道學(xué)報, 2011, 33(12)：1-8.

(CHEN Chongshuang, WANG Ciguang, YANG Yungui, et al. Research on Applicable Operation Conditions of Multi-Block Train with Fixed Weight under Uncertainty [J]. Journal of the China Railway Society, 2011, 33(12)：1-8. in Chinese)

[9]楊浩. 鐵路運輸組織學(xué)[M]. 2版.北京：中國鐵道出版社, 2006：248-253.

[10]王慈光. 關(guān)于固定車組重量的分組列車車小時消耗的計算[J]. 西南交通大學(xué)學(xué)報, 1985(4)：85-92.

(WANG Ciguang. The Computation of Wagon-Hour Consumption for Multi-Group Technical through Trains with Fixed-Weight Groups [J]. Journal of Southwest Jiaotong University, 1985(4)：85-92. in Chinese)

[11]紀(jì)麗君, 林柏梁, 喬國會, 等. 基于多商品流模型的鐵路網(wǎng)車流分配和徑路優(yōu)化模型[J]. 中國鐵道科學(xué), 2011, 32(3)：107-110.

(JI Lijun, LIN Boliang, QIAO Guohui, et al. Car Flow Assignment and Routing Optimization Model of Railway Network Based on Multi-Commodity Flow Model [J]. China Railway Science, 2011, 32(3)：107-110. in Chinese)