大型復(fù)雜樞紐列流圖的列流線排列優(yōu)化算法

耿敬春，倪少權(quán)，李建新，呂苗苗

(1.西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 610031；2.中國(guó)鐵路經(jīng)濟(jì)規(guī)劃研究院有限公司 線路站場(chǎng)咨詢部， 北京 100844；3.西南交通大學(xué) 綜合交通運(yùn)輸智能化國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室，四川 成都 610031；4.西南交通大學(xué) 綜合交通大數(shù)據(jù)應(yīng)用技術(shù)國(guó)家工程實(shí)驗(yàn)室，四川 成都 610031)

鐵路列流圖是鐵路建設(shè)項(xiàng)目運(yùn)輸組織設(shè)計(jì)的重要內(nèi)容之一，是反映某個(gè)鐵路樞紐、車站(技術(shù)作業(yè)站、客運(yùn)站等)及銜接的各方向鐵路線，在一定時(shí)間(一般指一晝夜)內(nèi)上下行方向到發(fā)各種列車列數(shù)的示意圖形；一般用不同類型的線條符號(hào)和顏色表示列車種類，附加以數(shù)字表示列車數(shù)量，沿鐵路線依次鋪畫。針對(duì)單一鐵路線或簡(jiǎn)單的鐵路樞紐，設(shè)計(jì)人員基于AutoCAD手工逐一鋪畫列流線較為簡(jiǎn)單、方便。大型復(fù)雜鐵路樞紐具有車站數(shù)量多、車站分工復(fù)雜、銜接鐵路線多、列流線多等新特點(diǎn)，基于AutoCAD手工編制列流圖的效率和質(zhì)量已不能適應(yīng)勘察設(shè)計(jì)要求。列流圖編制主要包括樞紐鐵路線路與車站拓?fù)潢P(guān)系、列車開行方案(即列流線)和列流線排列3個(gè)方面。其中，鐵路線路與車站拓?fù)潢P(guān)系由樞紐布局形態(tài)確定；列流線設(shè)計(jì)主要包括始發(fā)站、終到站、列車種類、經(jīng)由徑路和列車數(shù)量等，一般根據(jù)客貨運(yùn)OD(Origin-Destination)按照一定規(guī)則設(shè)計(jì)。

目前，我國(guó)對(duì)列流圖的優(yōu)化研究取得了一定成效。史峰等[1]提出列流圖的左右、緊湊、分層、對(duì)稱和分類5種排列原則，當(dāng)排列原則相沖突時(shí)，除對(duì)稱和分層排列原則外，應(yīng)遵循分類、左右、緊湊排列的先后順序。文獻(xiàn)[2-5] 給出了折點(diǎn)、徑點(diǎn)、拐點(diǎn)和描繪點(diǎn)等術(shù)語(yǔ)定義；借鑒最短徑路算法，提出鐵路路網(wǎng)點(diǎn)集合描繪思路、列流線自動(dòng)描繪的標(biāo)號(hào)算法思路、站點(diǎn)連通路徑標(biāo)號(hào)算法、點(diǎn)集合及邊集合自動(dòng)生成算法、列流線折點(diǎn)搜索算法、列流線偏移描繪算法等。這些研究為實(shí)現(xiàn)計(jì)算機(jī)自動(dòng)編制列流圖提供了技術(shù)支持。鑒于大型復(fù)雜樞紐內(nèi)車站數(shù)量多、銜接方向多、列流線多等新特點(diǎn)，本文在大型復(fù)雜樞紐線路與車站拓?fù)潢P(guān)系、大規(guī)模列流線既定的基礎(chǔ)上，研究基于“通道法”的列流線在各鐵路線和車站的互相排列優(yōu)化問題，以提高大型復(fù)雜樞紐列流圖的編制效率和編制質(zhì)量。

本文僅研究基于給定列車開行方案[6](始發(fā)終到站、列車種類、經(jīng)由徑路、列車數(shù)量)條件的列流線排列優(yōu)化問題，對(duì)客貨車開行方案[7-12]具體設(shè)計(jì)過(guò)程將另行研究。

1 問題描述及概念定義

1.1 符號(hào)設(shè)定及說(shuō)明

