基于排隊論的地鐵列車運行自動調整優化模型

寧正，牛宏俠，張肇鑫

基于排隊論的地鐵列車運行自動調整優化模型

寧正1, 2，牛宏俠1, 2，張肇鑫1, 2

(1. 蘭州交通大學 自動控制研究所，甘肅 蘭州 730070；2. 甘肅省高原交通信息工程及控制重點實驗室，甘肅 蘭州 730070)

針對乘客到達時間分布不均衡對列車晚點調整的影響，既有研究中的列車自動調整模型未涉及在動態變化的客流輸入下，對行車間隔和停站時間進行優化的問題，通過引入排隊理論研究客流變化和行車間隔與停站時間的關系?；谛菁倥抨犇Ｐ瞳@得調整過程中候車乘客平均排隊長，并以此為基礎建立以減少列車晚點時間和提高列車運輸量為目標函數的優化模型。根據候車排隊長優化停站時間，運用線性遞減權重粒子群算法進行求解。研究結果表明：與僅減小晚點時間的模型相比，本文提出的方法可以能在吸收晚點的過程中提高交通系統的運行效率。

運行自動調整；運行效率；排隊理論；地鐵列車；客流不均衡；列車晚點

城市軌道列車在運輸組織中，易受客流波動和設備失效等隨機因素的干擾造成列車晚點。作為一種短途出行的公共交通工具，地鐵列車不僅具有干線鐵路列車按圖運行的規律性特點，還具有公共交通工具服務機制應與客流變化規律相協調的特點。但隨著客流的高速增長和網絡負荷能力的日趨緊張，客流的狀態與變化趨勢已經成為列車運行調整需要考慮的關鍵因素。因此，從新的角度下考慮列車運行自動調整問題，是實現列車全自動化駕駛與智能化運行的重要研究方向之一。列車運行調整的模式一般主要有4種，包括自動調整模式、人工調整模式、人工調度模式和全人工模式。其中，自動調整模式是調度自動控制的最高級別。當列車出現較小范圍內的運行偏離情況時，列車自動調整子系統(ATR)可以通過不斷地對比計劃時刻表和實際運行時刻，調整列車到站和出站時間，通過對列車自動駕駛系統(ATO)設置列車運行等級而調整晚點時間[1]?，F有文獻對于列車晚點調整的研究主要有2個方面，一方面從人工調整的角度出發，優化列車運行圖緩沖時間和列車開行方案或列車行車均衡性，或者通過建立分布式調整方案，解決地鐵網絡下的換乘問題[2?6]。但此類研究需要在鋪畫運行圖之前完成，無法滿足當列車在運行過程中發生小范圍晚點，系統自動調整的實時性要求；另一方面從列車運行的角度出發，多以列車晚點時間最短，列車晚點數目最少等為目標函數，建立列車自動調整優化模型[7?10]，但此類方法不能在吸收晚點過程中同時優化地鐵系統的運營效率。目前的運行調整模型，無論在人工調整還是自動調整方面，均未研究在動態變化的客流輸入與行車間隔調整及列車停站時間改變的影響下，站臺候車乘客排隊隊長的變化規律?？梢娍紤]客流變化的地鐵列車運行調整尚在初步探究階段。本文針對地鐵列車運行晚點問題，引入排隊理論研究客流變化和行車間隔與停站時間的相互影響。分析客流在系統中的輸入，基于純限量服務休假模型獲得調整過程中候車乘客平均排隊長，并以此為基礎建立了減少列車晚點時間和提高列車運輸量的多目標優化模型，并優化停站時間，最后運用線性遞減權重粒子群算法進行求解。

1 地鐵列車候車排隊系統設計

排隊論是在研究各種排隊系統概率規律性的基礎上，解決相應排隊系統最優設計和最優控制的問題。一般排隊系統都有輸入過程、服務規則和服務臺3個組成部分[11]。由于地鐵列車雙線單方向的運行特點，列車到達一次提供一次服務，為單服務臺等待制服務。

1.1 候車系統排隊過程

將列車停車時間抽象為服務時間，列車行車間隔抽象為休假時間的平均值()。則地鐵列車服務過程是一個純限量服務休假排隊模型，即每提供一次服務就進入休假狀態的單重休假系統。利用該模型可以描述調整時間內顧客到達的平均排隊長()與列車行車間隔()以及停站時間的關系，可以在停站時間內最大吸收排隊顧客的目標下，優化列車行車間隔時間。根據文獻[12]不加推導地給出等待顧客的平均隊長()與列車行車間隔以及停站時間的關系為：

