列車開行方案優化中的機車交路影響研究

林柏梁，王振宇，倪少權，趙伊楠

(1.北京交通大學 交通運輸學院， 北京 100044；2.西南交通大學 交通運輸與物流學院，四川 成都 610031)

目前的貨物列車開行方案優化隱含著這樣一種假設：列車到達一個技術站時，若不進行解體改編作業則必有更換機車等無調作業，即默認直達列車途經技術站時必有無調作業。這種假設在蒸汽機車時代是合理的，因為蒸汽機車一般采用肩回式機車交路運行，通常每運行200～300 km就需要加煤加水換掛機車，這一距離與實際路網中相鄰技術站間距比較接近，因此默認直達列車途經技術站時必有無調作業是合理的。但是在牽引動力已經取得重大進步的今天，電力機車和內燃機車已經完全取代了蒸汽機車，它們兩者普遍采用循環制和半循環制機車長交路。除此之外，隨著鐵路網的不斷完善，部分技術站間的間距較短，甚至小于機車交路的距離，這也使得列車在途經技術站時并不一定需要換掛機車。實際中，在技術站的貨物列車作業類型主要有：到達解體或自編始發、無改編中轉、部分改編中轉和直接通過。其中到達解體和編組出發對應的是車輛的有調作業，無改編中轉對應的是無調作業，部分改編中轉列車主要是換掛車組作業，一般納入分組列車的組織范圍，本文暫不考慮部分改編中轉列車。這里的直接通過列車是指既不進行有調作業也不進行無調作業的列車。綜上分析，列車在技術站的作業模式可以歸納為：有調作業、無調作業、既不進行有調作業也不進行無調作業3種模式，而不是傳統的前兩類。需要說明的是，列車的無調作業通常在到發場或出發場(或直通場)上辦理，包括列檢、貨檢、換掛機車等作業。其中機車換掛作業占據了無改編中轉作業的主要時間。因此，本文將列車的無改編中轉作業等價為機車換掛作業，作業車站由機車交路確定，從而間接關聯機車交路與無改編中轉列車的內在聯系。本文在研究機車交路對列車開行方案的影響時，將機車交路作為輸入條件，綜合考慮無調作業和有調作業對貨物列車開行方案的影響。

在有關貨物列車開行方案優化的研究中，文獻[1]引入多商品流思想，將貨物列車開行方案問題看做多商品流網絡設計問題，并設計一種大規模領域搜索算法來求解。文獻[2-4]將該問題看做鐵路網節點能力有限的規劃問題，充分考慮了路網的通過能力和運輸能力，并根據所建模型的特性分別設計相應的啟發式算法進行求解。文獻[5]構建貨物列車開行方案雙層規劃優化模型，上層模型是列車服務網絡設計模型，下層模型在上層模型提供的網絡中進行配流，并設計模擬退火算法求解。文獻[6-7]構建鐵路車流徑路與列車編組計劃整體優化的非線性模型，并設計模擬退火啟發式算法進行求解。文獻[8]最早發現直達列車途經技術站均存在無調作業假設缺陷，考慮機車長交路因素，提出機車長交路條件下車流組織優化模式的重構模型。文獻[9-11]分別研究了分組列車和快運班列的開行方案優化問題。

綜上所述，既有的關于貨物列車開行方案優化的研究幾乎均未考慮機車交路的影響，僅文獻[8]發現直達列車途經支點站均存在無調作業假設缺陷，并提出機車長交路條件下車流組織優化模式的重構模型，由于文中模型沒有對直達列車服務網絡和車流有調中轉地點選擇進行上下層規劃分離，導致模型求解的困難，故僅僅給出了模型及其分析。本文在此基礎上，分離直達列車服務網絡優化與改編配流，分別構造直達去向優化的上層規劃模型，和針對每個備選直達方案的下層中轉配流模型，通過模擬退火隨機產生上層的直達去向進行迭代優化。

1 問題描述

傳統的貨物列車開行方案優化模型的目標函數是基于“min(集結車小時+有調作業停留車小時)”的框架，如文獻[5-6]中模型的目標函數為

(1)

