劉 杰，殷 勇*，甘志良

(1.西南交通大學(xué)交通與物流學(xué)院，成都610031；2.綜合交通運(yùn)輸智能化國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室，成都610031)

0 引言

高速鐵路到發(fā)線和咽喉區(qū)作為車(chē)站完成技術(shù)作業(yè)的重要設(shè)備，其作業(yè)效率和運(yùn)輸組織直接影響著整個(gè)路網(wǎng)的輸送能力.將兩者進(jìn)行綜合運(yùn)用研究對(duì)優(yōu)化車(chē)站作業(yè)組織、提高作業(yè)效率具有重要意義.

近年來(lái)，國(guó)內(nèi)外學(xué)者在該領(lǐng)域的研究重心逐漸轉(zhuǎn)移到高速鐵路車(chē)站.文獻(xiàn)[1]將到發(fā)線分配問(wèn)題看成時(shí)間上具有限制的排序問(wèn)題，并說(shuō)明到發(fā)線運(yùn)用屬于NP-hard問(wèn)題.文獻(xiàn)[2]用點(diǎn)包裝問(wèn)題描述到發(fā)線運(yùn)用問(wèn)題，建立了0-1整數(shù)規(guī)劃模型.文獻(xiàn)[3-4]以作業(yè)成本最小化為目標(biāo)構(gòu)建模型.文獻(xiàn)[5]基于設(shè)備使用均衡和旅客服務(wù)質(zhì)量分別建立到發(fā)線運(yùn)用優(yōu)化的多目標(biāo)模型.文獻(xiàn)[1-5]都構(gòu)建了到發(fā)線運(yùn)用優(yōu)化模型，但均未考慮與咽喉區(qū)進(jìn)路選擇的協(xié)調(diào)優(yōu)化且都只考慮了1個(gè)目標(biāo).文獻(xiàn)[6]基于既有研究成果建立到發(fā)線和咽喉區(qū)使用均衡的優(yōu)化模型，但未考慮列車(chē)接續(xù)時(shí)間問(wèn)題.文獻(xiàn)[7]基于到發(fā)線使用均衡和進(jìn)路偏好最大建立綜合運(yùn)用優(yōu)化模型，采用線性加權(quán)法求解，目標(biāo)權(quán)重賦值主觀性較強(qiáng)，僅能得到問(wèn)題的局部最優(yōu)解.文獻(xiàn)[8]建立設(shè)備占用效用最大的過(guò)站徑路模型，然而在求解時(shí)未考慮進(jìn)路占用效用和到發(fā)線運(yùn)用方案的穩(wěn)定性.

上述研究在到發(fā)線與咽喉區(qū)運(yùn)用整體性、求解算法適用性、作業(yè)計(jì)劃穩(wěn)定性等方面存在的不足，本文建立高速鐵路車(chē)站到發(fā)線與咽喉區(qū)綜合運(yùn)用優(yōu)化模型，基于改進(jìn)的帶精英策略的非支配排序遺傳算(NSGA-II)對(duì)模型進(jìn)行求解，得到的多種優(yōu)化方案為車(chē)站日常作業(yè)組織提供一定的參考.

1 問(wèn)題描述

到發(fā)線是為完成各類(lèi)列車(chē)作業(yè)而專(zhuān)門(mén)設(shè)置的線路，咽喉區(qū)是提供由進(jìn)站端接入至到發(fā)線和從到發(fā)線走行至出站端的通道.到發(fā)線使用規(guī)則決定了列車(chē)接入的到發(fā)線集合，接發(fā)列車(chē)對(duì)應(yīng)多個(gè)接發(fā)車(chē)進(jìn)路.如何在滿足列車(chē)到發(fā)時(shí)刻、作業(yè)時(shí)間標(biāo)準(zhǔn)、到發(fā)線占用原則[9]及咽喉區(qū)進(jìn)路占用原則[10]、動(dòng)車(chē)組運(yùn)用方案的前提下，確定所有接發(fā)列車(chē)的到發(fā)線及咽喉使用方案是研究的難點(diǎn).

2 建立綜合運(yùn)用優(yōu)化模型

2.1 模型基礎(chǔ)及假設(shè)

已知車(chē)站站型、列車(chē)運(yùn)行圖、作業(yè)時(shí)間標(biāo)準(zhǔn)、到發(fā)線固定使用方案及動(dòng)車(chē)組接續(xù)關(guān)系；具備接續(xù)關(guān)系的列車(chē)必須停靠在相同到發(fā)線；不考慮分段解鎖，軌道電路的解鎖時(shí)刻與所屬咽喉區(qū)的完全解鎖時(shí)刻相同；假設(shè)動(dòng)車(chē)段的能力沒(méi)有限制.

