基于換乘接續優化的高鐵周期性列車運行圖編制研究

李天琦， 聶 磊， 譚宇燕

(北京交通大學 交通運輸學院， 北京 100044)

近年來，我國高鐵路網規模不斷擴大、旅客服務質量需求逐漸提高，以高服務頻率、規律停站、便捷換乘、旅客方便記憶為特點的周期性列車運行圖得到了我國鐵路運營管理部門的關注。由于列車開行方案呈周期性重復，高速鐵路周期性列車運行圖與非周期性列車運行圖差異性顯著：一是周期性列車運行圖停站組合種類較少，在考慮保證列車旅行速度的條件下，需要設計換乘接續來滿足旅客多樣化的出行服務需求；二是受限于周期性列車運行圖鋪畫條件，長距離列車的開行數量受限制，故在列車起訖點選擇上，周期性列車運行圖的可選方案明顯少于非周期性列車運行圖，將產生較大數量的換乘服務需求。因此，在列車周期性開行條件下，為保障在相對少量的列車停站組合和起訖點種類條件下滿足多樣化的旅客出行需求，充分發揮周期性列車運行圖便捷換乘的優勢，需要在列車運行圖編制過程中優化列車接續關系。

在高鐵周期性列車運行圖編制方面，既有研究一般建模為周期事件規劃模型(Periodic Event Scheduling Problem，PESP)[1]和圈周期模型(Cycle Periodicity Formulation，CPF)[2]。國外學者針對周期性列車運行圖模型的諸多特性和求解算法開展了豐富的研究：模型結構方面，文獻[2-5]的研究內容涉及動車組接續的靈活性[2]、區間運行時間的可變性[2-3]、運行圖魯棒性[4]和結構的對稱性[5]等多個方面，提高了模型的實用價值；求解策略方面，除使用CPLEX等整數規劃求解器直接求解外，文獻[5-6]探討的圈基搜索輔助求解技術已成為該問題的主要求解方式，文獻[7]提出的模單純型算法進一步提高了模型求解效率。國內學者在借鑒國外研究經驗的基礎上，多結合我國單條高鐵線路開展研究：文獻[8]簡化處理了 CPF模型圈基約束，高效編制了京津城際鐵路周期性列車運行圖;文獻[9]與文獻[10]分別考慮了定序條件和可變區間運行時間編制了京滬高速鐵路周期性列車運行圖，文獻[11]探討了周期性列車運行圖編制系統開發的關鍵技術。以上成果為進一步研究周期性列車運行圖優化問題打下了堅實的基礎。

高鐵周期性列車運行圖編制過程中對換乘接續問題的考慮方面，既有研究多基于固定接續關系和不固定接續關系兩種思路。基于固定接續關系的研究一般將一套確定、可靠的列車接續方案作為列車運行圖編制模型的輸入，并以接續時間范圍約束的形式直接嵌入模型中。國外鐵路在多年周期性列車運行圖運用實踐中已形成了較為固定的列車接續關系，該思路在國外研究中得到了廣泛采納[2-5]。而不固定接續關系條件下，在所有可能的接續列車及對應接續車站的基礎上確定備選列車接續集合，經運行圖驗證最終確定接續關系。由于周期性列車運行圖在我國尚未得到全面推廣，列車接續關系無法在列車運行圖編制前確定，因此基于不固定接續的運行圖編制思路更適合我國高鐵運營實際。文獻[12]提出了以換乘接續數量最少和接續服務覆蓋換乘客流量最多為優化目標的備選列車接續優化模型。文獻[13-14]考慮了無直達服務的大節點客流OD換乘需求，提出了基于備選列車接續的周期性列車運行圖編制體系。文獻[15]解決了周期性列車運行圖編制過程中，同類列車間接續關系靈活選擇的問題。基于固定和不固定接續關系兩種思路的周期性列車運行圖編制流程見圖1。

圖1 基于固定和不固定接續關系兩種思路的周期性列車運行圖編制流程

