譚麗，韋子文

基于CCLPSO算法的Y型交路列車開行方案優(yōu)化研究

譚麗，韋子文

(蘭州交通大學 自動化與電氣工程學院，甘肅 蘭州 730070)

列車開行方案通常包括列車停站方案、交路計劃以及編組方案，是地鐵組織運輸?shù)幕A。結合交通運輸組織的實踐經(jīng)驗以及輸送能力與客流需求達到最佳匹配的原則，以乘客出行成本及企業(yè)運營成本最低為目標，綜合考慮線路最大通過能力、最小發(fā)車頻率和最大可用車底數(shù)量等限制條件，構建城市地鐵Y型交路模式下的列車開行方案優(yōu)化模型，來確定Y型交路模式列車開行方案的主線及支線的列車運行區(qū)段及各線的列車開行頻率。采用分類學習混合粒子群算法(CCLPSO)對其進行求解，通過實際案例驗證了模型的合理性和算法的有效性，并對折返站位置和列車開行頻率進行靈敏度分析。研究結果表明：Y型交路的折返站的選取對乘客出行成本影響顯著，相比于其他2種算法，采用該算法可使綜合成本分別減少16.9%和31.6%。

城市軌道交通；列車開行方案；混合粒子群算法；分類學習

在城市軌道交通發(fā)展過程中，由于城市形態(tài)、重大項目的建設及城市的多點戰(zhàn)略布局[1]等原因，逐漸形成了除傳統(tǒng)的單一交路運行模式外的大小交路、銜接交路等多交路運行模式，Y型交路運行模式即是其中一種特殊的交路形式。針對列車在各種交路運行模式下以何種開行方案運行這一問題，國內外學者進行了諸多研究。王永亮等[2]采用遺傳模擬退火算法求解以運營網(wǎng)絡系統(tǒng)最佳為目標的列車運行交路計劃雙層模型；朱宇婷[3]研究編制列車開行方案的各項影響因素，分別以單條線路和整個運營網(wǎng)絡作為研究對象，建立列車運行交路模型并提出城市軌道交通列車開行方案的優(yōu)化方法；Szetoa等[4]研究了近郊區(qū)公交車的運行交路和發(fā)車頻率的問題，采用改進的遺傳算法對所建立的以乘客出行時間最短和乘客換乘次數(shù)最少為目標的雙目標優(yōu)化模型；Chang等[5]構建高速鐵路列車交路方案雙目標優(yōu)化模型，用模糊數(shù)學的方法將其轉化為單目標優(yōu)化模型，并選取臺灣某高鐵線路驗證了模型的有效性；陳玥[6]綜合考慮列車滿載率和線路通過能力等約束，設計了遺傳模擬退火算法求解以乘客總候車時間最短為目標的交路方案模型。由于遺傳算法[7]具有較好的全局尋有能力、魯棒性高且容易與其他算法結合的特點，與粒子群算法結合(以粒子群算法為主體)可克服其收斂速度慢、局部搜索能力差等缺點，同時引入分類學習[8]的思想有利于求解離散類優(yōu)化問題，很適合在城市軌道交通這一離散事件動態(tài)系統(tǒng)[9]中應用。綜上，對城市軌道交通Y型交路的列車開行方案的研究相對匱乏。本文參考研究大小交路[10?15]的方法，構建城市軌道交通Y型交路列車開行方案優(yōu)化模型，采用分類學習混合粒子群算法對其進行求解并驗證模型的合理有效性。

1 問題描述

目前，我國采用Y型交路模式運行的城市軌道交通線路有廣州地鐵3號線、上海地鐵10號線和11號線等，且都僅以如圖1所示的2種開行方式運行。在支線獨立運營形式中，支線交路上的列車僅在支線(如虛線所示)上行駛；支線全直通運營形式中，支線交路上的列車與主線交路上的列車在部分區(qū)段共線行駛。

(a) 支線獨立運營形式示意圖；(b) 支線全直通運營交路形式示意圖