2.2 變量設(shè)置

假設(shè)某時(shí)段高速鐵路車(chē)站接發(fā)列車(chē)數(shù)量為m，根據(jù)到站先后編號(hào)為i，列車(chē)集合為I={1 ,2,…,i,…,m} ；到發(fā)線數(shù)量為n，編號(hào)為j，到發(fā)線集合為J={1 ,2,…,j,…,n} ；列車(chē)i接入到發(fā)線j的進(jìn)路集合為列車(chē)i接入到發(fā)線j的選用第k條進(jìn)路列車(chē)i從到發(fā)線j出發(fā)的發(fā)車(chē)進(jìn)路集合為列車(chē)i從到發(fā)線j的選用第k條發(fā)車(chē)進(jìn)路，

決策變量有：

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

(1)到發(fā)線占用與列車(chē)匹配最合理.

為保證作業(yè)安全有序，上下行列車(chē)分別接在上下行到發(fā)場(chǎng).列車(chē)接入的到發(fā)線與列車(chē)停站時(shí)間、列車(chē)等級(jí)和列車(chē)在站作業(yè)方式等最大程度匹配.匹配性程度用到發(fā)線占用費(fèi)用來(lái)體現(xiàn).優(yōu)化目標(biāo)1表示為

式中：cij為列車(chē)i占用到發(fā)線j的費(fèi)用.

目前多數(shù)學(xué)者的處理方法是為其賦予0、1、M共3種取值，無(wú)法體現(xiàn)不同種類(lèi)列車(chē)占用到發(fā)線的費(fèi)用差異[11].基于此，本文綜合考慮列車(chē)運(yùn)行方向、停站時(shí)間、在站作業(yè)方式和列車(chē)等級(jí)構(gòu)建到發(fā)線占用費(fèi)用矩陣.具體方法如下：

假設(shè)列車(chē)運(yùn)行方向集合S=(1,2,???,s)，列車(chē)分方向費(fèi)用矩陣為某方向列車(chē)停靠在j到發(fā)線，j到發(fā)線越靠近正線費(fèi)用值越低，列車(chē)遵循正接正發(fā)時(shí)費(fèi)用越低；列車(chē)作業(yè)類(lèi)型集合Y=(1,2,???,y)，列車(chē)作業(yè)方式費(fèi)用矩陣與列車(chē)進(jìn)行的始發(fā)、終到、停站、通過(guò)相關(guān)，且與到發(fā)線固定作業(yè)方式匹配程度相關(guān)；列車(chē)種類(lèi)集合G=(1,2,???,g)，列車(chē)種類(lèi)費(fèi)用矩陣與列車(chē)的等級(jí)和接入到發(fā)線的匹配程度密切相關(guān).定義算子⊕ ，若M=(h1,h2,???,hn) ，N=(u1,u2,???,un) ，則T=M⊕N=(max(h1,u1),???,max(hn,un)).基于算子運(yùn)算規(guī)則，列車(chē)i的費(fèi)用矩陣為

列車(chē)費(fèi)用矩陣構(gòu)成了到發(fā)線占用費(fèi)用矩陣C=(cij)，當(dāng)cij=∞時(shí)，表示列車(chē)i不能接入到發(fā)線j；當(dāng)cij≠∞時(shí)，表示列車(chē)i可以接入到發(fā)線j，所產(chǎn)生的費(fèi)用為cij.

(2)提高車(chē)站作業(yè)計(jì)劃穩(wěn)定性.

增大占用同一到發(fā)線的相鄰列車(chē)間的緩沖時(shí)間可有效提高車(chē)站作業(yè)計(jì)劃的穩(wěn)定性，同時(shí)兼顧到發(fā)線的均衡使用[12].假設(shè)列車(chē)i和i*接入同一到發(fā)線j，且列車(chē)i早于列車(chē)i*到達(dá)車(chē)站，則列車(chē)之間的緩沖時(shí)間表示為

因此，優(yōu)化目標(biāo)2表示為

(3)選擇長(zhǎng)度短、道岔少的進(jìn)路完成接發(fā)車(chē)作業(yè).

采用進(jìn)路占用費(fèi)用體現(xiàn)方案的優(yōu)劣.目標(biāo)函數(shù)3表示為

2.4 約束條件

優(yōu)化模型應(yīng)滿足下列約束條件：

