劉 源，?；厶m，張 鑫，董海隆

（1.蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州 730070；2.鄭州警察學(xué)院 交通管理工程系，河南 鄭州 450000）

高鐵站到發(fā)線運(yùn)用模型與算法

劉 源1，?；厶m1，張 鑫1，董海隆2

（1.蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州 730070；2.鄭州警察學(xué)院 交通管理工程系，河南 鄭州 450000）

為高效使用高鐵站到發(fā)線，建立多目標(biāo)整數(shù)規(guī)劃模型，以到發(fā)線均衡使用和旅客站內(nèi)走行距離最近為優(yōu)化目標(biāo)；以禁止反接到發(fā)線、滿足最小時(shí)間間隔、使用單一到發(fā)線為約束。使用遺傳算法求解，建立列車沖突矩陣與可用到發(fā)線集，確保初始、交叉與變異種群有效可行。結(jié)果表明：模型描述準(zhǔn)確，算法效率較高，能夠有效解決到發(fā)線運(yùn)用問(wèn)題。關(guān)鍵詞：高鐵站；列車沖突矩陣；遺傳算法；到發(fā)線運(yùn)用；多目標(biāo)優(yōu)化

高鐵站接發(fā)的列車具有開行密度大、速度快等特點(diǎn)，旅客對(duì)其服務(wù)質(zhì)量、列車正點(diǎn)率等有較高要求。到發(fā)線運(yùn)用作為車站作業(yè)計(jì)劃的一部分，對(duì)提高高鐵站作業(yè)效率有著重要意義。

我國(guó)研究人員對(duì)到發(fā)線的運(yùn)用做了相關(guān)研究，徐杰等［1］將到發(fā)線運(yùn)用問(wèn)題轉(zhuǎn)化為k-頂點(diǎn)著色問(wèn)題，并用遺傳算法求解；張英貴等［2］利用現(xiàn)代排序論，以總費(fèi)用最小和股道均衡使用為目標(biāo)函數(shù)，建立多目標(biāo)窗時(shí)排序模型；王保山等［3］根據(jù)車站拓?fù)浣Y(jié)構(gòu)建立優(yōu)化模型，提出誘導(dǎo)變異，避免變異產(chǎn)生病態(tài)個(gè)體；何林等［4］以均衡使用到發(fā)線為優(yōu)化目標(biāo)，構(gòu)建到發(fā)線占用權(quán)值；呂紅霞等［5］提出時(shí)間片的概念，建立技術(shù)站到發(fā)線運(yùn)用的二次0-1規(guī)劃模型，并將模型分解為2個(gè)簡(jiǎn)單的0-1規(guī)劃模型；Billionnet［6］以線性整數(shù)規(guī)劃表示圖著色模型，并用啟發(fā)式算法求解。

從研究目標(biāo)來(lái)看，多數(shù)文獻(xiàn)主要考慮單個(gè)目標(biāo)對(duì)于到發(fā)線運(yùn)用優(yōu)化的影響，對(duì)于多目標(biāo)優(yōu)化則沒(méi)有提及。本文建立起多目標(biāo)優(yōu)化模型，研究在具有到發(fā)線均衡使用與旅客站內(nèi)走行距離最近兩個(gè)相互矛盾目標(biāo)情況下的到發(fā)線運(yùn)用問(wèn)題。

1　問(wèn)題描述

高鐵站到發(fā)線運(yùn)用計(jì)劃根據(jù)列車運(yùn)行計(jì)劃、動(dòng)車組運(yùn)用計(jì)劃與車站作業(yè)計(jì)劃進(jìn)行編制。到發(fā)線的使用應(yīng)當(dāng)遵循以下條件：

（1）每列列車從頭部跨過(guò)進(jìn)站信號(hào)機(jī)直至從到發(fā)線出發(fā)、尾部跨過(guò)出站信號(hào)機(jī)為止，期間只占用一條到發(fā)線；

（2）每條到發(fā)線在同一時(shí)間只能接發(fā)一列列車；

（3）為減少交叉干擾，禁止列車反接到發(fā)線。

條件（1）、（2）為到發(fā)線使用的硬性約束；條件（3）是在我國(guó)高速鐵路的快速發(fā)展、列車開行密度逐步增大這一背景下提出的柔性約束。到發(fā)線的反接會(huì)造成接發(fā)列車作業(yè)時(shí)切割正線，產(chǎn)生大量敵對(duì)進(jìn)路，影響車站作業(yè)效率。

