李致遠(yuǎn),王曉陽,張 杰,2,3,徐長安

(1. 西南交通大學(xué)交通運(yùn)輸與物流學(xué)院,四川 成都 610031;2. 綜合交通運(yùn)輸智能化國家地方聯(lián)合工程實(shí)驗(yàn)室,四川 成都 610031;3. 綜合交通大數(shù)據(jù)應(yīng)用技術(shù)國家工程實(shí)驗(yàn)室,四川 成都 610031)

1 引言

鐵路樞紐列流圖能直觀地展示樞紐網(wǎng)絡(luò)的站場布局與列車密度、列流的匯集分流情況,是優(yōu)化鐵路運(yùn)輸規(guī)劃和組織的有力工具[1],也是體現(xiàn)車流組織和列流組織的重要成果,對我國提升鐵路運(yùn)輸組織水平和推動鐵路規(guī)劃建設(shè)有著非常重要的作用[2]。

許多學(xué)者針對樞紐列流圖編制問題開展了研究。史峰等[3]針對列流圖的站場布局優(yōu)化與自動編制問題展開了研究,提出了具體的列流圖繪制步驟;程學(xué)慶等[4]基于“見縫插針”的思想,提出自動繪制列流圖的標(biāo)號算法;王兵[5,6]所開發(fā)的列流圖編制系統(tǒng)可以從列車運(yùn)行圖編制系統(tǒng)中直接提取列車運(yùn)行徑路等基礎(chǔ)數(shù)據(jù),優(yōu)化了數(shù)據(jù)管理功能,避免了繁瑣的基礎(chǔ)數(shù)據(jù)輸入;王保山等[7]使用狀態(tài)矩陣描述列流線在車站矩形內(nèi)的分布狀態(tài),按照列車的等級和徑路長度排序后,依次嘗試鋪畫列流線。雖然既有研究為樞紐列流圖編制進(jìn)行了有益探索,但尚未完全實(shí)現(xiàn)樞紐列流圖自動化編制。目前,在鐵路勘察設(shè)計(jì)院的實(shí)際工作中,依舊采用人工方式編制列流圖,繪制時需要投入較大的精力排列線條位置來避免其交叉和重合,且后期對圖紙的修改與調(diào)整也較為困難。

本文針對鐵路樞紐結(jié)構(gòu)復(fù)雜性,列流線密度大且分布不均勻的特點(diǎn),提出基于分層網(wǎng)格的鐵路樞紐列流圖編制的數(shù)學(xué)優(yōu)化模型,并設(shè)計(jì)自適應(yīng)遺傳算法求解,實(shí)現(xiàn)鐵路樞紐列流圖自動編制與優(yōu)化調(diào)整。

2 鐵路樞紐列流圖的表示

2.1 參數(shù)和符號說明

2.2 鐵路樞紐分層網(wǎng)格化表示

鐵路樞紐分層網(wǎng)格化具體形式表現(xiàn)為:車站使用矩形表示,相鄰車站之間通過水平或豎直的區(qū)間線連接。同時,將區(qū)間上列流線層次化,將車站內(nèi)的列流線網(wǎng)格化[8]。通過層級確定區(qū)間線左側(cè)通過的列流線排列順序,緊貼區(qū)間線的列流線定義為第1層級,向左依次增長[9]。通過網(wǎng)格記錄車站矩形內(nèi)部通過的列流線轉(zhuǎn)折位置,網(wǎng)格內(nèi)列流線通過的位置點(diǎn)記為1,否則記為0。圖1給出了鐵路樞紐分層網(wǎng)格化表示,其中紅色線條表示依次經(jīng)過車站的列流線。

圖1 鐵路樞紐分層網(wǎng)格化表示

2.3 鐵路樞紐列流線表示

