地鐵線網(wǎng)末班列車時(shí)刻表協(xié)同編制優(yōu)化

楊艷

廣西交通技師學(xué)院，廣西 南寧 530001

0 引言

末班列車時(shí)刻表的編制方案是地鐵系統(tǒng)運(yùn)行組織工作的重要環(huán)節(jié)，其優(yōu)劣直接影響整體線網(wǎng)的運(yùn)營(yíng)效率與安全性，相應(yīng)優(yōu)化問題越來越被國(guó)內(nèi)外學(xué)術(shù)界和工程界重視[1]。國(guó)外研究多集中于城市軌道交通服務(wù)水平和運(yùn)營(yíng)指標(biāo)的改善，并充分結(jié)合現(xiàn)有的實(shí)踐策略和場(chǎng)景條件[2]。Kecman等[3]針對(duì)換乘限制條件設(shè)計(jì)了重分配優(yōu)化方法，D′Ariano等[4]基于運(yùn)營(yíng)體系服務(wù)水平和乘客滿意度提出了可變的列車時(shí)刻表方案，Corman等[5]在對(duì)服務(wù)區(qū)域進(jìn)行多樣化劃分的基礎(chǔ)上實(shí)現(xiàn)了列車調(diào)度和時(shí)刻表協(xié)同，Zhou等[6]分析了首班車和末班車之間的發(fā)車時(shí)刻影響。國(guó)內(nèi)相關(guān)研究多側(cè)重于修正建模和聚類建模方法，以組合優(yōu)化特性分析作為問題領(lǐng)域的研究熱點(diǎn)和重點(diǎn)[7]。徐文愷等[8]基于隨機(jī)延誤情景建立了城市軌道交通末班車時(shí)刻表調(diào)整模型，姚恩建等[9]考慮動(dòng)態(tài)可達(dá)性對(duì)城市軌道交通末班車時(shí)刻表進(jìn)行優(yōu)化，陳垚等[10]分析了換乘站停站時(shí)間延長(zhǎng)對(duì)末班列車時(shí)刻的影響，周瑋騰等[11]提出了城市軌道交通網(wǎng)絡(luò)時(shí)變路徑搜索算法。此外，還有學(xué)者對(duì)末班列車時(shí)刻表的路徑選址、能力限制等綜合性因素進(jìn)行了分析[12-14]。洪玲等[15]提出了基于換乘銜接的單線末班列車銜接方案優(yōu)化方法，徐瑞華等[16]分析了城市軌道交通網(wǎng)絡(luò)末班列車銜接方案的運(yùn)營(yíng)限制條件，寧麗巧等[17]研究了末班列車所處時(shí)段的可控影響因素，徐杰等[18]設(shè)計(jì)了對(duì)末班列車時(shí)刻表下的客流誘導(dǎo)系統(tǒng)?，F(xiàn)有研究對(duì)線網(wǎng)系統(tǒng)銜接程度的分析不夠深入，對(duì)優(yōu)化計(jì)算方法的探索不夠全面[19]。本文考慮末班列車銜接協(xié)同的實(shí)際因素，建立優(yōu)化模型，提出基于粒子群算法的計(jì)算流程，改進(jìn)銜接性能指標(biāo)，實(shí)現(xiàn)對(duì)地鐵末班列車時(shí)刻表編制方案的優(yōu)化。

1 地鐵末班列車時(shí)刻表協(xié)同優(yōu)化模型

編制地鐵末班列車時(shí)刻表應(yīng)著重考慮各線路銜接的時(shí)間協(xié)同要求，采用規(guī)劃模型形式明確目標(biāo)函數(shù)、決策變量和限制條件，最大程度實(shí)現(xiàn)接續(xù)系統(tǒng)化的線路組織方案[20]。

本文的優(yōu)化模型需考慮地鐵線網(wǎng)中換乘銜接成功的線路組合數(shù)量最多，即目標(biāo)函數(shù)為

(1)

式中：Xkmn為0-1二元變量，當(dāng)線路m的末班列車與線路n的末班列車在站點(diǎn)k處銜接成功時(shí)，xkmn=1，否則，xkmn=0;K為地鐵線網(wǎng)中站點(diǎn)集合；L為地鐵線網(wǎng)中線路集合。

線路m的末班列車到達(dá)站點(diǎn)k的時(shí)刻

(2)

線路n的末班列車于站點(diǎn)k的發(fā)車時(shí)刻