針對高鐵周期性列車運行圖編制與換乘接續綜合優化問題，本文基于文獻[13-14]對以下3個方面做出改進和完善。

(1) 僅考慮大節點間因無列車直達而產生的客流換乘服務需求，對于因列車直達服務不足而產生的旅客換乘需求有待進一步考慮。本文使用換乘服務頻率量化路網各客流OD間的換乘服務需求，引入客流OD換乘服務頻率約束和最小化換乘服務頻率欠缺值的目標函數，使模型不僅考慮了部分OD因無列車直達而產生的旅客換乘需求，同時兼顧為列車直達服務頻率不足的客流OD增加相應需求的快速換乘服務。

(2) 在備選列車接續中事先確定了接續列車和對應接續車站，可能造成最優解不在備選集中。本文拓展了不固定列車接續關系的研究思路，將接續列車及對應接續車站和接續時間3個要素全部在列車運行圖優化過程中動態確定，使接續關系的選擇更加靈活。

(3) 在選擇列車接續關系的同時缺乏接續時間優化，導致不必要的接續時間冗余。通過引入最小化換乘接續時間的優化目標和換乘接續選取與接續時間耦合關系約束，在規劃接續關系的基礎上進一步優化換乘接續時間。

1 問題描述

一個換乘接續關系包含接續列車、接續車站以及接續時間3個基本要素。接續列車和接續車站與列車開行方案密切相關，并且共同決定了該換乘接續可以服務的客流OD集合。接續時間由列車運行圖中前序列車到達與后續列車出發時間間隔確定，其上限不應超出旅客可容忍的換乘等待時間，其下限應滿足旅客換乘必要走行時間，單一換乘接續關系見圖2。

圖2 單一換乘接續關系

列車開行方案中符合一定條件的所有換乘接續關系構成了備選換乘接續關系集合，是本文模型的輸入條件，其構建包含換乘接續關系構造與篩選兩個基本過程。構造過程在遍歷全部列車組合方式的前提下，構建所有可行的換乘接續關系，一般考慮以下基本原則：(1)前后兩列車存在公共接續車站；(2)旅客可以通過接續車站在合理接續時間內完成換乘；(3)接續客流OD集合非空；(4)接續關系覆蓋的換乘客流OD集合對應的客流路徑繞行里程在可接受范圍內且無重復車站節點。篩選過程指根據決策者需要，在已構建的換乘接續關系中，篩選出有利于鐵路企業運營組織和方便旅客出行的換乘接續關系，一般建議考慮以下4點原則：(1)優先選擇前后列車特性與覆蓋換乘客流特性較匹配的換乘接續；(2)優先選擇接續車站旅客換乘能力較大、服務水平較高、列車接續作業組織條件較好的換乘接續；(3)優先選擇覆蓋換乘客流OD與潛在換乘客流量較大的換乘接續；(4)對運營實際中效果不佳的換乘接續予以刪除。

周期性列車運行圖換乘接續優化以向旅客提供便捷、快速的換乘服務為目標。一方面，換乘接續服務應盡可能滿足各客流OD間旅客的換乘出行需求，為旅客提供足夠數量的可選換乘方案。此方面可用換乘服務頻率衡量，即在規定換乘時間范圍內通過一次換乘到達目的地可供旅客選擇的列車組合數量。另一方面，應當盡量縮短旅客在換乘站的中轉換乘時間，優化旅客旅行時間。此方面可用換乘接續時間來衡量，即前序列車到達與后續列車出發的間隔時間。

周期性列車運行圖編制過程中換乘接續人工優化案例見圖3。

圖3 周期性列車運行圖換乘接續優化問題案例