隨著線路上客流分布特征愈發(fā)不均衡，當前這2種開行方案在高峰時段可能造成乘客等待時間過長、企業(yè)運營成本大幅增加等問題。針對以上問題，本文對Y型交路上支線的折返站位置及主、支線上列車的開行頻率組合優(yōu)化，以使線路上客流需求和運輸能力達到最佳匹配。

2 建模

本文綜合考慮乘客和運營企業(yè)雙方的利益，構建以乘客等待時間最短、列車走行公里最短和列車運用數(shù)量最少為目標的Y型交路列車開行方案優(yōu)化模型。如圖2所示，首先對線路上的各車站編號，主線依次從1編到，支線緊跟由+1編到。其中，a為待優(yōu)化的支線交路的折返站位置，b為Y型交路主線和支線的接軌站。其中，主線、支線上的列車分別如實線、虛線所示的線路以各自的開行頻率行駛，且2條交路上的列車在[a, b]區(qū)段共線 行駛。

圖2 Y型交路基本模型

2.1 模型基本假設及函數(shù)定義

根據(jù)Y型交路運營模式特點，做出如下假設：

假設1 Y型交路列車均采用站站停車的停車方案；

假設2 考慮乘客出行偏好，乘客會優(yōu)先選擇直達線路，并且不考慮乘客滯留情形；

假設3 車底周轉方式獨立運用，并且列車選型相同；

假設4 考慮列車運營組織的復雜性，各斷面的交路覆蓋層數(shù)最大為2；

假設5 在研究時段內，主、支線各自的發(fā)車間隔不變，并且上、下行列車成對開行。

為方便描述，本文對以下幾項函數(shù)做以下 定義：

1和2分別表示主、支線交路的列車開行頻率；

2.2 乘客出行成本

乘客出行成本主要由乘客的等待時間成本來表征，包括在途等待時間及候車等待時間，如式(1)所示。

式中：w和d表示候車等待時間和單位在途等待時間的單位時間價值；w和d表示乘客候車等待時間和在途等待時間。

在途等待時間指的是各OD客流運行經(jīng)過的各區(qū)間運行時間及在所經(jīng)過各車站的停站時間之和。

由于城市軌道交通行車密度大，行車間隔短，乘客到達獨立于列車到達時刻，呈現(xiàn)隨機正態(tài)分布。既有研究表明：在列車行車間隔較短(一般小于10 min時)的條件下，線路上客流的平均候車等待時間趨近于行車間隔的一半。

故Y型交路主線(除主線與支線共線區(qū)段以外)上行乘客和下行乘客的候車等待時間分別如式(2)~ (3)所示：

Y型交路支線(除主線與支線共線區(qū)段以外)上行乘客和下行乘客的候車等待時間分別如式(4)~(5)所示：

Y型交路主線與支線共線區(qū)段上的乘客和換乘客流的候車等待時間如式(6)~(7)所示：

故線路上乘客的總候車等待時間為式(2)~(7) 之和。

2.3 企業(yè)運營成本

企業(yè)運營成本主要可以分為固定成本(指車輛購置成本)及變動成本(主要由列車走行公里數(shù)決定)2部分。企業(yè)運營成本如式(8)所示：

式中：為單位列車購置費用；為單位列車運營耗費成本；N為所需列車數(shù)量；L為研究時段內列車總走行公里數(shù)。

2.3.1 車輛購置成本

運營所需列車數(shù)量可由式(9)求得：

式中：1和2分別表示主線、支線的列車周轉時間；乘以系數(shù)1.2是考慮了車輛維護等所必需的備 用車。

2.3.2 列車運行耗費成本

列車總走行公里數(shù)可由式(10)求得：

式中：1和2分別表示主線、支線交路的長度。

2.4 優(yōu)化模型及約束

本文采用理想點法將多目標優(yōu)化問題轉化為單目標優(yōu)化問題。構建優(yōu)化模型如式(11)所示：