(1)列車(chē)只能選擇1條到發(fā)線進(jìn)行作業(yè)，約束為

(2)到發(fā)線有效滿足列車(chē)接入條件，約束為

式中：Lj為編號(hào)為j的到發(fā)線的有效長(zhǎng)度；li為編號(hào)為i的列車(chē)長(zhǎng)度.

(3)列車(chē)只能選擇1條接車(chē)進(jìn)路和發(fā)車(chē)進(jìn)路，約束為

(4)到達(dá)同一到發(fā)線的相鄰列車(chē)作業(yè)之間須滿足最小安全時(shí)間間隔，約束為

(5)具備動(dòng)車(chē)組折返關(guān)系的2列列車(chē)必須安排在同一到發(fā)線上，約束為

式中：Mii*為0-1變量，依據(jù)列車(chē)方案確定，列車(chē)i與列車(chē)i*存在折返關(guān)系，取值為1；否則，為0.

(6)具有旅客換乘關(guān)系的列車(chē)必須停靠在同一站臺(tái)的到發(fā)線上，約束為

式中：Gjj*為0-1變量，依據(jù)車(chē)站站型確定，若到發(fā)線j與j*臨靠同一站臺(tái)，取值為1，否則，取值為0；Fii*為0-1變量，若列車(chē)i與列車(chē)i*存在換乘關(guān)系，取值為1，否則為0.

(7)通過(guò)列車(chē)s*應(yīng)安排在正線上，約束為

式中：L(j)為車(chē)站正線的集合；S*為通過(guò)列車(chē)集合.

(8)占用接發(fā)車(chē)作業(yè)進(jìn)路的交叉干擾疏解，約束為

(9)變量取值約束為

3 基于多目標(biāo)遺傳算法求解綜合運(yùn)用優(yōu)化問(wèn)題

上述模型是1個(gè)多目標(biāo)0-1規(guī)劃模型，此類(lèi)問(wèn)題通常不能得到唯一解使各個(gè)目標(biāo)都達(dá)到最優(yōu)，只能得到Pareto最優(yōu)解集.針對(duì)該類(lèi)問(wèn)題，一些學(xué)者求解的思想在于將多目標(biāo)問(wèn)題轉(zhuǎn)化為單目標(biāo)問(wèn)題求解，但轉(zhuǎn)化過(guò)程中權(quán)重等參數(shù)難以確定且受人為影響較大.部分學(xué)者采用啟發(fā)式算法對(duì)模型求解，但如何快速全面的找到具有收斂性的Pareto最優(yōu)解集是求解問(wèn)題的難點(diǎn).本文采用改進(jìn)的帶精英策略的非支配排序遺傳算法(NSGA-II)對(duì)模型求解.算法在保存優(yōu)秀個(gè)體和降低計(jì)算復(fù)雜度2個(gè)方面作了改進(jìn).

(1)染色體編碼和解碼：采用整數(shù)編碼的方式，列車(chē)數(shù)量為m，到發(fā)線數(shù)量為n，以列車(chē)占用的到發(fā)線作為編碼數(shù)值，編碼方式如圖1所示.對(duì)圖1的編碼子串進(jìn)行解碼，列車(chē)1占用到發(fā)線2，列車(chē)2占用到發(fā)線5，依次解碼不再贅述.

(2)種群快速非支配排序：使用快速非支配排序?qū)ΨN群進(jìn)行排序，為種群中的每個(gè)個(gè)體返回2列，分別是排序等級(jí)和擁擠距離.

(3)選擇算子：采用二進(jìn)制錦標(biāo)賽選擇，選擇過(guò)程中，隨機(jī)比較2個(gè)個(gè)體的排序等級(jí)，選擇排序等級(jí)低的個(gè)體，如果等級(jí)相同，則比較擁擠距離，選擇擁擠距離大的個(gè)體.

(4)交叉和變異：2個(gè)染色體之間的交叉如圖2所示，設(shè)交叉概率為pm，變異概率為pc，兩者可發(fā)生在編碼的任意位置.染色體1和2的交叉如圖2所示.

(5)精英策略：保留父代中的優(yōu)良個(gè)體，直接進(jìn)入子代，降低計(jì)算復(fù)雜度，同時(shí)保證精英個(gè)體不被遺漏.算法流程如圖3所示.

圖1 染色體編碼Fig.1 Chromosome coding

4 算例分析

4.1 算例求解

