高速鐵路列車運(yùn)行線鋪畫模型與算法設(shè)計(jì)

， ， ，

(1.交通運(yùn)輸部管理干部學(xué)院，北京 101601；2.北京賽寶工業(yè)技術(shù)研究院有限公司，北京 100041；3. 中鐵物資集團(tuán)華北有限公司，河北 石家莊 050000；4.石家莊鐵道大學(xué) 交通運(yùn)輸學(xué)院，河北 石家莊 050043)

0 引言

我國(guó)的專家學(xué)者對(duì)于列車開(kāi)行方案和計(jì)算機(jī)編圖的研究開(kāi)始于20世紀(jì)60年代。眾多學(xué)者[1-7]先后開(kāi)展了大量相關(guān)研究工作，經(jīng)過(guò)多年對(duì)列車運(yùn)行圖的深入研究，積累了豐富的理論方法和實(shí)踐經(jīng)驗(yàn)，提出了動(dòng)態(tài)規(guī)劃法、統(tǒng)籌圖方法、分支定界法、原始對(duì)偶法、區(qū)間推進(jìn)法、時(shí)間循環(huán)迭代法以及動(dòng)態(tài)系統(tǒng)法等優(yōu)化方法。論文基于高中速混跑模式，構(gòu)建了我國(guó)高速鐵路列車運(yùn)行線鋪畫模型，采用遺傳算法進(jìn)行求解，能夠?yàn)槲覈?guó)高鐵系統(tǒng)列車運(yùn)行線的自動(dòng)智能鋪畫提供理論和決策參考。對(duì)高鐵系統(tǒng)建設(shè)的現(xiàn)代化具有十分重要的理論意義和實(shí)用價(jià)值。

1 高速鐵路列車運(yùn)行線鋪畫模型構(gòu)建

1.1 模型假設(shè)

(1)本模型針對(duì)單條復(fù)線高速鐵路線路，線路采取高中速列車共線運(yùn)行模式。列車的開(kāi)行方案已知，列車開(kāi)行頻率已知，列車停站方案已知。(2)鋪畫列車運(yùn)行圖所需的各種參數(shù)已知，需鋪畫線路的沿線車站名稱、區(qū)間里程、各車站到發(fā)線數(shù)量等線路數(shù)據(jù)已知。(3)把列車的等級(jí)分為兩類，一類時(shí)速300 km/h的A類列車后文稱高等級(jí)列車，一類時(shí)速200 km/h的B類列車后文稱低等級(jí)列車，模型不考慮同等級(jí)列車之間的越行。(4)本文所列模型僅適用于計(jì)劃階段的列車運(yùn)行圖編制，而不適用于列車運(yùn)行圖的調(diào)整規(guī)劃。(5)假設(shè)需鋪畫線路的各車站到發(fā)線滿足本文模型中到發(fā)線約束條件。

1.2 參數(shù)定義

1.3 約束條件

(1)列車區(qū)間運(yùn)行時(shí)間約束

(1)

(2)

(s，s+1)為上行方向，(s+1，s)為下行方向，下同。

(2)車站停站時(shí)間約束

(3)

(4)

(3)追蹤列車間隔時(shí)間約束

(5)

(6)

(7)

(8)

(4)車站間隔時(shí)間約束

(9)

(10)

(11)

(12)

(5)車站發(fā)車、到達(dá)時(shí)間域約束

(13)

(14)

(15)

(16)

(6)車站到發(fā)線約束。在任意時(shí)刻t，在車站s同時(shí)停留的列車數(shù)不能大于車站到發(fā)線數(shù)量，當(dāng)車站到發(fā)線分上下行方向使用時(shí)，應(yīng)分別考慮上行和下行的到發(fā)線約束，定義函數(shù)

(17)

則到發(fā)線約束為

(18)

車站到發(fā)線分上下行方向使用時(shí)，上下行列車使用到發(fā)線約束分別為

(19)

(20)

(7)列車越行約束。兩列同向列車經(jīng)過(guò)相同區(qū)間應(yīng)滿足區(qū)間越行關(guān)系約束，分為如下4種情況：

