高速鐵路網絡延誤傳播分析

王 璞,譚淮銳,郭 寶,周 慧

(中南大學 交通運輸工程學院, 湖南 長沙 410075)

高速鐵路列車的運行狀態可能會受到多種因素(極端天氣、設備故障、運營管理不當等)的影響,進而發生列車延誤[1]。列車延誤不僅會打亂列車運行計劃,影響高速鐵路的運營管理;而且會使乘客的出行受到影響,降低乘客的乘車滿意度。對高速鐵路列車延誤進行分析研究,理解高速鐵路網絡中的延誤傳播機理,對于制定更為科學的列車運行計劃、提高運營管理水平具有十分重要的理論和實際意義。下面首先介紹列車延誤研究領域的相關研究工作。

根據列車延誤發生原因的不同,列車延誤可以分為初始延誤和連帶延誤[2]。列車發生初始延誤的主要因素包括天氣因素、人為因素和系統性因素[3]。列車發生初始延誤后,延誤傳播效應的存在會導致后續列車發生連帶延誤[4]。Meester等[5]建立了列車延誤傳播模型,并從列車初始延誤的概率分布推導出連帶延誤的概率分布。胡思繼等[6]研究了區段內列車延誤傳播過程和傳播規律,定義了相關延誤指標并推導出理論計算公式。莊河等[7]運用廣鐵集團管轄的6條高速鐵路實績數據建立了不同致因情況下初始延誤時長分布模型。Wang等[8]識別了列車延誤關鍵車站,并提出時間間隔閾值用于構建列車延誤傳播鏈,識別列車延誤傳播是否發生。柏赟等[9]考慮了不同運行線路的列車在運行線的交叉區域存在運行干擾的情況,并提出最優接近速度策略使受到延誤傳播影響的列車迅速通過運行干擾區域,盡快恢復正常運行。曾壹等[10]使用區間鎖閉時間模型對列車延誤區間增加和傳播的范圍進行預測,并提出列車節能-延誤恢復模型,不僅可以降低列車牽引能耗,還能緩解列車的延誤傳播。

上述研究針對列車間的延誤傳播,其延誤本因是鐵路線路的連通性以及列車共用鐵路線路的運行機制[1],所以列車間的延誤傳播會導致站點間的延誤傳播。為研究站點間的延誤傳播關系,Lessan等[11]運用武廣高鐵實績運行數據構建了三種貝葉斯網絡,發現基于數據驅動和領域專家知識的混合方法構建的貝葉斯網絡在預測延誤時間方面有更高的精度。Corman等[12]對瑞典鐵路一段交通走廊線路中的站點延誤傳播關系進行了研究,并運用領域專家知識構建了貝葉斯網絡。但這些研究都只關注單條鐵路線路,而不是鐵路網絡。相較于某條鐵路單線,鐵路網絡具有更復雜的拓撲結構,所以僅使用領域專家知識難以判別大型鐵路網絡中站點間的延誤傳播關系。因此,本文采用數據驅動方法構建高速鐵路站點延誤傳播貝葉斯網絡,并運用復雜網絡中的滲流理論尋找并分析處于滲流突變狀態下的延誤傳播團簇,以探究高速鐵路網絡中的延誤傳播機理。

1 站點延誤傳播貝葉斯網絡模型

1.1 貝葉斯網絡理論

貝葉斯網絡是一種對因果關系進行推理的概率圖模型[13],其中每個節點代表的隨機變量可用于表達任何問題的抽象形式,由父節點指向子節點的有向邊代表節點之間的相互依賴關系。若貝葉斯網絡中存在n個節點(1,2,…,n),每個節點對應的隨機變量為X1,X2,…,Xn,則其聯合概率分布為

(1)

式中,p(Xj)代表Xj的父節點集合。

1.2 貝葉斯網絡結構學習

在研究鐵路單線中站點間的延誤傳播關系時,學者大多結合領域專家知識建立貝葉斯網絡[11]。但是在研究大型高速鐵路網絡中站點間的延誤傳播關系時,復雜的網絡拓撲結構使上述方法難以判別站點間的延誤傳播關系。本文通過采用NO TEARS貝葉斯網絡結構學習算法將有向無環圖的結構學習問題表示為一個純連續優化問題,相較于傳統啟發式算法更加精準,可以學習到全局最優的貝葉斯網絡[14]。貝葉斯網絡的結構優化問題在數學上表示為以下形式:

s.t.h(W)=0

(2)

式中,W是給定數據集,F(W)是與數據有關的損失函數,h(W)是一個平滑函數。

對于此非凸優化問題,可以將上式中的無環約束表示為

