基于樹形結構的鐵路車流徑路優(yōu)化模型

溫旭紅，林柏梁, 陳 雷

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

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

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

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

1 樹狀徑路及鐵路車流徑路優(yōu)化模型

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

圖1 樹形徑路示意圖

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

1.1 模型構建前提和限定

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

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

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

1.2 參數(shù)及變量定義

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

1.3 基于樹狀結構的鐵路車流徑路優(yōu)化模型

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

M1：

( 1 )

s.t.

( 2 )

( 3 )

( 4 )

( 5 )

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

( 6 )

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

( 7 )

( 8 )

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

M2：

( 9 )

s.t.

(10)

(11)

(12)

(13)

(14)

(15)

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

2 算例研究

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

圖2 鐵路支點路網(wǎng)圖

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

表1 支點路網(wǎng)的弧段里程和弧段能力參數(shù)

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

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

表2 不同路段能力參數(shù)下的車流徑路優(yōu)化結果

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

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

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

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

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

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

表3 車流徑路優(yōu)化結果對比

圖4 終點到12的車流徑路優(yōu)化對比

3 結論及展望

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

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

參考文獻：

[1]高旭敏, 周潮, 顧炎. 鐵路網(wǎng)貨車車流經(jīng)路分配的優(yōu)化模型及算法[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]施其洲. 鐵路網(wǎng)絡系統(tǒng)運輸能力與車流路徑模型[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]孫晚華，鄭時德. 鐵路車流徑路優(yōu)化算法的研究[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]施其洲, 施勇. 具有雙向空重車流的路網(wǎng)車流徑路多目標線性規(guī)劃模型及算例[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]杜進有, 姚新勝, 黃洪鐘. 路網(wǎng)車流徑路的滿意優(yōu)化[J]. 系統(tǒng)工程, 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]史峰, 孔慶鈐, 胡安州. 車流徑路與編組計劃綜合優(yōu)化的網(wǎng)絡方法[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]林柏梁, 朱松年. 路網(wǎng)上車流徑路與列車編組計劃的整體優(yōu)化[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]紀麗君,林柏梁,喬國會,等.基于多商品流模型的鐵路網(wǎng)車流分配和徑路優(yōu)化模型[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] 溫旭紅, 林柏梁, 王龍, 等. 基于多商品網(wǎng)絡流理論的鐵路車流分配及徑路優(yōu)化模型[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]林柏梁, 徐忠義, 黃民, 等. 路網(wǎng)發(fā)展規(guī)劃模型[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]史峰, 李致中. 鐵路車流路徑的優(yōu)選算法[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分配優(yōu)化方法[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]李宵寅. 基于不確定參數(shù)的列車編組計劃與車流徑路綜合優(yōu)化研究[D]. 成都：西南交通大學, 2011.

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