秦 進，譚宇超，張 威，申純燕，趙 成

(1.中南大學 交通運輸工程學院，湖南 長沙 410075；2.中南大學 軌道交通安全教育部重點實驗室，湖南 長沙 410075；3.廣深鐵路股份有限公司 深圳北車站，廣東 深圳 518010)

城際高速鐵路是在人口稠密的都市圈或城市群中修建的高速鐵路客運專線，其主要特點是線路距離較短、列車班次公交化，且列車最大運行速度一般不低于250 km/h，兼有城際鐵路和高速鐵路的特征，目前京津、滬寧、武漢、長株潭等主要城市群的城際鐵路已在區(qū)域經(jīng)濟發(fā)展中發(fā)揮重要作用。但是要高效運用城際鐵路的設(shè)施與服務(wù)，必須建立起科學的組織理論與方法。列車開行方案是連接客流需求和列車時刻表的橋梁，一般包括列車等級、開行區(qū)段、停站方案、列車編組和開行頻率等內(nèi)容。作為組織和利用城際鐵路能力的關(guān)鍵環(huán)節(jié)和技術(shù)，列車開行方案的編制質(zhì)量直接關(guān)系到高速鐵路的市場競爭力和服務(wù)質(zhì)量水平。

列車開行方案問題在國內(nèi)外已經(jīng)得到了廣泛關(guān)注和深入研究。文獻[1]將包含不同類型列車的開行方案問題描述為多商品流網(wǎng)絡(luò)問題進行分析。文獻[2]以旅客旅行時間最短和換乘懲罰成本最小為目標，建立0-1整數(shù)規(guī)劃模型。文獻[3]假設(shè)同OD對的旅客會選擇相同最短路徑出行，并以列車運行成本和旅客旅行時間最小為目標建立了多商品流模型。文獻[4]針對城市軌道交通跨站越行模式，建立了雙目標非線性混合整數(shù)規(guī)劃模型。文獻[5-8]利用多目標優(yōu)化模型、雙層規(guī)劃模型、彈性需求等方法，對列車開行方案相關(guān)問題進行了深入研究。文獻[9]提出了高速鐵路列車停站的兩階段優(yōu)化方法。文獻[10]構(gòu)建了不確定需求下高速鐵路列車停站方案的機會約束規(guī)劃模型。為了滿足高鐵旅客的時變性需求，很多研究也建立了基于時刻表的離散整數(shù)規(guī)劃模型。文獻[11]針對以旅客選擇為基礎(chǔ)的高速列車時刻表鋪畫問題，建立了離散事件仿真模型和約束Logit選擇模型。文獻[12]不考慮列車能力限制，從列車成本和旅客成本兩方面出發(fā)，對列車開行方案和列車運行時刻進行綜合優(yōu)化。文獻[13]在列車開行方案優(yōu)化過程中考慮了列車運行圖優(yōu)化，以鐵路利益最大化為目標建立優(yōu)化模型，但暫時還不能適應(yīng)大規(guī)模實際問題。文獻[14]建立了基于列車候選集的高速鐵路列車開行方案優(yōu)化方法，但其中列車區(qū)段和停站方案來源于現(xiàn)有開行方案，當客流特征發(fā)生改變時，其適用性會有所降低。

時空網(wǎng)絡(luò)方法在處理帶時間維度的問題時具有易建模、求解便利等優(yōu)勢，國內(nèi)外很多學者在研究公共交通問題時都會使用時空網(wǎng)絡(luò)方法。文獻[15]使用時空網(wǎng)絡(luò)來研究航班機型分配問題。文獻[16]建立了基于離散時空網(wǎng)絡(luò)的不正常航班調(diào)度模型。文獻[17]根據(jù)旅客列車運行圖構(gòu)造了列車時空服務(wù)網(wǎng)絡(luò)，在此基礎(chǔ)上提出了體現(xiàn)旅客時空差異服務(wù)需求約束的客流分配模型及算法。文獻[18]考慮線路中斷后的情況，在時空網(wǎng)絡(luò)上建立了以旅客負效用和企業(yè)成本最低為目標的0-1整數(shù)規(guī)劃方法。

