網(wǎng)絡(luò)化城市軌道交通時刻表換乘協(xié)調(diào)優(yōu)化研究

白廣爭， 郭 進(jìn)，石紅國，楊 揚(yáng)，張?zhí)?/p>

(1.西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，四川 成都 610031；2.西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 610031；3.成都地鐵運(yùn)營有限公司,四川 成都 610031)

隨著城市內(nèi)軌道交通線路的不斷增加，網(wǎng)絡(luò)化運(yùn)營模式已經(jīng)成為一種趨勢，網(wǎng)絡(luò)中線路之間的相互影響也越來越顯著。為了減少乘客在換乘站的滯留時間，需要對各線路的行車組織進(jìn)行合理規(guī)劃，加強(qiáng)線路間列車運(yùn)行的銜接協(xié)調(diào)，進(jìn)而提高整個軌道交通網(wǎng)絡(luò)客流的暢通性。因此，優(yōu)化換乘站列車的銜接關(guān)系，對提高乘客換乘效率、降低乘客出行時間及提高乘客服務(wù)水平具有重要意義。

單個換乘站的協(xié)調(diào)是根據(jù)換乘站內(nèi)客流到達(dá)特征，對經(jīng)過該站的各方向列車的到發(fā)時刻進(jìn)行協(xié)調(diào)，使其形成良好的接續(xù)關(guān)系[1-7]，從而實(shí)現(xiàn)降低換乘站乘客候車時間的目的。而在網(wǎng)絡(luò)化的運(yùn)營環(huán)境中，由于列車在線路上各站之間的運(yùn)行時間及各車站的停站時間具有相對確定性，雖可適當(dāng)調(diào)整，但調(diào)整幅度有限，因此，列車在不同換乘站的到發(fā)時刻之間存在一定的相互制約關(guān)系。針對單個換乘站的協(xié)調(diào)優(yōu)化結(jié)果放在網(wǎng)絡(luò)中會出現(xiàn)運(yùn)行時間沖突的問題，要求換乘站之間的協(xié)調(diào)與換乘站內(nèi)各運(yùn)行方向上的銜接協(xié)調(diào)結(jié)合起來，才能制定出行之有效的優(yōu)化方案。

在網(wǎng)絡(luò)化的運(yùn)營條件下，既要考慮單線路的行車條件要求，將協(xié)調(diào)對單線路的行車組織影響降至最低，又要實(shí)現(xiàn)全路網(wǎng)乘客換乘等待時間最少，因此，城市軌道交通時刻表換乘協(xié)調(diào)工作是一個多目標(biāo)多約束問題。本文分析單個換乘站中各方向運(yùn)行列車的接續(xù)問題，得出換乘站客流的總換乘等待時間計算方法；考慮在網(wǎng)絡(luò)化運(yùn)行條件下?lián)Q乘站間列車運(yùn)行時間的調(diào)整問題，以網(wǎng)絡(luò)中乘客總換乘等待時間最少及換乘站間列車運(yùn)行時間調(diào)整最小為目標(biāo)，建立多目標(biāo)優(yōu)化模型；設(shè)計非支配排序進(jìn)化算法(Non-dominated Sorting Genetic Algorithm Ⅱ，NSGA-Ⅱ) 求解問題，并通過實(shí)例進(jìn)行驗(yàn)證。

1 條件假設(shè)與符號說明

1.1 條件假設(shè)

設(shè)所協(xié)調(diào)時段為[ta，tb]，為了降低問題復(fù)雜性，對運(yùn)行條件作如下假設(shè)：

(1)線路上、下行列車獨(dú)立運(yùn)行，各自到達(dá)與離開換乘站的時刻相互沒有制約關(guān)系。

(2)乘客均能乘上所遇到的第一趟換乘列車，不會因?yàn)閾頂D而錯過，即運(yùn)能是充足的。

(3)協(xié)調(diào)時段內(nèi)，各線路列車采取均衡行車方式。

(4)同一線路的上、下行之間不產(chǎn)生換乘關(guān)系。

(5)列車的區(qū)間運(yùn)行時間與車站停站時間可做適當(dāng)調(diào)整。

1.2 符號說明

為了方便問題描述，對網(wǎng)絡(luò)中某一個確定換乘站的運(yùn)行參數(shù)作如下符號說明。