以雙線高鐵站下行列車反接為例，下行列車到達(dá)進(jìn)路接入上行列車到發(fā)場(chǎng)，與上行通過(guò)列車產(chǎn)生交叉干擾，并與上行列車出發(fā)進(jìn)路產(chǎn)生交叉干擾；下行列車由上行到發(fā)場(chǎng)出發(fā)與上行列車到達(dá)進(jìn)路產(chǎn)生交叉干擾。以上3種交叉均為行行交叉，會(huì)對(duì)高鐵站作業(yè)效率造成較大影響。

2　建立到發(fā)線運(yùn)用模型

設(shè)高鐵站高峰時(shí)間段內(nèi)順序到達(dá)列車的集合為S，S=｛s1，s2，…，si，…，sn｝，i∈［1，n］，i為高峰時(shí)間段內(nèi)到站的第i列列車，n為到站列車總數(shù)；高鐵站到發(fā)線總數(shù)的集合為T，T=｛t1，t2，…，tj，…，tm｝，j∈［1，m］，j為高鐵站第j條到發(fā)線，m為到發(fā)線總數(shù)［7］。

2.1列車信息集合

設(shè)高鐵站順序到達(dá)第i輛列車si包含以下信息：

在到發(fā)線運(yùn)用問(wèn)題中，高鐵站可用到發(fā)線與空閑時(shí)間是一種有限資源，在時(shí)空條件的約束下，可建立矩陣Q用于存放到發(fā)列車的沖突情況。列車沖突包含3種情況如下：

（1）順序到達(dá)的列車相同時(shí)間使用了不同的到發(fā)線；

（2）順序到達(dá)的列車不同時(shí)間使用同一條到發(fā)線；

（3）順序到達(dá)的列車在同一時(shí)間使用同一條到發(fā)線。

由于列車運(yùn)用計(jì)劃是固定的，在列車到站時(shí)間固定的情況下，時(shí)間沖突避免轉(zhuǎn)變?yōu)闀r(shí)空沖突就顯得尤為重要，建立列車沖突矩陣Q的目的就是為了避免情況（3） 的發(fā)生。

式中：qij表示列車i與列車j的時(shí)空沖突情況，qij∈Q，若兩列車時(shí)間沖突則qij=1，否則qij=0。

2.2高鐵站到發(fā)線運(yùn)用模型

分別以到發(fā)線均衡使用和旅客站內(nèi)走行距離最近為優(yōu)化目標(biāo)，建立到發(fā)線運(yùn)用多目標(biāo)整數(shù)規(guī)劃模型，如式（3）、式（4）所示。

式中：t附加為接發(fā)車附加時(shí)間，包括為列車安排進(jìn)路的時(shí)間，列車頭部跨過(guò)進(jìn)站信號(hào)機(jī)走行至到發(fā)線的時(shí)間，開放出站信號(hào)后列車尾部跨過(guò)出站信號(hào)機(jī)的時(shí)間。xij表示列車i是否占用到發(fā)線j，xij=1表示列車i占用到發(fā)線j，xij=0表示列車i不占用到發(fā)線j。

式中：C為列車?？空九_(tái)的權(quán)益矩陣，cij表示當(dāng)?shù)趇列列車?？吭诘趈條到發(fā)線所在站臺(tái)時(shí)的權(quán)值，cij=0表示G字頭列車?？吭诨菊九_(tái)，cij=1表示反接站臺(tái)。

旅客站內(nèi)走行距離指的是旅客以高鐵站進(jìn)站口為起點(diǎn)，途經(jīng)候車區(qū)直至列車?？空九_(tái)所經(jīng)過(guò)的距離。一部分高鐵站候車區(qū)布局與既有客站類似，如新鄉(xiāng)東站。但另一部分高鐵站候車區(qū)直接與站臺(tái)對(duì)接，旅客從進(jìn)站口走行至對(duì)應(yīng)列車候車區(qū)距離不同，但從對(duì)應(yīng)候車區(qū)走行至站臺(tái)距離相同，如鄭州東站。旅客站內(nèi)走行距離可以表示為：M=m1+m2，m1表示旅客從進(jìn)站口至對(duì)應(yīng)候車區(qū)的距離，m2表示旅客從對(duì)應(yīng)候車區(qū)至列車停靠站臺(tái)的距離。無(wú)論是哪一種候車區(qū)布局，旅客站內(nèi)走行距離通常為基本站臺(tái)最近，距離基本站臺(tái)越遠(yuǎn)走行距離越遠(yuǎn)，因此，可以將旅客站內(nèi)走行距離與停靠站臺(tái)相關(guān)聯(lián)。

