軌道交通封站條件下應急疏散車輛路徑優化

摘要：針對軌道交通封站條件下站外滯留乘客需要應急疏散的現實需求，設計了一種疏散服務模式，在保證滯留旅客有效疏散的前提下，允許線路沿途旅客搭乘以提高車輛的利用效率。以車輛運營成本和乘客時間成本之和最小為優化目標，建立應急疏散車輛路徑優化模型，根據問題特點改進自適應大鄰域搜索算法進行模型求解。最后，結合北京市城市交通數據，對應急疏散車輛進行路線設計并進行靈敏度分析，用算例驗證了模型與算法的有效性。結果表明，相較于最短路徑疏散方案，模型的優化結果節省了15.02%的乘客乘車時間，能夠在保證乘客出行體驗的前提下實現對站點滯留乘客的快速疏散，提升封站事件下軌道交通應急管理的精細化水平。

關鍵詞：城市軌道交通；應急疏散；車輛路徑問題；軌道交通封站；自適應大鄰域搜索算法

中圖分類號：U491.12 文獻標志碼：A 文章編號：1002-4026（2023）04-0080-09

開放科學（資源服務）標志碼（OSID）：

Route optimization for emergency evacuation vehicles in case of rail station closure

ZHANG Yiguo， QU Yunchao^*， YIN Haodong， WU Jianjun

（State Key Laboratory of Rail Traffic Control and Safety， Beijing Jiaotong University， Beijing 100044， China）

Abstract∶To address the problem of emergency evacuation of stranded passengers outside a rail station in case of its closure， this paper designs an evacuation route map， which allows passengers along the line to avail the emergency evacuation vehicles and facilitates the overall evacuation process. To minimize the total cost of vehicle operation and passenger time， this work proposes a route optimization model for emergency evacuation vehicles and improves the adaptive large neighborhood search algorithm to implement the model based on the characteristics of the problem. Finally， based on the urban traffic data of Beijing， we designed routes for emergency evacuation vehicles， analyzed their sensitivity， and verified the model and algorithm with specific examples. The results show that compared with the shortest route algorithm， the optimization results of the proposed model can reduce passengers′ travelling time by 15.02%， allowing them to evacuate rapidly while ensuring their experience and improving emergency management systems in case of rail station closure.

Key words∶urban rail transit；emergency evacuation；vehicle routing problem; rail station closure; adaptive large neighborhood search algorithm

城市軌道交通以其安全、節能、運量大、速度快等優點，逐步發展為我國城市居民出行的主要方式之一。封站作為城市軌道交通應急管理措施，分為偶發事件導致的臨時封站和提前通知的計劃封站兩種類型。當車站封站時，相關線路列車將跳站運營，原計劃從該站點出行的乘客無法進站，大量滯留在站外的乘客會持續影響城市地面交通。此時，選擇地面公交作為應急疏散車輛可以在一定程度上恢復滯留乘客的行程，避免乘客集聚造成的交通秩序混亂。

既有的公交接駁路徑優化研究集中在給定客流需求下設計線路結構和運營頻率^［1］兩個方面。從OD需求的角度，接駁路徑優化可分為多對一、多對多兩種場景。多對一的需求考慮將乘客從多個起點運送至同一終點^［2］，多對多的需求考慮將乘客從多個起點運送至多個終點^［3-5］。從應用場景的角度，又可分為常規條件和軌道交通中斷條件下的路徑設計。其中，Yin等^［6］建立了三層離散選擇行為模型，分析車站中斷情況下的動態客流需求。Liang等^［7］考慮公交車行程時間的不確定性，采用一種基于路徑的多商品流公式用于軌道交通中斷下公交車接駁服務設計。Jin等^［8］將公交線路的生成以及車輛調車問題分成兩個階段進行求解，建立了軌道交通故障情況下接駁公交網絡優化的數學規劃模型。魏超等^［9］從公交線路布局以及開行頻率的角度對接駁公交路線進行優化。針對疏散需求超過單輛公交運能的特點，何勝學^［10］引入了虛擬路段和節點的時空網絡以處理車輛的載客上限。胡華等^［11］采用車輛循環調度的方法設計公交橋接疏運服務。陳治亞等^［12］提出“虛擬疏運目的地”的新概念，允許公交車輛跨線運行，建立疏散調度模型。