1.2 客流輸入分析

2 自動調整模型建立

列車運行自動調整就是列車運行發生晚點時，在一定約束下，利用運行圖的冗余時間調整列車在各車站的實際到站和出站時間的多目標優化問題。

2.1 優化目標

圖1 與列車行車間隔E(V)以及客流到達率λ的關系圖

用實際到發時間表示服務時間為：

用實際到發時間表示行車間隔即休假時間為：

將式(3)，(4)和(5)式代入式(1)，候車系統的顧客平均排隊長表示為：

考慮變化客流的影響，以最小停站時間顧客吸收數最多為依據的目標函數為：

用各列車在各車站實際到站晚點時間與實際出站晚點時間的總和表示，列車總晚點時間最短的目標函數為：

將雙目標線性加權，則列車運行調整的總目標函數為：

其中：1和2是分目標在總目標中所占的權重系數。運行調整時，列車晚點最少和交通運行效率均需權衡考慮，所以本文以2個目標等權重同時優化，取2=0.4，1=0.5。

2.2 停站時間優化下的約束條件

2.2.1 系統平衡條件約束

2.2.2 區間運行時間約束

2.2.3 列車追蹤時間約束

2.2.4 附加停站時間約束

在運行調整過程中，在縮短列車晚點的基礎上要考慮最大程度的吸收客流，當最小停站時間內不能完全吸納客流時，要增加附加停站時間。假設客流是勻速上車，每個人所需的服務時間為，s/人，則附加停站時間為：

2.3 評價指標

3 仿真實驗

3.1 模型求解算法

在粒子群算法可調參數中，慣性權重較大時有利于全局搜索，較小時利于進行精確的局部搜索，因此針對PSO算法后期易在全局最優附近產生振蕩的現象，采用線性變化的權重[15]，隨算法迭代次數的變化公式為：

其中：max和min分別表示的最大值和最小值；為當前迭代次數，max為最大迭代步數。本模型中取max=0.9，min=0.4。

為了提高算法的求解速度，初始化時需要限制微粒矩陣滿足停站時間、行車間隔以及停站時間的約束，選取無量綱處理后的總目標函數為適應度函數。由于求解問題的復雜性，取種群個數為200，學習因子1=2=2。算法基本流程如圖2所示。

3.2 算例

案例采用某地鐵線路的運行數據和MATLAB仿真平臺，對獲取得到晚點信息的列車進行調整，然后對調整后所輸出的數據進行驗證。該線路車站數目14個，開行列車數10個，選取客流影響程度較高的早高峰8:00~9:00為研究時段，該時段內的列車追蹤冗余時間是30 s，計劃停站時間是35 s，最小停站時間是30 s，最大停站時間為35 s，高峰小時內顧客在站臺的平均到達率是0.05人/s，調整時間內的客流到達率在平均到達率鄰域內取值。顧客乘車所需的平均時間為0.7 s/人，其余一些基本運行參數，如表1所示。

假設列車運行過程中由于隨機因素的干擾，自動調整模塊識別到10104次列車到達A站時晚點了100 s，采用本文提出的列車運行調整模型計算，可以在14 s內輸出調整后的結果，受影響的車次調整后的列車時刻表和計劃時刻表對比如表2所示。

圖2 粒子群算法求解流程圖

表1 運行調整模型基本參數

表2 調整后時刻表與原始時刻表對比

注：斜體表示調整后的時間。

表2中斜體表示調整后的時間，由于10104次列車在A站晚點，到達D站才充分吸收晚點，并連帶影響了后續車輛，使10107次列車在C站吸收晚點。初始晚點時由于2車次到站時間過長候車人數過多，模型主要縮短了晚點時間。而在調整晚點的連帶晚點影響的車輛時，同時考慮乘客到達率變化的影響，調整了行車間隔時間，避免晚點初期車輛吸收過多顧客造成車內擁擠。

為比較本文模型優化效果，本文建立了僅考慮吸收晚點的自動調整模型。晚點調整中的停站時間為最小停站時間，其對比結果如表3所示。

