城市軌道交通同步協(xié)調(diào)的優(yōu)化模型

曹志超　袁振洲　李得偉

(1北京交通大學(xué)城市交通復(fù)雜系統(tǒng)理論與技術(shù)教育部重點實驗室，北京　100044)(2北京交通大學(xué)軌道交通控制與安全國家重點實驗室，北京　100044)

?

城市軌道交通同步協(xié)調(diào)的優(yōu)化模型

曹志超1，2袁振洲1李得偉2

(1北京交通大學(xué)城市交通復(fù)雜系統(tǒng)理論與技術(shù)教育部重點實驗室，北京100044)
(2北京交通大學(xué)軌道交通控制與安全國家重點實驗室，北京100044)

摘要:為實現(xiàn)換乘客流的無縫銜接和列車到發(fā)的同步協(xié)調(diào)，以總換乘等車時間最少為目標，將列車行車間隔、客流劃分結(jié)果和等車時間作為主要輸入條件，構(gòu)建了帶有0-1決策變量的城市軌道交通同步協(xié)調(diào)優(yōu)化模型．運用改進的遺傳算法與計算機模擬相結(jié)合的方法有效解決了模型的求解問題．最后，以北京市城市軌道交通為例進行仿真，輸出整點發(fā)車和非整點發(fā)車條件下的2種優(yōu)化方案．結(jié)果表明，整點發(fā)車方案和非整點發(fā)車方案的總換乘等車時間較基礎(chǔ)方案分別縮短2．26%和2．48%，單個車站的最大換乘等車時間分別節(jié)省了7．90%和12．87%．該優(yōu)化模型能夠有效縮短乘客的換乘等車時間，提高城市軌道交通的服務(wù)水平．

關(guān)鍵詞:城市軌道交通;同步協(xié)調(diào);列車時刻表;無縫銜接;換乘等車時間

引用本文:曹志超，袁振洲，李得偉．城市軌道交通同步協(xié)調(diào)的優(yōu)化模型［J］．東南大學(xué)學(xué)報(自然科學(xué)版)，2016，46(1) : 221－225．DOI: 10．3969/j．issn．1001－0505．2016．01．036．

列車時刻表編制是城市軌道交通運輸計劃的重要內(nèi)容．在網(wǎng)絡(luò)條件下，尤其是客流高峰期高密度行車環(huán)境下，實現(xiàn)列車到發(fā)的同步協(xié)調(diào)，減少乘客因換乘而導(dǎo)致的等車時間是列車時刻表優(yōu)化的重要目標．鑒于網(wǎng)絡(luò)條件下不同線路間換乘設(shè)施走行時間的動態(tài)性以及列車到發(fā)同步調(diào)整的復(fù)雜性，如何科學(xué)合理地優(yōu)化列車時刻表一直是學(xué)術(shù)界和軌道運營管理者們研究的熱點問題．

國外學(xué)者研究列車時刻表同步協(xié)調(diào)問題時主要采用以下2種方法:①基于客流分配的方法，其目標函數(shù)為最小化乘客總換乘等車時間．例如，Wong等［1］通過調(diào)整列車的在途時間、停站時間和發(fā)車間隔來實現(xiàn)目標優(yōu)化，基于0-1變量定義接駁成功的列車; Shafahi等［2］采用最小公約數(shù)的方法得到了多條換乘線路平均換乘等車時間，并通過引入額外等車時間以進一步優(yōu)化列車時刻表．②基于列車到發(fā)銜接的方法，其目標函數(shù)為最大化列車銜接的換乘同步成功的次數(shù)．此處，學(xué)者們對換乘同步成功的定義各不相同，Ceder等［3］提出的模型僅適用于簡單網(wǎng)絡(luò)，且求解為試算法，精確性較差; Ibarra-Rojas等［4］通過優(yōu)化提出了準確算法．

國內(nèi)關(guān)于同步協(xié)調(diào)優(yōu)化問題的相關(guān)研究較少，模型主要以換乘等車時間最小化為目標．周艷芳等［5］增加了換乘不滿意度最低的模型目標;曹志超等［6］增加了列車承載能力的約束．現(xiàn)階段研究尚無法實現(xiàn)全網(wǎng)絡(luò)交通的同步協(xié)調(diào)優(yōu)化．

本文基于正態(tài)分布的換乘客流到達規(guī)律，結(jié)合基本行車約束和準確劃分換乘客流的計算方法，構(gòu)建了帶有0-1決策變量的同步協(xié)調(diào)的優(yōu)化模型，并提出了求解算法．

