楊艷

廣西交通技師學院，廣西 南寧 530001

0 引言

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

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

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

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

(1)

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

線路m的末班列車到達站點k的時刻

(2)

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

(3)

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

m≠n。

(4)

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

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

(5)

輔助決策變量定義為：

Xkmn∈{0,1}，

(6)

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

(7)

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

2 粒子群算法設計

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

pi=[t1t2…tΓ]，

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

采用PSO的計算步驟為：

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

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

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

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

(8)

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

粒子所在位置

(9)

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

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

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

圖1 試驗網絡示意圖

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

3 數值試驗

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

表1 試驗網絡末班列車時刻表原始方案

表1(續(xù))

表2 原始末班列車時刻表對應的線路銜接效果

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

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

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

表3(續(xù))

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

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

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

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

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

4 結語

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

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