h(W)=tr(W°W)-d=0

(3)

式中,tr()表示求矩陣的跡,“° ”表示Hadamard積。h(W)的梯度值為

?h(W)=(eW°W)T° 2W

(4)

得到最終需要進行優化的數學表達式:

s.t.h(W)=0

(5)

式中:ρ是大于0的一個二次懲罰項,以表示懲罰違反約束h(W)=0。至此可以采用NO TEARS算法對問題進行求解,具體步驟如算法1所示。

算法1 NO TEARS算法

1.3 數據處理

通過分析2018年1月20日至3月20日的高速列車實績運行數據和列車時刻表數據,得到高速列車延誤信息,這些信息包括列車車次、日期、到達站點、圖定到站時間、實際到站時間、延誤時長(見表1)?？紤]到海南省和臺灣省高鐵站點暫時未與其他省份高速鐵路網絡相連接,所以本文只將上述兩者以外省份的高速鐵路網絡作為研究范圍(共543個站點,481 523條列車延誤信息)。

1.4 模型構建

將高速列車主要運行時段6:00—24:00分割為18個1 h的時間窗,研究時段內共有1 080個時間窗。通過式(6)計算各站點在各時間窗內所有延誤列車的平均延誤時長,最后將其整理為NO TEARS貝葉斯網絡結構學習算法輸入所需的數據矩陣形式,即1 080行、543列的站點平均延誤時長矩陣T。

(6)

根據1.2節推導過程,建立高速鐵路網絡站點延誤傳播貝葉斯網絡模型的目標函數和約束條件:

s.t.h(W)=0

(7)

進一步使用Python 3.8 集成環境Anaconda,同時應用NO TEARS貝葉斯網絡結構學習算法對應的causalnex貝葉斯網絡庫建立高速鐵路網絡站點延誤傳播貝葉斯網絡,并分別采用causalnex貝葉斯網絡庫、pympy貝葉斯網絡庫和Networkx復雜網絡庫中有向無環圖檢驗模塊對所建立的網絡結構進行檢驗,結果顯示所建立的貝葉斯網絡均通過算法的有向無環圖檢驗。模型結構示意如圖1所示。

圖1 站點延誤傳播貝葉斯網絡示意圖Fig.1 Schematic diagram of delay propagation Bayesian network

2 基于滲流理論的延誤傳播規律分析

在復雜網絡中,滲流理論[15]描述了網絡中節點或邊被移除時,網絡結構發生變化的過程。當網絡中某一參數發生變化,網絡會出現巨大團簇分裂成若干個小團簇的現象;參數變化到某一臨界閾值(滲流閾值)時,網絡性質會突然發生改變,這種突變稱為滲流突變。

2.1 延誤傳播團簇演變分析

站點延誤傳播貝葉斯網絡模型中邊和邊的權重由NO TEARS算法獲取,模型中的邊表示兩個站點之間的延誤傳播關系,邊權重wij越大表示父節點站點i對子節點站點j造成的延誤傳播影響越強?；跐B流理論和已構建的站點延誤傳播貝葉斯網絡,本文設置不同的權重閾值q觀察站點延誤傳播貝葉斯網絡的演變情況[16]。對于給定的權重閾值q,站點延誤傳播貝葉斯網絡中各條邊根據權重wij被劃分為有效邊(eij=1)和無效邊(eij=0),如式(8)所示。網絡中的站點通過有效邊相互連接形成團簇,同一團簇中的站點存在有效邊互相連接,不同團簇中的站點之間沒有邊相連。所以在給定權重閾值q下,根據不同團簇之間是否存在有效邊連接,網絡被劃分為多個不同大小的延誤傳播團簇。

(8)

隨著權重閾值q的變化,網絡發生滲流突變過程。為了展示網絡的滲流突變過程,圖2展示了在不同權重閾值下網絡中延誤傳播團簇的地理位置分布情況(分別選取小于、等于和大于滲流臨界權重閾值的權重q=0.2、q=0.35、q=0.6)。結合圖3中不同權重閾值下的延誤傳播團簇規?？梢钥闯?隨著權重閾值q逐漸增大,站點延誤傳播貝葉斯網絡中最大延誤傳播團簇不斷變小,而第二大延誤傳播團簇規模呈現震蕩變大的趨勢;當權重閾值q增加到滲流臨界權重閾值qc時,第二大延誤傳播團簇的規模達到峰值,而最大延誤傳播團簇突然瓦解,此時站點延誤傳播貝葉斯網絡處于滲流突變狀態[15];當權重閾值q大于滲流臨界權重閾值qc時,整體網絡繼續瓦解,直至網絡全部解體。