綜上所述，目前關(guān)于列車開行方案的研究主要集中在停站方案、開行頻率等單個方面的優(yōu)化研究，綜合考慮這些因素的研究較少，時空網(wǎng)絡(luò)方法也多應(yīng)用在列車時刻表優(yōu)化問題和列車開行方案基礎(chǔ)上的客流分配問題。本文從實際出發(fā)，在給定的運輸線路和客流需求條件下，構(gòu)建城際鐵路運營時空網(wǎng)絡(luò)，在此基礎(chǔ)上考慮設(shè)備資源限制、時空網(wǎng)絡(luò)客流及列車流守恒、客流需求特征和城際列車時空運行規(guī)律等，建立基于時空網(wǎng)絡(luò)的列車開行方案優(yōu)化模型，并利用雙層模擬退火算法進行求解和計算分析。

1 問題分析

在城際鐵路線路列車開行方案中，每列列車可以用一組途經(jīng)車站的有序序列來表示，表示列車的運行起訖點和停站方案，并且有途經(jīng)各個車站的到達和離開時刻，通過列車的發(fā)車時刻可以推算出列車的開行頻率。

在城際鐵路列車提供具有高速度、高密度特征運輸服務(wù)模式下，城際客流需求具有明顯的時變特性，即城際出行需求在運營時間段內(nèi)，每對起訖站之間的需求大小都會隨著時間的變化而變化。以滬寧城際高速鐵路為例，如圖1所示，根據(jù)城際鐵路售票數(shù)據(jù)，2017年5月31日的滬寧城際下行方向客流需求，呈現(xiàn)出明顯的小時變化特征，上午高峰期客流與晚間客流差異極大。

圖1 2017年5月31日滬寧城際下行方向每小時旅客出發(fā)數(shù)量

盡管城際鐵路客流需求實際是一個隨時間變化的函數(shù)，但是在一定的時間段內(nèi)，客流需求仍是可以被視為一個固定不變的常量，因此可以考慮將城際鐵路總的運營時段劃分為若干個小的時間段，假設(shè)每個時間段內(nèi)的客流需求都固定不變，由此可將時變需求轉(zhuǎn)化為固定客流需求，從而有效簡化問題分析。

城際鐵路旅客出行時，若列車發(fā)車時刻與期望出發(fā)時刻存在差異，將會為旅客帶來不便。如果能在開行方案決策過程中，適當考慮旅客期望出發(fā)時刻信息，必然可以保證決策者能更全面的從空間和時間兩個角度進行方案評價，以保證所得方案的整體最優(yōu)。

時間信息的加入無疑會顯著增加問題的復(fù)雜度。結(jié)合問題的特性，可以考慮引入能將時間和空間要素進行有機結(jié)合的時空網(wǎng)絡(luò)方法進行問題的分析和優(yōu)化。列車開行方案的時空網(wǎng)絡(luò)模型會增加列車在沿途各站到發(fā)時刻的信息，可在方案優(yōu)化的同時處理時變客流分配問題，從而為考慮時間信息的城際列車開行方案優(yōu)化問題的建模和求解帶來極大便利。尤其是該方法可根據(jù)實際情況靈活調(diào)整時間信息的精確度。

為簡化問題，做如下合理假設(shè)：

(1)列車運行時間只考慮區(qū)間純運行時分，不考慮起停附加時分。

(2)列車采用固定編組，所有列車等級相同。

(3)城際列車間隔時間類型眾多，為提高計算效率，同時獲取合理的列車運行時間估計值，僅考慮始發(fā)車站的發(fā)車間隔時間，因此會有部分列車運行線發(fā)生沖突的可能。

(4)假設(shè)線路上下行列車是對稱開行，即上下行列車開行方案一致，暫不考慮動車組運用問題。

2 模型構(gòu)建

2.1 列車開行方案的時空網(wǎng)絡(luò)構(gòu)造

圖2為某城際高速鐵路線路，其上的車站集合為S，車站數(shù)量為|S|。圖中節(jié)點代表車站，弧代表車站之間的線路。