(3)

地鐵線網(wǎng)中的一對(duì)換乘接續(xù)線路對(duì)象

m≠n。

(4)

式(4)確保了兩項(xiàng)原則成立：1)在模型定義中，以同一條地鐵物理鏈路為載體實(shí)施運(yùn)營(yíng)的上行、下行及交路線路屬于不同線路；2)模型的應(yīng)用計(jì)算中，避免同一條線路的相關(guān)變量被重復(fù)計(jì)算[21]。

換乘銜接的成功場(chǎng)景定義為：

(5)

輔助決策變量定義為：

Xkmn∈{0,1}，

(6)

決策變量區(qū)間，即地鐵線網(wǎng)中的末班列車運(yùn)營(yíng)時(shí)段范圍為：

(7)

式中tmin和tmax分別為末班列車運(yùn)營(yíng)時(shí)段的下限控制點(diǎn)和上限控制點(diǎn)。

2 粒子群算法設(shè)計(jì)

考慮地鐵末班列車時(shí)刻表編制問題的組合優(yōu)化復(fù)雜性，為確保計(jì)算效率，本文采用粒子群算法(particle swarm optimization, PSO)求解所提出的模型。PSO對(duì)于最優(yōu)化規(guī)劃模型中涉及的函數(shù)性質(zhì)特點(diǎn)沒有特殊限制，可直接應(yīng)用于啟發(fā)式計(jì)算流程[22-23]。每一個(gè)粒子的位置為1×Γ矩陣編碼形式，表示地鐵線網(wǎng)中Γ個(gè)線路的始發(fā)時(shí)刻，即

pi=[t1t2…tΓ]，

式中：i為粒子序號(hào)，i=1,2,3,…,N，N為群規(guī)模；Γ為地鐵線網(wǎng)中的線路數(shù)量。

采用PSO的計(jì)算步驟為：

1)計(jì)算流程初始化。設(shè)置算法中粒子群的規(guī)模為N，粒子飛行的最大速度為vmax，計(jì)算中的最大迭代次數(shù)為φ，解更新過程的學(xué)習(xí)因子為c1、c2，慣性權(quán)重ω的計(jì)算參數(shù)為c1f、c2f、c1g、c2g、ωmin、ωmax。計(jì)算開始時(shí)，初始化設(shè)定粒子的位置和速度，每一個(gè)粒子初始的飛行速度為vi=vmaxδ，δ為區(qū)間(0,1]內(nèi)的隨機(jī)數(shù)。令迭代次數(shù)j=1。

2)粒子個(gè)體指標(biāo)計(jì)算評(píng)定。對(duì)于當(dāng)前群體中的每一個(gè)飛行粒子，判斷是否在約束條件構(gòu)成的解空間范圍內(nèi)，若符合，代入模型；若不符合，在解空間條件下繼續(xù)隨機(jī)生成新粒子個(gè)體。計(jì)算粒子對(duì)應(yīng)的目標(biāo)函數(shù)值，獲得每一個(gè)飛行粒子個(gè)體的相應(yīng)適用性指標(biāo)。

3)更新粒子最優(yōu)位置記錄。①粒子個(gè)體當(dāng)前位置ppc對(duì)應(yīng)適用性指標(biāo)Zpc，記錄的粒子個(gè)體歷史最優(yōu)位置ppb對(duì)應(yīng)適用性指標(biāo)Zpb，若Zpc

4)更新粒子個(gè)體移動(dòng)信息。粒子飛行速度

(8)

式中；R1、R2為區(qū)間[0,1]內(nèi)的輔助隨機(jī)數(shù)，c1=j(c1f-c1g)/φ+c1g，c2=j(c2f-c2g)φ+c2g。

粒子所在位置

(9)

根據(jù)式(8)(9)更新粒子個(gè)體的飛行速度、所在位置及粒子個(gè)體飛行的慣性權(quán)重參數(shù)

ω=ωmax-j(ωmax-ωmin)/φ,

ω及c1、c2隨計(jì)算迭代過程線性減小[24]。

圖1 試驗(yàn)網(wǎng)絡(luò)示意圖

5)更新迭代次數(shù)。令j=j+1，計(jì)算過程循環(huán)至步驟2)，停止條件為達(dá)到設(shè)定的最大迭代次數(shù)。

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