Rij：線路i的j方向，j=1，2。其中j=1表示上行；j=2表示下行；i=1，2，…，n。其中n為經(jīng)過該換乘站的線路數(shù)。

nijs：[ta，tb]內(nèi)，Rij方向上共開行的列車對數(shù)。

Aij：[ta，tb]內(nèi)Rij上各列車到達(dá)該換乘站的時刻集合。

Dij：[ta，tb]內(nèi)Rij上各列車在該換乘站的停站時間集合。

Lij：[ta，tb]內(nèi)Rij上各列車駛離該換乘站的時刻集合。

hij：[ta，tb]內(nèi)Rij上各列車的行車間隔。

M：[ta，tb]內(nèi)該換乘站所有接續(xù)關(guān)系的集合。即：M={Rij→Rpq︱i≠p；i，p∈{1，2，…，n}；j，q∈{1，2}}。

對于網(wǎng)絡(luò)化環(huán)境中，運(yùn)行參數(shù)做如下設(shè)定：

U：網(wǎng)絡(luò)中換乘站集合，存在Um、Un∈U。

S：網(wǎng)絡(luò)中換乘站總個數(shù)。

2 單個換乘站乘客換乘等待時間計算

列車在線路上采取等間隔方式運(yùn)行，則會在換乘站內(nèi)形成穩(wěn)定的“銜接周期”[1]，即當(dāng)相交的兩條線路上列車行車間隔分別為h1和h2時，則這兩條線路在換乘站內(nèi)以lcm(h1，h2)為周期形成銜接關(guān)系。文獻(xiàn)[1]分析了“銜接周期”內(nèi)乘客換乘總候車時間的計算方法，并以該值最小為優(yōu)化目標(biāo)。但是，在實(shí)際運(yùn)營過程中，每趟列車帶來的換乘客流量各不相同，乘客在每個“銜接周期”內(nèi)的到站量分布并不一定相同，因此，在一個“銜接周期”內(nèi)乘客換乘總候車時間最少并不能代表在其他“銜接周期”內(nèi)的換乘乘客總等待時間也最少。因此，本文計算協(xié)調(diào)時段換乘站內(nèi)所有換乘乘客的總候車時間，并做為網(wǎng)絡(luò)化運(yùn)營協(xié)調(diào)的基礎(chǔ)。

為了計算單個換乘站內(nèi)乘客的總換乘候車時間，首先應(yīng)確定與換乘站相關(guān)的列車運(yùn)行基本參數(shù)，包括到發(fā)時刻的表示及各參數(shù)受到的約束；然后計算一個換乘接續(xù)方向上所有乘客的換乘等待時間；最后，對各接續(xù)方向乘客換乘候車時間求和，即可得出換乘站中所有換乘乘客的候車時間表達(dá)式。

2.1 換乘站列車到發(fā)時刻分析

nij=0，1，2，…，nijs-1

( 1 )

式( 1 )中，nij滿足

( 2 )

( 3 )

根據(jù)Rij上列車的離站時刻集合Lij和列車停站時間集合Dij，可以確定列車的到站時刻集合Aij為

( 4 )

2.2 線路間換乘接續(xù)關(guān)系分析

( 5 )

相鄰兩趟列車離站時刻滿足

( 6 )

( 7 )

( 8 )

2.3 換乘站內(nèi)乘客總候車時間計算

以上求得一個換乘接續(xù)方向上所有換乘乘客的候車時間。而在換乘站中通常會存在多個換乘接續(xù)方向，因此，對各接續(xù)方向乘客候車時間求和可得站內(nèi)乘客換乘總候車時間為

( 9 )

3 網(wǎng)絡(luò)化運(yùn)營條件下列車運(yùn)行協(xié)調(diào)優(yōu)化