1　模型構(gòu)建

1．1問題描述

令城市軌道交通列車運行網(wǎng)絡(luò)拓撲G = (L，S，Q)，其中，L = { 1，2，…，M}為線路集，S = { 1，2，…，N}為車站集，Q = { 1，2，…，B}為列車集．令研究時段為T．

換乘等車時間是指乘客因換乘的需要，從列車下車通過換乘設(shè)施到達接駁列車的站臺開始，等待最近一班接駁列車所花費的時間．

2)當線路i上列車p到達車站n時，接駁列車2尚未發(fā)車，但乘客通過換乘設(shè)施后接駁列車2已發(fā)車，即，則換乘乘客不能上車．

3)乘客從線路i上列車p下車，通過換乘設(shè)施后，接駁列車4未發(fā)車，但之前已有列車3進行接駁，即為線路j上列車在車站n的停站時間，則列車p的換乘乘客不能被列車4接駁．

圖1　城市軌道交通2條線路同步協(xié)調(diào)換乘示意圖

列車接駁成功是指乘客到達接駁列車所在站臺后發(fā)現(xiàn)列車恰好在停車等待．基于上述分析，列車接駁成功的條件須嚴格滿足

1．2目標函數(shù)

基于給定的換乘客流量，模型以最小化乘客的總換乘等車時間為目標，即

1．3約束條件

1．3．1行車約束

列車時刻表的編制應(yīng)滿足基本行車約束，如安全追蹤間隔約束、首末班車出發(fā)時刻約束、列車到發(fā)時刻與發(fā)車間隔的運算關(guān)系約束等［7－9］．

連續(xù)2班列車的出發(fā)時刻應(yīng)滿足列車安全追蹤間隔時間約束，即

式中，H為列車安全追蹤間隔時間．

首末班車的出發(fā)時刻須控制在研究時段的第1個和最后1個發(fā)車間隔區(qū)間內(nèi)．假定研究時段T內(nèi)，線路i上列車發(fā)車間隔hi固定不變，則

列車發(fā)車間隔的運算關(guān)系為

1．3．2客流劃分

由于組成客流的乘客個體具有異質(zhì)性，不同乘客具有不同的年齡、性別、結(jié)伴特征及攜帶行李特征，因此，即使同一班列車的客流通過換乘設(shè)施，不同乘客個體到達換乘站臺的時間也存在一定差異．令客流在換乘設(shè)施的走行時間域為其中分別為車站n處乘客從線路i換乘到線路j走行時間的最小值和最大值，且

可得

換乘走行時間將影響接駁列車的上車人數(shù)，具體可分為以下2種情況:

1)所有下車乘客均成功換乘到某一列車(見圖2(a) )．從列車p下車的換乘乘客中，步行時間最長的乘客在接駁列車q發(fā)車之前到達，即滿足

2)換乘乘客走行速度不一，速度較快的乘客換乘到某一列車，剩余乘客換乘到下一列車(見圖2(b) )．換乘客流被劃分為2個部分．速度較快的客流可以換乘到列車q，對應(yīng)于圖2(b)中左側(cè)陰影部分，客流量表示為剩余客流需多等待一個發(fā)車間隔hi，客流量表示為即

換乘客流量計算公式為

式中，Φ為正態(tài)分布的概率．

圖2　客流劃分示意圖

1．3．3等車時間

基于客流劃分的結(jié)果，不同情況下客流換乘的列車不同，其等車時間計算方法也不同，具體如下:

情況1

情況2

2　求解算法

則目標函數(shù)可轉(zhuǎn)化為

本文采用改進的遺傳算法求解以上模型．其核心思想為:選取i∈L，j∈L時首班列車出發(fā)時刻為00: 00的方案作為基礎(chǔ)方案，并將其作為初始解，迭代求較優(yōu)解;令線路上的首班列車出發(fā)時刻為決策變量．具體求解步驟如下:

②基因設(shè)置．運營線分上行和下行，故染色體集合為2M．選擇所有線路上的首班列車出發(fā)時刻組成的集合作為基因．根據(jù)約束(2)～(7)，求得城市軌道網(wǎng)絡(luò)中所有列車在每個站的到發(fā)時刻．

③適應(yīng)度函數(shù)．將模型目標函數(shù)作為適應(yīng)度函數(shù)，即

④交叉與變異．在發(fā)車間隔［0，hi］內(nèi)對