僅縮短列車晚點時間模型中，列車在晚點初期為了減小晚點時間會以最短時間運行，到調整后期逐漸增大行車間隔。橫向對比相鄰車次在不同車站的到站間隔時間，初始晚點的車輛在2個模型均以最小間隔時間進行調整，后期本文提出優化模型根據不同客流到達調整了行車間隔?？v向對比在同一站相鄰的車次到站的時間間隔，該優化模型在顧客到達率較小時延長了行車間隔，顧客到達率增大時縮短了行車間隔。

考慮客流吸收的列車調整模型在優化行車間隔的同時還根據站臺等待顧客數延長了停站時間，與僅縮短晚點時間調整模型的停站時間對比如表4所示。

表3 不同顧客到達率下的行車間隔時間對比

優化模型均以最小停站時間內吸收的顧客數調整了10106和10107次列車的行車間隔，并計算的停站時間。實際調整過程中當10107次列車到達B和C 2站時小于計劃運行時刻時，列車運行自動調整模塊終止了調整，實際列車停站時間為35 s，所以出現了偏差。與普通模型相比，雖然優化模型總晚點時間增加了26%，但是行車空閑率降低了20.6%。盡管總晚點時間越長，列車實際行駛時分與計劃運行圖的偏離程度越高，但是由于地鐵系統在優化過程中需首先考慮滿足客流需求，優化模型平衡了列車調整中吸收晚點與吸納客流之間的關系，提高了交通系統效率。

表4 不同模型下的停站時間及停站時間空閑率對比

4 結論

1) 考慮乘客到達的變化與行車間隔時間對平均排隊長的相互影響，設計了基于純限量服務休假模型的地鐵列車候車排隊系統，研究行車間隔與站臺候車顧客數的數學關系。

2) 建立列車晚點調整的多目標優化模型，并增加了附加停站時間。該模型能在顧客到達較多時，縮短行車間隔來減少等候服務的顧客數，并能通過延長停站時間增加吸收的等待顧客數。當休假時間內顧客到達數較少時，能延長行車間隔，在吸收晚點時間的同時，分散吸收客流，避免較多客流在同一列車內擁擠。

3) 通過粒子群算法驗證了該模型的可行性，其能在14 s內求解得出調整后的運行時刻表，符合自動調整對于時間效率性的要求。仿真結果表明優化模型能根據客流變化調整行車間隔，與僅調整列車晚點時間的自動調整模型相比，本文提出的模型在減少列車晚點的同時，使停站時間行車空閑率降低了20.6%，提高了交通系統的運行效率。

[1] 徐金祥. 城市軌道交通列車運行自動控制技術[M]. 北京: 中國鐵道出版社, 2013. XU Jinxiang. Urban rail transit train operation automatic control technology[M]. Beijing: China Railway Press, 2013.