網(wǎng)絡(luò)化運(yùn)營條件下，換乘站的協(xié)調(diào)比單個換乘站的協(xié)調(diào)優(yōu)化問題增加了換乘站之間列車運(yùn)行時間及停站時間的影響，根據(jù)第2節(jié)研究所得出的單個換乘站列車離站時刻協(xié)調(diào)結(jié)果，放在網(wǎng)絡(luò)中往往會造成換乘站之間運(yùn)行時間的沖突，列車在線路上運(yùn)行，無法同時滿足多個換乘站各自計算的離站時刻要求。為了協(xié)調(diào)換乘站之間的離站時刻，需要對線路上車站間的運(yùn)行時間及各站停站時間做一定調(diào)整。由于平峰時段網(wǎng)絡(luò)中各線路行車間隔基本較大，因此適當(dāng)調(diào)整列車站間運(yùn)行時間和停站時間的方案是可行的。調(diào)整的依據(jù)是相鄰換乘站Um、Un之間的運(yùn)行時間TUm→Un和TUn→Um，使其滿足

(10)

或者

(11)

圖1 換乘站位置關(guān)系

TUm→Un由Um→Un的車站停車時間和區(qū)間運(yùn)行時間組成，即

(12)

TUn→Um同理可得

(13)

(14)

(15)

為了避免調(diào)整對原有運(yùn)行時間的影響過大，要求列車運(yùn)行參數(shù)調(diào)整的幅度越小越好。

根據(jù)以上分析可以得出，網(wǎng)絡(luò)條件下運(yùn)行協(xié)調(diào)的第一目標(biāo)是使得整個網(wǎng)絡(luò)中在協(xié)調(diào)時段內(nèi)乘客總換乘等待時間最小，如式(16)所示，即

Obj 1:

(16)

協(xié)調(diào)的第二目標(biāo)是換乘站站間運(yùn)行時間及停站時間調(diào)整最少，以調(diào)整后與調(diào)整前的運(yùn)行時間方差來表示，則運(yùn)行調(diào)整應(yīng)滿足

Obj 2:

(17)

式中：TUm→Un(0)表示調(diào)整前相鄰換乘站之間列車的運(yùn)行時間；TUm→Un表示調(diào)整后相鄰換乘站之間列車的運(yùn)行時間；lx表示共需要調(diào)整的換乘站間運(yùn)行時間的數(shù)量。

根據(jù)以上分析，得出網(wǎng)絡(luò)條件下線路間銜接性協(xié)調(diào)優(yōu)化模型。其中式(16)、式(17)為模型目標(biāo)，式( 1 )～式(15)為模型約束條件及參數(shù)間關(guān)系描述。在求解目標(biāo)(16)的過程中參考第2節(jié)單個換乘站乘客等待時間的求解過程。

4 算法設(shè)計

網(wǎng)絡(luò)化換乘站協(xié)調(diào)優(yōu)化模型包含兩個目標(biāo)，屬于多目標(biāo)優(yōu)化問題(MOP)。在求解MOP時，通常采用兩類方法：其一為首先按照某種策略確定多種目標(biāo)之間的權(quán)重，然后將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題的傳統(tǒng)求解方法，如加權(quán)求和法、理想點(diǎn)法等，最終求解單目標(biāo)的優(yōu)化解；其二為采用一些近代智能搜索算法，如NSGA、NSGA-Ⅱ、PAES、PESA、SPEA等，通過搜索多個目標(biāo)的非劣(又稱Pareto)解，找出可接受的“不壞”解[8]供決策者參考，實(shí)現(xiàn)多目標(biāo)優(yōu)化。多目標(biāo)優(yōu)化問題一般不存在單個最優(yōu)解，而是一個Pareto解集。在眾多的多目標(biāo)進(jìn)化算法中，NSGA-Ⅱ算法是目前處理2～3個優(yōu)化目標(biāo)中最優(yōu)秀的算法之一，本文設(shè)計NSGA-Ⅱ算法求解。

采用實(shí)數(shù)編碼方式，編碼對象為各個換乘站內(nèi)的各方向上列車在協(xié)調(diào)時段內(nèi)的初始離站時刻，進(jìn)化過程中的選擇操作設(shè)置為二元錦標(biāo)賽模式，賽制規(guī)模取2。為了簡化設(shè)計，本文采取算術(shù)交叉策略，設(shè)計交叉策略為[9]

(18)

分別采取均勻變異策略和非均勻變異策略為[10]

(19)

(20)

Δ(g，y)=y×γ×(1-g/G)b

式中：b為形參，其值可取2～5，本算法中取2；γ為[0，1]的隨機(jī)數(shù)，在計算過程中隨機(jī)產(chǎn)生；G為終止代數(shù)，在本文算例中取200。