對城市軌道交通Y型線路列車開行方案的影響因素進行分析，它對該模型構成如下幾個約束條件：

約束條件中，式(13)~(14)為基本約束，規(guī)定了折返站的位置及開行頻率的整數(shù)約束；式(15)是為了滿足列車最小追蹤間隔；式(16)是為了滿足最小發(fā)車頻率的限制；式(17)為運用列車數(shù)量的約束。綜上，該模型為多目標優(yōu)化模型，各目標之間存在矛盾關系。如果側重考慮乘客的利益，乘客出行成本降低的同時，列車開行頻率及所需列車數(shù)必然增加；如果側重考慮運營企業(yè)的利益，則地鐵運輸服務差，嚴重影響乘客出行。

3 分類學習混合粒子群優(yōu)化算法

3.1 標準粒子群算法

粒子群(PSO)算法通用性強，控制參數(shù)少，操作簡單等優(yōu)點，與傳統(tǒng)的數(shù)學規(guī)劃方法相比具有不可比擬的優(yōu)勢。

3.2 分類學習混合粒子群算法

首先，以PSO算法為主體，混合(Commix)遺傳算法中的交叉、變異策略來解決其搜索中后期收斂速度變慢和“早熟收斂”等問題。其次，由以上所建立的Y型交路列車開行方案優(yōu)化模型可知，它屬于典型的離散、動態(tài)多目標優(yōu)化問題，根據(jù)參考文獻[8]，引入“分類學習”(Clssified Learning)思想，不僅增加了粒子種類的多樣性，而且能獲得良好的收斂特性。以下將該改進的算法稱為分類學習混合粒子群算法(Commix Classified Learning PSO)。

根據(jù)大量數(shù)值實驗計算，粒子種群將按1:1:2的比例劃分為“好”、“中”和“差”3類，并根據(jù)各自的學習策略更新粒子速度，粒子位置更新公式與標準PSO算法相同。具體更新公式如式(20)~(22)所示。

同時采用慣性權重對數(shù)遞減的策略代替以往線性遞減的策略，以更好地反映粒子的真實搜索過程，2個學習因子1和2也分別動態(tài)變化以平衡算法的全局搜索和局部搜索能力。

在采用分類學習混合粒子群算法優(yōu)化Y型交路列車開行方案過程中，每個粒子都是3維的，其速度、位置表示方法與標準粒子群算法相同，各維變量分別表征折返站位置，主/支線的開行頻率1和2對/h。

3.3 算法求解流程

該改進算法的求解流程如圖3所示。

圖3 算法流程圖

3.4 數(shù)值試驗

選取Sphere, Noise Quadric和Rastrigin這幾個測試函數(shù)以測試算法的綜合性能，并與混沌粒子群(CPSO)算法和遺傳?粒子群(GAPSO)算法對比。其中，Sphere為單峰值函數(shù)，Noise Quadric函數(shù)中有隨機參數(shù)，可被看作含有離散問題的函數(shù)， Rastrigin函數(shù)為多峰值函數(shù)。

算法的參數(shù)設置如下：粒子群數(shù)目設置為40，維數(shù)設置為3，最大迭代次數(shù)設置為500。對比結果分別如圖4~6所示。

圖4 Sphere函數(shù)全局最優(yōu)曲線圖

圖5 Noise Quadric函數(shù)全局最優(yōu)曲線圖

由以上對比結果可知，CCLPSO具有較快的收斂速度和求解精度。

圖6 Rastrigin函數(shù)全局最優(yōu)曲線圖

4 案例研究與仿真

4.1 參數(shù)設置

以某城市軌交通線路為例，該軌道交通線上共設31座車站，線路全長約36 km。對線路上31座車站按先主線后支線的方法進行編號,且研究時段的列車運行參數(shù)及線路參數(shù)已知。模型中各參數(shù)的定義如表1所示。

表1 模型參數(shù)符號及定義

4.2 優(yōu)化流程及案例求解

Y型交路列車開行方案優(yōu)化流程如圖7所示。

