楊艷

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

0 引言

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

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

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

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

(1)

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

線路m的末班列車到達(dá)站點k的時刻

(2)

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

(3)

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

m≠n。

(4)

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

換乘銜接的成功場景定義為：

(5)

輔助決策變量定義為：

Xkmn∈{0,1}，

(6)

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

(7)

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

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

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

pi=[t1t2…tΓ]，

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

采用PSO的計算步驟為：

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

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

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

4)更新粒子個體移動信息。粒子飛行速度

(8)

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

粒子所在位置

(9)

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

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

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

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

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

3 數(shù)值試驗

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

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

表1(續(xù))

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

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

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

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

表3(續(xù))

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

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

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

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

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

4 結(jié)語

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

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