圖2 城際高速鐵路線路示意圖

圖3 城際列車開行方案時空網(wǎng)絡(luò)示意圖

2.2 模型變量

2.3 優(yōu)化模型

基于所構(gòu)建的列車開行方案時空網(wǎng)絡(luò)，可構(gòu)建城際列車開行方案的0-1規(guī)劃模型。模型的優(yōu)化目標是最小化系統(tǒng)內(nèi)的列車運行成本和旅客出行成本，同時考慮時空網(wǎng)絡(luò)中的時空節(jié)點上列車流和客流守恒特性，列車流和客流之間的時間邏輯，以及鐵路行車組織要求的車站發(fā)車間隔時間、列車定員、列車運行總數(shù)等約束條件。

列車運行成本由列車在弧段上運行時間表示，旅客出行成本由旅客在弧段上出行時間、出發(fā)偏差時間和未登上列車旅客懲罰時間表示，這4者的線性組合構(gòu)成模型的優(yōu)化目標函數(shù)。

(1)

(2)

(3)

則旅客出發(fā)偏差總時間Ψ3為

(4)

(5)

對于列車運行時間Ψ1、旅客弧段出行時間Ψ2、旅客出發(fā)偏差時間Ψ3和未登上列車旅客懲罰時間Ψ4，引入加權(quán)參數(shù)δ1、δ2、δ3、δ4，組合生成列車開行方案優(yōu)化目標為

minZ=δ1Ψ1+δ2Ψ2+δ3Ψ3+δ4Ψ4

(6)

優(yōu)化模型中需考慮的約束如下：

①列車流守恒約束

(7)

(8)

式(7)為在時空點上的列車流守恒約束，使得到達時空點(j,τ)的列車數(shù)減去終到列車數(shù)等于離開時空點(j,τ)的列車數(shù)減去始發(fā)列車數(shù)；式(8)保證列車流在其中間途經(jīng)時空點守恒。

②客流守恒約束

(9)

(10)

(11)

③決策變量關(guān)系約束

(12)

時空網(wǎng)絡(luò)中旅客只能使用有列車經(jīng)過的弧段，即在任意弧段上，任何旅客群體的決策變量值均不能大于任何列車決策變量值。

④列車定員約束

(13)

式(13)表示同時乘坐同一列車的旅客數(shù)應(yīng)不大于列車定員數(shù)。

⑤始發(fā)車站發(fā)車時間間隔約束

(14)

?t′≤t+ε?f≠f′

f,f′∈Ωi∈Sf∩Sf′j′∈Sf′

式(14)表示始發(fā)車站任意兩列列車的發(fā)車時間間隔不小于固定值ε。

⑥列車總數(shù)約束

(15)

這主要是考慮列車數(shù)量對企業(yè)的運輸效率與能力有重要的影響，開行過多的列車必然會增加成本，同時使線路區(qū)間與車站能力接近飽和，因此應(yīng)對列車使用數(shù)量進行限制，即列車開行方案Ω使用的列車數(shù)不大于給定值b。

⑦變量取值約束

(16)

(17)

(18)

根據(jù)以上分析，就可建立基于時空網(wǎng)絡(luò)的城際高鐵列車開行方案優(yōu)化模型為

3 求解算法

基于時空網(wǎng)絡(luò)的高速鐵路列車開行方案優(yōu)化模型，實際上是一個大規(guī)模的0-1整數(shù)規(guī)劃模型，其計算復(fù)雜度隨著列車和車站的數(shù)量增加而呈現(xiàn)幾何級增長，目前的精確算法很難在有效時間內(nèi)獲得問題的滿意解。本文使用基于模擬退火算法(Simulated Annealing,SA)設(shè)計模型的求解方法。

圖4 內(nèi)層算法鄰域解