列流圖主要包括車站及銜接方向、鐵路線、列流線等基礎(chǔ)數(shù)據(jù)。樞紐內(nèi)鐵路線與車站的位置布局及其銜接關(guān)系，形成了復(fù)雜的拓?fù)潢P(guān)系。列流線根據(jù)列車編組計(jì)劃的要素[6]，按照列車沿鐵路線左側(cè)行車的要求，沿著鐵路線左側(cè)依次從內(nèi)側(cè)向外側(cè)緊湊排列。據(jù)此，給出了車站及其相關(guān)、鐵路線、列流線等定義，車站相關(guān)定義見圖1；根據(jù)列流線沿一系列具有特定特征兩兩首尾相銜接的鐵路線外側(cè)行進(jìn)具有不改變排列關(guān)系的特點(diǎn)，給出了通道到發(fā)節(jié)點(diǎn)對(duì)集合的定義；相關(guān)的集合、參數(shù)符號(hào)及說(shuō)明見表1，變量符號(hào)及說(shuō)明見表2。

圖1 車站相關(guān)定義

表1 集合、參數(shù)符號(hào)及說(shuō)明

表2 參數(shù)符號(hào)及說(shuō)明

1.2 鐵路線布局

由任意2個(gè)不相同的節(jié)點(diǎn)連接形成的邊即為一條鐵路線ri(鐵路區(qū)間)，ri滿足ri=(gs,ls,k,gs′,l′s′,k′),?gs,ls,k≠gs′,l′s′,k′。按前述車站相關(guān)概念，鐵路線r1=(gs1,1,1,gs2,3,0)為水平布置、r2=(gs2,0,0,gs3,2,0)為垂直布置、r3=(gs1,0,0,gs3,3,0)為拐彎布置和r4=(gs1,0,1,gs1,1,0)為環(huán)形布置，見圖2。

圖2 鐵路線布置形式

1.3 通道模型建立

wi={Ni,s0,Ni,s1,…,Ni,sm}=

滿足：?m，|l′sm-lsm|=2，

[gsm,ls,k(x)=gsm,l′s,k′(x)∧(lsm=0∨lsm=2)]∨

[gsm,ls,k(y)=gsm,l′s,k′(y)∧(lsm=1∨lsm=3)]

通道構(gòu)成示意見圖3。圖3中，由藍(lán)色、紫色、紅色、綠色鐵路線共組成8個(gè)通道，如w0為由藍(lán)色鐵路線兩兩首尾相連接銜接的車站s1、s2、s3、s4對(duì)應(yīng)節(jié)點(diǎn)對(duì)組成的通道，w4為其按列車運(yùn)行的反方向組成的通道；w2為由紅色鐵路線兩兩首尾相連接銜接的車站s10、s6、s2、s3、s4對(duì)應(yīng)節(jié)點(diǎn)對(duì)組成的通道，w6為其按列車運(yùn)行的反方向組成的通道。

圖3 通道構(gòu)成示意

2 假設(shè)與通道集合求解算法

2.1 假設(shè)

假設(shè)1：排列在同一鐵路線外側(cè)的所有列流線相互之間的排列關(guān)系保持不變，且所有列流線均與鐵路線按一定間距d的整數(shù)倍n距離平行排列。

假設(shè)2：排列在同一通道wi內(nèi)所有鐵路線外側(cè)的所有列流線相互之間的排列關(guān)系保持不變，且所有列流線均與鐵路線按d的n倍距離平行排列。

在假設(shè)1和假設(shè)2條件下，求解列流線的優(yōu)化排列問題將化簡(jiǎn)為求解通道集合和求解列流線在通道wi中對(duì)應(yīng)節(jié)點(diǎn)的占用狀態(tài)集合元素的值。

2.2 通道集合求解算法

在求解列流線的優(yōu)化排列問題，根據(jù)列流圖中車站、鐵路線布局，通道和通道集合的定義，構(gòu)建通道集合W，求解算法如下。

Step1在鐵路線集合R中任取一個(gè)鐵路線ri=(gs,ls,k,gs′,ls′,k)，將其作為通道wi經(jīng)由的一個(gè)鐵路區(qū)間；為使鐵路線ri僅包含于一個(gè)通道中，將ri從集合R中剔除。以此鐵路線銜接的2個(gè)節(jié)點(diǎn)為起始，按照Step2和Step4分別向兩端建立到發(fā)節(jié)點(diǎn)對(duì)。

Step3在鐵路線集合R中遍歷所有鐵路線，得到包含節(jié)點(diǎn)gs,l′s,k′的鐵路線ri=(gs,l′s,k′,gs′,ls′,k)。若ri=?，終止順向建立到發(fā)節(jié)點(diǎn)對(duì)；否則，將鐵路線ri銜接的節(jié)點(diǎn)gs′,ls′,k代入Step2循環(huán)執(zhí)行，同時(shí)在集合R剔除元素ri。

