何 林，呂紅霞

（西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 610031）

高速鐵路車站到發(fā)線運(yùn)用優(yōu)化研究

何 林，呂紅霞

（西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 610031）

高速鐵路車站到發(fā)線運(yùn)用計(jì)劃根據(jù)列車運(yùn)行計(jì)劃、動(dòng)車組交路計(jì)劃編制各列車占用到發(fā)線的起止時(shí)間，以均衡、合理使用到發(fā)線和方便旅客上下車為原則，為每一列車安排合適的到發(fā)線。在分析高速鐵路車站到發(fā)線運(yùn)用特點(diǎn)和原則的基礎(chǔ)上，建立高速鐵路車站到發(fā)線運(yùn)用的0-1規(guī)劃模型，并利用遺傳算法求解。通過(guò)算例分析，編制長(zhǎng)沙南站的到發(fā)線運(yùn)用方案，說(shuō)明方法的具體應(yīng)用。

高速鐵路；到發(fā)線；0-1規(guī)劃；遺傳算法

我國(guó)高速鐵路車站開行的列車種類較少、列車作業(yè)過(guò)程也較簡(jiǎn)單，但列車開行密度大，出入站頻率高、作業(yè)時(shí)間短、客運(yùn)服務(wù)質(zhì)量要求高，對(duì)列車正點(diǎn)運(yùn)行要求較高。一些專家、學(xué)者對(duì)客運(yùn)專線車站的到發(fā)線運(yùn)用進(jìn)行了相關(guān)研究。例如，以滿足接發(fā)車需要的程度建立模型，采用啟發(fā)式算法求解[1]；以保證出發(fā)列車正點(diǎn)、減少行車和調(diào)車作業(yè)干擾，盡量按照固定方案接發(fā)列車建立數(shù)學(xué)模型，并設(shè)計(jì)基于MMAS算法求解模型[2]；建立客運(yùn)專線車站作業(yè)計(jì)劃協(xié)同編制模型，并采用蟻群算法進(jìn)行求解[3]。因此，主要針對(duì)高速鐵路車站到發(fā)線運(yùn)用，研究適合高速鐵路特點(diǎn)，通用性好、適應(yīng)性強(qiáng)的車站到發(fā)線運(yùn)用計(jì)劃具有重要意義。

1 高速鐵路列車占用車站到發(fā)線分析

車站到發(fā)線運(yùn)用計(jì)劃根據(jù)列車到發(fā)計(jì)劃、動(dòng)車組交路計(jì)劃編制階段內(nèi)各列車占用到發(fā)線的起止時(shí)間，按照均衡、合理使用到發(fā)線，方便旅客上下車的原則，為每列車安排合適的到發(fā)線，保證所有列車都能按時(shí)出發(fā)、按時(shí)接入。在實(shí)際工作中，到發(fā)線的占用需符合以下約束條件。

（1）一條到發(fā)線同一時(shí)間只能接發(fā) 1 列列車，直至該列車離去。

（2）一列列車只能占用1條到發(fā)線。

（3）同一到發(fā)線接發(fā)相鄰到發(fā)列車的時(shí)間間隔要滿足最小安全時(shí)間間隔要求。

（4）同一站臺(tái)兩側(cè)的到發(fā)線最好不要同時(shí)安排2 列出發(fā)時(shí)刻相近的列車，或者 1 列出發(fā)和 1 列到達(dá)的列車。

（5）具有換乘關(guān)系的列車應(yīng)盡量安排?？肯嗤九_(tái)。

（6）高等級(jí)列車的接發(fā)應(yīng)盡量安排靠近基本站臺(tái)(貴賓候車室)的到發(fā)線。

（7）由于客運(yùn)站旅客列車到發(fā)時(shí)刻相對(duì)固定，為方便車站的客運(yùn)工作組織，盡量按照到發(fā)線固定使用方案安排到發(fā)線的使用。

（8）減少交叉干擾。

在滿足上述基本約束條件下，車站作業(yè)計(jì)劃還應(yīng)具有一定程度的適應(yīng)列車運(yùn)行波動(dòng)的能力。

2 建立高速鐵路車站到發(fā)線運(yùn)用模型

