譚麗，韋子文

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

譚麗，韋子文

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

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

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

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

1 問題描述

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

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

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

2 建模

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

圖2 Y型交路基本模型

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

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

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

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

假設(shè)3 車底周轉(zhuǎn)方式獨(dú)立運(yùn)用，并且列車選型相同；

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

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

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

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

2.2 乘客出行成本

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

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

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

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

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

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

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

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

2.3 企業(yè)運(yùn)營成本

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

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

2.3.1 車輛購置成本

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

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

2.3.2 列車運(yùn)行耗費(fèi)成本

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

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

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

本文采用理想點(diǎn)法將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題。構(gòu)建優(yōu)化模型如式(11)所示：

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

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

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

3.1 標(biāo)準(zhǔn)粒子群算法

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

3.2 分類學(xué)習(xí)混合粒子群算法

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

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

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

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

3.3 算法求解流程

該改進(jìn)算法的求解流程如圖3所示。

圖3 算法流程圖

3.4 數(shù)值試驗(yàn)

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

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

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

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

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

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

4 案例研究與仿真

4.1 參數(shù)設(shè)置

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

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

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

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

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

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

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

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

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

4.3 靈敏度分析

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

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

圖9 支線頻率靈敏度分析

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

5 結(jié)論

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

2) 設(shè)計(jì)分類學(xué)習(xí)混合粒子群算法(CCLPSO)求解該模型。

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

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

[2] 王永亮, 張星臣, 蔣洋, 等. 城市軌道交通網(wǎng)絡(luò)運(yùn)營魯棒性[J]. 北京工業(yè)大學(xué)學(xué)報(bào), 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]. 北京: 北京交通大學(xué), 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] 陳玥. 城市軌道交通列車運(yùn)行交路方案研究[D]. 北京:北京交通大學(xué), 2016. CHEN Yue. Study on train routing scheme of urban rail transit[D]. Beijing: Beijing Jiaotong University, 2016.

[7] 雷明, 孟學(xué)雷. 基于協(xié)同進(jìn)化遺傳算法的高速鐵路運(yùn)行調(diào)整研究[J]. 鐵道科學(xué)與工程學(xué)報(bào), 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] 張凱, 宋錦春, 李松, 等. 基于分類學(xué)習(xí)粒子群優(yōu)化算法的液壓矯直機(jī)控制[J]. 機(jī)械工程學(xué)報(bào), 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].北京: 北京交通大學(xué), 2006. LI Aiju. Study on the maximum algebraic model of urban rail transit system[D]. Beijing: Beijing Jiaotong University, 2006.

[10] 許得杰, 毛保華, 雷蓮桂. 城市軌道交通大小交路列車開行方案優(yōu)化研究[J]. 交通運(yùn)輸系統(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] 王媛媛, 倪少權(quán). 城市軌道交通大小交路模式列車開行方案的優(yōu)化[J]. 鐵道學(xué)報(bào), 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

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

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

(編輯 陽麗霞)