已知周期長度60 min，換乘接續時間限制為15～20 min，列車3、4在車站C的出發時間分別為第13、0分，列車5的在車站D的出發時間為第36分，各列車在經由車站均辦理旅客乘降，客流OD：A-E、B-E、A-F存在換乘服務需求，頻率為1次。為滿足A-E、B-E換乘服務需求，接續1和接續2是應當納入選定接續，取最短接續時間15 min。為方便對比，按各列車區間運行和停站時間均取最小的條件推算列車1、2在車站C、D的到發時間，結果見圖3中標識。在此條件下，備選列車接續3、4、5可用于滿足換乘服務需求A-F：對于換乘接續3，可取最短接續時間15 min；對于換乘接續4，接續時間為16 min；對于換乘接續5，接續時間為20 min。除換乘接續3外，若需進一步優化列車接續4、5的接續時間，則需延長接續1、2的接續時間或額外附接續列車區間運行或停站時間。基于此，若車站接續能力和列車接續數量未達瓶頸不受限制，顯然接續3為最優方案；若假定車站C的單周期內列車接續數量上限為2次，接續4為較優方案；若假定列車2的接續次數限制為1次時，則僅可選擇接續5。

由此可見，周期性列車運行圖換乘接續優化問題是一個復雜的系統優化問題，人工優化難以應用于大規模案例。本文綜合考慮周期性列車運行圖編制約束和換乘接續相關約束，以盡量滿足換乘服務頻率需求、最小化列車總旅行時間和總換乘接續時間為優化目標，建立多目標混合整數規劃模型，完成周期性列車運行圖和接續方案的一體化編制。

2 優化模型

2.1 相關符號定義

路網及周期性列車開行方案層面基礎要素定義如下。S：路網全部車站集合；L：單周期內全部列車集合；Sl：列車l停站車站集合；Pl：列車l經由車站集合；Stransfer：路網中備選換乘接續車站集合；F：路網換乘客流OD集合；Z：備選列車接續集合。

對于周期性列車運行圖，采用事件—活動圖(Event-Activity Graph，簡稱EA圖[7])描述其要素，三列車組成的EA圖，見圖4。

圖4 事件—活動圖

定義事件—活動圖G=(E,A)。點集合E中的元素e∈E稱為事件，用以表達列車到達和出發時刻，E由列車出發點(事件)集合Edep和列車到達點(事件)集合Earr兩個子集構成。

弧集合A中的元素a∈A稱為活動，表示列車事件間的時間間隔約束關系，可以用一對列車事件表示，以換乘接續弧為例表示為

|i,j∈L,s∈Si∩Sj∩Stransferi,j,s∈Z}

本文考慮以下4類弧集合。Adriving：運行弧(活動)集合，表示列車在區間運行過程中從前序車站出發與到達后續車站的時間間隔約束；Astop：停站弧(活動)集合，表示列車在站停站過程中從列車到達車站與自該站出發的時間間隔約束，當列車不停站通過時，弧長取值為0；Asafety：安全弧(活動)集合，表示同方向經由同一區間的兩列車到達時間間隔與出發時間間隔約束；Aconnection：接續弧(活動)集合，表示接續前序列車到達與后續列車出發的時間間隔約束。

2.2 約束條件

(1) 弧約束

為保證列車安全高效運行，列車區間運行時間、停站時間、安全間隔時間應限制在規定時間范圍內；為保證旅客換乘的效率與安全，對于一個換乘接續，在換乘車站的前序列車到達時間和后續列車出發時間間隔應保證在一定范圍內。

la≤xa≤ua

?a∈Asafety∪Adriving∪Astop∪Aconnection

( 1 )

式中：la為弧a所代表的時間間隔取值下限；ua為弧a所代表的時間間隔取值上限。

(2) 圈基約束

