基于時空網絡的城際高速鐵路列車開行方案優化方法

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

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

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

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

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

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

1 問題分析

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

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

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

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

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

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

為簡化問題，做如下合理假設：

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

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

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

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

2 模型構建

2.1 列車開行方案的時空網絡構造

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

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

圖3 城際列車開行方案時空網絡示意圖

2.2 模型變量

2.3 優化模型

基于所構建的列車開行方案時空網絡，可構建城際列車開行方案的0-1規劃模型。模型的優化目標是最小化系統內的列車運行成本和旅客出行成本，同時考慮時空網絡中的時空節點上列車流和客流守恒特性，列車流和客流之間的時間邏輯，以及鐵路行車組織要求的車站發車間隔時間、列車定員、列車運行總數等約束條件。

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

(1)

(2)

(3)

則旅客出發偏差總時間Ψ3為

(4)

(5)

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

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

(6)

優化模型中需考慮的約束如下：

①列車流守恒約束

(7)

(8)

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

②客流守恒約束

(9)

(10)

(11)

③決策變量關系約束

(12)

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

④列車定員約束

(13)

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

⑤始發車站發車時間間隔約束

(14)

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

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

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

⑥列車總數約束

(15)

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

⑦變量取值約束

(16)

(17)

(18)

根據以上分析，就可建立基于時空網絡的城際高鐵列車開行方案優化模型為

3 求解算法

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

圖4 內層算法鄰域解

基于時空網絡的高速鐵路列車開行方案優化模型，需要同時優化列車的運行起訖點、停站方案、服務頻率及列車在停站到發時刻4項內容，由于區間運行時分均為定值，因此結合列車始發時刻與停站方案，就能獲得列車沿途各站的到發時間，結合列車始發時刻與區段列車數量，就能獲得列車服務頻率，由此可將模型優化內容簡化為列車運行起訖點、停站方案、各運行區段開行數量及始發時刻4項內容。考慮到停站方案是在運行起訖點和開行數量確定的基礎上才能優化確定，因此所建立模型可以分為上下兩層進行決策。根據這一特點，設計了雙層SA算法進行城際高速鐵路列車開行方案優化模型求解，即將問題分為內外兩層進行求解，其中外層SA算法首先確定列車運行起訖點、開行數量和始發站始發時間，在外層決策的基礎之上，內層SA算法優化列車停站方案。

3.1 解的表達形式算法初始解構造

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

(19)

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

(20)

(21)

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

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

3.2 算法鄰域構造

(1)內層算法鄰域構造

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

(2)外層算法鄰域構造

外層退火算法的鄰域構造方法如下[14]：

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

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

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

圖5 拆分列車示意圖

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

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

3.3 算法步驟

根據以上分析，可設計雙層SA算法具體步驟如下：

(1)外層SA算法

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

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

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

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

Step7算法終止檢驗。若T

(2)內層SA算法

4 算例分析

4.1 算例數據

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

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

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

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

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

4.2 計算分析

根據所提出的時空網絡優化方法，計算得到如圖7所示的優化開行方案，相應的動車組列車的起訖點和開行數量見表1，停站方案基本信息見表2。

圖7 滬寧城際下行方向優化列車開行方案

表1 列車起訖點和開行數量

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

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

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

表3 優化方案/實際方案在不同始發時段的列車數量分布

表4 算法初始解與最優解比較

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

圖8 各時段旅客出發偏差平均值

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

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

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

5 結論

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