鐵路樞紐列流線使用折線段表示,以車站矩形邊為起訖點(diǎn),沿列車徑路依次經(jīng)過車站與區(qū)間。站內(nèi)列流線按照其形態(tài)可被劃分為I型、Z型、L型、U型四種基本形式,。根據(jù)四種基礎(chǔ)列流線的定義,結(jié)合定義的變量和參數(shù),對圖2列流線進(jìn)行具體表示。

圖2 列流線的表示

(1)

(2)

列流線在所有經(jīng)過車站內(nèi)的水平整數(shù)點(diǎn)集合Fk和豎直整數(shù)點(diǎn)集合F′k可由(3)表示。

(3)

進(jìn)一步可知,兩列流線t1和t2在車站內(nèi)的交叉點(diǎn)數(shù)目θ(t1,t2)和重疊點(diǎn)數(shù)目γ(t1,t2)分別為

(4)

(5)

3 列流圖編制算法優(yōu)化模型

鐵路樞紐列流圖編制關(guān)鍵在于優(yōu)化列流線在區(qū)間線上的排列順序和列流線在車站矩形內(nèi)的轉(zhuǎn)折位置,考慮鐵路樞紐列流線密度大且分布不均勻的特點(diǎn)[9],本文建立了基于分層網(wǎng)格的鐵路樞紐列流圖編制優(yōu)化模型。

3.1 模型假設(shè)

為簡化模型復(fù)雜度,做出如下假設(shè):

1)模型僅優(yōu)化列流線布局,路網(wǎng)結(jié)構(gòu)信息作為確定的輸入數(shù)據(jù);

2)銜接方向和道岔看作特殊的車站,且在模型中不加以區(qū)分;

3)將復(fù)線區(qū)間簡化為單線區(qū)間進(jìn)行編制。

3.2 目標(biāo)函數(shù)

鐵路樞紐列流圖分層網(wǎng)格編制模型提出了三個優(yōu)化目標(biāo),具體描述如下所示。

1)最小化列流線交叉點(diǎn)的數(shù)目

(6)

2)最小化列流線與區(qū)間的間距

(7)

3)最小化列流線與車站的間距

(8)

本文模型各個子目標(biāo)存在著相互制約關(guān)系,結(jié)合鐵路樞紐列流圖的特點(diǎn)與前文的分析,三個子目標(biāo)的重要性依次降低,因此采用加權(quán)求和的方式轉(zhuǎn)換為單一目標(biāo)函數(shù)。令三個子目標(biāo)的加權(quán)系數(shù)C1?C2?C3,則轉(zhuǎn)換后的目標(biāo)函數(shù)如下

minZ=C1Z1+C2Z2+C3Z3

(9)

3.3 約束條件

為了保證模型的可行性,同時加快模型收斂速度,設(shè)置如下約束條件。

1)列流線的第一段與最后一段不進(jìn)入車站

(10)

2)當(dāng)列流線tk徑路上的第r個區(qū)間和列流線tl徑路上的第m個區(qū)間互相重疊,即qkr=qlm時,滿足如下約束

xkr≠xlm

(11)

3)任意兩條列流線在車站內(nèi)不重疊,即列流線ti與列流線tj車站內(nèi)的重疊點(diǎn)數(shù)目為0;

(12)

(13)

(14)

(15)

(16)

7)列流線在車站內(nèi)進(jìn)行U型轉(zhuǎn)折時,需要保證前后列流線進(jìn)入車站的深度相等,且不超出車站邊界。即當(dāng)ekrek(r+1)=-1時需滿足

(17)

8)區(qū)間上的列流線與區(qū)間的間距xkr不能超過區(qū)間線到其左側(cè)最近的車站邊界距離dkr,需滿足

0

(18)

(19)

4 模型求解

針對本文提出模型的多目標(biāo)、非線性特征,采用自適應(yīng)遺傳算法[10,11](Adaptive Genetic Algorithm,AGA)來求解。并使用Java語言編程實(shí)現(xiàn)。

4.1 自適應(yīng)遺傳算法