(a) q=0.2

(b) q=0.35

(c) q=0.6圖2 不同權重閾值q下延誤傳播團簇的地理位置Fig.2 Delay propagation clusters′ locations under different weight threshold q values

圖3 不同權重閾值q下延誤傳播團簇規模Fig.3 Size of delay propagation clusters under different weight threshold q values

2.2 滲流突變狀態下的網絡分析

在滲流理論中,網絡突變十分關鍵。Wu等[16]通過分析權重閾值等于滲流閾值的網絡結構,發現核心團簇可以以較少的邊展現原網絡的骨架結構,體現出原網絡的核心特征。在其他多數研究中[17-20]也將網絡的權重閾值設置為滲流閾值,進而對網絡中的核心團簇進行分析,從復雜的網絡結構中尋找到重要的邊。本節為尋找到網絡中重要的延誤傳播關系,揭示網絡中延誤傳播的核心特征,進一步分析圖2(b)中滲流突變狀態下站點延誤傳播貝葉斯網絡形成的核心延誤傳播團簇(qc=0.35)。

站點延誤傳播貝葉斯網絡模型以有向邊連接具有延誤傳播關系的兩個站點,因此,在延誤傳播團簇中,根據站點的出度和入度,可將站點劃分為3類:

南京南站在最大延誤傳播團簇內被劃分為延誤發散站點。圖4展示了南京南站產生的延誤傳播鏈,從圖中可以看出南京南站可以首先將延誤傳播至附近的合肥南站、蚌埠南站等站點,而合肥南站、蚌埠南站可以進一步將延誤分別傳播至六安站、徐州東站等站點;在延誤傳播的過程中,湖州站、徐州東站、濟南西站等延誤發散站點具有多條延誤傳播鏈,進而可以在多方向將延誤傳播至浙江、河北等與南京南站相距較遠地區的站點。這種延誤傳播模式使大部分延誤發散站點成為延誤傳播中心(如圖4中南京南站、濟南西站、徐州東站等站點),將延誤“輻射式”傳播至其他站點。

圖4 南京南站產生的延誤傳播鏈Fig.4 Delay propagation chain generated by Nanjingnan Railway Station

圖5 長沙南站產生的延誤傳播鏈Fig.5 Delay propagation chain generated by Changshanan Railway Station

其他延誤傳播團簇具有相似的延誤傳播規律。以第二大延誤傳播團簇為例,圖5展現了湖南地區的站點延誤傳播規律,可以看出湖南地區延誤傳播以長沙南站和衡陽東站這類延誤發散站點為延誤傳播中心,將延誤以延誤傳播鏈的形式“輻射式”傳播至其他站點。其中長沙南站向北可以將延誤經岳陽東站繼續傳播至湖北地區,向南可以傳播至衡陽東站;而衡陽東站也具有多條延誤傳播鏈,可以將延誤傳播至祁東站、郴州西站等站點,進而傳播至永州和廣東地區,向網絡繼續擴散延誤。

為從定量的角度分析網絡中的延誤傳播規律,本文進一步分析了受到延誤發散站點延誤傳播影響的站點數量變化情況。在延誤傳播的過程中,如果站點j受到站點i延誤傳播影響,那么存在一條從站點i至站點j的傳播路徑滿足以下要求:延誤由站點i開始,隨著時間窗的推移,其路徑上的站點沿傳播路徑方向依次發生延誤。

圖6展示了2018年3月15日網絡中受到長沙南站延誤傳播影響的站點數量變化情況。從圖中可以看出:在15:00—18:00時間段,延誤處于初始傳播階段,此時新增的延誤站點數量不斷增加,延誤站點減少數量一直為0,致使此時段內每一時間窗的延誤站點數量和累計延誤站點總數急劇升高。在18:00—21:00時間段,新增的延誤站點數量和延誤站點減少數量接近平衡,所以各時間窗的延誤站點數量基本維持不變;但由于新增的站點數仍然保持在較高值,所以累計延誤站點總數仍然急劇升高。在21:00—23:00時間段,由于大部分延誤的高速列車在晚間結束全天的運行,延誤在網絡中擴散被阻礙,所以新增的延誤站點數量逐步減少而延誤站點總數繼續增長,大部分站點從延誤狀態逐步恢復為正常狀態。

(a) 延誤站點數量變化(a) The number of delayed stations

(b) 延誤站點增減數量變化(b) Changes of the number of delayed stations 圖6 受延誤傳播影響的站點數量Fig.6 The number of stations affected by delay propagation

3 站點延誤狀態預測

3.1 預測模型建立