Step5在鐵路線集合R中遍歷所有鐵路線，得到包含節(jié)點(diǎn)gs′,l′s′,k′的鐵路線ri=(gs,ls,k,gs′,l′s′,k′)。若ri=?，終止逆向建立到發(fā)節(jié)點(diǎn)對(duì)；否則，將鐵路線ri銜接的節(jié)點(diǎn)gs,ls,k代入Step4循環(huán)執(zhí)行，同時(shí)在集合R剔除元素ri。

3 列流線排列優(yōu)化算法

3.1 列流線的排列關(guān)系

(1)直行最內(nèi)側(cè)原則

→列流線；--2條鐵路線間接上下行線鋪畫的列流分割線。圖4 列流線排列關(guān)系

(2)始發(fā)最外側(cè)原則和終到最外側(cè)原則

(3)到達(dá)節(jié)點(diǎn)列流線“逆時(shí)針”排列原則

(4)出發(fā)節(jié)點(diǎn)列流線“順時(shí)針”排列原則

3.2 列流線的“通道法”排列優(yōu)化算法

(1)“通道法”排列優(yōu)化思路

由列車徑路節(jié)點(diǎn)集合Pt和通道wi可知，任一列流線t的徑路節(jié)點(diǎn)集合Pt是由一個(gè)或若干個(gè)通道wi的子集按列車運(yùn)行方向先后經(jīng)由的車站順序排列構(gòu)成的集合。如圖5所示，列流線a的徑路節(jié)點(diǎn)集合Pa由通道w1的子集構(gòu)成，列流線b的徑路節(jié)點(diǎn)集合Pb分別由通道w2、w1的子集構(gòu)成，列流線c的徑路節(jié)點(diǎn)集合Pc分別由通道w7、w1的子集構(gòu)成，列流線d的徑路節(jié)點(diǎn)集合Pd分別由通道w0、w3、w1的子集構(gòu)成。因此，可將列流線的排列優(yōu)化問題按經(jīng)由的通道子集進(jìn)行分段求解優(yōu)化；如列流線d的排列問題將分解為在通道w0中車站s1至車站s2、通道w3中車站s2至車站s7和通道w1中車站s7至車站s9的3個(gè)排列問題。

圖5 通道列流線排列示意

(2)“通道法”列流線排列優(yōu)先權(quán)重求解算法

在假定2條件下，將在同一通道內(nèi)經(jīng)由到發(fā)節(jié)點(diǎn)數(shù)量越多的列流線排列在越靠近鐵路線的內(nèi)側(cè)，使得列流線布局越緊湊。因此，同一通道內(nèi)的列流線需要按照優(yōu)先權(quán)重的大小進(jìn)行排列，權(quán)重越大的，越優(yōu)先排列，且排列在內(nèi)側(cè)；否則，排列在外側(cè)。求解算法如下。

Step1設(shè)置默認(rèn)值。Zt,wi為列流線t在通道wi的排列優(yōu)先權(quán)重；設(shè)置所有列流線的排列優(yōu)先權(quán)重Zt,wi=0，?t∈Twi。

Step2求解列流線排列優(yōu)先權(quán)重。

Step3求解通道wi內(nèi)優(yōu)先權(quán)重。

Step4求解順向至終到站優(yōu)先權(quán)重。

圖6 到達(dá)節(jié)點(diǎn)列流線數(shù)量級(jí)

Step4.3循環(huán)遞歸執(zhí)行Step4，順向至列流線t的終到站時(shí)終止。

Step5求解逆向至始發(fā)站優(yōu)先權(quán)重。

圖7 出發(fā)節(jié)點(diǎn)列流線數(shù)量級(jí)

Step5.3循環(huán)遞歸執(zhí)行Step5，反向至列流線t的始發(fā)站時(shí)終止。

(3)“通道法”列流線排列優(yōu)化算法

在大型復(fù)雜鐵路樞紐中，根據(jù)鐵路線與車站的拓?fù)潢P(guān)系及布局，將其劃分為若干個(gè)通道；以通道為單位，求解列流線在通道的排列優(yōu)化，以達(dá)到整個(gè)列流圖中列流線的布局優(yōu)化。借鑒文獻(xiàn)[13-14]思路，求解算法如下。

Step1根據(jù)車站、鐵路線布局，按照通道集合求解算法，構(gòu)建通道集合W；在通道集合W任取一個(gè)通道wi。若wi≠?，執(zhí)行Step2，同時(shí)在W中剔除元素wi；否則，終止。

Step2按照通道列流線集合定義，求解Twi；若Twi≠?，執(zhí)行Step3；否則，返回Step1。