本文使用的自適應(yīng)遺傳算法引入了自適應(yīng)策略,不使用固定的概率參數(shù),而是在進(jìn)化過程中動態(tài)地自適應(yīng)調(diào)整交叉概率pc和變異概率pm,提高了算法搜索能力和收斂能力。交叉概率pc和變異概率pm的計(jì)算公式如下

(20)

(21)

f′=max{f1,f2}

(22)

式中,fmax為群體中的最大適應(yīng)度;favg表示群體中的平均適應(yīng)度;f表示變異個體的適應(yīng)度;f1,f2分別表示交叉的兩個體適應(yīng)度;k1,k2,k3,k4表示控制制參數(shù)取值為(0,1]。同時,將該代種群中最優(yōu)秀的部分個體視作精英,不參與交叉、變異操作,直接進(jìn)入下一代種群中,防止了遺傳算法運(yùn)行過程中產(chǎn)生的優(yōu)秀個體被交叉、變異等操作破壞。

4.1.1 初始種群編碼

初始種群編碼設(shè)計(jì)通過選擇合適的數(shù)據(jù)結(jié)構(gòu)描述待求解問題,良好的編碼設(shè)計(jì)可以使交叉、變異等操作易于實(shí)現(xiàn),也可避免產(chǎn)生過多的無效解,加速算法收斂。

本文使用一維整數(shù)數(shù)組描述單列流線,在此基礎(chǔ)上使用二維數(shù)組描述多條列流線。在圖3中,列流線ABC的編碼為[0,1,4,6,3,0];列流線EBD在B站內(nèi)屬于I型列流線,列流線在B站內(nèi)的長度為0,編碼為[0,3,0,0,3,0];列流線CBD的編碼為[0,1,7,9,2,0]。則包含這三條列流線的列流圖可用二維整數(shù)數(shù)組表示:[[0,1,4,6,3,0],[ 0,3,0,0,3,0],[0,1,7,9,2,0]]。

圖3 多列流線編碼

4.1.2 適應(yīng)度函數(shù)

由于本文采用了錦標(biāo)賽選擇和精英選擇結(jié)合作為選擇算子,僅要求個體之間能夠按照某種比較規(guī)則完成排序即可,因此無需計(jì)算出加權(quán)后的適應(yīng)度進(jìn)行比較。故本文自定義可自定義a,b兩個個體的比較策略,依次比較三個優(yōu)化目標(biāo)Z1,Z2,Z3。整個過程如下,程序定義的基本數(shù)據(jù)結(jié)構(gòu)有基因類:Gene、個體類:Individual、算法參數(shù)類:GeneticConfig和種群類:Population,使用Java實(shí)現(xiàn):

boolean is better(Individual a,Individual b) {

if (a.Z1==b.Z1) {

if (a.Z2==b.Z2) {

return a.Z3

} else {

return a.Z2

}

} else {

return a.Z1

}

}

4.2 算法實(shí)現(xiàn)

基于模型定義與算法設(shè)計(jì),本文算法主要步驟如下:

Step1:輸入原始數(shù)據(jù),即樞紐內(nèi)各車站數(shù)據(jù)表、鐵路樞紐內(nèi)各區(qū)間數(shù)據(jù)表、列車徑路數(shù)據(jù)表、列流數(shù)據(jù)表,并設(shè)置算法各類參數(shù)等;

Step2:通過二維數(shù)組編碼的方式生成初始種群,每個種群對應(yīng)一種列流圖編制方案,并按照設(shè)計(jì)規(guī)則進(jìn)行個體之間適應(yīng)度比較并排序;

Step3:判斷是否滿足終止條件,若滿足,則直接執(zhí)行Step4,反之繼續(xù)執(zhí)行下一步;

Step4:通過錦標(biāo)賽選擇和精英選擇,最大限度保留種群中最優(yōu)秀的個體,同時引入修復(fù)算子縮小搜索空間,并進(jìn)行交叉、變異運(yùn)算,形成下一代新種群,轉(zhuǎn)到Step2;

