基于樹形結構的鐵路車流徑路優化模型

溫旭紅，林柏梁, 陳 雷

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

鐵路網車流徑路分配優化是我國鐵路運輸一項重要的基礎工作，是編制貨物運輸計劃、技術計劃、列車編組計劃以及列車運行圖的基礎[1]。我國鐵路運輸領域的專家學者對鐵路車流徑路優化進行廣泛研究，包括單、多目標的車流徑路問題[1-3]，重、空車流的協同車流徑路問題[4-5]，鐵路車流徑路與列車編組計劃綜合優化[6-7]以及基于多商品網絡流思想的車流徑路問題[8-10]等。鐵路車流有著獨特的運行特征，不僅要求同一股車流需要滿足不可拆分原則，還要求不同發站車流在某個支點站匯合后，對于具有相同到站的車流視為同一股車流，具有共同的運行徑路[11]，即同一到站的車流具有合并式路徑。具有這種結構特點的鐵路車流徑路不僅符合鐵路現場組織實際要求，同時也為鐵路運輸組織工作者制定編組計劃創造了良好基礎條件。

目前，針對鐵路車流的樹狀徑路優化方面的代表性的研究文獻有：文獻[12]將同一終點的車流合而不分的特點定義為“合并式路徑”，并提出了求解合并式路徑的多項式啟發式算法。文獻[13]構建了基于路徑集合的鐵路車流分配優化模型并通過模擬退火算法進行求解，其中路徑集合的確定對模型結果的影響難以忽視。文獻[14]將該特點形象地定義為“樹形徑路”，并在路網規劃研究中構建具有樹形結構貨流分配優化的模型[15]，該模型的約束條件包含高階非線性項。

本文基于文獻[12，14]的相關研究，構建以總走行費用最小為目標函數、滿足車流不可拆分和樹形徑路特點、以弧段上能力限制為約束的鐵路車流徑路優化的改進模型。

1 樹狀徑路及鐵路車流徑路優化模型

車流徑路方案作為制定編組計劃基礎必須與改編方案相互匹配。車流徑路是由沿途編組去向的徑路組合而成[15]，車流的改編中轉站必須限制在車流徑路上[6]。因此，在車流徑路方案中體現為同一終點的車流合而不分的特點。此時，同一終點所有車流的路徑呈“樹狀結構”。結合車流徑路和編組計劃相關理論，這里把車流徑路的樹形特點定義為：在支點路網上，有相同到站的技術車流在某支點站匯合后則視為同一股車，具有相同的運行路徑直至終點[11]。下面將在由7個技術站構成的簡化圖(圖1)中解釋該特點。假設需要對技術車流N17和N27進行分配，路網唯一的瓶頸區段(3,5)的能力為cap(3,5)。

圖1 樹形徑路示意圖

當cap(3,5)≥N17+N27時，則車流N17和N27在路網中的運行徑路為廣義最短路，如圖1(a)所示。當cap(3,5)∈[N27,N17+N27)：若不存在樹狀徑路要求，那么兩支車流的運輸路徑如圖1(b)所示，即技術車流N17和N27在支點3匯合后分開，并再次相遇于支點6；若滿足樹狀結構要求，那么車流N18和N28在支點站3匯合后不再分開，將共同經過支點4、支點6運輸直至終點7，如圖1(c)所示。值得注意的是，技術車流也必須滿足同一股車流不允許拆分運輸的原則。

1.1 模型構建前提和限定

模型的構建主要基于以下假設：

(1)假設已經完成車流以及路網歸并[16]，形成了由支點站構成的支點網絡；

(2)限定模型應用對象為技術車流在支點路網上的運行徑路。

1.2 參數及變量定義

鐵路支點網絡簡化為一個無向圖G=(V,E)，其中V為路網的支點站集合，E為路網的弧段集合，且有?e∈E。對于?i,j∈V，用Nij表示始發站點i到終到站點j的始發車流量。對于?i∈V，定義Yi是站點i所有的鄰接弧段集合且Yi?E；定義Hi為點i的所有鄰接點的集合且Hi?V。此外，定義Cape為弧段e的通過能力，Le為弧段e的里程。

1.3 基于樹狀結構的鐵路車流徑路優化模型

大多數情況下，車流徑路優化問題多以廣義里程最小衡量標準。故本文提出的模型以車流的廣義運輸里程最小化為目標，以樹形徑路約束、車流強度守恒約束以及路段能力約束為條件，記為鐵路車流徑路優化模型M1。

M1：

( 1 )

s.t.

( 2 )

( 3 )