基于時空網(wǎng)絡(luò)的高速鐵路列車開行方案優(yōu)化模型，需要同時優(yōu)化列車的運行起訖點、停站方案、服務(wù)頻率及列車在停站到發(fā)時刻4項內(nèi)容，由于區(qū)間運行時分均為定值，因此結(jié)合列車始發(fā)時刻與停站方案，就能獲得列車沿途各站的到發(fā)時間，結(jié)合列車始發(fā)時刻與區(qū)段列車數(shù)量，就能獲得列車服務(wù)頻率，由此可將模型優(yōu)化內(nèi)容簡化為列車運行起訖點、停站方案、各運行區(qū)段開行數(shù)量及始發(fā)時刻4項內(nèi)容?？紤]到停站方案是在運行起訖點和開行數(shù)量確定的基礎(chǔ)上才能優(yōu)化確定，因此所建立模型可以分為上下兩層進行決策。根據(jù)這一特點，設(shè)計了雙層SA算法進行城際高速鐵路列車開行方案優(yōu)化模型求解，即將問題分為內(nèi)外兩層進行求解，其中外層SA算法首先確定列車運行起訖點、開行數(shù)量和始發(fā)站始發(fā)時間，在外層決策的基礎(chǔ)之上，內(nèi)層SA算法優(yōu)化列車停站方案。

3.1 解的表達形式算法初始解構(gòu)造

列車開行方案由所有列車的開行信息構(gòu)成，因此問題的解Ω為

(19)

式中：Hf為列車f的開行信息。

(20)

(21)

通過Hf的前|S|個變量就可確定列車起訖點、停站方案，由于區(qū)間運行時分均為定值，因此通過始發(fā)時間和停站方案就可推算列車f在各停站的到發(fā)時刻。

內(nèi)層算法初始解采用站站停模式；外層算法初始解可利用文獻[14]的方法進行構(gòu)造，因篇幅所限，這里不做詳細描述。

3.2 算法鄰域構(gòu)造

(1)內(nèi)層算法鄰域構(gòu)造

停站方案(即Hf中前|S|個變量)是由0-1變量所構(gòu)成，因此可利用在列車起訖點間非始發(fā)終到車站對應(yīng)變量取反方法構(gòu)造停站方案的鄰域。如圖4所示，列車f在其行駛路徑上，隨機選擇車站2進行變量取反而獲得鄰域解。

(2)外層算法鄰域構(gòu)造

外層退火算法的鄰域構(gòu)造方法如下[14]：

①刪除列車：檢查所有列車弧段客座率，若最高客座率低于規(guī)定閾值，則刪除該列車。

②添加列車：在滿足約束前提下，對于未登上車的客流，按照初始解構(gòu)造方法生成站站停的列車；對于每個區(qū)間，若所有列車在該區(qū)間客座率的平均值達到規(guī)定閾值，則添加1列車，其停站方案與客座率最高列車相同，始發(fā)時刻亦安排在該列車所在始發(fā)時段內(nèi)。

③拆分列車：檢查所有列車弧段上的客座率，刪除低于規(guī)定閾值的弧段，并根據(jù)車站等級、發(fā)車間隔時間確定拆分后列車的始發(fā)終到站和發(fā)車時刻。如圖5所示，列車f由車站1運行至車站4，為站站停，其中車站1、2、4均可始發(fā)終到列車，由于車站1至車站2之間客座率為10%低于預(yù)設(shè)閾值30%，故將列車f改為由車站2始發(fā)。

圖5 拆分列車示意圖

④拼接列車：對于方向相同的兩列列車f1與f2，若列車f1在車站s終到的同時列車f2也在車站s始發(fā)，并且f1在車站s的到達時間與f2在車站s的發(fā)車時間間隔不超過預(yù)設(shè)值，且拼接后的列車滿足約束條件，則列車f1與f2進行拼接，新列車始發(fā)時間與f1相同，停站方案不變。

⑤調(diào)整列車始發(fā)時刻：在滿足約束前提下，以一定概率將列車的始發(fā)時刻提前或推遲一定時間。

3.3 算法步驟

根據(jù)以上分析，可設(shè)計雙層SA算法具體步驟如下：

(1)外層SA算法

設(shè)置初始溫度值T0、溫度下降比例θ，終止溫度Tend，當前溫度T=T0，迭代次數(shù)K=1。