基于滲流突變狀態下站點延誤傳播貝葉斯網絡中的核心延誤傳播團簇,對高速鐵路站點延誤狀態進行預測。為預測下一時間窗目標站點的延誤狀態,在站點延誤狀態預測模型中不僅考慮了目標站點的父節點站點延誤狀態,而且加入了兩站點間的列車運行信息,以捕捉延誤隨列車運行傳播到站點的動態變化情況。用于預測站點延誤狀態的貝葉斯網絡模型結構如圖7所示(在本圖的案例中,待預測站點有兩個父節點),其中模型變量集確定如下:

Y={S1j,…,Snj,SAj+1,Z1j+1,…,Znj+1}

式中,SAj+1為待預測站點A在j+1時間窗的延誤狀態,Snj為站點A的第n個父節點站點在j時間窗的延誤狀態。中國鐵路總公司將小于等于4 min的列車到站晚點視為可被車站運營組織管理所吸收的晚點,不會對列車和車站造成大的影響[22]。因此根據式(9)將站點的延誤狀態劃分為延誤狀態Sij=1和非延誤狀態Sij=0。

(9)

式中,Sij為i站點在j時間窗的延誤狀態,Tij為i站點在j時間窗的列車平均延誤時長。

Znj+1表示在j+1時間窗內,站點A的第n個父節點站點與站點A之間是否有列車運行。因為兩站點間并不是在所有時段內都會有高速列車運行,所以在預測站點延誤狀態時加入兩站點間的列車運行信息Znj+1,以捕捉列車的運行動態變化情況。Znj+1根據列車時刻表數據和j時間窗的列車運行信息得到,取值為{1,0},其中1表示兩站點間有高速列車運行,0表示無高速列車運行。

3.2 預測結果分析

將60天數據集劃分為模型的訓練集和測試集,以數據集前70%時段即2018年1月20日至2018年3月2日的數據作為模型的訓練集,以數據集后30%時段即2018年3月3日至2018年3月20日的數據作為模型的測試集。預測準確率R(計算見式(10))為89.56%,表明基于核心延誤傳播團簇的預測模型很好地捕捉了網絡中核心的延誤傳播關系。

(10)

式中,N為預測樣本數,ytrue為正確預測站點是否處于延誤狀態的樣本數。

(a) 14:00預測結果(a) Prediction result at 14:00

(b) 15:00預測結果(b) Prediction result at 15:00

(c) 16:00預測結果(c) Prediction result at 16:00

(d) 17:00預測結果(d) Prediction result at 17:00圖8 湖南地區預測結果示例Fig.8 Example prediction result in Hunan province

為進一步說明模型的預測結果和網絡中的延誤傳播規律,選取2018年3月15日的實際案例,對延誤在網絡中大范圍傳播的動態過程進行分析。圖8展示了延誤首先發生在長沙南站逐步傳播至湖南地區的動態變化情況和模型的預測結果。從圖中可以看出,14:00湖南地區長沙南站首先處于延誤狀態,附近的其他站點此時都處于非延誤狀態;隨著時間的推移,15:00長沙南站的延誤已經傳播到了岳陽東站、衡陽東站,進而形成多條延誤傳播鏈,在后續時段內將延誤傳播至郴州西站、衡山西站等更多站點;直到17:00,湖南地區大部分站點都處于延誤狀態。預測模型雖然未能捕捉到14:00長沙南站產生的突發性延誤,但能夠精準地預測延誤的動態傳播趨勢,對于網絡中站點延誤預警有著重要意義。

4 結論

本文建立了高速鐵路網絡的站點延誤傳播貝葉斯網絡模型,并結合滲流理論對高速鐵路網絡延誤傳播規律進行研究,主要得到以下結論:隨著權重閾值q增大,站點延誤傳播貝葉斯網絡中最大延誤傳播團簇不斷減小,而第二大延誤傳播團簇在滲流臨界權重閾值qc時達到最大;從延誤傳播的角度將站點劃分成延誤發散站點、延誤傳遞站點和延誤消散站點,其中延誤發散站點產生的延誤傳播鏈使網絡以部分延誤發散站點為延誤中心向延誤傳遞站點和延誤消散站點進行“輻射式”延誤傳播。在預測站點延誤狀態方面,由于延誤傳播團簇很好地捕捉了網絡中核心的延誤傳播關系,能夠用于站點延誤狀態預警。

研究結果可以幫助管理者從全局性視角理解延誤在網絡中的傳播機理,進而制定更高效的高速鐵路行車組織管理方案,以防止延誤從局部網絡向全網擴散。未來可在現有基礎上融合多源數據更深層次地分析站點發生延誤的原因,并結合專家領域知識提升模型預測精度。