5 案例分析

5.1 初始數(shù)據(jù)設(shè)置

某城市軌道交通網(wǎng)絡(luò)如圖2所示，由3條線路構(gòu)成，即R1，R2，R3。3條線路存在5個換乘車站a，b，c，d，e，其中R1與R2相交于換乘車站c，R1與R3相交于換乘車站b，d，R2與R3相交于換乘車站a，e。規(guī)定各線路運(yùn)行時間如網(wǎng)絡(luò)圖中所示，例如線路R1中，由換乘站b出發(fā)到離開換乘站c的運(yùn)行時間tbc=9.5 min，由換乘站c出發(fā)到離開換乘站d的運(yùn)行時間tcd=7.3 min。為了計算方便，設(shè)定調(diào)整前相同兩換乘站之間列車上行運(yùn)行時間與下行運(yùn)行時間相同。

圖2 城市軌道交通網(wǎng)絡(luò)

以10:00～12:00為例，設(shè)置換乘客流量見表1，單元格中的數(shù)據(jù)表示相交于對應(yīng)換乘站的兩線路所在行方向的一列車所帶來的要換乘到所在列方向的客流量。

各線路上列車采取均衡行車方式， 且同一線路的上、下行行車間隔相同，R1、R2、R3行車間隔分別設(shè)置為h1=360 s，h2=330 s，h3=300 s。各車站各方向乘客換乘走行時間均設(shè)置為100 s。各換乘站對應(yīng)線路上列車的停車時間設(shè)置見表2。

表1 每列車運(yùn)送的換乘客流量數(shù)據(jù) 人

表2 各換乘站停站時間 s

根據(jù)圖2線路網(wǎng)絡(luò)所示，各線路上、下行方向在換乘站的離站時刻共有20個，因此，決策變量個數(shù)為20，采用實(shí)數(shù)編碼方式的染色體設(shè)置見表3。

表3 實(shí)數(shù)編碼染色體設(shè)置

每一代的種群規(guī)模設(shè)置為200，交叉概率取0.9，變異概率取0.1[11]。分別采取均勻變異策略和非均勻變異策略以驗(yàn)證計算結(jié)果。

5.2 計算結(jié)果及分析

通過均勻變異和非均勻變異兩種方法計算，求得Pareto解集近似相同，圖3顯示了非均勻變異的計算結(jié)果。

圖3 非均勻變異運(yùn)算結(jié)果

圖3顯示的計算結(jié)果均為優(yōu)化解，根據(jù)圖3所示， 模型的兩個目標(biāo)存在“此消彼長”的博弈。若增大站間

運(yùn)行時間的調(diào)整幅度，即目標(biāo)f2增大，則乘客的換乘等待時間f1減小；相反，若目標(biāo)f2減小，則目標(biāo)f1增大。表4列出了兩組調(diào)整方案，分別對應(yīng)以上兩種情況。

具體選擇哪一組結(jié)果做調(diào)整方案，則由決策者根據(jù)以下情況判斷：若期望調(diào)整對單線路的原有時刻表影響較小，即換乘站間列車運(yùn)行時間調(diào)整幅度較小，則選擇圖3中偏右下方的優(yōu)化解，例如表4中第1組優(yōu)化解；而若更看重網(wǎng)絡(luò)乘客的整體換乘時間優(yōu)化，則選擇圖3中偏左上方的優(yōu)化解，例如表4中第2組優(yōu)化解。

為了檢驗(yàn)優(yōu)化效果，將模型的目標(biāo)1網(wǎng)絡(luò)乘客換乘總等待時間修改為取倒數(shù)后再求最小值，目標(biāo)2不變，仍采用本文算法求解，對計算結(jié)果的目標(biāo)1再取倒數(shù)變換后，由此得出一些站間運(yùn)行時間調(diào)整幅度近似情況下的較劣運(yùn)行時刻協(xié)調(diào)結(jié)果。表5列出了其中的一組較劣解，該組解與表4中的第1組解對比，全網(wǎng)換乘等待時間延長了約6.4%，與表4中的第2組解對比，換乘時間延長了約11.3%。

表4 兩組優(yōu)化解

表5 一組較劣解

6 結(jié)束語