Step5:輸出適應(yīng)度最高的種群,即滿足所有約束條件,同時使目標(biāo)函數(shù)達(dá)到最優(yōu)的解,并使用分層網(wǎng)格模型自動繪制出最優(yōu)解對應(yīng)的列流圖。

5 算例分析

以文獻(xiàn)[12]中的武漢-宜昌客運(yùn)專線客車列流圖編制為例,對本文模型算法的有效性進(jìn)行驗(yàn)證。由于武漢-宜昌客運(yùn)專線客車列流圖中不存在U型列流線與Z型列流線,因此兩張列流圖中的列流線與車站的間距均為0,所以本算例只比較兩個指標(biāo):列流線交叉點(diǎn)數(shù)目和列流線與區(qū)間間距。

本文使用Java構(gòu)建仿真平臺進(jìn)行計(jì)算,配置最大迭代次數(shù)為5000次;最大穩(wěn)定迭代次數(shù)為500代(即若目標(biāo)函數(shù)值連續(xù)達(dá)到500代穩(wěn)定,則認(rèn)為達(dá)到收斂狀態(tài),對應(yīng)的解為最優(yōu)解);錦標(biāo)賽規(guī)模為10;精英個體數(shù)為2;配置參數(shù)k1,k2,k3,k4分別為:0.6,0.01,0.6,0.01。在此基礎(chǔ)上,列流線交叉點(diǎn)數(shù)目和列流線與區(qū)間間距分別對應(yīng)的迭代過程如圖4和圖5。整個程序總共運(yùn)行139.125 s,總共迭代4376代,其中,列流線交叉點(diǎn)數(shù)目在第3271代形成最優(yōu)解后,持續(xù)保持500代穩(wěn)定,列流線與區(qū)間的間距在第3877代形成最優(yōu)解后,并持續(xù)保持500代穩(wěn)定,均達(dá)到了算法終止條件。最優(yōu)解對應(yīng)的列流圖如圖6所示。

圖4 交叉點(diǎn)數(shù)目迭代過程

圖5 區(qū)間間距迭代過程

圖6 自適應(yīng)遺傳算法編制列流圖

為進(jìn)一步驗(yàn)證本文算法的有效性,將本文算法與文獻(xiàn)[12]算法以及人工編制結(jié)果進(jìn)行比較,結(jié)果如圖7和圖8所示?？梢钥闯?雖然本文算法和現(xiàn)有算法在交叉點(diǎn)數(shù)目和區(qū)間間距兩個指標(biāo)的表現(xiàn)均優(yōu)于人工鋪畫結(jié)果。但由于兩個指標(biāo)的加權(quán)系數(shù)關(guān)系為:C1>C2,可知本文算法明顯優(yōu)于現(xiàn)有算法。

圖7 交叉點(diǎn)數(shù)目對比

圖8 區(qū)間間距對比

6 結(jié)論

通過梳理列流圖編制的工作流程,分析列流圖的圖形特點(diǎn),構(gòu)建了基于分層網(wǎng)格的鐵路樞紐列流圖編制模型。考慮模型特點(diǎn),設(shè)計(jì)了自適應(yīng)遺傳算法進(jìn)行求解。結(jié)果表明,所提方法在區(qū)間間距和交叉點(diǎn)數(shù)目兩個指標(biāo)的表現(xiàn)均優(yōu)于現(xiàn)有算法以及人工鋪畫結(jié)果,實(shí)現(xiàn)了鐵路樞紐列流圖編制的自動化,為列流圖編制系統(tǒng)的開發(fā)創(chuàng)造了基礎(chǔ)條件。未來可結(jié)合鐵路專家經(jīng)驗(yàn)與實(shí)際列流圖數(shù)據(jù),采用深度學(xué)習(xí)方法對鐵路樞紐列流圖編制問題進(jìn)一步研究。