目前軌道交通中斷條件下的接駁路徑優化研究主要關注區間中斷情況，即根據城市軌道交通線路結構，開行接駁車輛將受影響線路區間與臨近折返站進行銜接，從發車頻率和車輛調度的角度進行優化。這種服務模式可能導致乘客出行的換乘次數增多、候車時間增長。

為了減少乘客換乘次數，提供快速疏散服務，本文建立車輛運營成本和乘客時間成本之和最小的應急疏散車輛路徑優化模型，將待疏散乘客總乘車時間最小作為優化目標，增加停靠次數約束，避免多數乘客隨疏散車輛繞行。對于出行人數超過單輛車運力的車站，采用虛擬節點的方法拆分需求。最后結合北京市城市交通數據，以軌道交通朝陽門站封站為例進行應急疏散路徑設計。結果表明，模型可以實現封站條件下滯留乘客的快速疏散，降低乘客的總乘車時間。

1 模型建立

封站發生時，出行乘客無法從該站點進入軌道交通系統，以該站點為目的地的乘客由于列車跳站運營無法出站。基于此，本文考慮開行應急疏散車輛以滿足上述兩類乘客的出行需求。

本文建立的應急疏散車輛路徑優化模型中，疏散車輛從封站車站出發，將滯留乘客疏散至周邊正常運營的換乘站，疏散乘客可由換乘站重新進入軌道交通系統前往出行目的地。同時，沿途站點有出行需求的乘客可搭乘車輛返回封站站點。

1.1 模型假設

本文研究的應急疏散路徑優化問題基于以下假設：

（1） 選擇封站站點周圍正常運營的換乘站作為疏散目的地，便于滯留乘客后續通過軌道交通網絡前往目的地；

（2） 車輛只服務于封站站點與上述正常運營站點間的出行，乘客的出行需求已知；

（3） 允許上下車人數超過單輛車運力的站點接受多輛車的服務；

（4） 用于疏散服務的車輛規格相同，有相同的最大載客數和行駛速度；

（5） 任意兩個軌道交通站點之間距離已知，為站點間城市道路的最短路距離。

1.2 參數及變量意義

軌道交通站點集合記作N₀，由正常運營站點集合N={1，2，…，n}和運營中斷站點（即起點站，記為0）組成。備選車輛集合K={1，2，…，k}。應急疏散路徑優化問題中涉及的參數和決策變量如表1、表2所示。

1.3 應急疏散車輛路徑優化模型

模型的目標函數由乘客時間成本Z₁和車輛運營成本Z₂兩部分組成：

min Z=Z₁+Z₂，（1）

其中，乘客乘車時間包括站點停靠時間和站間行駛時間兩部分。根據疏散問題特點，模型只考慮最小化離站乘客的乘車時間Z₁：

車輛運營成本Z₂包括固定成本和可變成本兩部分，其中固定成本與開行的疏散車輛數成正比，可變成本與車輛運行總距離成正比：

針對部分站點客流需求可能超過單輛車運能的問題，采用站點拆分^［12］的方法對交通出行量大的站點事先劃分需求，同一車站拆分出的虛擬站點有相同的位置坐標。約束（4）保證分割后各站點有且僅有一條路徑與之連接：

約束（5）保證若站點j被某輛車服務，站點j前后必有與之相鄰的站點由此路徑連接：

約束（6）表示一輛車最多調用一次，約束（7）限制疏散車輛的停靠次數，約束（8）表示停靠次數相關的決策變量間關系：

約束（9）限制乘客乘車時間在可接受范圍內，避免車輛過度繞行：