①同等級(jí)列車之間不能相互越行(不考慮同等級(jí)之間的越行)；②高等級(jí)列車可以越行低等級(jí)列車；③低等級(jí)列車禁止越行高等級(jí)列車；④一列低等級(jí)列車最多連續(xù)被兩列高等級(jí)列車越行；⑤一列高等級(jí)列車最多連續(xù)越行一列低等級(jí)列車。

(8)天窗約束。a為天窗開(kāi)始前最后一列車與天窗之間的最小間隔時(shí)間；β為天窗結(jié)束后發(fā)車的第一個(gè)列車與天窗之間的最小間隔時(shí)間。

(21)

(22)

(23)

(24)

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

以列車總旅行時(shí)間最小為目標(biāo)

(25)

式中，w1(i)、w2(i)分別代表上、下行列車的等級(jí)系數(shù)，列車等級(jí)越高系數(shù)越大，可以確保高優(yōu)先級(jí)列車優(yōu)先權(quán)。本文構(gòu)建了以列車總旅行時(shí)間最小為目標(biāo)函數(shù)，8個(gè)約束條件的數(shù)學(xué)模型。

2 列車運(yùn)行線鋪畫的優(yōu)化算法設(shè)計(jì)

2.1 遺傳算子設(shè)計(jì)

本算法選擇染色體編碼方式為整數(shù)編碼，每個(gè)染色體定義為n層，每一層代表著一個(gè)區(qū)間的列車發(fā)車順序，比如第1層編碼代表列車在始發(fā)站的發(fā)車順序，第k層編碼代表第k個(gè)區(qū)間的列車發(fā)車順序，編碼的初始化令所有的區(qū)間列車發(fā)車順序相同。

本文采用部分匹配交叉算子來(lái)保證基因的唯一性和完整性。本文模型編碼初始化每一層編碼的序列是相同的，如果僅僅隨機(jī)一行進(jìn)行交叉操作，那么交叉后的個(gè)體編碼中只有一行與其它行不同，這樣的個(gè)體編碼滿足越行約束的概率是極小的，所以本文采用全部行都進(jìn)行交叉操作的策略。

2.2 遺傳解碼策略

在遺傳算法中，編碼操作和解碼操作互為逆操作，在用遺傳算法求解列車運(yùn)行線鋪畫模型中，編碼表示在每個(gè)區(qū)間列車的發(fā)車順序，解碼就是根據(jù)確定的列車發(fā)車順序求解列車在每個(gè)車站的到發(fā)時(shí)刻。

解碼步驟如下：

始發(fā)站定義為第0站，按照線路下行方向依次為第1站、第2站，…，第n站，時(shí)間單位以分鐘計(jì)，例如6:05即為365，13:15計(jì)為795，一天時(shí)間為0～1 440。

(1)計(jì)算第0站的列車發(fā)車時(shí)刻。取個(gè)體編碼的第一行編碼[1，3，2，5，4]，按照編碼順序，設(shè)第1列車的始發(fā)時(shí)間為360(滿足了列車發(fā)車時(shí)間域約束)，第2列車的始發(fā)時(shí)間為前行列車的始發(fā)時(shí)間加上列車最小發(fā)車間隔(滿足列車最小發(fā)車時(shí)間間隔約束)，依次類推，求出第0站所有列車的始發(fā)時(shí)刻。

3 算例