( 4 )

( 5 )

很明顯，模型M1中包含非線性約束等式。接下來，將引入0-1輔助變量對模型中非線性約束條件( 2 )進行轉化處理。

( 6 )

那么，模型M1中約束( 2 )轉換為如下形式

( 7 )

( 8 )

其中，M表示一個足夠大的正數。不等式約束( 7 )和( 8 )共同體現了車流徑路的樹形樣式特點。所以，模型M1可以轉化為模型M2。

M2：

( 9 )

s.t.

(10)

(11)

(12)

(13)

(14)

(15)

顯然，模型M2是一個0-1混合整數的單目標數學規劃模型，可以通過IBM ILOG CPLEX進行求解驗證。

2 算例研究

本文采用文獻[8]中路網結構為背景構建了鐵路支點路網圖(如圖2所示)來驗證構建的鐵路車流徑路優化模型的可行性。

圖2 鐵路支點路網圖

圖2中包括20條弧段、14個支點站。假設支點路網中所有路段的上、下行的里程相同，只有序號為4、9和12號的三條路段為瓶頸區段。支點路網的弧段里程以及瓶頸區段通過能力參數見表1。另外，為了全面驗證模型的樹狀徑路效果，表1中設置了3組不同的瓶頸區段能力限制數據。

表1 支點路網的弧段里程和弧段能力參數

注：“—”表示路段的通過能力不受限制。

基于以上假設和數據，在處理器為Intel Core i3、內存為6 G的計算機上通過MATLAB 2012a編程語言調用IBM ILOG CPLEX 12.6優化軟件對所構建鐵路車流徑路優化模型M2進行驗證。驗證采用21支模擬車流OD數據。三組不同能力參數下模型徑路優化結果見表2。

表2 不同路段能力參數下的車流徑路優化結果

由表2可以看出，在三組不同的弧段能力數據下終到點為①、⑨和的車流路徑發生了調整，詳細車流徑路變化對比如圖3所示。

圖3(a)和3(b)為終到點為①的兩支車流N10,1和N12,1的徑路變化對比圖。在第2和3組能力限制下這兩支車流的徑路相同，均在支點②匯合后直到終點，如圖3(b)所示。而在第1組能力數據下，車流N12,1徑路調整為12→9→6→2→1，與車流N10,1在支點⑥匯合后直到終點①，如圖3(a)所示。

圖3(c)和3(d)為終到點為⑨的三支車流N4,9、N7,9和N8,9徑路變化對比圖。在第1、2組能力數據下這三支車流在支點⑥相匯后直到終點，如圖3(c)所示。在第3組能力數據下，N7,9和N8,9的車流徑路不變而車流N4,9徑路調整為4→1→2→3→9，如圖3(d)所示。

圖3 在不同能力限制下車流徑路變化對比

由圖3可以明顯發現，雖然受到弧段能力參數變化的影響車流徑路產生變化，但是模型仍可以保證得到車流徑路具有樹狀結構特征。

在第1組能力參數下與文獻[8]中模型優化的路徑結果對比見表3。

表3 車流徑路優化結果對比

圖4 終點到12的車流徑路優化對比

3 結論及展望

本文根據我國鐵路車流獨特的運行特征，提出了具有樹狀結構的鐵路車流徑路優化模型。模型以傳統車流總走行里程最小為優化目標，約束條件包括車流徑路的樹狀結構特點、車流強度守恒以及弧段通過能力限制。研究表明：本文提出的模型可以保證不同的弧段能力參數下優化的車流路徑都具有樹狀結構；與傳統優化模型對比，構建的模型可以滿足鐵路車流徑路的樹狀結構要求。

鐵路網車流優化是NP難問題，優化軟件難以解決大規模問題。接下來的研究重點是大規模鐵路網下模型求解算法研究。另外，車流徑路與編組計劃關系密切，與編組計劃的綜合優化也是未來研究的重要方向。

參考文獻：

[1]高旭敏, 周潮, 顧炎. 鐵路網貨車車流經路分配的優化模型及算法[J]. 鐵道學報, 1992, 14(4): 43-48.

GAO Xumin, ZHOU Chao, GU Yan. The Optimization Model and Algorithm of the Distribution of Cars' Paths in a Railway Network[J]. Journal of the China Railway Society, 1992, 14(4):43-48.

[2]施其洲. 鐵路網絡系統運輸能力與車流路徑模型[J]. 鐵道學報, 1996, 18(4): 1-9.

SHI Qizhou. Models for Rail Network System Transportation Capacity and Traffic Pathing[J]. Journal of the China Railway Society, 1996, 18(4): 1-9.