設(shè)某高速鐵路車站到發(fā)線集合D＝{d1，d2，…，dj，…，dm}，j為到發(fā)線編號(hào)，m為到發(fā)線總數(shù)；編制計(jì)劃階段內(nèi)到發(fā)列車集合L＝{l1，l2，…，li，…，ln}，i為列車到達(dá)車站的先后順序編號(hào)，n為列車總數(shù)。

2.1 時(shí)間片

將編制計(jì)劃階段的時(shí)間劃分為若干段，每段時(shí)間被列車占用，并且由于列車在占用到發(fā)線的時(shí)間上存在著交叉干擾，不能使用同一條到發(fā)線。劃分的每段時(shí)間稱為一個(gè)時(shí)間片[1]，時(shí)間片根據(jù)列車占用到發(fā)線作業(yè)的起止時(shí)刻進(jìn)行劃分，每?jī)蓛上噜彽牧熊嚨竭_(dá)時(shí)刻或出發(fā)時(shí)刻之間的時(shí)間劃分為一個(gè)時(shí)間片。通過(guò)引入時(shí)間片概念，可以把計(jì)劃編制時(shí)間段劃分為幾個(gè)時(shí)間片，列車占用到發(fā)線的時(shí)間可以表示為占用一個(gè)或多個(gè)連續(xù)的時(shí)間片。

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

高速鐵路列車在車站作業(yè)時(shí)間短，到發(fā)線運(yùn)用以方便旅客上下車為優(yōu)化目標(biāo)，建立車站到發(fā)線分配問(wèn)題的0-1規(guī)劃模型。以減少旅客站內(nèi)走行距離為目標(biāo)構(gòu)成到發(fā)線權(quán)值，以到發(fā)線使用權(quán)值最大為目標(biāo)建立車站到發(fā)線運(yùn)用模型。

（1）到發(fā)線使用目標(biāo)：方便旅客上下車，減少旅客站內(nèi)走行距離。

（2）到發(fā)線使用約束條件：一條到發(fā)線同時(shí)只能接發(fā) 1 列列車，直至該列車離去；一列列車在同一時(shí)間只能占用 1 條到發(fā)線。

建立數(shù)學(xué)模型：

式中：xij為 0-1 變量，xij＝1 表示列車i占用到發(fā)線j；xij＝0 表示列車i不占用到發(fā)線j；n為階段內(nèi)接入高速鐵路車站的總列車數(shù)；m為高速鐵路車站到發(fā)線數(shù)量；cij為列車i占用到發(fā)線j的權(quán)值；Ak為第k個(gè)時(shí)間片的到達(dá)列車集合，K為計(jì)劃編制階段內(nèi)的時(shí)間片總數(shù)。

公式 ⑵ 保證每一列車只占用 1 條到發(fā)線；公式 ⑶ 保證一條到發(fā)線在同一時(shí)間內(nèi)最多被 1 列車占用。

2.3 到發(fā)線占用權(quán)值的構(gòu)建

權(quán)值矩陣C的構(gòu)建是通過(guò)列車等級(jí)、到發(fā)線固定使用方案、列車長(zhǎng)度、列車在站作業(yè)性質(zhì)，以及本階段站內(nèi)施工計(jì)劃等確定的。而方便旅客是高速鐵路的首要考慮因素，主要考慮減少旅客在站內(nèi)的走行距離。旅客在站內(nèi)的走行距離與其所乘列車?？康恼九_(tái)相關(guān)，因此采用以下規(guī)則確定到發(fā)線占用權(quán)值：首先，根據(jù)站臺(tái)與站房的距離，將車站站臺(tái)分為 4 個(gè)等級(jí)：第一等級(jí)表示最靠近站房的站臺(tái)，第二等級(jí)的站臺(tái)次之，第三等級(jí)表示最靠近正線的站臺(tái)，第四等級(jí)表示相反方向到發(fā)場(chǎng)的站臺(tái)；其次，再確定列車等級(jí)，相同等級(jí)的列車占用相同等級(jí)的站臺(tái)權(quán)值相同。由以上規(guī)則構(gòu)建的到發(fā)線占用權(quán)值矩陣C為：

式中：當(dāng)cij＝0 時(shí)，表示列車i不可占用j到發(fā)線；當(dāng)cij≠0時(shí)，表示列車i可以占用j到發(fā)線，且其權(quán)值為cij。