建立矩陣L存儲(chǔ)列車等級(jí)與接發(fā)站臺(tái)的信息。k為列車的等級(jí)信息，依據(jù)其技術(shù)速度將其分為不同等級(jí)；w為列車停靠高鐵站站臺(tái)信息，依據(jù)其停靠的站臺(tái)，從基本站臺(tái)直至反接站臺(tái)依次劃分等級(jí)。

建立起矩陣C與矩陣L的映射，依據(jù)列車等級(jí)信息與占用站臺(tái)信息，找出其映射關(guān)系，確定列車的權(quán)益值。

根據(jù)前文所述，到發(fā)線運(yùn)用問(wèn)題的約束條件表示為：

式（7）表示列車i只能占用一條到發(fā)線；式（8）表示列車使用同一到發(fā)線應(yīng)滿足最小時(shí)間間隔，為列車i占用到發(fā)線j的發(fā)車時(shí)刻，為列車i+1占用到發(fā)線j的停車時(shí)刻；式（9）表示上下行列車應(yīng)接入各自到發(fā)場(chǎng)；R（a）為列車行車方向。

3　基于遺傳算法的求解

到發(fā)線運(yùn)用問(wèn)題屬于NP-Hard問(wèn)題，解決這類問(wèn)題，隨機(jī)化搜索是一種有效可行的方法。遺傳算法作為一種啟發(fā)式搜索算法，可以較好地解決到發(fā)線運(yùn)用問(wèn)題。

3.1染色體編碼

采用自然數(shù)編碼，建立一個(gè)包含n個(gè)元素的集合X，用以存放順序到達(dá)列車占用的到發(fā)線信息。

3.2初始種群的生成

在隨機(jī)生成初始種群的過(guò)程中，往往會(huì)產(chǎn)生不符合約束的染色體——列車與到發(fā)線產(chǎn)生時(shí)空沖突，解決的方法之一為構(gòu)建罰函數(shù)。本文以杜絕產(chǎn)生不符合約束染色體為核心，依據(jù)列車沖突集合Q與可用到發(fā)線集合K，保證產(chǎn)生的染色體全部可行。

設(shè)置種群規(guī)模為40，染色體內(nèi)基因個(gè)數(shù)為接發(fā)列車總數(shù)s，構(gòu)建40×s的二維矩陣A。

產(chǎn)生初始種群的過(guò)程如下：

（1）隨機(jī)生成種群內(nèi)各染色體的第一個(gè)基因Aq；

（2）依據(jù)列車沖突集合Q，確定沖突列車占用的到發(fā)線，計(jì)算出可用到發(fā)線集合Aq（Kih；

（3）依據(jù)可用到發(fā)線集合Aq（Kih，隨機(jī)確定該列車占用的到發(fā)線。

Aq（s1

5h表示種群A中第q條染色體第1位基因占用的到發(fā)線；Aq（Kih表示種群A中第q條染色體第i位基因的可用到發(fā)線集合。

3.3適應(yīng)度函數(shù)的選取

由于高鐵站到發(fā)線運(yùn)用問(wèn)題具有在同一約束條件下存在兩個(gè)相互矛盾優(yōu)化目標(biāo)的特點(diǎn)，根據(jù)兩優(yōu)化目標(biāo)重要程度不同求解就成了問(wèn)題的關(guān)鍵。在解決這一問(wèn)題時(shí)需要考慮兩點(diǎn)：

（1）在考慮到旅客站內(nèi)走行距離最近的時(shí)候，并沒(méi)有考慮咽喉區(qū)道岔的使用，若僅僅使用近距離站臺(tái)，勢(shì)必造成行車作業(yè)中產(chǎn)生大量敵對(duì)進(jìn)路，這并不利于高鐵站行車設(shè)備的使用；

（2）由于有到發(fā)線均衡度的限制，低等級(jí)列車接發(fā)站臺(tái)應(yīng)優(yōu)先考慮外側(cè)站臺(tái)，以便于高等級(jí)列車接入基本站臺(tái)。將兩個(gè)優(yōu)化目標(biāo)分別記為：