進行隨機取值，分別進行客流劃分計算和等車時間計算，求得適應(yīng)度值Z．比較Z與Zt，如果Z值更優(yōu)，則記錄Zt= Z;否則，繼續(xù)迭代尋找，且t = t +1．

⑤較優(yōu)解．在限定的時間或迭代次數(shù)內(nèi)，適應(yīng)度值已收斂且不能更優(yōu)，則停止迭代，認為為較優(yōu)解．

3　算例

北京市城市軌道交通某運營期內(nèi)開行16條雙向線路，共設(shè)235個車站，其中38個為換乘站．假設(shè)各運營線的列車在途時間和停站時間均已知．選取的研究時段T為高峰時段中的1 h．根據(jù)本文所提模型，利用Matlab軟件對問題進行求解．分別將整數(shù)決策變量和實數(shù)決策變量作為整點發(fā)車方案和非整點發(fā)車方案進行優(yōu)化，其優(yōu)化單位分別為60和1 s．通過對算法中迭代參數(shù)的不斷試驗和模擬，在個體數(shù)量為20、代溝為0．8、變異率為0．5的1 000次迭代中求得較優(yōu)解．2種方案的優(yōu)化結(jié)果與基礎(chǔ)方案結(jié)果的對比見表1．基礎(chǔ)方案、整點發(fā)車方案和非整點發(fā)車方案的總換乘等車時間分別為735 112，718 838，717 311 min．對比發(fā)現(xiàn)，在總換乘等車時間上，整點發(fā)車方案和非整點發(fā)車方案比基礎(chǔ)方案分別節(jié)省了16 274和17 801 min，較基礎(chǔ)方案分別優(yōu)化了2．21%和2．42%．

表1　北京市城市軌道交通列車時刻表優(yōu)化結(jié)果

進一步對比全網(wǎng)5個換乘量最大的車站的總換乘等車時間，結(jié)果見圖3．由圖可知，各換乘站的總換乘等車時間均減少．以換乘客流量最大的車站西直門站為例，與基礎(chǔ)方案相比，整點發(fā)車方案和非整點發(fā)車方案的最大換乘等車時間分別節(jié)省了7．90%和12．87%．

研究發(fā)現(xiàn)，通過優(yōu)化城市軌道交通的列車時刻表，能夠有效縮短乘客的換乘等車時間，增加換乘線路間列車的接駁成功次數(shù)，實現(xiàn)更多換乘乘客的無縫銜接，從而提高城市軌道交通的換乘效率和乘客服務(wù)水平．

圖3　不同換乘站的換乘等車時間

4　結(jié)語

城市軌道交通的同步協(xié)調(diào)控制是列車時刻表編制的重要內(nèi)容，是網(wǎng)絡(luò)化運輸組織協(xié)調(diào)性的具體體現(xiàn)．本文對城市軌道交通換乘站的換乘客流進行了準確劃分，提出了針對性的換乘等車時間計算方法，構(gòu)建了以乘客總換乘等車時間最少為目標的列車時刻表優(yōu)化模型，解決了既有研究換乘走行時間計算誤差大或換乘客流劃分模糊的問題，從而使計算更加高效和準確．實例證明，利用所提模型可實現(xiàn)換乘站列車的同步到發(fā)和網(wǎng)絡(luò)的協(xié)調(diào)控制，有效縮短了乘客的換乘等車時間，提高了城市軌道交通的服務(wù)水平．本文所研究的場景主要針對發(fā)車間隔不變的條件，對于動態(tài)發(fā)車間隔條件下的列車時刻同步問題將是下一步的研究內(nèi)容．

參考文獻(References)

［1］Wong R C W，Yuen T W Y，F(xiàn)ung K W，et al．Optimizing timetable synchronization for rail mass transit ［J］．Transportation Science，2008，42(1) : 57－69．DOI: 10．1287/trsc．1070．0200．

［2］Shafahi Y，Khani A．A practical model for transfer optimization in a transit network: Model formulations and solutions［J］．Transportation Research Part A: Policy and Practice，2010，44(6) : 377－389．DOI: 10．1016/ j．tra．2010．03．007．

［3］Ceder A，Golany B，Tal O．Creating bus timetables with maximal synchronization［J］．Transportation Research Part A: Policy and Practice，2001，35 (10) : 913－928．

［4］Ibarra-Rojas O J，Rios-Solis Y A．Synchronization of bus timetabling［J］．Transportation Research Part B: Methodological，2012，46 (5) : 599－614．DOI: 10．1016/j．trb．2012．01．006．