本文分析了網(wǎng)絡(luò)化運(yùn)營條件下，線路間列車運(yùn)行協(xié)調(diào)優(yōu)化問題。針對平峰時段，以網(wǎng)絡(luò)中乘客總換乘候車時間最少及路網(wǎng)列車運(yùn)行參數(shù)調(diào)整幅度最小為目標(biāo)建立多目標(biāo)優(yōu)化模型。設(shè)計了NSGA-Ⅱ算法，并對案例求解，結(jié)果驗(yàn)證了本模型能夠有效減少乘客的換乘等待時間。研究過程及結(jié)論可為網(wǎng)絡(luò)化的運(yùn)行協(xié)調(diào)工作提供參考。

參考文獻(xiàn)：

[1]張銘,杜世敏.基于遞階偏好的軌道交通網(wǎng)絡(luò)化運(yùn)營換乘協(xié)調(diào)優(yōu)化[J].鐵道學(xué)報,2009,31(6):9-14.

ZHANG Ming,DU Shimin.Transfer Coordination Optimization for Network Operation of Urban Rail Transit Based on Hierarchical Preference[J].Journal of the China Railway Society,2009,31(6):9-14.

[2]周艷芳,周磊山,樂逸祥.城市軌道網(wǎng)絡(luò)換乘站列車銜接同步協(xié)調(diào)優(yōu)化研究[J].鐵道學(xué)報,2011,33(3):9-16.

ZHOU Yanfang,ZHOU Leishan,YUE Yixiang.Synchronized and Coordinated Train Connection Optimization for Transfer Stations of Urban Rail Networks[J].Journal of the China Railway Society,2011,33(3):9-16.

[3]徐瑞華,張銘,江志彬.基于線網(wǎng)運(yùn)營協(xié)調(diào)的城市軌道交通首末班列車發(fā)車時間域研究[J].鐵道學(xué)報,2008,30(2):7-11.

XU Ruihua,ZHANG Ming,JIANG Zhibin.Study on Departure Time Domain of the First and Last Trains of Urban Mass Transit Network Based on Operation Coordination[J].Journal of the China Railway Society,2008,30(2):7-11.

[4] RACHEL C W.Optimizing Timetable Synchronization for Rail Mass Transit[J].Transportation Science,2008,42(1):57-69.

[5] CUUNG M K,CHANG C S.Timetable Synchronization of Mass Rapid Transit System Using Multiobjective Evolutionary Approach[J].IEEE Transactions on Systems,Man,and Cybernetics,2008,38(5):636-648.

[6]孫鵬,趙佳虹,丁宏飛.基于換乘協(xié)調(diào)的城市軌道交通列車開行方案優(yōu)化[J].鐵道運(yùn)輸與經(jīng)濟(jì),2011,33(12):67-70.

SUN Peng,ZHAO Jiahong,DING Hongfei.The Optimization of Urban Rail Transit Operation Scheme based on Coordinated Transfer[J].Railway Transport and Economy,2011,33(12):67-70.

[7]白廣爭,郭進(jìn),石紅國,等.基于離站時刻協(xié)調(diào)的地鐵換乘站列車銜接優(yōu)化研究[J].交通運(yùn)輸系統(tǒng)工程與信息,2013,13(5):134-139,201.

BAI Guangzheng,GUO Jin,SHI Hongguo,et al.Optimization of Convergence Based on the Coordination of Train Departure Time in Transfer Station[J].Journal of Transportation Systems Engineering and Information Technology,2013,13(5):134-139,201.

[8]雷德明,嚴(yán)新平.多目標(biāo)智能優(yōu)化算法及其應(yīng)用[M].北京:科學(xué)出版社,2009.

[9]陳小平,于盛林.實(shí)數(shù)遺傳算法的交叉策略的改進(jìn)[J].電子學(xué)報,2003(1):71-74.

CHEN Xiaoping,YU Shenglin.Improvement on Crossover Strategy of Real-valued Genetic Algorithm[J].Acta Electronica Sinica,2003(1):71-74.

[10]朱燦.實(shí)數(shù)編碼遺傳算法機(jī)理分析及算法改進(jìn)研究[D].長沙：中南大學(xué),2009.

[11]徐宗本.計算智能(第一冊)——模擬進(jìn)化算法[M].北京:高等教育出版社,2005.