Step3按照“通道法”列流線排列優(yōu)先權(quán)重求解算法，求解通道列流線集合Twi中所有列流線的優(yōu)先權(quán)重。取max(Zt,wi)，?t∈Twi；若t≠?，執(zhí)行Step4，同時(shí)在Twi中剔除t；否則，返回Step1。

按照上述算法，求解圖5中通道w1中列流線的排列優(yōu)先權(quán)重如下：

4 上海鐵路樞紐算例驗(yàn)證

以上海鐵路樞紐客運(yùn)列流圖的編制對(duì)前述算法進(jìn)行實(shí)例驗(yàn)證。上海鐵路樞紐連接京滬高速、滬寧城際、南沿江鐵路、北沿江鐵路、滬昆高鐵、滬杭城際、滬乍杭鐵路、滬通鐵路、滬蘇湖鐵路、京滬鐵路、滬昆鐵路、金山鐵路、浦東鐵路，共計(jì)13條線路。隨著規(guī)劃線路的引入，樞紐客運(yùn)系統(tǒng)形成上海、上海南、上海虹橋、上海東以及上海寶山、松江南等“四主多輔”的客站格局。根據(jù)銜接線路所承擔(dān)客流以及上海鐵路樞紐客運(yùn)需求，上海鐵路樞紐規(guī)劃年度始發(fā)客車對(duì)數(shù)詳見表3，樞紐銜接4個(gè)方向間通過(guò)客車，始發(fā)、通過(guò)客車主要見表4，規(guī)劃年度遠(yuǎn)期始發(fā)、通過(guò)客車主要客站分工及作業(yè)量見表5、表6。

表3 規(guī)劃年度始發(fā)客車對(duì)數(shù)表 對(duì)/d

表4 規(guī)劃年度通過(guò)客車對(duì)數(shù) 對(duì)/d

表5 規(guī)劃年度遠(yuǎn)期始發(fā)客車主要客站分工及作業(yè)量 對(duì)/d

表6 規(guī)劃年度遠(yuǎn)期通過(guò)客車主要客站分工及作業(yè)量 對(duì)/d

圖8 規(guī)劃年度客運(yùn)列流

運(yùn)用本文提出的算法,在Windows操作系統(tǒng)Visual Studio 2019開發(fā)環(huán)境下,使用C#編程語(yǔ)言[15]研發(fā)了大型復(fù)雜鐵路樞紐列流圖編制系統(tǒng)；利用該系統(tǒng)，以上海鐵路樞紐為研究對(duì)象，根據(jù)表3～表6中的數(shù)據(jù)，編制了客運(yùn)列流圖，見圖8。

在列流圖編制過(guò)程中，為減少繪圖圖幅，可將具有相同列車徑路的同種列車類型的列流線合并鋪畫，將另行研究。經(jīng)人工核查，圖8所示的列流圖無(wú)列流線鋪畫和標(biāo)識(shí)錯(cuò)誤，驗(yàn)證了算法的合理性和有效性；在列流圖的自動(dòng)編制過(guò)程中，通道集合的求解和列流線的排列優(yōu)化時(shí)間消耗均小于1 s，在運(yùn)輸組織設(shè)計(jì)中可以忽略不計(jì)，表明了算法的高效性。

5 結(jié)論

本文針對(duì)大型復(fù)雜鐵路樞紐具有的車站數(shù)量多、車站分工復(fù)雜、銜接鐵路線多、列流線多等新特點(diǎn)，為解決設(shè)計(jì)人員基于AutoCAD的手工編制列流圖工作量大、效率低下、質(zhì)量不高等問題，根據(jù)鐵路樞紐內(nèi)車站、鐵路線之間拓?fù)潢P(guān)系以及車站銜接方向節(jié)點(diǎn)間的橫縱坐標(biāo)關(guān)系，提出了列流線直行最內(nèi)側(cè)、始發(fā)最外側(cè)、終到最外側(cè)、到達(dá)節(jié)點(diǎn)“逆時(shí)針”和出發(fā)節(jié)點(diǎn)“順時(shí)針”6條排列原則和列流線沿鐵路線、通道內(nèi)排列關(guān)系不變的2個(gè)假定條件，構(gòu)建了通道到發(fā)節(jié)點(diǎn)對(duì)集合的求解算法、列流線排列優(yōu)先權(quán)重求解算法和排列優(yōu)化算法。以上海鐵路樞紐客運(yùn)列流圖編制為例，運(yùn)用研發(fā)的列流圖編制系統(tǒng)驗(yàn)證了算法的合理性、有效性和高效性，解決了手工編制存在的困難和問題，實(shí)現(xiàn)計(jì)算機(jī)自動(dòng)編制大型復(fù)雜鐵路樞紐的列流圖。