約束（10）表示疏散過程中車內人數不超過車輛最大載客數：

約束（11）和（12）表示每個站點的上下車人數關系：

約束（13）保證車輛出發時車上僅有待疏散乘客，約束（14）保證車輛返回時疏散乘客已全部下車：

約束（15）和（16）保證所有站點的上下車總人數守恒，約束（17）定義了所有的決策變量：

2 模型求解

2.1 自適應大鄰域搜索算法流程

本文研究的軌道交通封站背景下應急疏散路徑優化問題為同時上下車車輛路徑問題（vehicle routing problem with simultaneous pickup and delivery，VRPSPD）的變種，屬于NP難問題。自適應大鄰域搜索（adaptive large neighborhood search，ALNS）算法^［13］可對大規模實例快速求解。根據問題特點，本文對算法迭代過程中新解劃分路徑的方式進行改進，算法具體流程見圖1。

2.2 初始解生成

按照貪婪算法的思想，在滿足車輛載客約束的條件下初始化車輛服務路徑。例如問題中包含10個軌道交通站點，編號0代表封站站點，編號1～9代表正常運營的軌道交通站點。假設按照初始解生成規則可產生一個可行解為［1，5，4，8］［9，3，2］［7，6］。

2.3 Destroy和Repair方法

本文使用隨機移除、最差移除兩種移除算子。其中，最差移除指從當前解中移除引起目標函數值增幅最大的站點。

本文使用隨機插入、貪婪插入、后悔插入等3種修復算子。其中，后悔插入指優先選擇后悔值最大的站點將其插回。后悔值定義如下：記每一次插入過程中站點i插入當前解S第k優位置所帶來的成本變化值為Δf_i，k，即當k≤k′時，滿足Δf_i，k≤Δf_i，k′。r=Δf_i，2－Δf_i，1表示將站點i插回當前解S最優位置和次優位置之間的后悔值。

2.4 新解生成

考慮到疏散問題特點，算法對迭代過程中劃分路徑的方式進行改進。區別于初始解路徑劃分時的貪婪插入策略，對迭代產生的新序列進行路徑劃分時，即使車輛未達到容量約束也會以一定概率結束裝載，調用下一輛車。這樣可以增大解空間的搜索范圍，保證不同疏散路徑上乘客數量的均衡分布。

2.5 權重更新

根據迭代過程中產生新解的效果對算子進行打分。如果新解是目前為止搜索到的最優解，算子得分為r₁；如果新解不是最優解但優于當前解，算子得分為r₂；如果新解不優于當前解但被接受，算子得分為r₃，有r₁gt;r₂gt;r₃。新解產生后，根據公式（18）對各destroy和repair算子的權重w（h）進行更新，w（h）為下一次輪盤賭選擇中算子的權重。

其中，w（h）為算子權重，ρ為衰減系數，s（h）為算子總得分，u（h）為算子選擇次數。

2.6 接受準則和終止準則

搜索過程中，按照Metropolis準則^［14］接受新解：如果產生的新解x′優于當前解x則接受新解。如果新解劣于當前解，則以一定概率p接受，p的計算如公式（19）所示。算法的終止準則是達到最大迭代次數。

3 案例分析

3.1 案例背景

依托北京市城市道路數據和軌道交通數據，以朝陽門站臨時封站為例，選擇周圍正常運營的換乘站作為疏散目的地，進行應急疏散路徑設計。如圖2所示，換乘站前往封站站點的人數為該站上車人數，從封站站點疏散至周邊換乘站的人數為該站下車人數。站點的經緯度、站間距離通過百度地圖API（application programming interface）獲取，站點間行駛的時間矩陣由車輛行駛速度和站間距離矩陣計算得出。案例中，燈市口站和東單站下車人數超過車輛最大載客數，采用虛擬節點的方法對需求進行等分處理。