由于f1和f2的單位度量值不同，故需要進(jìn)行無(wú)綱量化處理。根據(jù)式（11）、（12），按照兩個(gè)優(yōu)化目標(biāo)的重要程度，分別賦予系數(shù)λ1、λ2，構(gòu)建單目標(biāo)適應(yīng)度函數(shù)：

目標(biāo)函數(shù)f3的權(quán)重矩陣采用專家法確定。將到發(fā)線均衡使用和旅客站內(nèi)走行距離最近的重要性調(diào)查問(wèn)卷分別發(fā)送給鐵路技術(shù)部門與調(diào)度等生產(chǎn)部門，然后將之回收匯總，根據(jù)專家給出的結(jié)果進(jìn)行計(jì)算。

式中：λj為目標(biāo)j的權(quán)重系數(shù)，N為專家人數(shù)。

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

分別采用輪盤賭選擇法，依照f(shuō)3的適應(yīng)度選擇個(gè)體。采用單點(diǎn)交叉，完成交叉操作后，若新生成的與存在列車到發(fā)線使用沖突，依據(jù)初始種群生成的思路，進(jìn)行改良。隨機(jī)選取種群內(nèi)某一染色體，對(duì)其某一基因進(jìn)行實(shí)值變異。如圖1所示。

圖1　染色體單點(diǎn)交叉

4　算例分析

模擬構(gòu)建一通過(guò)式高鐵站Z，銜接BJ、GZ兩個(gè)方向，共有7條到發(fā)線、2條正線。其中Ⅰ、Ⅱ道分別為連接GZ、BJ方向的正線，3、5、7、9道所在區(qū)域?yàn)檫B接GZ方向的下行到發(fā)場(chǎng)，2、4、6道所在區(qū)域?yàn)檫B接BJ方向的上行到發(fā)場(chǎng)。找出Z站作業(yè)計(jì)劃最繁忙時(shí)段，優(yōu)化到發(fā)線使用。15∶00～18∶00時(shí)段，Z站共接發(fā)動(dòng)車組26列，其中上行動(dòng)車組12列，下行動(dòng)車組14列。G字頭動(dòng)車組20列，D字頭動(dòng)車組6列，接發(fā)列車數(shù)據(jù)如表1所示。

利用Matlab編程，種群規(guī)模為40，基因長(zhǎng)度為26，最大遺傳代數(shù)為300，交叉概率為0.75，變異概率為0.05。確定到發(fā)線均衡使用為重要目標(biāo)，旅客站內(nèi)走行距離為次要目標(biāo)，分別賦予權(quán)值0.9和0.1。

表1　Z站高峰時(shí)段接發(fā)列車

利用遺傳算法求解，得到目標(biāo)函數(shù)f3的最優(yōu)值。由于上下行動(dòng)車組分別接入上下行到發(fā)場(chǎng)故在計(jì)算到發(fā)線均衡使用、旅客站內(nèi)走行距離時(shí)可以分別求解。列車占用到發(fā)線的初始安排如表2所示，最優(yōu)安排如表3所示［8］。

作為重要目標(biāo)，到發(fā)線均衡使用是指在高峰時(shí)段內(nèi)到發(fā)線使用的時(shí)間方差最小。不考慮列車密集到達(dá)時(shí)同一條到發(fā)線大量使用，而另一時(shí)段空閑，只需注意在總的時(shí)間段內(nèi)均衡即可。在初始安排中上行到發(fā)線f1=44.67，下行到發(fā)線f1=108.76；在最優(yōu)安排中上行到發(fā)線f1=0.67，下行到發(fā)線f1=4.76。最優(yōu)安排與初始安排相比，上下行到發(fā)線使用均衡度均大幅提升。

作為次要目標(biāo)，旅客站內(nèi)走行距離最近可以看作在到發(fā)線均衡使用的前提下，高等級(jí)列車優(yōu)先接入距離站房近的站臺(tái)，低等級(jí)列車優(yōu)先接入遠(yuǎn)距離站臺(tái)。在初始安排中，BJ方向的D字頭列車s7接入較近站臺(tái)；GZ方向的D字頭列車s21接入較近站臺(tái)。在最優(yōu)安排中6列D字頭動(dòng)車組都接入走行較遠(yuǎn)站臺(tái)，BJ方向的D字頭列車s7、s16、s23分別接入4、6、6道；GZ方向的D字頭列車s3、s17、s21分別接入7、7、9道。最優(yōu)安排與初始安排相比，高等級(jí)列車接入近距離站臺(tái)次數(shù)更多。Z站高峰時(shí)段到發(fā)現(xiàn)線運(yùn)用最優(yōu)方案如圖2所示。

