城市軌道交通末班列車的運行時刻表編制與線路接續優化

摘要：為了實現城市軌道交通末班列車的列車運行時刻表編制與線路接續優化，以城市軌道交通線網為研究對象，在既有研究基礎上進一步考慮線網的空間復雜性和列車銜接的序列性，增加結構化的換乘時間和運營時段等實際場景條件，以各條線路末班列車時刻的組合優化為決策切入點，分析換乘線路接續成功的場景數量；基于列車運行時刻表編制要素構建集成的優化模型，應用人工魚群算法進行啟發式求解，并以北京市城市軌道交通局部干線區域為對象進行算例研究。結果表明，與現有的優化方法相比，所提出的優化模型與計算流程在線路接續成功方向數量、線路接續成功率、平均富余時差、運算執行時間和初次迭代中央處理器使用率方面均具有明顯優勢。

關鍵詞：交通信息工程及控制；列車運行時刻表；線路接續；城市軌道交通；人工魚群算法

中圖分類號：TP14

文獻標志碼：A

Timetable Preparation and Line Connection Optimization of Last Trains in Urban Rail Transit

ZHANG Lukai1， WANG Yingping^{1， 2}， YANG Yan3

（1. Transport Planning and Research Institute， Ministry of Transport， Beijing 100029， China; 2. Laboratory for Traffic and Transport Planning Digitalization， Beijing 100029， China; 3. Guangxi Traffic Technician College， Nanning 530001， Guangxi， China）

Abstract：" To realize the timetable preparation and line connection optimization of last trains in urban rail transit， taking the urban rail transit line network as a research object， the spatial complexity of the line network and the sequence of train connections were further considered based on the existing research， and the number of scenarios such as structured transfer time and operating period were added. With the combination optimization of the last train time of each line as the decision making starting point， the directions in successful transfer line connection were analyzed. An integrated optimization model was constructed based on the timetable preparation elements， artificial fish swarm algorithm was applied for heuristic solving， and numerical experiments were carried out with the local trunk line area of Beijing urban rail transit as the object. The results show that compared with the existing optimization methods， the proposed optimization model and calculation process have obvious advantages in number of successful line connection directions， success rate of line connection， average surplus time difference， operation execution time， and central processing unit usage rate of the first iteration.

Keywords： transportation information engineering and control; timetable; line connection; urban rail transit; artificial fish swarm algorithm

收稿日期：2022-01-09 網絡首發時間：2022-12-28T12∶18∶22

基金項目：國家自然科學基金項目（62173167）

第一作者簡介：張路凱（1988—），男，山東濟寧人。工程師，博士，研究方向為交通信息工程及控制。E-mail： 18114054@bjtu.edu.cn。

通信作者簡介：王英平（1980—），女，山西大同人。高級工程師，碩士，研究方向為交通信息工程及控制。E-mail： wangyptpri@sina.com。

網絡首發地址：https：//kns.cnki.net/kcms/detail//37.1378.N.20221227.1647.002.html

隨著社會經濟的高速發展，城市軌道交通對城市居民的生產生活服務作用愈來愈突出。同時，高效準確的末班列車時刻表與線路接續方案可以減少車站內滯留旅客的數量，從而提高車站、線路及整體網絡的安全性和運營效率，因此城市軌道交通末班列車運營控制的系統性優化引起了行業的廣泛關注。城市軌道交通末班列車運營控制系統優化涉及時刻表協同調度，關聯線路方向和站點繁多，組合量化難度大，信息級聯程度強，計算效率要求高，因此相關研究具有重要的理論分析價值和工程實踐意義。

對于城市軌道交通時刻表編制與接續優化的既有相關成果，在研究內容上常見于線網運營復雜性分析、列車開行方案制定和同步時刻表優化，并融入延誤指標體系的改善和客流量特征的研究。在研究方法上多集中于計量修正分析、控制理論應用，以及數學規劃建模。Zhou等^［1］分析了城市軌道交通雙線路接續的有效時間間隔，并通過特定列車時刻的限制調控來促進系統時刻表的同步。楊艷^［2］建立了整數規劃模型研究地鐵系統接續下的時刻表編制問題，并設計了粒子群算法求解模型?？盗?sup>［^3］對城市軌道交通末班列車時刻表協同問題的非確定性多項式難題（NP-hard）性質進行了證明。Guo等^［4］深入分析了城市軌道交通首班列車開行方案的優化問題，并以北京地鐵為實例進行了驗證。Corman等^［5］提出了實時的列車延誤分析模型，主要圍繞列車動態調度魯棒性的改進進行研究，Kecman等^［6］也通過完善部分限制條件進行了類似的研究。Samà等^［7］基于提出的列車組合調度模型，對比分析了城市軌道交通服務中實現高效運營的必需條件。