圖7 案例優(yōu)化流程圖

如圖7，首先，對線路上的客流量進行調查分析，并設定模型的主要控制參數(shù)；其次，根據(jù)Y型交路的特點以及模型的約束條件，先后形成可行線路集、可行方案集；最后，采用改進的算法在可行解集中尋求最佳列車開行方案，并對該方案進行評估及對比。

通過Matlab軟件編程，對上述模型進行求解。表2為用GAPSO，CPSO和CCLPSO算法分別優(yōu)化交路方案時的仿真對比結果，包括3個決策變量(折返站位置，主/支線的開行頻率1和2對/h)和2個中間量(乘客候車等待時間w分鐘及列車走行公里數(shù)zkm)及綜合成本Fitness。

由表2可知，在對第2節(jié)所述多目標模型優(yōu)化時，與另外2種算法相比較，CCLPSO算法使綜合成本分別減少約16.9%和31.6%，結果表明：CCLPSO具有較好的尋優(yōu)性能，極大地優(yōu)化了該軌道交通線路的列車開行方案，使線路上客流需求與運力資源達到更好地匹配。

表2 各算法優(yōu)化方案對比

4.3 靈敏度分析

采用控制變量法對折返站位置的靈敏度進行分析，結果分別如圖8~9所示。

圖8 折返站位置靈敏度分析

圖9 支線頻率靈敏度分析

由圖8~9可知，折返站的位置對乘客出行成本影響較大，折返站設置得越靠后，乘客出行成本增加越大，當折返站設置在第17站及以后位置時，乘客出行成本的增加才趨于平緩；支線上列車的開行頻率在大于15對/h時，企業(yè)運營成本開始逐漸增加。

5 結論

1) 根據(jù)Y型交路的運營模式建立交路的列車開行方案多目標優(yōu)化模型。

2) 設計分類學習混合粒子群算法(CCLPSO)求解該模型。

3) 結合實際案例驗證模型及算法是可行有效的。在綜合考慮乘客和運營企業(yè)雙方利益求解優(yōu)化模型時，與GA-PSO算法和CPSO算法相比較，用CCLPSO算法求解效果更佳，綜合成本分別減少16.9%和31.6%。為地鐵運營企業(yè)列車開行方案的編制提供新的技術參考。

[1] 劉猛. 城市軌道交通Y型線路列車交路方案研究[D].北京: 北京交通大學, 2017. LIU Meng. Analysis on the train routing scheme of Y-type urban rail line[D]. Beijing: Beijing Jiaotong University, 2017.

[2] 王永亮, 張星臣, 蔣洋, 等. 城市軌道交通網(wǎng)絡運營魯棒性[J]. 北京工業(yè)大學學報, 2013, 39(7): 1014?1019. WANG Yongliang, ZHANG Xingchen, JIANG Yang, et al. Urban rail transit network operation robustness[J]. Journal of Beijing University of Technology, 2013, 39(7): 1014?1019.

[3] 朱宇婷. 考慮乘客出行效率的城市軌道交通列車開行方案優(yōu)化研究[D]. 北京: 北京交通大學, 2016. ZHU Yuting. An optimization research for train plan of urban rail transit with the consideration of passengers’ travel efficiency[D]. Beijing: Beijing Jiaotong University, 2016.

[4] Szetoa W Y, WU Yongzhong. A simultaneous bus route design and frequency setting problem for Tin Shui Wai, Hong Kong[J]. European Journal of Operation Research, 2011, 209: 141?155.

[5] Chang Y H, Yeh C H, SHEN C C. A multi-objective model for passenger train services planning application to Taiwan’s High-speed Rail Line[J]. Transportation Research Part B, 2000, 34(2): 91?106.

[6] 陳玥. 城市軌道交通列車運行交路方案研究[D]. 北京:北京交通大學, 2016. CHEN Yue. Study on train routing scheme of urban rail transit[D]. Beijing: Beijing Jiaotong University, 2016.