模型參數取值如下，疏散車輛固定成本200元/車，可變成本5元/km，最大載客量80人/車，平均運營速度為20 km/h，單條路徑最大停靠次數5次，乘客時間成本系數0.3元/（人·h）^［15］，站點停靠時間0.05 h，乘客接受的最長乘車時間為1 h。

本文參考利用ALNS算法求解VRP問題的研究結果^［16］，對算法的參數進行設置，參數取值見表3。

3.2 優化結果

本文使用Python3.7在Anaconda環境下編寫算法，在 i5-7200uCPU 2.5 GHz，內存8 GB的PC平臺下運行。單次求解過程共計進行400次迭代，算法運行結果如圖3所示，解對應的路線開行方案見表4。

6條疏散路徑分別為：路徑1，朝陽門—北新橋—安定門—鼓樓大街—北海北—南鑼鼓巷—朝陽門；路徑2，朝陽門—燈市口—東四十條—東直門—亮馬橋—朝陽門；路徑3，朝陽門—東單—建國門—磁器口—朝陽門；路徑4，朝陽門—東單—廣渠門外—勁松—潘家園—朝陽門；路徑5，朝陽門—燈市口—前門—天橋—珠市口—朝陽門；路徑6，朝陽門—國貿—金臺夕照—金臺路—呼家樓—工人體育場—朝陽門。

生成的6條疏散路徑中，單條路徑最長行駛時間0.95 h，最短行駛時間0.63 h，所有待疏散乘客總乘車時間為99.02 h，相比于只考慮車輛運營成本方案的116.5 h，節省了15.02%的乘客乘車時間。

3.3 對比分析

為了進一步驗證本文ALNS算法的有效性，采用文獻［17］中的實例進行對比試驗。

文獻［17］中實例的問題規模在50～199個節點，每個問題都包括CMT-X型和CMT-Y型兩組數據。對于每一個節點i，x_i和y_i表示節點的橫縱坐標，節點間距離為節點x_i和節點y_i間的歐氏距離。其中X系列問題按以下方法構造：定義比例值r_i=minx_i/y_i，y_i/x_i，上車人數為r_in_i，下車人數為1－r_in_i，其中n_i為原始CVRP問題中節點i的需求值。交換產生的上車和下車人數即生成Y系列問題。

表5中列出了10個算例的已知最優解和用ALNS求解所獲得的最優解，從中可以看出，ALNS的計算結果中有8個算例的最優解優于文獻［17］中的已知最優解，且求解的時間平均縮短18.29%，證明了本文改進的ALNS算法的求解速度與精度。

3.4 靈敏度分析

本文選取車輛最大載客量進行靈敏度分析，研究模型參數變化對路徑優化結果的影響。根據表6中的結果，隨著最大載客量的增加，需求的疏散車輛數減少，總行駛距離減少，單輛車服務的站點數增多，乘客總乘車時間顯著增加。例如最大載客量從60增至100，車輛數減少了3輛，乘客總乘車時間增加了32.51 h。由于最大停靠次數的約束，單輛車服務的站點數有限，選用載客量過大的會降低車輛滿載率，造成運力浪費。

4 結論

（1）本文針對軌道交通封站背景下應急疏散的現實問題，建立疏散公交路徑優化模型，以軌道交通朝陽門站臨時封站為例進行實例分析，設計6條應急疏散線路，優化結果縮減乘客15.02%的乘車時間。

（2）本文建立的軌道交通封站應急疏散路徑優化模型僅適用于單站點封站且疏散需求固定的情況。事實上，封站事件會對乘客出行行為產生影響，因此乘客疏散需求往往具有動態不確定性。如何刻畫封站對乘客行為的影響，考慮不確定需求下應急疏散路線優化是下一步研究的方向。

參考文獻：

［1］GUIHAIRE V， HAO J K. Transit network design and scheduling： A global review［J］. Transportation Research Part A： Policy and Practice， 2008， 42（10）： 1251-1273. DOI： 10.1016/j.tra.2008.03.011.