第p等級(jí)的列車占用第q等級(jí)站臺(tái)的到發(fā)線權(quán)值為vpq，對(duì)應(yīng)的等級(jí)列車占用到發(fā)線矩陣V為：

式中：p為列車等級(jí)編號(hào)，p＝1，2，…，M，M取值根據(jù)各高速鐵路車站具體情況而定；q為站臺(tái)等級(jí)編號(hào)，q＝1，2，3，4。

定義：映射g是從矩陣C到矩陣V的一個(gè)對(duì)應(yīng)法則，滿足當(dāng)?shù)趇列車等級(jí)為p，且占用等級(jí)為q的到發(fā)線j時(shí)，cij＝vpq，則到發(fā)線占用權(quán)值矩陣C可相應(yīng)確定。

3 基于遺傳算法的高速鐵路車站到發(fā)線運(yùn)用模型

設(shè)某客運(yùn)站共有m條到發(fā)線，某編制計(jì)劃階段內(nèi)有n列車使用車站到發(fā)線，其算法如下。

（1）編碼。將車站編制計(jì)劃階段內(nèi)到達(dá)列車按照先后順序編號(hào)，生成 1～n的序列。每一列車使用 l 位二進(jìn)制碼表示其使用到發(fā)線的號(hào)數(shù)。其中，l表示恰好使 2l＞m的最小整數(shù)。

（2）初始群體的選取。在一個(gè)計(jì)劃階段內(nèi)到達(dá)車站的列車數(shù)是固定的，因此群體規(guī)模覆蓋所有列車可能使用的到發(fā)線即可，隨機(jī)產(chǎn)生n個(gè)個(gè)體的初始群體。

（3）適應(yīng)度函數(shù)的選取。適應(yīng)度函數(shù)主要考慮目標(biāo)函數(shù)的取值，采用罰函數(shù)處理邊界約束條件，產(chǎn)生適應(yīng)度函數(shù)值，以保證較優(yōu)解有較大的生存機(jī)會(huì)。其中，邊界約束條件為一個(gè)時(shí)間片內(nèi)一條到發(fā)線最多只被 1 列車占用。在求解的過(guò)程中，若 2 列及以上列車占用同一到發(fā)線，目標(biāo)函數(shù)采用罰函數(shù)處理，除以一個(gè)較大的數(shù) (如1 000)，以處罰這樣的個(gè)體，使其只有十分微小的生存機(jī)會(huì)，從而保證解的可行性。適應(yīng)度函數(shù)為：

（4）遺傳操作設(shè)計(jì)。選擇：采用比例選擇，從群體中選擇具有較高適應(yīng)度的個(gè)體組成下一個(gè)種群；交叉：?jiǎn)吸c(diǎn)交叉，隨機(jī)選取一個(gè)交叉點(diǎn)，將 2 個(gè)染色體在交叉點(diǎn)分開，然后交換其尾部；變異：遺傳變異是給隨機(jī)的基因有較小的變異概率，使其發(fā)生突變。

（5）終止規(guī)則。采用確定的迭代次數(shù)作為終止條件，根據(jù)實(shí)驗(yàn)調(diào)整迭代作為終止條件。

4 算例分析

采用長(zhǎng)沙南站 2010 年 7 月 1 日的運(yùn)行圖數(shù)據(jù)，編制最繁忙時(shí)段 9∶00—12∶00 的到發(fā)線運(yùn)用計(jì)劃。在此階段長(zhǎng)沙南站共到發(fā)列車30 列，其中長(zhǎng)沙南站始發(fā)、終到的列車共 5 列，停站通過(guò)列車 23 列，不停站通過(guò)列車 2 列。

4.1 基于遺傳算法的車站到發(fā)線運(yùn)用計(jì)劃

本算例中，車站到發(fā)列車等級(jí)相同，結(jié)合已有研究經(jīng)驗(yàn)，列車占用第一、二、三、四等級(jí)站臺(tái)到發(fā)線權(quán)值分別取值 3、2、1、0。本次運(yùn)行群體大小為 500，運(yùn)行迭代次數(shù)為 300，交叉率 0.5，變異率 0.005。在第 134 代時(shí)，得到最優(yōu)值，整理數(shù)據(jù)得到發(fā)線運(yùn)用情況如表 1 所示。