[7] 雷明, 孟學雷. 基于協(xié)同進化遺傳算法的高速鐵路運行調整研究[J]. 鐵道科學與工程學報, 2017, 14(6): 1138?1142. LEI Ming, MENG Xuelei. High-speed railway operation adjustment based on co-evolutionary genetic algorithm[J]. Journal of Railway Science and Engineering, 2017, 14(6): 1138?1142.

[8] 張凱, 宋錦春, 李松, 等. 基于分類學習粒子群優(yōu)化算法的液壓矯直機控制[J]. 機械工程學報, 2017, 53(18): 202?204. ZHANG Kai, SONG Jinchun, LI Song, et al. Hydraulic straightener control optimizer based on particle swarm with classification learning[J]. Journal of Mechanical Engineering, 2017, 53(18): 202?204.

[9] 李愛菊. 城市軌道交通系統(tǒng)的極大代數(shù)模型研究[D].北京: 北京交通大學, 2006. LI Aiju. Study on the maximum algebraic model of urban rail transit system[D]. Beijing: Beijing Jiaotong University, 2006.

[10] 許得杰, 毛保華, 雷蓮桂. 城市軌道交通大小交路列車開行方案優(yōu)化研究[J]. 交通運輸系統(tǒng)工程與信息, 2017, 17(1): 120?126. XU Dejie, MAO Baohua, LEI Liangui. Optimization for train plan of full-length and short-turn routing in urban rail transit[J]. Journal of Transportation Systems Engineering and Information Technology, 2017, 17(1): 120?126.

[11] Cadarso L. Integration of timetable planning and rolling stock in rapid transit networks[J]. Annals of Operations Research, 2012, 199(1): 113?135.

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

[13] 田晟, 馬美娜, 楊錦明. 基于大小交路優(yōu)化的地鐵行車組織方案[J]. 交通信息與安全, 2017, 35(1): 112?117. TIAN Sheng, MA Meina, YANG Jinming. An organizational scheme for metro traffic based on long-short route optimization[J]. Traffic Information and Safety, 2017, 35(1): 112?117.

[14] Alejandro T, Cristian E, Sergio J D. Optimal design and benefits of short turning strategy for a bus corridor[J]. Transportation, 2011, 38(1): 169?189.

[15] Canca D, Barrena E, Laporte G, et al. A short-turning policy for the management of demand disruptions in rapid transit systems[J]. Annals of Operations Research, 2016, 246(1/2): 145?166.

Optimization research of train schedule of Y-type train routing mode based on CCLPSO algorithm

TAN Li, WEI Ziwen

(School of Automation and Electrical Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China)

The train schedule usually includes train stop schedule plan, routing scheme and formation scheme. It is the basis of subway transportation. Combining the practical experience of transport organizations and the principle of the best match between transport capacity and passenger flow demand, taking the minimum value of passenger travel costs and corporate operating costs as the goals, considering the constraints of maximum rail capacity, minimum departure frequency and maximum available electric multiple units, a optimization model for city subway Y-type operation mode is constructed to determine the operation section of mainline and branch line and the train frequency on both lines in the Y-type operation mode. The commix classified learning particle swarm algorithm (CCLPSO) was used to solve the model. The rationality of the model and the effectiveness of the algorithm were verified by a practical case, and the sensitivity analysis of the turn-back station and frequency were conducted. The results show that the selection of turn-back station affects the cost of waiting time of passengers significantly, the comprehensive cost can be reduced by 16.9% and 31.6% by comparing with the other two algorithms, respectively.

urban rail traffic; train schedule; commix particle swarm algorithm; classified learning

U2-9；TP312

A

1672 ? 7029(2019)08? 2122 ? 08

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

2018?11?23

甘肅省教育廳自然科學基金資助項目(2017A-020)；中國鐵路總公司科技研究開發(fā)計劃項目(2017J012-A)

譚麗(1962?)，女，遼寧海城人，副教授，從事交通信息工程及控制研究；E?mail：2403323264@qq.com

(編輯 陽麗霞)