相關研究成果的特點分析匯總如表1所示。從優化目標來看，線路接續程度和列車延誤量仍然是研究的重點方向。從模型特點來看，整數規劃模型仍然是解析研究的實用形式；從算法類型來看，CPLEX工具與啟發式算法仍然是求解計算的有效途徑。同時，既有研究中換乘時間常被作為單一的影響參數，而實際場景中換乘時間的組成是較為復雜的，涉及乘客上、下車時間，乘客換乘步行時間，列車啟動安全預留時間等要素，尤其是乘客換乘步行時間，在數值上具有明顯的變量分布特征，將其視為定值會與實際情形偏差較大。此外，相關研究成果中仍普遍存在計算效率低的問題，啟發式算法的應用拓展值得進一步探討。基于上述分析，本文中以城市軌道交通線路列車時刻組合優化為切入點，突出實際時間因素的影響和運營條件的限制，建立線性整數規劃模型并設計人工魚群算法，最后通過數值實驗對比論證所提出方法的效率與優勢。

1 城市軌道交通末班列車時刻表編制與接續優化模型

本文中以集成的組合優化流程來協調城市軌道交通末班列車時刻表編制與接續，在考慮時刻限制、時長約束和線路運行要求的前提下，基于時刻表方案實現系統最優下的換乘接續。從局部角度來看，2條線路的末班列車在某換乘站接續成功的必要條件如圖1所示。此外，所建立的優化模型由式（1）—（10）構成。

式（1）描述了模型的目標函數，即城市軌道交通網絡的末班列車系統接續失敗場景數最少。

式中：Z為目標函數值；x為城市軌道交通網絡中的換乘站；Θ為城市軌道交通網絡中的換乘站集合，x∈Θ；y、z為一對相組合的前續線路和后續線路；ω為線路的集合；P_xyz為換乘標識變量，若乘客能夠在站點x完成自線路y至線路z的換乘，則取值為1，否則為0。

式（2）為前續線路末班列車在換乘站到達時刻的約束定義。

2 人工魚群算法設計

傳統研究方法中，通常調用CPLEX工具或采用啟發式算法求解含有整數規劃的組合優化模型。受限于計算軟硬件環境和解空間的復雜性，既有算法中求解精度與計算效率通常難以保證，尤其是初始解向全局最優解逼近的合理規則難以確定。結合既有相關研究成果，分析常見優化算法求解本文模型的特點并進行比較，如表2所示。本文中考慮決策變量解空間的多元耦合與高維度特點，在啟發式求解中同時兼顧解更新過程的隨機性和有序性^［10］。鑒于此，設計人工魚群算法（artificial fish swarm algorithm，AFSA）求解所建立的模型^［11］。一條人工魚包含一組城市軌道交通末班列車時刻表，人工魚個體的適應度（食物數量）為模型目標函數值的倒數。AFSA流程如2所示。

算法流程中計算參數包括人工魚個體總數N、人工魚位置X、人工魚最大步距S、人工魚視距V、人工魚移動嘗試最大次數n_max、種群最大迭代次數G_max、魚群擁擠程度δ、區間（0， 1］內隨機數R、人工魚個體位置X_i與X_j之間的距離d_ij=X_i-X_j、人工魚個體所在位置的食物數量Y=f（X）。

算法流程中解更新函數包括覓食行為函數（Prey）、隨機行為函數（RandMove）、聚群行為函數（Swarm）和追尾行為函數（Follow）。

2.1 覓食行為函數

人工魚個體自X_i點出發，在視距V內選擇目標位置X_j點并移動，其移動距離d_ij≤V。個體移動后的位置X_j=X_i+VR。通過目標函數計算獲得的當前位置食物數量為Y_i=f（X_i）和Y_j=f（X_j）。判斷如下：

1）若Y_jgt;Y_i，人工魚由X_i向X_j移動，新位置X_i+1=X_i+［（X_j-X_i）/X_j-X_i］SR；

2）若Y_j≤Y_i，人工魚在X_i處搜索新X_j；

3）若嘗試n_max次數后仍未獲得理想的X_j，執行隨機移動函數。

2.2 隨機行為函數

隨機移動是覓食行為的缺省行為，人工魚個體由X_i處隨機向周圍移動，新的增量變化位置X_i+1=X_i+VR。

2.3 聚群行為函數

人工魚個體在X_i處尋找其視距范圍內（d_ij≤V）周圍數量為n_f的個體對應的中心位置X_c，判定條件Y_c/n_fgt;δY_i是否滿足，其中Y_c為中心位置食物數量，δ為比例系數。該條件表示該中心位置處并不擁擠，因此人工魚個體由X_i處向X_c處進行移動，相應的變化增量即X_i+1=X_i+［（X_c-X_i）/X_c-X_i］SR。

2.4 追尾行為函數

人工魚個體在X_i處尋找其視距范圍內（d_ij≤V）周圍數量為n_f的個體，并根據Y_j選擇最優個體位置X_j。若Y_j/n_fgt;δY_i，表示X_j周圍并不擁擠，因此人工魚個體由X_i處向X_j處移動，相應的位置增量變化即X_i+1=X_i+［（X_j-X_i）/X_j-X_i］SR。

在每次迭代計算中，將個體適應度與公告板相應最新值進行比較以確定公告板是否更新。當達到最大迭代次數時計算停止，公告板上的解為最終輸出的系統最優接續下城市軌道交通末班列車線路時刻表方案。

3 算例

以北京市的城市軌道交通局部干線區域為對象