本文采用的京滬高速鐵路數(shù)據(jù)主要有車站名稱、車站的到發(fā)線數(shù)量、高等級(jí)列車在區(qū)間的運(yùn)行時(shí)間、低等級(jí)列車在區(qū)間的運(yùn)行時(shí)間。實(shí)例的開(kāi)行方案在現(xiàn)有列車時(shí)刻表的基礎(chǔ)上修改得到。(1)列車運(yùn)行圖參數(shù)設(shè)置如下：停車附加時(shí)間 ，高等級(jí)列車為3 min，低等級(jí)列車為2 min；啟動(dòng)附加時(shí)間2 min，停站時(shí)間3 min；追蹤間隔時(shí)間4 min；同方向列車最小到達(dá)間隔時(shí)間2 min；同方向列車最小發(fā)車時(shí)間間隔2 min；天窗時(shí)間：0點(diǎn)～4點(diǎn)。(2)遺傳算法的參數(shù)設(shè)置。本文的遺傳算法設(shè)計(jì)中參數(shù)設(shè)置如下所示：最大迭代次數(shù)maxgen = 1 000；種群規(guī)模popsize = 20；交叉概率：pc = 0.6；變異概率pm = 0.3。列車運(yùn)行線鋪畫仿真結(jié)果如圖1。

圖1 列車運(yùn)行線鋪畫仿真結(jié)果

在本實(shí)例鋪畫的列車運(yùn)行圖中可以看出D1次列車在滄州西連續(xù)被G7、G43越行，在德州東被G45越行，在濟(jì)南西被G47越行，在滕州東連續(xù)被G49、G9越行，在棗莊西被G21越行，在徐州東連續(xù)被G51、G53越行，D1最多連續(xù)被兩列高等級(jí)列車越行，而一列高等級(jí)列車最多連續(xù)越行一列低等級(jí)列車，完全符合列車越行約束。

4 結(jié)論

采用遺傳算法求解高速鐵路列車運(yùn)行線鋪畫模型，設(shè)計(jì)了n層編碼方式，以列車總旅行時(shí)間的倒數(shù)為適應(yīng)度函數(shù)，采用輪盤賭選擇算子，改進(jìn)的部分匹配交叉方法，改進(jìn)的兩點(diǎn)變異方式，以適應(yīng)本模型的二維矩陣編碼，保證了染色體編碼的唯一性，設(shè)計(jì)列車越行約束檢查算法，在每個(gè)遺傳操作結(jié)束后均進(jìn)行越行約束檢查，引導(dǎo)遺傳進(jìn)化往好的方向發(fā)展，并詳細(xì)說(shuō)明了其它約束條件的處理方法；以MyEclipse10為平臺(tái)，開(kāi)發(fā)設(shè)計(jì)了計(jì)算機(jī)鋪畫列車運(yùn)行線仿真系統(tǒng)，并以京滬高速鐵路為背景，鋪畫了47對(duì)高等級(jí)列車、3對(duì)低等級(jí)列車，總共50對(duì)列車的運(yùn)行線，輸出了列車時(shí)刻表，驗(yàn)證了模型和算法的有效性。

參 考 文 獻(xiàn)

[1]張英貴. 鐵路客運(yùn)站股道運(yùn)用優(yōu)化方法與應(yīng)用研究[D].長(zhǎng)沙:中南大學(xué),2012.

[2]朱向,雷定猷. 帶平衡約束三維裝箱問(wèn)題的雙層混合遺傳算法[J].交通運(yùn)輸系統(tǒng)工程與信息,2015,2:203-209.

[3]馬建軍,胡思繼. 基于網(wǎng)狀線路的京滬高速鐵路列車運(yùn)行圖編制理論的研究[J].中國(guó)鐵道科學(xué), 2002,23(5):135-137.

[4]彭其淵,楊明倫. 計(jì)算機(jī)編制復(fù)線實(shí)用貨物列車運(yùn)行圖的整數(shù)規(guī)劃模型及求解方法[J].中國(guó)鐵道科學(xué), 1994,15(4):60-66.

[5]倪少權(quán),楊明倫. 計(jì)算機(jī)編制全路直通旅客列車運(yùn)行圖的研究[J].鐵道運(yùn)輸與經(jīng)濟(jì), 2002, 24(6),41-43.

[6]Tormos P. A genetic algorithm for railway scheduling problems [J].Studies in Computational Intelligence, 2008,128: 255-276.

[7]李明. 遺傳算法的改進(jìn)及其在優(yōu)化問(wèn)題中的應(yīng)用研究[D].長(zhǎng)春: 吉林大學(xué), 2004.