[2] 柏赟, 陳垚, 陳玥, 等. 考慮列車總晚點和到發均衡性的地鐵列車運行調整方法研究[J]. 交通運輸系統工程與信息, 2014, 14(3): 104?110. BAI Yun, CHEN Yao, CHEN Yue, et al. Rescheduling of metro train timetable for delay reductionand equilibrium of trains’ arrival and departure[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(3): 104?110.

[3] 趙宇剛, 毛保華, 蔣玉琨. 基于列車運行時間偏離的地鐵列車運行圖緩沖時間研究[J]. 中國鐵道科學, 2011, 32(1): 118?121. ZHAO Yugang, MAO Baohua, JIANG Yukun. Study on the buffer time of metro train diagram based on train running time deviation[J]. China Railway Science, 2011, 32(1): 118?121.

[4] 王媛媛, 倪少權. 城市軌道交通大小交路模式列車開行方案的優化[J]. 鐵道學報, 2013, 35(7): 1?8. WANG Yuanyuan, NI Shaoquan. Optimization of train schedules of full-length and short turn operation modes in urban rail transit[J]. Journal of the China Railway Society, 2013, 35(7): 1?8

[5] LING X, WANG D C, LI K P, et al. A green train scheduling model and fuzzy multi-objective optimization algorithm[J]. Applied Mathematical Modeling, 2013, 37(4): 2063?2073.

[6] LI Shukai, ZHOU Xuesong, YANG Lixing, et al. Automatic train regulation of complex metro networks with transfer coordination constraints: A distributed optimal control framework[J]. Transportation Research (Part B), 2018(117): 228?253.

[7] CHANG S C, CHUNG Y C. From timetabling to train regulation-a new train operation model[J]. Butterworth- Heinemann, 2005, 47(9): 575?585.

[8] 吳洋, 羅霞. 一種晚點地鐵列車實時調整策略及其動態速控模式[J]. 中國鐵道科學, 2005, 26(6): 113?118. WU Yang, LUO Xia. Tactic for real-time operation adjustment and correspo-nding dynamic velocity control mode for delayed metro trains[J]. China Railway Science, 2005, 26(6): 113?118.

[9] 盧穩, 朱愛紅, 宋麗梅. 城市軌道交通列車運行過程的多目標優化研究[J]. 鐵道標準設計, 2017, 61(2): 131? 135. LU Wen, ZHU Aihong, SONG Limei. Multi-objective optimization of train operation process of urban rail trainsit[J]. Railway Standard Design, 2017, 61(2): 131? 135.

[10] Seles P, Dewilde T, Cattrese D, et al. Reducing the passenger travel time in practice by the automated construction of a robust railway timetable[J]. Transport (Part B) Methodol, 2016(81): 124?156.

[11] 何選森. 隨機過程與排隊論[M]. 長沙: 湖南大學出版社, 2010. HE Xuansen. Random process and queuing theory[M]. Changsha: Hunan University Press, 2010.

[12] 田乃碩. 休假隨機服務系統[M]. 北京: 北京大學出版社, 2001. TIAN Naishuo. Vacation random service system[M]. Beijing: Beijing University Press, 2010.

[13] 蔡昌俊, 姚恩建, 張永生, 等. 基于AFC數據的城軌站間客流量分布預測[J]. 中國鐵道科學, 2015, 36(1): 126?132. CAI Changjun, YAO Enjian, ZHANG Yongsheng, et al. Forecasting of passenger flow’s distribution among urban rail transit station based on AFC data[J]. China Railway Science, 2015, 36(1): 126?132.

[14] 胡路. 考慮穩定性的城市軌道交通車站交通服務設施系統優化配置理論與方法[D]. 成都: 西南交通大學, 2014: 135?137. HU Lu. The optimization theory and method for configuration of transportation facilities in urban rail trainsit station with consideration of stability analysis[D]. Chengdu: Southwest Jiaotong University, 2014: 135?137.

[15] DONG C, WANG G, CHEN Z, et al. A method of self-adaptive inertia weight for PSO[C]// International Conference on Computer Science and Software Engineering. IEEE, 2008: 1195?1198.

Automatic operation regulation optimization model of metro train based on queuing theory

NING Zheng1, 2, NIU Hongxia1, 2, ZHANG Zhaoxin1, 2

(1. Automatic Control Institute, Lanzhou Jiaotong University, Lanzhou 730070, China; 2. Gansu Provincial Key Laboratory of Traffic Information Engineering and Control, Lanzhou 730070, China)

Considering the impact of uneven arrival time distribution of passengers on train delay adjustment, the automatic train adjustment model in existing studies are little involve the optimization of train interval and stop time under the dynamic change of passenger flow input. The queuing theory was introduced to study the relationship among passenger flow changes and train running intervals and dwell times. Based on pure limited service action model, the train operation adjustment model with the objectives of the shortest train delay and the maximum number of passengers accommodated during the minimum dwell time was established and then optimized the dwell time. The simulation suggests that the presented method not only can reduce the delay time of the train, but also can improve the operational efficiency of transportation systems compared with the model that only reduced the time delay.

automatic train operation regulation; operation efficiency; queuing theory; metro train; unbalanced arriving passengers; train delay

U231.92

A

1672 ? 7029(2019)07? 1826 ? 07

10.19713/j.cnki.43?1423/u.2019.07.029

2018?10?15

甘肅省自然科學基金資助項目(1606RJZA002，1610RJYA034，17JR5RA089)；甘肅省高等學?？蒲匈Y助項目(2017A-026)；甘肅省重點研發能力提升計劃資助項目(2060404)

牛宏俠(1978?)，女，遼寧黑山人，副教授，從事交通信息工程與智能控制理論研究；E?mail：nhx56055@mail.lzjtu.cn

(編輯 蔣學東)