進行數值實驗，對所提出的模型與算法進行驗證，如圖3所示。研究中分析了11個換乘方向，包括6條線路（3條雙向線路）和5個換乘站。線路上的箭頭表示上行末班列車的方向，每條線路都有2個方向（上行和下行）。與既有關于城市軌道交通時刻表的優化方法相比，本文方法的主要特點在于考慮了乘客滯留時間的影響。數值實驗模型條件與環境設置對比如表3所示^［1］，既有不考慮滯留時間的優化方法所得城市軌道交通末班列車時刻表方案如表4所示。為了便于解析計算，采用相對時間值，即城市軌道交通線網末班列車統一運行的起始時刻為0，時間數值單位為min。表中相關數字表示末班列車到達和出發的時刻。例如，1號線路的上行方向末班列車于時間為10.0 min到達換乘站2，并于時間為10.5 min出發。

應用本文考慮滯留時間的優化方法，在MATLAB R2016b環境下計算獲得城市軌道交通末班列車時刻表方案結果，如表5所示。此外，不考慮滯留時間與考慮滯留時間的優化指標對比如表6所示?？梢钥闯?，本文中考慮滯留時間的優化方法在系統接續效果、平均富余時差和計算效率等指標上均體現出相應優勢。

表6中的富余時差為乘客下車并至換乘列車之前的等待時間，代表了實施接續優化的靈活性和末班列車時刻表方案的魯棒性，其對應模型中參數的計算公式為T ^z，B_x-T ^y，A_x-t^safe_xy-t^off_xy-t^walk_xyz-t^board_xz-t^safe_xz，即后續線路發車時刻與前續線路到達時刻、前續線路預留安全時間、下車所需時間、平均走行時間、上車所需時間、后續線路預留安全時間之間的差值。富余時差數值越大，表示應對隨機擾動的調整空間越大，優化方案的適用性越強。初次迭代中央處理器（CPU）使用率代表了計算初始解的難易程度，該數值越小表示初始階段計算迭代效率越高^［12］。

4 結論

針對城市軌道交通末班列車時刻表編制與接續優化問題，本文中以運行時刻的組合優化為切入點，構建優化模型以分析系統接續場景，設計人工魚群算法對模型進行求解。數值實驗結果表明，與既有方法相比，本文中提出的考慮滯留時間的優化方法在接續成功方向數量、接續成功率、平均富余時差、運算執行時間和初次迭代CPU使用率方面均具有明顯優勢。

同時，本文中提出的模型與算法緊貼現實問題，反映客觀運營需求，可操作性較強，可為城市軌道交通運營管理和列車調度提供可靠的基礎理論依據和有效的工程實踐參考。此外，本文模型中未涉及站點位置的瓶頸效應影響，對客流需求的分析也較為抽象，可在未來研究中有針對性地進行深入探究。

參考文獻：

［1］ ZHOU C C， ZHANG L K， KANG L J. Modeling timetable coordination in urban mass transit networks［J］. Advanced Materials Research， 2014， 1030/1031/1032： 2207.

［2］ 楊艷. 地鐵線網末班列車時刻表協同編制優化［J］. 山東交通學院學報， 2020， 28（4）： 46.

［3］ 康柳江. 城市軌道交通末班列車運行計劃協同組織優化［D］. 北京： 北京交通大學， 2016.

［4］ GUO X， WU J J， SUN H J， et al. Timetable coordination of first trains in urban railway network： a case study of Beijing［J］. Applied Mathematical Modelling， 2016， 40（17/18）： 8048.

［5］ CORMAN F， D’ARIANO A， PACCIARELLI D， et al. Dispat-

ching and coordination in multi-area railway traffic management ［J］. Computers amp; Operations Research， 2014， 44： 146.

［6］ KECMAN P， CORMAN F， D’ARIANO A， et al. Rescheduling models for railway traffic management in large-scale networks［J］. Public Transportation， 2013， 5（1/2）： 95.

［7］ SAM M， PELLEGRINI P， D’ARIANO A， et al. Ant colony optimization for the real-time train routing selection problem［J］. Transportation Research Part B： Methodological， 2016， 85： 89.

［8］ DU P， LIU C， LIU Z L. Walking time modeling on transfer pedestrians in subway passages［J］. Journal of Transportation Systems Engineering and Information Technology， 2009， 9（4）： 103.

［9］ 郭欣. 城市軌道交通線網列車時刻表分階段協同優化［D］. 北京： 北京交通大學， 2018.

［10］ KANG L J， MENG Q. Two-phase decomposition method for the last train departure time choice in subway networks［J］. Transportation Research Part B： Methodological， 2017， 104： 568.

［11］ LIU Y， FENG X S， DING C C， et al. Electric transit network design by an improved artificial fish swarm algorithm［J］. Journal of Transportation Engineering， Part A： Systems， 2020， 146（8）： 04020071.

［12］ LIU Y， FENG X S， ZHANG L K， et al. A pareto artificial fish swarm algorithm for solving a multi-objective electric transit network design problem［J］. Transportmetrica A： Transport Science， 2020， 16（3）： 1648.

（責任編輯：劉建亭）