當(dāng)所有列車都被安排到最優(yōu)股道時(shí)，目標(biāo)函數(shù)值為z＝28×3＝84，得到目標(biāo)函數(shù)最優(yōu)值。將列車及其占用股道繪制成圖，如圖 1 所示。

到發(fā)線運(yùn)用權(quán)值矩陣構(gòu)建中，上行列車占用1、2、3 股道的權(quán)值為最高值 3，下行列車占用 10、11、12、13 股道的權(quán)值為最高值 3，加之本算例求得目標(biāo)函數(shù)理論上的最優(yōu)值，因而上行列車比較均勻地分布在 1、2、3 股道，而下行列車比較均勻地分布在 10、11、12、13 股道，并沒(méi)有分布在權(quán)值較小的股道上。

表1 長(zhǎng)沙南站 9 ：00—12 ：00 到發(fā)線運(yùn)用情況

圖1 長(zhǎng)沙南站9 ： 00—12 ： 00到發(fā)線運(yùn)用方案

4.2 分析結(jié)果的斂散性

在算法程序運(yùn)行時(shí)，同時(shí)記錄了到發(fā)線占用模型求解的每一代的最優(yōu)個(gè)體、群體的平均值和最優(yōu)個(gè)體適應(yīng)度。目標(biāo)函數(shù)最優(yōu)值的收斂曲線如圖 2 所示。

由圖 2 中的收斂曲線可以看出，利用遺傳算法求解建立的車站到發(fā)線占用模型，函數(shù)值近似呈對(duì)數(shù)函數(shù)形式收斂，收斂速度較快。

圖2 目標(biāo)函數(shù)最優(yōu)值的收斂曲線

5 結(jié)束語(yǔ)

利用遺傳算法對(duì)建立的高速鐵路車站到發(fā)線運(yùn)用模型求解，能夠較快地得到最優(yōu)解，而且尋優(yōu)過(guò)程收斂性較好。另外，通過(guò)修改遺傳算法適應(yīng)度函數(shù)，加入均衡因素，可實(shí)現(xiàn)列車均衡地分布在權(quán)值相同的到發(fā)線上。車站到發(fā)線運(yùn)用計(jì)劃是高速鐵路車站作業(yè)計(jì)劃的重要組成部分，對(duì)高速鐵路車站作業(yè)計(jì)劃智能化的實(shí)現(xiàn)進(jìn)行理論探討，具有一定的現(xiàn)實(shí)意義。

[1] 呂紅霞. 鐵路大型客運(yùn)站作業(yè)計(jì)劃智能編制的優(yōu)化技術(shù)和方法研究[D]. 成都：西南交通大學(xué)，2008.

[2] 馮樹明. 客運(yùn)專線車站作業(yè)計(jì)劃編制系統(tǒng)的研究[D]. 成都：西南交通大學(xué)，2008.

[3] 陳建鑫. 客運(yùn)專線車站作業(yè)計(jì)劃協(xié)同優(yōu)化方法研究[D]. 北京：北京交通大學(xué)，2007.

Research on Optimization of Arrival-departure Track Using in High-speed Railway Stations

HE Lin,LV Hong-Xia

(SchoolofTransportandLogistics,SouthwestJiaotongUniversity,Chengdu610031,Sichuan,China)

According to start-stop time of arrival-departure track occupied by trains which drawn by referring train operation scheme and EMU routing scheme, the suitable arrival-departure track could be arranged for each train by the arrival-departure track using program of high-speed railway station with principle of equilibrium and reasonable use as well as convenient for get on or get off train. Based on analyzing the using characteristics and principle of the arrival-departure track, the 0-1 programming model of arrival-departure track using is established, then got the solution by inherit algorithm. Through analyzing example, the arrival-departure track using program of Changsha South Station is drawn and its detailed utilization of the program.

High-speed Railway; Arrival-departure Track; 0-1 Programming; Inherit Algorithm

1003-1421(2012)08-0047-04

U293.2；U292.3+5

A

2012-05-16

國(guó)家自然科學(xué)基金(60776826)

何瑩