基于排隊論的地鐵列車運行自動調(diào)整優(yōu)化模型

寧正，牛宏俠，張肇鑫

基于排隊論的地鐵列車運行自動調(diào)整優(yōu)化模型

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

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

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

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

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

1 地鐵列車候車排隊系統(tǒng)設(shè)計

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

1.1 候車系統(tǒng)排隊過程

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

1.2 客流輸入分析

2 自動調(diào)整模型建立

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

2.1 優(yōu)化目標(biāo)

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

用實際到發(fā)時間表示服務(wù)時間為：

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

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

考慮變化客流的影響，以最小停站時間顧客吸收數(shù)最多為依據(jù)的目標(biāo)函數(shù)為：

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

將雙目標(biāo)線性加權(quán)，則列車運行調(diào)整的總目標(biāo)函數(shù)為：

其中：1和2是分目標(biāo)在總目標(biāo)中所占的權(quán)重系數(shù)。運行調(diào)整時，列車晚點最少和交通運行效率均需權(quán)衡考慮，所以本文以2個目標(biāo)等權(quán)重同時優(yōu)化，取2=0.4，1=0.5。

2.2 停站時間優(yōu)化下的約束條件

2.2.1 系統(tǒng)平衡條件約束

2.2.2 區(qū)間運行時間約束

2.2.3 列車追蹤時間約束

2.2.4 附加停站時間約束

在運行調(diào)整過程中，在縮短列車晚點的基礎(chǔ)上要考慮最大程度的吸收客流，當(dāng)最小停站時間內(nèi)不能完全吸納客流時，要增加附加停站時間。假設(shè)客流是勻速上車，每個人所需的服務(wù)時間為，s/人，則附加停站時間為：

2.3 評價指標(biāo)

3 仿真實驗

3.1 模型求解算法

在粒子群算法可調(diào)參數(shù)中，慣性權(quán)重較大時有利于全局搜索，較小時利于進(jìn)行精確的局部搜索，因此針對PSO算法后期易在全局最優(yōu)附近產(chǎn)生振蕩的現(xiàn)象，采用線性變化的權(quán)重[15]，隨算法迭代次數(shù)的變化公式為：

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

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

3.2 算例

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

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

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

表1 運行調(diào)整模型基本參數(shù)

表2 調(diào)整后時刻表與原始時刻表對比

注：斜體表示調(diào)整后的時間。

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

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

僅縮短列車晚點時間模型中，列車在晚點初期為了減小晚點時間會以最短時間運行，到調(diào)整后期逐漸增大行車間隔。橫向?qū)Ρ认噜徿嚧卧诓煌囌镜牡秸鹃g隔時間，初始晚點的車輛在2個模型均以最小間隔時間進(jìn)行調(diào)整，后期本文提出優(yōu)化模型根據(jù)不同客流到達(dá)調(diào)整了行車間隔。縱向?qū)Ρ仍谕徽鞠噜彽能嚧蔚秸镜臅r間間隔，該優(yōu)化模型在顧客到達(dá)率較小時延長了行車間隔，顧客到達(dá)率增大時縮短了行車間隔。

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

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

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

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

4 結(jié)論

1) 考慮乘客到達(dá)的變化與行車間隔時間對平均排隊長的相互影響，設(shè)計了基于純限量服務(wù)休假模型的地鐵列車候車排隊系統(tǒng)，研究行車間隔與站臺候車顧客數(shù)的數(shù)學(xué)關(guān)系。

2) 建立列車晚點調(diào)整的多目標(biāo)優(yōu)化模型，并增加了附加停站時間。該模型能在顧客到達(dá)較多時，縮短行車間隔來減少等候服務(wù)的顧客數(shù)，并能通過延長停站時間增加吸收的等待顧客數(shù)。當(dāng)休假時間內(nèi)顧客到達(dá)數(shù)較少時，能延長行車間隔，在吸收晚點時間的同時，分散吸收客流，避免較多客流在同一列車內(nèi)擁擠。

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

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

[2] 柏赟, 陳垚, 陳玥, 等. 考慮列車總晚點和到發(fā)均衡性的地鐵列車運行調(diào)整方法研究[J]. 交通運輸系統(tǒng)工程與信息, 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]. 中國鐵道科學(xué), 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] 王媛媛, 倪少權(quán). 城市軌道交通大小交路模式列車開行方案的優(yōu)化[J]. 鐵道學(xué)報, 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] 吳洋, 羅霞. 一種晚點地鐵列車實時調(diào)整策略及其動態(tài)速控模式[J]. 中國鐵道科學(xué), 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] 盧穩(wěn), 朱愛紅, 宋麗梅. 城市軌道交通列車運行過程的多目標(biāo)優(yōu)化研究[J]. 鐵道標(biāo)準(zhǔn)設(shè)計, 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]. 長沙: 湖南大學(xué)出版社, 2010. HE Xuansen. Random process and queuing theory[M]. Changsha: Hunan University Press, 2010.

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

[13] 蔡昌俊, 姚恩建, 張永生, 等. 基于AFC數(shù)據(jù)的城軌站間客流量分布預(yù)測[J]. 中國鐵道科學(xué), 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] 胡路. 考慮穩(wěn)定性的城市軌道交通車站交通服務(wù)設(shè)施系統(tǒng)優(yōu)化配置理論與方法[D]. 成都: 西南交通大學(xué), 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

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

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

(編輯 蔣學(xué)東)