劉 杰，殷 勇*，甘志良

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

0 引言

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

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

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

1 問題描述

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

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

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

已知車站站型、列車運行圖、作業(yè)時間標(biāo)準、到發(fā)線固定使用方案及動車組接續(xù)關(guān)系；具備接續(xù)關(guān)系的列車必須?？吭谙嗤桨l(fā)線；不考慮分段解鎖，軌道電路的解鎖時刻與所屬咽喉區(qū)的完全解鎖時刻相同；假設(shè)動車段的能力沒有限制.

2.2 變量設(shè)置

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

決策變量有：

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

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

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

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

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

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

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

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

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

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

(3)選擇長度短、道岔少的進路完成接發(fā)車作業(yè).

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

2.4 約束條件

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

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

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

式中：Lj為編號為j的到發(fā)線的有效長度；li為編號為i的列車長度.

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

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

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

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

(6)具有旅客換乘關(guān)系的列車必須?？吭谕徽九_的到發(fā)線上，約束為

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

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

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

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

(9)變量取值約束為

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

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

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

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

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

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

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

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

4 算例分析

4.1 算例求解

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

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

圖3 算法流程Fig.3 Algorithm steps

表1 作業(yè)時間標(biāo)準Table 1 Operating time standard

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

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

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

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

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

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

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

4.2 結(jié)果分析

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

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

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

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

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

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

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

5 結(jié)論

本文建立滿足列車到發(fā)占用到發(fā)線匹配性最大、作業(yè)計劃穩(wěn)定性最強和接發(fā)車進路偏好性最好的優(yōu)化模型.以某高速鐵路車站為例，采用基于改進的帶精英策略的非支配排序遺傳算法(NSGA-II)編程求解，選擇Pareto解集中一個方案與原有方案對比發(fā)現(xiàn)新的方案在列車與到發(fā)線的匹配性，車站作業(yè)計劃的穩(wěn)定性，接發(fā)車進路條件，軌道利用均衡性都較原方案優(yōu)，驗證了模型和算法的有效性，為車站日常接發(fā)車作業(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]李琦.高速鐵路大型客運站到發(fā)線運用優(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]趙鵬,宋文波,陳霞,等.大型鐵路客運站到發(fā)線與咽喉區(qū)綜合運用優(yōu)化[J].北京交通大學(xué)學(xué)報,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]喬瑞軍.客運專線車站接發(fā)車進路選擇與調(diào)整問題研究[D].北京:北京交通大學(xué),2012.[QIAO R J.Study on route selection and adjustment of 6passenger dedicated line[D].Beijing:Beijing Jiaotong University,2012.]

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

[9]王克豹.客運專線與既有線銜接站到發(fā)線運用優(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è)計劃協(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),陳釘均.客運站到發(fā)線運用優(yōu)化研究綜述[J].鐵道運輸與經(jīng)濟,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]賈文崢.大型鐵路客運站的進路分配問題及緩沖時間研究[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)遺傳算法的項目調(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.]