以某高速鐵路車(chē)站為例，如圖4所示，接發(fā)A、C、E共3個(gè)方向的列車(chē).動(dòng)車(chē)段1、2分別與下、上行到發(fā)場(chǎng)連通.采用模型及算法，對(duì)車(chē)站8:00-16:00接發(fā)的84列列車(chē)安排相應(yīng)股道及咽喉區(qū)進(jìn)路.列車(chē)技術(shù)作業(yè)時(shí)間標(biāo)準(zhǔn)按表1取值，到發(fā)線占用費(fèi)用矩陣如表所示2所示.

圖2 染色體交叉示意圖Fig.2 Chromosome cross diagram

圖3 算法流程Fig.3 Algorithm steps

表1 作業(yè)時(shí)間標(biāo)準(zhǔn)Table 1 Operating time standard

圖4 某高速鐵路車(chē)站平面站型Fig.4 Layout of a high-speed railway station plane

表2 到發(fā)線占用費(fèi)用矩陣Table 2 Occupancy cost matrix of arrival and departure line

列車(chē)從不同方向接入各到發(fā)線和從各到發(fā)線發(fā)出的最優(yōu)接發(fā)車(chē)進(jìn)路是確定的，例如從A端接入列車(chē)到股道1的最優(yōu)接車(chē)進(jìn)路經(jīng)過(guò)的股道為：9,11,19,21,35,37,39,41.因此可以確定各到發(fā)線對(duì)應(yīng)的最優(yōu)接發(fā)車(chē)進(jìn)路費(fèi)用如表3所示.

表3 各股道最優(yōu)接發(fā)車(chē)進(jìn)路的占用費(fèi)用Table 3 The cost of the optimal access route and departure route to the track

利用Matlab編程求解，參數(shù)為：初始種群100，最大進(jìn)化代數(shù)200，交叉概率0.9，變異概率0.1.計(jì)算得到上行列車(chē)作業(yè)方案最優(yōu)邊界如圖5所示.下行列車(chē)作業(yè)方案最優(yōu)邊界如圖6所示.

圖5 上行列車(chē)作業(yè)方案最優(yōu)邊界Fig.5 The optimal boundary of down train

圖6 下行列車(chē)作業(yè)方案最優(yōu)邊界Fig.6 The optimal boundary of up train operation

4.2 結(jié)果分析

根據(jù)模型優(yōu)化結(jié)果可知，有多種作業(yè)方案可供選擇.不同目標(biāo)函數(shù)對(duì)應(yīng)的最優(yōu)值對(duì)應(yīng)圖5和圖6的邊界點(diǎn).選擇解集中的一個(gè)方案，將其結(jié)果與原始方案進(jìn)行對(duì)比分析，驗(yàn)證方案的合理性.

分析表4，得出如下結(jié)論：

(1)列車(chē)占用到發(fā)線匹配性.優(yōu)化方案所有列車(chē)均采用“正接正發(fā)”的方式進(jìn)行作業(yè)；接入臨近正線的股道的列車(chē)數(shù)量較原始方案增多，列車(chē)接入與列車(chē)停站時(shí)間、列車(chē)等級(jí)和列車(chē)在站作業(yè)方式匹配度更高，占用總費(fèi)用減少10.因此，到發(fā)線與列車(chē)匹配度更合理.

表4 優(yōu)化前后車(chē)站作業(yè)方案的對(duì)比分析Table 4 Comparison and analysis of station operation schemes before and after optimization

(2)車(chē)站作業(yè)計(jì)劃穩(wěn)定性.優(yōu)化后車(chē)站作業(yè)計(jì)劃穩(wěn)定性評(píng)價(jià)函數(shù)值減少225，說(shuō)明優(yōu)化方案穩(wěn)定性更強(qiáng)；優(yōu)化方案的股道平均緩沖時(shí)間和相鄰兩次占用股道的平均緩沖時(shí)間都有所增加，列車(chē)接入到發(fā)線的緩沖時(shí)間越大，車(chē)站抗干擾能力越強(qiáng).

(3)接發(fā)車(chē)進(jìn)路條件好.優(yōu)化后車(chē)站接發(fā)列車(chē)占用總費(fèi)用相比優(yōu)化前減少475，列車(chē)接發(fā)的進(jìn)路條件好.

(4)軌道利用均衡性.優(yōu)化方案股道占用次數(shù)方差更小，到發(fā)線的使用越均衡.

5 結(jié)論