圈基約束是保證列車運行圖滿足周期性質的約束。根據文獻[2]，周期性列車運行圖的EA圖中所有圈應當滿足圈周期性質，即該圈包含的順向弧取值之和與逆向弧取值之和的差值應當是周期的整數倍，同時證明整數變量qc的取值范圍應滿足式( 2 )。文獻[5]證明圖G(E，A)中存在元素個數為(|A|-|E|+1)的圈集合B，當該集合中的圈滿足圈周期性質時，則圖G中的全部圈均滿足圈周期性質，將圈集合B稱為整數圈基。文獻[13]將按圈基B內的圈是否是包含接續弧將其劃分為普通圈基Btrivial和接續圈基Bconnection，普通圈基內的圈由若干運行弧、停站弧和安全弧組成，接續圈基內的圈由唯一接續弧和若干運行弧、停站弧和安全弧組成。

按照上述原理，本文所建EA圖中普通圈基和被選定的接續弧對應的接續圈基應當滿足周期性質，即：對于普通圈基中的圈應滿足式( 3 )、接續圈基中的圈應滿足式( 4 )、式( 5 )。式( 4 )、式( 5 )引入了松弛變量δc，當接續弧a對應的換乘接續關系被選擇時ta=1，對應松弛變量δc=0，對應接續圈滿足圈周期性質約束；當接續弧a對應的換乘接續關系未被選擇時ta=0，對應松弛變量δc可任取，松弛對應圈約束。

c∈Btrivial∪Bconnection

( 2 )

( 3 )

( 4 )

-M(1-ta)≤δc≤M(1-ta)

c∈Bconnectiona∈Aconnection

( 5 )

式中：c+為圈c中的順向弧的集合；c-為圈c中的逆向弧的集合；Btrivial為普通圈基；Bconnection為接續圈基。

(3) 沖突消解約束

當兩列追蹤列車的區間運行時分之差大于到達、出發安全間隔時間之和時，將造成運行線在區間交會，故需引入沖突消解約束。將經由同一區間的同向列車對應的一對運行弧和一對安全弧組成的圈稱為沖突消解圈，見圖5，當其順向弧取值之和與逆向弧取值之和的差值為0時，列車運行線不會在區間交會[3]。

圖5 沖突消解圈

( 6 )

式中：Cnon-collision為EA圖中全部沖突消解圈的集合。

(4) 客流OD換乘服務頻率約束

限于周期性列車運行圖有限的停站組合和起訖點種類，列車直達服務難以滿足多樣化的旅客出行需求，因此應考慮為列車直達頻率不足的客流OD設計相應頻率的快速換乘服務，以提高旅客出行的效率與便捷性。但嚴格限制換乘服務頻率可能會導致問題無解，因此引入非負松弛變量yod，當換乘服務頻率達到設計值時，松弛變量yod取值為0；否則松弛變量取值為正整數，該約束被松弛。

( 7 )

現階段我國高速鐵路主要實行非周期化運營，客流輸送方式以直達為主。出于實用性考慮，同時保證我國高鐵改行周期性運行圖后各OD列車服務頻率的相對穩定，本文參考了我國現行高速鐵路列車運行圖，將各OD直達與換乘服務頻率需求總量按式( 8 )計算、換乘服務頻率需求設計值按式( 9 )計算，即

( 8 )

( 9 )

(5) 列車接續數量約束

為避免單列車接續數量過大造成嚴重的晚點傳播，對列車運行調整工作造成困難，故應限制單列車接續數量。

(10)

(6) 接續車站約束

為保證換乘接續車站可以靈活選擇，該模型將接續列車相同、接續車站不同的若干換乘接續歸為一組換乘接續。為保證規劃接續車站選擇的唯一性，每組接續關系應當滿足式(11)；同時受車站換乘設備和線路布局的影響，單周期內車站內的接續能力有限，故應限制周期內車站接續數量，避免車站接續能力不足、防止換乘接續過多集中于單一換乘車站，即式(12)。

(11)

(12)

(7) 接續對稱性約束

由于我國高鐵列車基本成對開行，同時換乘服務應滿足旅客出行的往返性，故列車接續關系應具有對稱性[14]。

ta=ta′a,a′∈Aconnection

(13)

式中：接續弧a′是接續弧a的對向接續弧。