［2］KUAH G K， PERL J. The feeder-bus network-design problem［J］. Journal of the Operational Research Society， 1989， 40（8）： 751-767. DOI： 10.1057/jors.1989.127.

［3］KUAN S N， ONG H L， NG K M. Applying metaheuristics to feeder bus network design problem［J］. Asia-Pacific Journal of Operational Research， 2004， 21（4）： 543-560. DOI： 10.1142/s0217595904000382.

［4］XIONG J， HE Z B， GUAN W， et al. Optimal timetable development for community shuttle network with metro stations［J］. Transportation Research Part C： Emerging Technologies， 2015， 60： 540-565. DOI： 10.1016/j.trc.2015.10.007.

［5］柳伍生， 潘自翔， 魏雋君， 等. 地鐵站點運營中斷下周邊乘客的出行行為研究［J］. 鐵道科學與工程學報， 2020， 17（11）： 2953-2961.DOI： 10.19713/j.cnki.43-1423/u.T20200035.

［6］YIN H D， WU J J， SUN H J， et al. Optimal bus-bridging service under a metro station disruption［J］. Journal of Advanced Transportation， 2018， 2018：1-16. DOI： 10.1155/2018/2758652.

［7］LIANG J P， WU J J， QU Y C， et al. Robust bus bridging service design under rail transit system disruptions［J］. Transportation Research Part E： Logistics and Transportation Review， 2019， 132： 97-116. DOI： 10.1016/j.tre.2019.10.008.

［8］JIN J G， TEO K M， ODONI A R. Optimizing bus bridging services in response to disruptions of urban transit rail networks［J］. Transportation Science， 2016， 50（3）： 790-804. DOI： 10.1287/trsc.2014.0577.

［9］魏超， 龍建成. 城市軌道交通接駁公交線路優化設計［J］. 山東科學， 2015， 28（3）：65-73. DOI： 10.3976/j.issn.1002-4026.2015.03.013.

［10］何勝學. 無預警緊急疏散中公交車輛路徑的確定方法［J］. 運籌學學報， 2014， 18（3）： 47-59. DOI： 10.15960/j.cnki.issn.1007-6093.2014.03.016.

［11］胡華， 高云峰， 劉志鋼， 等. 地鐵運營中斷下公交橋接疏運車輛應急調度模型及算法［J］. 鐵道學報， 2018， 40（5）：31-37. DOI： 10.3969/j.issn.1001-8360.2018.05.005.

［12］陳治亞， 譚斐， 馮芬玲. 地鐵突發運營中斷下應急公交調度研究［J］. 鐵道科學與工程學報， 2019， 16（9）： 2360-2367. DOI： 10.19713/j.cnki.43-1423/u.2019.09.031.

［13］DETHLOFF J. Vehicle routing and reverse logistics： The vehicle routing problem with simultaneous delivery and pick-up［J］. OR-Spektrum， 2001， 23（1）： 79-96. DOI： 10.1007/PL00013346.

［14］STEINBRUNN M， MOERKOTTE G， KEMPER A. Heuristic and randomized optimization for the join ordering problem［J］. The VLDB Journal， 1997， 6（3）：191-208. DOI： 10.1007/s007780050040.

［15］彭巍，周和平，高攀.面向城際軌道交通的定制化接駁公交線路優化［J］.長沙理工大學學報（自然科學版），2017，14（4）：49-54. DOI：10.3969/j.issn.1672-9331.2017.04.008

［16］ROPKE S， PISINGER D. A unified heuristic for a large class of Vehicle Routing Problems with Backhauls［J］. European Journal of Operational Research， 2006， 171（3）： 750-775. DOI： 10.1016/j.ejor.2004.09.004.

［17］CHEN J F， WU T H. Vehicle routing problem with simultaneous deliveries and pickups［J］. Journal of the Operational Research Society， 2006， 57（5）： 579-587. DOI： 10.1057/palgrave.jors.2602028.