［5］周艷芳，周磊山，樂逸祥．城市軌道網(wǎng)絡(luò)換乘站列車銜接同步協(xié)調(diào)優(yōu)化研究［J］．鐵道學(xué)報，2011，33 (3) : 9－16．DOI: 10．3969/j．issn．1001－8360．2011．03．002．Zhou Yanfang，Zhou Leishan，Yue Yixiang．Synchronized and coordinated train connecting optimization for transfer stations of urban rail networks［J］．Journal of the China Railway Society，2011，33(3) : 9－16．DOI: 10．3969/j．issn．1001－8360．2011．03．002．(in Chinese)

［6］曹志超，袁振洲，李得偉，等．結(jié)合列車時間表的地鐵換乘同步性優(yōu)化［J］．現(xiàn)代城市軌道交通，2014 (5) : 59－62，74．DOI: 10．3969/j．issn．1672－7533．2014．05．016．Cao Zhichao，Yuan Zhenzhou，Li Dewei，et al．Optimization for metro interchange synchronization with consideration of train timetable［J］．Modern Urban Transit，2014(5) : 59－62，74．DOI: 10．3969/j．issn．1672－7533．2014．05．016．(in Chinese)

［7］Ceder A，Marguier P H J．Passenger waiting time at transit stops［J］．Traffic Engineering and Control，1985，26(6) : 327－329．

［8］Niu H，Zhou X．Optimizing urban rail timetable under time-dependent demand and oversaturated conditions ［J］．Transportation Research Part C: Emerging Technologies，2013，36: 212－230．DOI: 10．1016/j．trc．2013．08．016．

［9］李得偉，韓寶明，李曉娟，等．基于節(jié)點服務(wù)的高速鐵路列車停站方案優(yōu)化模型［J］．鐵道學(xué)報，2013，35 (6) : 1－5．DOI: 10．3969/j．issn．1001－8360．2013．06．001．Li Dewei，Han Baoming，Li Xiaojuan，et al．Highspeed railway stopping schedule optimization model based on node service［J］．Journal of the China Railway Society，2013，35 (6) : 1－5．DOI: 10．3969/j．issn．1001－8360．2013．06．001．(in Chinese)

［10］Liu Z，Shen J，Wang H，et al．Regional bus timetabling model with synchronization［J］，Journal of Transportation Systems Engineering＆Information Technology，2007，7(2) : 109－112．DOI: 10．1016/ S1570－6672(07) 60018-X．

Synchronization and coordination optimization model of urban rail transit

Cao Zhichao1，2Yuan Zhenzhou1Li Dewei2
(1MOE Key Laboratory for Urban Transportation Complex Systems Theory and Technology，Beijing 100044，China)
(2State Key Lab of Rail Traffic Control and Safety，Beijing Jiaotong University，Beijing 100044，China)

Abstract:In order to achieve the seamless connections of passengers and the synchronization and coordination of arrival and departure of trains，a synchronization and coordination optimization model of urban rail transit(URT) with 0-1 binary decision variables was proposed．The objective is the minimization of the total transfer waiting time and the inputs are the running interval，the results of passenger division and the waiting time．The model was solved by combining the improved genetic algorithm with computer simulation．Finally，Beijing URT was simulated for case study．Two optimization strategies，the minute-departure scheme and the second-departure scheme，were described．The results show that compared with the traditional scheme，the total waiting time of the transfer passengers of the minute-departure scheme and the second-departure scheme is decreased by 2．26% and 2．48%．The maximum transfer waiting time at one station is reduced by 7．90% and 12．87%．The proposed model is effective to decrease the transfer waiting time and to improve the service level．

Key words:urban rail transit; synchronization and coordination; timetable; seamless connection; transfer waiting time

基金項目:國家重點基礎(chǔ)研究發(fā)展計劃(973計劃)資助項目(2012CB725403)、北京市自然科學(xué)基金資助項目(9132015)、教育部高等學(xué)?；究蒲袠I(yè)務(wù)費資助項目(2014JBZ008)、北京高等學(xué)校青年英才計劃資助項目(YETP0555)、北京交通大學(xué)軌道交通控制與安全國家重點實驗室自主課題資助項目(RCS2014ZTY1)．

收稿日期:2015-06-23．

作者簡介:曹志超(1988—)，男，博士生;袁振洲(聯(lián)系人)，男，博士，教授，博士生導(dǎo)師，zzyuan@ bjtu．edu．cn．

DOI:10．3969/j．issn．1001－0505．2016．01．036

中圖分類號:U121

文獻標志碼:A

文章編號:1001－0505(2016) 01-0221-05