表2　Z站初始到發(fā)線運(yùn)用安排

表3　Z站最優(yōu)到發(fā)線運(yùn)用安排

圖2　Z站高峰時(shí)段到發(fā)線運(yùn)用最優(yōu)方案

5　結(jié)語(yǔ)

本文對(duì)于高鐵站到發(fā)線運(yùn)用問(wèn)題，構(gòu)建了多目標(biāo)非線性整數(shù)規(guī)劃模型，利用遺傳算法求解。通過(guò)建立列車沖突集與可用到發(fā)線集保證產(chǎn)生健康個(gè)體，提高算法效率。在優(yōu)化了到發(fā)線均衡使用的同時(shí)，縮短了高等級(jí)動(dòng)車組乘客的站內(nèi)走行距離。

在高鐵站實(shí)際作業(yè)過(guò)程中，每條到發(fā)線通常都有兩條及以上接發(fā)車進(jìn)路，兩列使用不同到發(fā)線的動(dòng)車組也會(huì)因?yàn)榻影l(fā)車進(jìn)路不同而使用相同道岔，造成行車作業(yè)交叉干擾。高鐵站接發(fā)車進(jìn)路的分配問(wèn)題還需進(jìn)一步研究。

［1］ 徐杰，杜文，常軍乾，等.基于遺傳算法的區(qū)段站到發(fā)線運(yùn)用優(yōu)化安排［J］.中國(guó)鐵道科學(xué)，2003（2）：112-117.

［2］ 張英貴，雷定猷，湯波，等.鐵路客運(yùn)站股道運(yùn)用窗時(shí)排序模型與算法［J］.鐵道學(xué)報(bào)，2011（1）：1-7.

［3］ 王保山，侯立新，劉海東.客運(yùn)專線車站到發(fā)線運(yùn)用優(yōu)化方法［J］.交通運(yùn)輸系統(tǒng)工程與信息，2012（2）：105-110.

［4］ 何林，呂紅霞.高速鐵路車站到發(fā)線運(yùn)用優(yōu)化研究［J］.鐵道運(yùn)輸與經(jīng)濟(jì)，2012（8）：47-50，66.

［5］ 呂紅霞，倪少權(quán)，紀(jì)洪業(yè).技術(shù)站調(diào)度決策支持系統(tǒng)的研究——到發(fā)線的合理使用［J］.西南交通大學(xué)學(xué)報(bào)，2000（3）: 255-258.

［6］ Biilionnet A.. Using Integer Programming to Solve the Train-Piatforming Problem ［J］.Transportation Science，2003，37（2）：213-222.

［7］ 張?zhí)K波，廖勇，鄒健康，黃志彤.基于遺傳算法的客運(yùn)站到發(fā)線優(yōu)化安排［J］. 鐵道運(yùn)輸與經(jīng)濟(jì)，2007（11）：24-27.

［8］ 左大杰，王慈光，陳韜.鐵路旅客列車開行方案問(wèn)題的研究綜述［J］. 鐵道運(yùn)輸與經(jīng)濟(jì)，2010（1）：35-39.

Model and Algorithm for Arrival-departure Track Utilization at High-speed Railway Station

Liu Yuan1， Niu Huilan1， Zhang Xin1， Dong Hailong2
（1. School of Traffic and Transportation， Lanzhou Jiaotong University， Lanzhou 730070， China；2. Transportation Management Engineering Department， Henan Police College， Zhengzhou 450000， China）

In order to use the arrival and departure track of the high-speed rail station efficiently， this paper established the overall planning model based on multi-objective. The balanced use of arrival and departure track and shortest walking distance in passenger station was looked upon as the optimization objective. Prohibiting to link the arrival and departure tracks on the contrary， meeting the minimum time interval and using a single track were regarded as constraint. Baesd on genetic algorithm it established train conflict matrix and available arrival and departure track set to ensure the initial， crossover and mutation reproduction effective and feasible. The results showed that the model description was accurate and the algorithm efficiency was high， which could effectively utilize the arrival and departure track.

high-speed railway station；conflict matrix；genetic algorithm；arrival and departure track；multi-objective optimization

U293.2

A

1672-9889（2015）02-0069-05

2014-07-03）

劉源（1989-），男，河南鄭州人，碩士研究生，研究方向?yàn)檫\(yùn)輸規(guī)劃與管理。