(8) 接續選取和接續時間耦合約束

(14)

式中:M為較大常數。

2.3 目標函數

本文將列車總旅行時間最小z1、總換乘接續時間最小z2以及各OD的實際換乘服務頻率相對于換乘服務頻率需求總欠缺值最小z3為優化目標。最小化列車總旅行時間不僅可提高動車組運用效率，還可節省旅客旅行時間；最小化總換乘接續時間使旅客換乘時間在合理換乘接續時間范圍內盡量少，節省了旅客換乘等待時間；最小化換乘服務頻率欠缺值，使換乘接續服務盡量滿足各客流OD換乘服務頻率需求。

(15)

(16)

(17)

采用線性加權法將多目標規劃轉化為單目標規劃問題。

minZ=α1z1+α2z2+Mz3

(18)

式中:α1，α2，M分別為三項目標函數的權重系數，為優先保證換乘接續服務盡量滿足各客流OD換乘服務頻率需求，取M?α1,α2。

2.4 模型求解

以CPF模型為基礎，經線性加權法轉化為單目標混合整數規劃模型，通過Cplex、Gurobi等整數規劃求解器可以快速求解。此問題的一般求解流程是：在以備選列車接續和周期性列車開行方案構建的EA圖的基礎上，搜索整數圈基作為模型輸入的一部分，采用整數規劃求解器求解，通過生成樹算法推算各列車事件發生時刻。問題求解的關鍵在于分類整數圈基的構建，優質圈基將極大提高模型求解效率。本文參考文獻[14]采用CFCB算法搜索分類整數圈基。

3 案例驗證

本文以京滬高鐵及其部分銜接線路周期性列車運行圖編制作為研究案例，以優化生成的周期性列車開行方案為基礎，見圖6。周期為60 min。各線路區間最高運行速度為：京滬350 km/h，鄭徐、合蚌、津秦、寧杭高鐵300 km/h，其余線路取200 km/h。最低運行速度取最高運行速度的0.9倍。300、350 km/h線路起車附加時分2 min、停車附加時分3 min；200 km/h線路起停車附加時分均取2 min。車站最小到達、出發時間間隔：北京南站取5 min、上海虹橋取4 min、其余車站取3 min。列車停站時間取1～4 min。備選接續車站有：天津西、天津南、濟南西、徐州東、蚌埠南和南京南。各車站周期內最大接續數量為10次，單列車最大接續數量為2次，換乘接續時間為15～20 min。服務頻率高峰系數取為1.05。目標函數各項系數出于不同考慮有多種組合方式，本案例取值為α1=1,α2=1,M=200。

使用Visual Studio 2015結合C#語言編程調用CPELX 12.7.1，硬件環境為Intel Xeon E5-2620 2.4 GHZ 32 G內存。經過1 572.97 s求解時間，得到路網周期性列車運行圖及換乘接續方案。京滬高速鐵路下行方向周期性列車運行圖見圖7。

最終選定的列車換乘接續關系見表1，接續方案見圖8。

圖6 京滬高速鐵路及部分銜接線路周期性列車開行方案