Step1生成初始解Ω0，并設(shè)置當前解Ω=Ω0。

Step2計算目標函數(shù)。通過開行方案Ω確定列車與旅客所經(jīng)弧段，計算目標值Z。

Step6迭代次數(shù)檢驗。K=K+1，若K>Uiner，Uiner為迭代次數(shù)上限，則令T=T×θ；否則轉(zhuǎn)Step3。

Step7算法終止檢驗。若T

(2)內(nèi)層SA算法

4 算例分析

4.1 算例數(shù)據(jù)

以滬寧城際鐵路下行方向的本線列車開行方案為研究對象。滬寧城際線是連接華東兩大城市上海與南京的城際鐵路客運專線，運營里程301 km，沿線共設(shè)車站23個，其中南京南站通過仙林聯(lián)絡(luò)線接入滬寧城際，上海虹橋站通過虹安聯(lián)絡(luò)線接入滬寧城際，區(qū)間運行時分根據(jù)現(xiàn)有的列車運行圖獲得，區(qū)間和車站信息見圖6。

根據(jù)線路結(jié)構(gòu)特點，可將南京站、南京南站合并為南京站，上海站、上海虹橋站、上海西站合并為上海站，客流信息也做相應(yīng)處理。對于當日無到發(fā)客流的丹徒站、南翔北站也不予考慮。經(jīng)上述處理后的線路共18個車站?？紤]除南京站和上海站之外，常州站、無錫站、蘇州站同樣具備車底檢修和夜間存車條件，因此將這5座車站設(shè)置為始發(fā)終到車站，即所有列車均在上述車站完成始發(fā)終到。

圖6 滬寧城際鐵路下行方向區(qū)間里程及運行時分

選取2017年5月31日滬寧城際的客流和運行圖進行計算分析。其時滬寧城際下行方向運行本線車55列，客流需求總量為75 659人，所有列車定員統(tǒng)一為Mf=1 230，并將當前所購車票出發(fā)時間視為旅客期望出發(fā)時間。設(shè)定鐵路運營時段為[05:00,24:00]，客流時段劃分為1 h。時空網(wǎng)絡(luò)中時間間隔σ=2 min，這樣每個車站共有571個離散時間點。根據(jù)現(xiàn)有列車運行圖，車站最小發(fā)車間隔時間為6 min。另外根據(jù)文獻[14]，目標函數(shù)加權(quán)參數(shù)可分別設(shè)為δ1=6 000,δ2=1,δ3=50,δ4=100。

SA算法中參數(shù)T0=1 000，θ=0.98，Tend=0.001，Uiner=300。外層SA算法構(gòu)造鄰域策略中，刪除列車閾值為0.5，添加列車閾值為0.7，拆分列車閾值為0.2，拼接列車閾值為10 min，調(diào)整列車始發(fā)時間概率為0.5，調(diào)整量為10 min。

4.2 計算分析

根據(jù)所提出的時空網(wǎng)絡(luò)優(yōu)化方法，計算得到如圖7所示的優(yōu)化開行方案，相應(yīng)的動車組列車的起訖點和開行數(shù)量見表1，停站方案基本信息見表2。

圖7 滬寧城際下行方向優(yōu)化列車開行方案

表1 列車起訖點和開行數(shù)量

與實際運行圖相比，優(yōu)化方案中列車總數(shù)減少19列，其中南京—上海和蘇州—上海的開行列車數(shù)降低，南京—蘇州、常州—上海和無錫—上海的開行列車數(shù)增加，由于短途列車始發(fā)時間可安排在線路中間車站出發(fā)旅客數(shù)量較多的時段，能有效降低短途旅客出發(fā)偏差時間，同時短途列車在弧段上運行時間更低，能更好的降低總成本，因此短途列車數(shù)量有所增加，而蘇州—上海區(qū)間的部分旅客需求可以由常州、無錫始發(fā)的列車滿足，列車數(shù)量也有所降低；列車平均停站數(shù)方面，優(yōu)化方案相比實際方案增加3.1站，這是由于開行列車總數(shù)減少，為了使短途旅客能夠得到列車服務(wù)，故列車停站數(shù)量有所增加。其中南京—上海區(qū)間里程最長，所能服務(wù)短途旅客數(shù)量最多，因此列車停站數(shù)量增幅最大，平均增加4.7站。