[3]孫晚華，鄭時德. 鐵路車流徑路優化算法的研究[J];北方交通大學學報, 1995, 19(1): 39-44.

SUN Wanhua, ZHENG Shide. Study on the Optimization Algorithm of Railway Wagon Flow Path [J]. Journal of Northern Jiaotong University, 1995, 19(1): 39-44.

[4]施其洲, 施勇. 具有雙向空重車流的路網車流徑路多目標線性規劃模型及算例[J]. 鐵道學報, 1999, 21(1): 1-9.

SHI Qizhou, SHI Yong. Multi-objective Linear-programming Model and Its Algorithm for Car Flow Routing with Bidirectional Heavy and Empty Cars in Railway Network[J]. Journal of the China Railway Society, 1999, 21(1): 1-9.

[5]杜進有, 姚新勝, 黃洪鐘. 路網車流徑路的滿意優化[J]. 系統工程, 2006, 23(9): 46-49.

DU Jinyou, YAO Xinsheng, HUANG Hongzhong. Satisfactory Optimization of the Wagon Flow Problem in Railway Network[J]. Systerm Engineering, 2006, 23(9): 46-49.

[6]史峰, 孔慶鈐, 胡安州. 車流徑路與編組計劃綜合優化的網絡方法[J]. 鐵道學報, 1997, 19(1): 1-6.

SHI Feng, KONF Qingqian, HU Anzhou. A Network Method of Comprehensive Optimization of Wagon Path and Train Formation Plan[J]. Journal of the China Railway Society, 1997, 19(1): 1-6.

[7]林柏梁, 朱松年. 路網上車流徑路與列車編組計劃的整體優化[J]. 鐵道學報, 1996, 18(1): 1-7.

LIN Boliang, ZHU Songnian. Synthetic Optimization of Train Routing and Makeup Plan in a Railway Network[J]. Journal of the China Railway Society, 1996, 18(1): 1-7.

[8]紀麗君,林柏梁,喬國會,等.基于多商品流模型的鐵路網車流分配和徑路優化模型[J]. 中國鐵道科學, 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.

[9] 田亞明, 林柏梁, 紀麗君. 基于多商品里和虛擬弧的鐵路車流分配點-弧和弧-路模型研究[J].鐵道學報,2011, 33(4): 7-12.

TAN Yaming, LIN Boliang, JI Lijun. Railway Car Flow Distribution Node arc and Arc-path Models Based on Multi-commodity and Virtual Arc[J]. Journal of the China Railway Society, 2011, 33 (4):7-12

[10] 溫旭紅, 林柏梁, 王龍, 等. 基于多商品網絡流理論的鐵路車流分配及徑路優化模型[J]. 北京交通大學學報, 2013, 37(3): 117-121.

WEN Xuhong, LIN Boliang, WANG Long, et al. Optimization Model for Railway Car Flow Assignment and Routing Plan Based on Multi-commodity Network Flow theory[J]. Journal of Beijing Jiaotong University, 2013, 37(3): 117-121.

[11]林柏梁, 徐忠義, 黃民, 等. 路網發展規劃模型[J]. 鐵道學報, 2002, 24(2): 1-6.

LIN Boliang, XU Zhongyi, HUANG Min, et al. An Optimization Model to Railroad Network Designing [J]. Journal of the China Railway Society, 2002, 24(2):1-6.

[12]史峰, 李致中. 鐵路車流路徑的優選算法[J]. 鐵道學報, 1993, 15(3): 70-76.

SHI Feng, LI Zhizhong. An Algorithm for the Wagon Path Problem[J]. Journal of the China Railway Society, 1993, 15(3): 70-76.

[13]史峰, 黎新華, 莫輝輝, 等. 鐵路OD分配優化方法[J]. 中國鐵道科學, 2004, 25(4): 116-119.

SHI Feng, LI Xinhua, MO Huihui, et al. An Optimal Method for Railway Origin Destination Assignment[J]. China Railway Science, 2004, 25(4): 116-119.

[14]LIN B L. A Tree-type Car Route Guidance Models for ITS[C]//Kelvin Wang,Guiping Xiao, Lei Nie, et al. Traffic and Transportation Studies(2002).American Society of Civil Engineers,2002:620-625.

[15]李宵寅. 基于不確定參數的列車編組計劃與車流徑路綜合優化研究[D]. 成都：西南交通大學, 2011.

[16]胡思繼. 鐵路行程組織[M].北京：中國鐵道出版社，2012:114-116.