式(1)中第一項為貨物列車的總集結費用，第二項為車流的額外改編總費用。由式(1)可知，傳統模型僅考慮了直達貨物列車的集結費用成本并未考慮其無調作業費用成本。目前國內直通、直達列車機車交路為400～600 km較為普遍化，而鐵路網中相鄰技術站間的間距一般在100～300 km，這意味著在現有背景下，若直達列車采用機車長交路，則在途經技術站時并不一定進行換掛機車等無調作業。以圖1為例說明傳統模型假設的局限性，假設開行F到H的直達列車，其中B站、F站、G站為機務折返段所在站，C站、E站、H站為機務段所在站，下圖中綠色線段代表肩回式機車交路，藍色線段代表循環式機車交路。

圖1 傳統模型(單位：km)

圖1(a)中，該直達列車在各個區段均采用肩回式機車交路，即列車途經各個技術站時必會進行換掛機車等無調作業。這種情況適用于傳統的基于蒸汽機車的假設，因此在貨物列車開行方案優化研究時，默認直達列車在技術站必有換掛機車的無改編作業是合理的。

圖1(b)中，該直達列車在F—B和B—G區間采用循環運轉制機車交路，在G—H區間采用肩回式機車交路。結合圖中實際情況，列車從F站出發，由于在F—B區間采用的是循環式機車交路，那么列車在途經E站時并不會停站換掛機車，而是到達B站后進行機車換掛，其原因是機車運行受到所屬區段的限制。同理，列車在途經C站時也不需要換掛機車，只需要在G站進行換掛機車等無調作業，最后到達H站。綜上分析，在現有背景下，直達列車在途經技術站時并不一定進行無調作業，具體作業情況受到機車交路的影響。

2 雙層規劃建模

2.1 模型參數及決策變量

參數符號及定義見表1。

表1 模型符號及定義

2.2 上層規劃模型的構建

如果計劃提供一組從i站到j站的直達列車，假設其途經的技術站有n個，則其中要辦理無調作業的車站數量一般小于n，這在不同的鐵路線路上有不同的方案。在數學上，這樣的在途無調作業總費用為

(2)

式中：λij為編組去向i→j的日均開行列數，其值為該編組去向的日均流量與列車編成輛數之比，即

λij=Dij/mij

(3)

(4)

式中：fij為i到j的實際車流量，包括i的后方站在該站中轉(在i站進行改編)形成的去往j站的車流，是一個中間變量，即

(5)

上層規劃模型確定鐵路網絡上哪些點對之間要提供直達列車服務，可構造為

(6)

(7)

(8)

Fk≤θkCRk?k∈S

(9)

(10)

(11)

(12)

式中：φ(Dij)為調車線數需求函數；Fk為k支點站的改編負荷量。按照文獻[12]，一般是200車占用一條股道。

目標函數式(6)由3部分構成，第一項為直達列車的集結車小時和途經技術站無改編通過的列車小時總成本，第二項為直達列車在途的無調作業總費用，第三項為所有支點站的車流改編費用。式(7)確保每支車流僅選擇一種輸送方案，即車流輸送方案的唯一性。式(8)是邏輯約束，如果i站到j站的車流在k站進行改編，那么i站到k站一定開行直達列車。式(9)是關于車站解編能力的約束，即車站的解編負荷要小于車站的解編能力。式(10)是車場調車線約束，考慮到編組股道運用具有一定的靈活性，本文采用φ(Dij)=Dij/200的形式確定每個編組去向對股道的需求。即需要占用的調車線數要小于車場可用的調車線數。式(11)表明決策變量為0-1變量。

2.3 下層規劃模型的構建

(13)

s.t.

(14)

(15)

(16)

?n≠in≠jn,j,u∈S

(17)

(18)

式中：M為一個正無窮大數。

式(13)為下層模型的目標函數，旨在實現車流的總相對延誤最小化。式(14)表示若不開行i到k的直達列車，那么i到j的車流不能在k站改編。式(15)～式(17)為模型的約束條件，采用流量平衡的思想，確保每支車流被送達至目的地。式(18)表明決策變量為0-1變量。

3 求解模型的模擬退火算法

結合本文模型在求解過程中需要不斷循環迭代的特性，選用模擬退火算法(Simulated Annealing，SA)對模型進行求解。

3.1 能量函數

