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

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

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

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

劉 源1，牛慧蘭1，張 鑫1，董海隆2

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

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

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

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

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

1　問題描述

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

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

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

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

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

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

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

設(shè)高鐵站高峰時間段內(nèi)順序到達(dá)列車的集合為S，S=｛s1，s2，…，si，…，sn｝，i∈［1，n］，i為高峰時間段內(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)用問題中，高鐵站可用到發(fā)線與空閑時間是一種有限資源，在時空條件的約束下，可建立矩陣Q用于存放到發(fā)列車的沖突情況。列車沖突包含3種情況如下：

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

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

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

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

式中：qij表示列車i與列車j的時空沖突情況，qij∈Q，若兩列車時間沖突則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ā)車附加時間，包括為列車安排進(jìn)路的時間，列車頭部跨過進(jìn)站信號機(jī)走行至到發(fā)線的時間，開放出站信號后列車尾部跨過出站信號機(jī)的時間。xij表示列車i是否占用到發(fā)線j，xij=1表示列車i占用到發(fā)線j，xij=0表示列車i不占用到發(fā)線j。

式中：C為列車?？空九_的權(quán)益矩陣，cij表示當(dāng)?shù)趇列列車停靠在第j條到發(fā)線所在站臺時的權(quán)值，cij=0表示G字頭列車停靠在基本站臺，cij=1表示反接站臺。

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

建立矩陣L存儲列車等級與接發(fā)站臺的信息。k為列車的等級信息，依據(jù)其技術(shù)速度將其分為不同等級；w為列車?？扛哞F站站臺信息，依據(jù)其?？康恼九_，從基本站臺直至反接站臺依次劃分等級。

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

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

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

3　基于遺傳算法的求解

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

3.1染色體編碼

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

3.2初始種群的生成

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

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

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

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

（2）依據(jù)列車沖突集合Q，確定沖突列車占用的到發(fā)線，計算出可用到發(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)用問題具有在同一約束條件下存在兩個相互矛盾優(yōu)化目標(biāo)的特點(diǎn)，根據(jù)兩優(yōu)化目標(biāo)重要程度不同求解就成了問題的關(guān)鍵。在解決這一問題時需要考慮兩點(diǎn)：

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

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

由于f1和f2的單位度量值不同，故需要進(jìn)行無綱量化處理。根據(jù)式（11）、（12），按照兩個優(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)查問卷分別發(fā)送給鐵路技術(shù)部門與調(diào)度等生產(chǎn)部門，然后將之回收匯總，根據(jù)專家給出的結(jié)果進(jìn)行計算。

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

3.4遺傳算子設(shè)計

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

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

4　算例分析

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

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

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

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

作為重要目標(biāo)，到發(fā)線均衡使用是指在高峰時段內(nèi)到發(fā)線使用的時間方差最小。不考慮列車密集到達(dá)時同一條到發(fā)線大量使用，而另一時段空閑，只需注意在總的時間段內(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ā)線均衡使用的前提下，高等級列車優(yōu)先接入距離站房近的站臺，低等級列車優(yōu)先接入遠(yuǎn)距離站臺。在初始安排中，BJ方向的D字頭列車s7接入較近站臺；GZ方向的D字頭列車s21接入較近站臺。在最優(yōu)安排中6列D字頭動車組都接入走行較遠(yuǎn)站臺，BJ方向的D字頭列車s7、s16、s23分別接入4、6、6道；GZ方向的D字頭列車s3、s17、s21分別接入7、7、9道。最優(yōu)安排與初始安排相比，高等級列車接入近距離站臺次數(shù)更多。Z站高峰時段到發(fā)現(xiàn)線運(yùn)用最優(yōu)方案如圖2所示。

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

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

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

5　結(jié)語

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

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

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

［2］ 張英貴，雷定猷，湯波，等.鐵路客運(yùn)站股道運(yùn)用窗時排序模型與算法［J］.鐵道學(xué)報，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é)報，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］ 左大杰，王慈光，陳韜.鐵路旅客列車開行方案問題的研究綜述［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ī)劃與管理。