序號接續站前序列車后續列車接續時間/min序號接續站前序列車后續列車接續時間/min1濟南西G7:北京南—上海虹橋G35:濟南西—青島北192濟南西G36:青島北—濟南西G8:上海虹橋—北京南163濟南西G6:上海虹橋—北京南G16:濟南西—沈陽北204濟南西G15:沈陽北—濟南西G5:北京南—上海虹橋175濟南西G15:沈陽北—濟南西G37:濟南西—青島北206濟南西G38:青島北—濟南西G16:濟南西—沈陽北157濟南西G20:鄭州東—濟南西G35:濟南西—青島北158濟南西G36:青島北—濟南西G19:濟南西—鄭州東159南京南G1:北京南—上海虹橋G25:南京南—上海虹橋1510南京南G26:上海虹橋—南京南G2:上海虹橋—北京南1511南京南G1:北京南—上海虹橋G49:南京南—杭州東1512南京南G50:杭州東—南京南G2:上海虹橋—北京南1513南京南G5:北京南—上海虹橋G47:南京南—杭州東1514南京南G48:杭州東—南京南G6:上海虹橋—北京南1515南京南G9:北京南—杭州東G27:南京南—上海虹橋1516南京南G28:上海虹橋—南京南G10:杭州東—北京南1517南京南G17:天津西—上海虹橋G45:南京南—杭州東1518南京南G46:杭州東—南京南G18:上海虹橋—天津西1519天津西G18:上海虹橋—天津西G31:天津西—沈陽北1520天津西G32:沈陽北—天津西G17:天津西—上海虹橋1521徐州東G10:杭州東—北京南G41:徐州東—鄭州東1522徐州東G42:鄭州東—徐州東G9:北京南—杭州東1523徐州東G21:青島北—徐州東G39:徐州東—鄭州東1524徐州東G40:鄭州東—徐州東G22:徐州東—青島北1525徐州東G4:上海虹橋—北京南G22:徐州東—青島北1626徐州東G21:青島北—徐州東G3:北京南—上海虹橋1727徐州東G4:上海虹橋—北京南G43:徐州東—鄭州東2028徐州東G44:鄭州東—徐州東G3:北京南—上海虹橋2029徐州東G8:上海虹橋—北京南G39:徐州東—鄭州東1930徐州東G40:鄭州東—徐州東G7:北京南—上海虹橋18

圖7 京滬高速鐵路下行方向周期性列車運行圖

客流OD列車服務頻率方面，周期性列車開行方案設計服務的856個京滬高鐵本跨線客流OD中，596個客流OD滿足服務頻率需求，260個客流OD服務頻率未達到設計需求值，需要補充換乘接續服務。換乘接續優化后，原滿足服務頻率需求的596個客流OD中，有372個客流OD服務頻率得到提高，旅客除可通過直達出行外，還可通過設計的快速換乘接續完成出行；未滿足服務頻率需求的260個OD中，有198個客流OD通過增加快速換乘接續服務滿足服務頻率需求，該部分旅客客流通過規劃的15～20 min的快速換乘服務完成出行；最終僅剩62個客流OD無法通過規劃換乘接續或列車直達完成出行。優化前后客流OD服務頻率變化情況見表2。

換乘接續時間方面，選定的30個換乘接續中，平均換乘接續時間16.2 min，較未考慮換乘接續時間優化的情形下，平均減少冗余接續時間3.8 min。

圖8 列車接續方案圖

優化前優化后服務頻率滿足需求的客流OD數量596服務頻率原已滿足需求、優化后提高的客流OD數量及占比服務頻率原已滿足需求、優化后不變的客流OD數量及占比372(62%)224(38%)服務頻率未滿足需求的客流OD數量260服務頻率原不滿足、優化后滿足需求的客流OD數量及占比仍未滿足服務頻率需求的客流OD數量及占比198(76%)62(22%)

4 結束語

本文建立了基于換乘接續優化的高鐵周期性列車運行圖多目標混合整數規劃模型，從換乘頻率、動態接續、換乘時間3個方面優化設計列車換乘接續關系，較為全面考慮了周期性列車運行圖編制和換乘接續關系設計相關約束和優化目標，解決了周期性列車運行圖與列車換乘接續方案的一體化編制問題，為周期性列車運行圖接續優化提供了系統的方法。案例涵蓋京滬高鐵及部分銜接線路，服務頻率需求參數參考了我國現行列車運行圖運營情況，提高了案例的實用性。求解結果表明：原直達服務頻率不足260個客流OD中，76%的客流OD可以在15～20 min的換乘時間范圍內通過規劃換乘接續滿足出行需求，驗證了模型的有效性。此外，針對車站接續能力、列車合理接續數量以及接續魯棒性等換乘接續設計的精細化問題有待進一步研究。