為降低模型求解復雜度，將模型中的復雜約束條件作為懲罰項加入到目標函數中。復雜約束主要是式(9)、式(10)，將其作為懲罰項加入到上層規劃模型的目標函數中作為能量函數。

H(X)=β1max{0,Fk-θkCRk}+β2max{0,

(19)

式中：β1、β2為正懲罰參數，根據實際經驗，分為取值為400、200。

能量函數為

(20)

3.2 初始溫度的確定

在確定初始溫度時，根據文獻[13]先隨機產生m個解，則有

(21)

(22)

式中：m+、m-分別為能量函數Z(Xn)值增加、減少的解數；ρ0為給定的初始接受率，一般取0.9～0.99，本文對取值為0.98；Δavg為m+個能量函數增加值的平均值。

3.3 初始解的生成

3.4 鄰域解的生成

3.5 模擬退火算法步驟

Step1確定初始溫度T0。記當前的降溫次數k=0，轉Step2。

Step2記迭代次數為n=0。初始溫度下，按照3.3節中的方法產生初始解并計算能量函數值，轉Step3。

Step3當經過k次降溫后，在溫度Tk下，記第n-1次迭代后的解為Xn-1，為了得到鄰域解Xn，隨機增加1個或減少1個直達去向，計算出對應的函數值能量Z(Xn)，轉Step4。

Step4利用Metroplis抽樣準則對當前解進行檢驗，若Z(Xn)-Z(Xn-1)<0，則無條件接受Xn代替Xn-1；若Z(Xn)-Z(Xn-1)>0，則以概率γn(Tk)接受鄰域解。γn(Tk)為

(23)

轉Step5。

Step6算法收斂終止判定。本文設置了兩個終止準則：一種是接受率小于給定的閾值時，另一種是能量函數在多次迭代過程中保持不變，兩個準則滿足一個即結束該算法。否則，轉Step7。

Step7按如下公式進行降溫：

(24)

式中：參數δ一般取0.4，α一般取0.95；kd為高低溫迭代次數的分界點，一般為70；φ(Tk)為Tk溫度下能量函數期望值的標準差。

Tk溫度下經過降溫后，溫度更新，此時記降溫次數k=k+1，置迭代步數n=0，返回Step3，在新的溫度下進行循環迭代。

4 算例分析

4.1 算例背景

以京滬鐵路為背景進行案例研究。該線路的主要支點站有：豐臺西、南倉、德州、濟南西、兗州、徐州北、蚌埠東、南京東、南翔等，分別對其編號為Y1～Y9。其中，德州、兗州、蚌埠東為一般技術站，豐臺西、南倉、濟南西、徐州北、南京東、南翔為路網性編組站，具體網絡結構見圖2。

圖2 京滬線結構圖

4.2 潛在的列車編組去向及無調作業車站

表2 各編組去向換掛機車車站集合

4.3 技術站參數及OD矩陣

目前京滬線各區段的牽引定數普遍在5 000 t，考慮到區段列車編成輛數一般小于遠程直達列車的編成輛數，為了不失一般性，本文選取相鄰技術站間的區段(直通)列車編成輛數為50車，不相鄰技術站間的列車編成輛數為63車。9個支點站間的OD矩陣見表3。

表3 車流OD 車

表4 支點站技術參數

各支點站的能力參數見表5。考慮本文的研究算例僅是整個鐵路網中的一條通道，未考慮跨線流量，故這里的能力參數是經過理論分析后的剩余能力。例如，以豐臺西編組站為例，它是一個雙向系統的路網性編組站，其上下行系統的合計解體能力達萬車以上，兩個調車場的股道數量達百條之多，如果在該算例中仍采用其實際的能力參數，那么相當于在一定程度上松弛掉了某些約束。因此，本文在對能力參數取值時進行了人工處理。比如，在對可用調車線數CTk取值時適當縮小了相應的數值，如果仍采用實際中的CTk，那么相當于在一定程度上松弛掉了上層規劃模型中的約束式(10)，因此，為了體現其約束性，對技術參數CTk進行了適當的縮減。同理，對CRk也進行了適當地縮減。

表5 支點站能力參數

4.4 結果分析

為了體現本文所建模型的創新性和有效性，基于該算例分別使用文獻[5]中的傳統模型和本文構建的新模型進行計算，兩個模型的不同之處在于文獻[5]是傳統的貨物列車開行方案優化模型，由于默認直達列車在途經技術站時必有無調作業，因而模型中并未考慮無調作業對列車開行方案的影響；而本文的新模型則充分考慮了列車的無調作業產生的影響。

4.4.1 傳統模型計算結果

這里需要說明的是，在利用傳統模型進行計算時，采用表4中的無改編作業參數，默認列車在途經技術站時必會進行換掛機車等無調作業，并采用式(6)的形式將其無調作業費用作為定值分別計算到對應的直達列車去向yij中(以往認為其為定值，模型中僅有cimijyij而沒有將其計算在內)，這樣做的目的是為了便于與新模型的計算結果進行對比分析，以便突出其優越性。本文同樣采用模擬退火算法對傳統模型進行求解。最終結果表明，經過46次降溫迭代之后完成了優化計算，求解結果確定了12個理論優化編組去向，最終得到上層規劃目標函數的最優解為60 965車·h，計算結果見圖3。

圖3 傳統模型計算結果

以編組去向Y1→Y8為例進行說明，根據計算結果，Y1→Y8編組去向的車流需要在Y2和Y6進行改編，體現在圖中其改編鏈是(Y1→Y2)∪(Y2→Y6)∪(Y6→Y8)。計算結果中統計見表6,其中中最后一列表示車流改編鏈，比如(Y1→Y2)∪(Y2→Y3)表示 Y1→Y3去向的車流運輸任務由(Y1→Y2)和(Y2→Y3)的列車服務擔當。技術站的改編能力和調車線占用情況見表7。

表6 傳統模型計算結果統計

表6(續)

表7 傳統模型車站改編負荷及調車線占用情況

4.4.2 新模型計算結果

本文模型的計算結果見圖4，根據本文設計的求解步驟，采用VC++程序設計實現，在Core 2.4 GHz的PC機上運行，經過129次降溫迭代之后完成了優化計算。求解結果確定了17個理論優化編組去向，最終所得上層規劃目標函數的最優值41 390車·h。結果見圖4和表8，圖中弧段意義和表8中的參數，均與傳統模型計算結果中的參數一致。新模型技術站的改編能力和調車線占用情況見表9。

圖4 新模型計算結果

表8 新模型計算結果統計

表8(續)

通過對比結果可以看到，本文所建模型的優越性較為明顯，傳統模型得到的最優開行方案車流開行總成本為60 965車·h，本文所建模型得到的最優開行方案車流開行總成本為41 390車·h，車流開行總成本減少了32%。除此之外，所有車站的總體改編負荷有所下降，由之前的23 703車減少為22 181車。同時，新模型得到的結果也更加符合實際，比如Y7(蚌埠東)到Y2(南倉)的車流，在傳統模型的結果中，該編組去向需要開行直達列車。新模型得到的結果中，該編組去向的列車需要在Y6(徐州北)、Y4(濟南西)進行改編，這正是考慮了機車交路對列車編組計劃的影響。結合實際運行情況，上述兩種結果中后者更加符合實際，這是因為蚌埠東是一般技術站，而徐州北和濟南西為路網性編組站，在實際車流組織中，蚌埠東的車流一般要先到徐州北進行解體改編，然后進入濟南局管轄范圍，在到達濟南西后進行解體改編，最后進入北京局管轄范圍到達目的地。綜上分析，新模型得到的結果明顯優于傳統模型得到的結果，主要體現在車流開行總成本的減少，改編次數的減少和所得結果更加符合實際。

5 結論

本文為適應機車長交路普遍化發展，考慮了機車交路對直達列車無調作業的影響，構建了考慮無調和有調作業的列車開行方案優化雙層規劃模型。上層規劃模型在傳統模型的基礎上引進了列車的無改編作業費用，旨在實現列車開行總成本最小化。下層規劃模型以車流的總相對延誤最小化為目標，以流量平衡為約束條件。結合模型求解時需要不斷循環迭代的特性，采用模擬退火算法對模型進行求解。所得結果表明，新模型得到的最優開行方案明顯優于傳統模型得到的開行方案，主要體現在車流開行總成本的減少，所得結果更加符合實際。