試驗(yàn)網(wǎng)絡(luò)如圖1所示。由物理鏈路Line 1、Line 2、Line 3和Line 4組成，區(qū)分上下行方向，共計(jì)8條運(yùn)行線路。圖1中x1～x8為線路相關(guān)站點(diǎn)(上下行均停駐)，各鏈路旁箭頭表示上行方向。該試驗(yàn)網(wǎng)絡(luò)各線路末班列車時(shí)刻表的原始方案如表1所示，線路銜接效果如表2所示。

表1 試驗(yàn)網(wǎng)絡(luò)末班列車時(shí)刻表原始方案

表1(續(xù))

表2 原始末班列車時(shí)刻表對(duì)應(yīng)的線路銜接效果

由表1、2可知：線路的銜接組合較少，x5和x7這兩處站點(diǎn)存在明顯的“瓶頸”問題。

采用C++語言編寫粒子群算法，求解地鐵末班列車時(shí)刻表優(yōu)化模型。連續(xù)運(yùn)算10次，最長(zhǎng)運(yùn)算時(shí)長(zhǎng)為463 s，最短運(yùn)算時(shí)長(zhǎng)為247 s，平均運(yùn)算時(shí)長(zhǎng)為391 s。同時(shí)，以地鐵線網(wǎng)系統(tǒng)銜接程度最高為優(yōu)化目標(biāo)，運(yùn)算得到的試驗(yàn)網(wǎng)絡(luò)各線路末班列車時(shí)刻表的最佳優(yōu)化方案如表3所示，線路銜接效果如表4所示。

表3 試驗(yàn)網(wǎng)絡(luò)末班列車時(shí)刻表優(yōu)化方案

表3(續(xù))

表4 優(yōu)化后末班列車時(shí)刻表對(duì)應(yīng)的線路銜接效果

對(duì)比表1～4可看出：線路的銜接組合由表2中的12組增加至表4中的20組，改善幅度達(dá)66.7%，優(yōu)化效果明顯。從微觀單元看：x5和x7這兩處站點(diǎn)的組合優(yōu)化場(chǎng)景得到了充分改善，有效避免了系統(tǒng)最優(yōu)原則下的“瓶頸”問題[25]。

傳統(tǒng)的末班列車時(shí)刻表優(yōu)化方法中以Zhou等[20]16為典型代表，即分析單一線路調(diào)控下的系統(tǒng)最優(yōu)問題，應(yīng)用CPLEX求解器求解線性整數(shù)規(guī)劃模型。針對(duì)本文算例，應(yīng)用傳統(tǒng)方法進(jìn)行優(yōu)化計(jì)算，線路接續(xù)結(jié)果如表5所示。

表5 文獻(xiàn)[20]的接續(xù)優(yōu)化結(jié)果

由表5可以看出：傳統(tǒng)方法下仍然存在x5這一“瓶頸”站點(diǎn)。本文提出的優(yōu)化方法采用雙線路組合優(yōu)化流程，在啟發(fā)式算法中通過粒子個(gè)體的多維編碼促進(jìn)解的多樣性。對(duì)比本文方法與傳統(tǒng)方法的優(yōu)化性能可知，本文優(yōu)化方法接續(xù)改善幅度大，平均運(yùn)算時(shí)間由499 s縮減至341 s，“瓶頸”站點(diǎn)由1個(gè)減至0。從整個(gè)地鐵網(wǎng)絡(luò)線路接續(xù)的改善幅度來看二者作用相同，但運(yùn)算時(shí)間上本文方法具有優(yōu)勢(shì)，并且未出現(xiàn)“瓶頸”站點(diǎn)問題。

4 結(jié)語

針對(duì)地鐵末班列車時(shí)刻表優(yōu)化問題，考慮涉及的各類實(shí)際運(yùn)行因素，創(chuàng)建優(yōu)化模型以解析化描述問題。采用粒子群算法求解模型以獲得地鐵末班列車時(shí)刻表優(yōu)化方案。數(shù)值試驗(yàn)結(jié)果表明：本文提出的方法實(shí)現(xiàn)了優(yōu)化改進(jìn)的目的，獲得合理可行的末班列車時(shí)刻表編制方案。

在后續(xù)研究中可將模型的限制條件進(jìn)一步細(xì)化，例如考慮乘客的安全預(yù)留時(shí)間和站內(nèi)擁擠度的時(shí)間指標(biāo)等，以充分反映真實(shí)條件下的計(jì)算結(jié)果和優(yōu)化效果。