如表3所示，長途列車 (即南京—上海)在優(yōu)化方案和實際方案中的列車始發(fā)時間分布都比較均勻；短途列車的始發(fā)列車多分布在前3個時段，且該時段內(nèi)的優(yōu)化方案比實際方案多出6列而達到26列，占到列車總數(shù)的72%。這主要是因為南京至上海之間增開較多的長途列車，可滿足大部分的客流需求。短途列車主要分布在旅客需求較多的時空區(qū)域，即高峰時段[7:00,14:00]，見圖7。

表4所示為最優(yōu)解與初始解的比較分析。相對初始解，最優(yōu)解中開行列車總數(shù)、列車運行成本、旅客出行成本和旅客平均出發(fā)時間偏差，分別減少12列、1.11×107min、0.23×106min和增加0.15 min，平均客座率上升25.18%。時間偏差增加的原因，主要是由于初始解構(gòu)造時更傾向于滿足旅客出行期望，較少考慮運營成本因素，但算法會逐漸平衡企業(yè)和旅客兩方面成本，故最優(yōu)方案中企業(yè)成本下降，時間偏差增加，但偏差始終未超過20 min。

表3 優(yōu)化方案/實際方案在不同始發(fā)時段的列車數(shù)量分布

表4 算法初始解與最優(yōu)解比較

各時段旅客出發(fā)偏差平均值見圖8，大部分時段的偏差值均在平均值之下，時段1出發(fā)時間偏差值較高主要是由于該時段出發(fā)人數(shù)較少；出發(fā)旅客數(shù)量最多的時段3的偏差值僅為15.1 min，說明在高峰時段的旅客需求能得到較好的滿足。

圖8 各時段旅客出發(fā)偏差平均值

圖9展示了線路能力、客流和列車客座率隨時間變化的情況。列車客座率大部分時段都達到80%以上，圖中兩端時段客座率較低主要是由于最早最晚時段內(nèi)的客流較少。時段9中客座率有所下滑則是由于此時需求有所減少，但是大部分列車還未抵達終點站。圖10展示了各區(qū)間運營時段內(nèi)平均的斷面客流量、區(qū)間運輸能力和列車客座率情況?？土鞲叻宄霈F(xiàn)在陽澄湖—上海區(qū)段，該區(qū)段內(nèi)的客座率均達到86%以上。而且所有區(qū)間內(nèi)列車客座率都在70%以上，運輸能力得到較好的利用。

圖9 線路能力、客流量和客座率

圖10 平均區(qū)間運輸能力、斷面流量和客座率

5 結(jié)論

列車開行方案是組織運用高鐵運輸能力的關(guān)鍵環(huán)節(jié)。利用時空網(wǎng)絡(luò)方法研究考慮時變需求的高鐵開行方案，可為開行方案決策者提供包括旅客期望出行時間等更多服務(wù)信息，從而提高列車開行方案的編制質(zhì)量和系統(tǒng)的服務(wù)水平。本文在構(gòu)造高鐵開行方案時空網(wǎng)絡(luò)的基礎(chǔ)上，建立城際高鐵列車開行方案的時空網(wǎng)絡(luò)優(yōu)化模型，以最小化鐵路企業(yè)運營成本和旅客出行成本為目標，考慮時空網(wǎng)絡(luò)客流及列車流守恒、發(fā)車時間間隔、列車定員、列車數(shù)量等約束，并結(jié)合問題特征設(shè)計了雙層模擬退火算法進行求解。算例分析表明，所提出的方法計算快捷，結(jié)果合理，且與實際方案相比，優(yōu)化方案在滿足時變客流需求的前提下，降低了系統(tǒng)總成本，說明上述方法能為城際高鐵列車開行方案提供科學決策支持。下一步工作將主要考慮動車組運用對列車開行方案的影響而開展協(xié)同優(yōu)化研究。