本文建立滿足列車(chē)到發(fā)占用到發(fā)線匹配性最大、作業(yè)計(jì)劃穩(wěn)定性最強(qiáng)和接發(fā)車(chē)進(jìn)路偏好性最好的優(yōu)化模型.以某高速鐵路車(chē)站為例，采用基于改進(jìn)的帶精英策略的非支配排序遺傳算法(NSGA-II)編程求解，選擇Pareto解集中一個(gè)方案與原有方案對(duì)比發(fā)現(xiàn)新的方案在列車(chē)與到發(fā)線的匹配性，車(chē)站作業(yè)計(jì)劃的穩(wěn)定性，接發(fā)車(chē)進(jìn)路條件，軌道利用均衡性都較原方案優(yōu)，驗(yàn)證了模型和算法的有效性，為車(chē)站日常接發(fā)車(chē)作業(yè)組織提供一定的參考.

[1]KANG L J,WU J J,SUN H J.Using simulated annealing in a bottleneck optimization model at railway station[J].Journal of Transportation Engineering,2012,138(11):1396-1402.

[2]ZWANEVELD P,KROON L G,HOESEL S P M V.Routing trains through a railway station based on a node packing model[J].European Journal of Operational Research,1997,128(1):14-33.

[3]CRAREY M,CRARVILLE S.Scheduling and plat forming trains at busy complex stations[J].Transportation Research,Part A,Policy and Practice,2003,37(A3):195-224.

[4]ZWANEVELD P J,KROON L G,HOESEL P M V.Routing trains through a railway station based on a node packing model[J].European Journal of Operational Research,2001,128(1):14-33.

[5]李琦.高速鐵路大型客運(yùn)站到發(fā)線運(yùn)用優(yōu)化研究[D].成都:西南交通大學(xué),2012.[LI Q.Study on the optimization of the development of large-scale passenger station in high-speed railway[D].Chengdu:Southwest Jiaotong University,2012.]

[6]趙鵬,宋文波,陳霞,等.大型鐵路客運(yùn)站到發(fā)線與咽喉區(qū)綜合運(yùn)用優(yōu)化[J].北京交通大學(xué)學(xué)報(bào),2015,39(6):1-7.[ZHAO P,SONG W B,CHENG X.Comprehensive utilization of large-scale railway passenger station to hairline and throat zone[J].Journal of Beijing Jiaotong University,2012.]

[7]喬瑞軍.客運(yùn)專(zhuān)線車(chē)站接發(fā)車(chē)進(jìn)路選擇與調(diào)整問(wèn)題研究[D].北京:北京交通大學(xué),2012.[QIAO R J.Study on route selection and adjustment of 6passenger dedicated line[D].Beijing:Beijing Jiaotong University,2012.]

[8]陳彥.鐵路客運(yùn)站列車(chē)過(guò)站徑路與調(diào)機(jī)運(yùn)用優(yōu)化[D].長(zhǎng)沙:中南大學(xué),2010.[CHEN Y.Optimization of trains and trunking of railway passenger station[D].Changsha:Central South University,2010.]

[9]王克豹.客運(yùn)專(zhuān)線與既有線銜接站到發(fā)線運(yùn)用優(yōu)化研究[D].成都:西南交通大學(xué),2011.[WANG K B.Study on optimization of passenger dedicated line and existing line connection station[D].Chengdu:Southwest Jiaotong University,2011.]

[10]陳建鑫.客運(yùn)專(zhuān)線車(chē)站作業(yè)計(jì)劃協(xié)同優(yōu)化方法研究[D].北京:北京交通大學(xué),2007.[CHEN J X.Research on cooperative optimization method of passenger dedicated line station operation plan[D].Beijing:Beijing Jiaotong University,2007.]

[11]江秀,倪少權(quán),陳釘均.客運(yùn)站到發(fā)線運(yùn)用優(yōu)化研究綜述[J].鐵道運(yùn)輸與經(jīng)濟(jì),2014,36(11)：14-18.[JIANG X,NI S Q,CHEN D J.A summary of optimization research on the application of passenger terminal[J].Railway Transport and Economy,2014,36(11):14-18.]

[12]賈文崢.大型鐵路客運(yùn)站的進(jìn)路分配問(wèn)題及緩沖時(shí)間研究[D].北京:北京交通大學(xué),2010.[JIA W Z.Research on route assignment and buffer time of large railway passenger station[D].Beijing:Beijing Jiaotong University,2010.]

[13]刁訓(xùn)娣.基于多目標(biāo)遺傳算法的項(xiàng)目調(diào)度及其仿真研究[D].上海:上海交通大學(xué),2010.[DIAO X D.Research on project scheduling and simulation based on multi-objective genetic algorithm[D].Shanghai:Shanghai Jiaotong University,2010.]