城市軌道交通網絡首班車時段時刻表優化研究

楊冀琴，田 秦，徐占東，雷 莉

(1. 成都工業職業技術學院，四川 成都 610218；2.西南交通大學 交通運輸與物流學院，四川 成都 611756；3. 中國鐵路成都局集團有限公司干部培訓中心，四川 成都 611731)

0 引 言

隨著城市軌道交通網絡的形成，其一方面為居民的出行帶來便捷，另一方面網絡的復雜性給列車換乘銜接問題增加了難度。由于各條線路根據其客流情況確定一天的運營時間，各線路的運營時間不同。因此，根據首末班車的客流特性制定適宜的時刻表，提供高效的列車銜接優化方案，對于提高乘客換乘效率，提升城市軌道交通早晚間運營服務水平具有一定的理論與現實意義。

近年來，末班車的換乘銜接優化引起了研究者的關注，主要集中在以下幾個方面：①基于線網的可達性優化末班車時刻表[1,2]；②采用分層協調策略[3]，開展網絡換乘銜接優化研究；③基于全網銜接優化，構建網絡末班車銜接和時刻表的優化模型，考慮不同的優化目標：乘客換乘銜接間隔最大[4]、換乘冗余時間的標準差最小[5]、乘客總換乘等車時間最小化[6]、換乘銜接的客流量最大[7]、成功換乘銜接客流量最大和總換乘等車時間最小[8]、最大限度滿足旅客需求[9]、減少乘客換乘等車時間與乘客不可達OD量和改善可達乘客的可靠性[10]、換乘成功乘客數量最大和末班車運行時間最小[11]。

在首班車的銜接優化方面，基于換乘銜接方向的重要程度，徐瑞華等[3]設計分層協調的優化策略和算法；宋悅等[12]提出將各個換乘方向的換乘客流量作為權重定量衡量首班車協調層次的方法；W. L. ZHOU等[10]以乘客總的起點等車和換乘等車時間最短為目標；L. J. KANG等[13]以總的乘客換乘等車時間最小、列車到站時間差最小、在合理的時間內未實現換乘服務的列車數量最小[14]為目標；X. GUO等[15]提出子網絡銜接方法，使首班車列車間的銜接時間最小，分別采用遺傳算法[10, 12]、模擬退火算法[13]、啟發式搜索算法[14]和CPLEX軟件[15]進行求解。

當前研究主要集中于末班車的換乘銜接，對首班車的換乘銜接研究較少，已有研究未考慮企業運營成本。然而，首班車的乘客行為和客流特征與末班車不同，換乘銜接的目標也不同?？紤]到首班車時段的客流需求較少、運能充足等特點，筆者以乘客換乘等車成本和線路發車成本最小為優化目標，構建首班車時段列車時刻表優化模型，利用遺傳算法進行求解。

1 首班車時段換乘銜接優化問題概述

首班車時段的運營組織是城市軌道交通全天運營的基礎，該時段的時刻表是全天運營時刻表的一部分。筆者提出的首班車時段不是指各條線路每日早間運營發出的首班列車，而是指從各條線路首班車出發開始到早高峰之前或者到早高峰時段內的某個時間為止。該時段的選取與各個城市的最早發車時間、線路運行時間和客流高峰時段有關，例如，從運營公司最早發車時間開始至早高峰時段之前(6:30—8:00)。

首班車時段由于接近早高峰時段，客流量較少但呈逐漸增加的趨勢。首班車時段的乘客不存在換乘不可達情況，僅有乘客換乘等車時間的長短之分。如圖1，乘客從L線路上的第q班列車換乘到L′線路的第q′班列車上，此時換乘等車時間大于等于0，換乘等車時間取決于換乘列車間的銜接時間與乘客的換乘走行時間。如果列車的銜接時間不合理，導致乘客在換乘站等車時間過長，會降低乘客的滿意度和軌道交通的運營服務水平。

圖1 首班車時段乘客換乘銜接過程Fig. 1 Passenger transfer connection at the first train time period

2 城市軌道交通線網拓撲圖的簡化

城市軌道交通線網由若干條線路組成，各條線路由若干個車站與區間構成。因此，線網可用所有車站與區間共同組成的拓撲來表示。車站按照其在線路中的具體位置可以分為中間站、換乘站、端點站(起點站和終點站)3種，見圖2。

圖2 城市軌道交通線網拓撲Fig. 2 Network topology of urban rail transit

隨著線網規模的擴大，線網中線路和車站隨之增加，適當簡化線網拓撲，可以方便模型求解并提高模型對大規模網絡的適用性。由于端點站的發車時間和換乘站的到站、離站時間對換乘銜接影響較大，稱其為關鍵站；其余的中間站稱為非關鍵站。因此，將端點站與換乘站間以及相鄰換乘站間的列車運行區間進行簡化，得到由端點站、換乘站以及區段組成的軌道交通線網簡化拓撲(圖3)。

圖3 城市軌道交通線網簡化拓撲Fig. 3 Simplified network topology of urban rail transit

便于問題描述，對線網模型的基礎參數做如下定義：I為線網中線路的集合, 任意一條線路分上、下行儲存在集合中，I={i|i=1,2,3,…,LI}，其中LI為集合中線路的數量；X為線網中關鍵站的集合，X={x|x=1,2,3,…,SX}，其中SX為集合中關鍵站的數量；Q為線網中所有線路的列車班次序號集合，Q={q|q=1,2,3,…,NQ}, 其中NQ為時段內所有線路的最大發車班次。

3 首班車時段時刻表優化模型構建

首班車時段內由于有后續列車的銜接，乘客的可達性可以得到保證，但列車之間銜接時間過長，會造成乘客的換乘不便。由于首班車時段客流較少，線網運力較充足，因此，除了考慮線路的銜接關系以減少乘客的換乘等車時間，該時段的銜接優化目標還可兼顧企業的運營成本。筆者考慮乘客和運營兩個方面，以乘客換乘等車成本和線路發車成本最小為目標，構建首班車時段的列車時刻表優化模型。

3.1 模型假設

1)同一個換乘站不同乘客的換乘走行時間相同。首班車時段乘客的出行特征區別較小，走行時間比較接近。

2)各線路首班列車的發車時間不早于運營公司設定的最早發車時間。

3)假設首班車時段的列車運載能力充足，乘客不會因列車滿載而被滯留在車站，即乘客在起點站與換乘站均乘坐乘客到站后的第一列到達車站的列車。

3.2 優化目標

為了提高乘客換乘方便性，并減少城市軌道交通的運營成本，筆者構建的首班車時段列車時刻表優化模型的目標函數為總成本(乘客換乘等車時間成本和企業運營發車成本)最小，考慮乘客的換乘走行時間和換乘失敗懲罰，以列車離開、到達關鍵站時間、區間運行時間以及關鍵站停站時間為決策變量。

3.2.1 換乘等車時間成本

乘客換乘銜接時間為線路j銜接列車的第q’班列車從換乘站x的出發時間(D′xjq)減去線路i換乘列車第q班列車到達換乘站x的時間(Axiq)與乘客在換乘站x從線路i到線路j的換乘走行時間Tij,w之和。從線路i的第q班列車換乘到線路j的第q′班列車的乘客換乘等車時間Wijqq′為：

Wijqq′=Dxjq′-Axiq-Tij,w

(1)

與末班車不同，首班車時段乘客不會出現換乘失敗不可達的情況，但是可能出現換乘等待時間過長的情況。筆者將乘客能夠忍受的最大換乘等車時間(Tij,C)作為首班車時段換乘失敗與否的判別標準。如果乘客的換乘等車時間小于等于Tij,C，則根據式(1)可得出乘客的換乘等車時間。如果乘客的換乘等車時間大于Tij,C，將這種情況視為“換乘失敗”，筆者引入換乘懲罰值，乘客的換乘等車時間為：

Wijqq′=max{Dxjq′-Axiq-Tij,w,εij}

(2)

式中：εij為從線路i到線路j換乘失敗后的懲罰值。

換乘等車時間通過時間費用轉換系數δ轉換得到換乘等車時間成本。換乘等車時間成本為首班車時段內線網中所有換乘乘客的換乘等車時間成本之和：

(3)

式中：Ni,u為線路i首班車時段內的發車數量；Cijq為從線路i上的第q班列車換乘到線路j的乘客數量。

3.2.2 發車成本

發車成本為線網中所有線路在首班車時段內發出的列車所產生的運營成本之和：

(4)

式中：Gi為線路i每發出一列車的發車成本，筆者主要考慮電力成本。

3.2.3 目標函數

換乘等車時間成本和發車成本之和是首班車時段時刻表優化模型的目標函數，如式(5)：

(5)

3.3 約束條件

3.3.1 模型變量的基礎關系

列車到達某關鍵站的時間可用該線路起點站的離站時間、區間運行時間以及關鍵站停站時間來表示，如式(6)：

(6)

式中：Rxiq為線路i上的第q班列車從關鍵站x-1行駛到關鍵站x的區間運行時間，包括所經過的非關鍵站的停站時間；Pxiq為線路i上的第q班列車在關鍵站x的停站時間。

同理，列車離開某關鍵站的時間可表述為：

(7)

由式(6)、式(7)可以得出列車離開某關鍵站的時間Dxiq等于到達該站的時間Axiq與該站的停站時間Pxiq之和，如式(8)：

Dxiq=Axiq+Pxiq

(8)

3.3.2 乘客換乘成功等車時間約束

考慮到在首班車時段客流量較少、運能充足的情況下，沒有乘客滯留的現象，乘客在換乘站乘坐乘客到站后的第一列到達車站的銜接列車，即為乘客換乘成功。乘客的換乘成功等車時間應該滿足以下約束條件：

0

(9)

3.3.3 發車間隔時間約束

時段內列車的發車間隔時間應該按照規定控制在最大值與最小值的范圍之內，且相鄰兩列車的發車時間間隔應該等于發車間隔時間，如式(10)、式(11)：

th,min≤Hi≤th,max

(10)

D1iq=D1i,q-1+Hi

(11)

式中：ht,max，th,min為各線路發車間隔時間的上下限；Hi為線路i在首末班車時段的發車間隔時間，每條線路在時段內的發車間隔時間為定值。

3.3.4 列車停站、運行時間約束

列車停站時間的取值應該在列車規定停站時間的最大、最小值之間。區間運行時間的取值應該小于列車最小速度時的最大運行時間且大于列車最大運行速度的最小運行時間，如式(12)、式(13)：

tp,ximin≤Pxiq≤tp,ximax

(12)

tr,ximin≤Rxiq≤tr,ximax

(13)

式中：tp,ximax，tp,ximin為線路i上車站x的停站時間上下限；tr,ximax，tr,ximin為線路i上車站x的區間運行時間上下限。

3.3.5 首班列車發車時間約束

為了不影響后續早高峰的運營，首班車的發車時間應該在一定范圍內，有約束如式(14)：

0≤D1i1≤TD

(14)

式中：TD為首班車發車時間上限。

3.3.6 首班車時段內列車的運行時間約束

首班車發車時段內發車數量也應該遵循相應的條件，即列車到達每一站點的時間都應該處于該時段內：

T2f-T1f-Hi≤AXi,i1+(Ni,u-1)·Hi≤T2f-T1f

(15)

式中：T1f、T2f為首班車時段的起止時間；AXi,i1為線路i上的首班車到達終點站Xi的時間。

4 求解算法設計

城市軌道交通首班車時段的時刻表優化問題是一個復雜的組合優化問題，模型的變量多且約束復雜，解的空間大。遺傳算法具有快速搜索全局最優解(或準最優解)的能力，執行簡單靈活，被廣泛應用于優化問題的求解。因此，筆者采用遺傳算法進行模型求解，具體步驟如下：

步驟1染色體設計。模型的4個決策變量為線路首班車的發車時間、發車間隔時間、區間運行時間以及關鍵站的停站時間。考慮到首班車時段時刻表優化模型的搜索空間大、模型變量多，筆者采用實數編碼方式進行編碼[2,16]，染色體編碼如圖4。

圖4 染色體編碼Fig. 4 The encoding illustration of a chromosome

步驟2初始化種群。輸入模型數據與算法參數，采用隨機初始化的方式在各變量的約束范圍內生成初始種群。

步驟3計算適應度函數值。計算種群中每一個染色體的適應度函數。采取以目標函數轉化為適應度函數的轉換方式，適應度函數Fit(F)設置為目標函數F的相反數，即：

Fit(F)=-F

(16)

步驟4選擇運算。根據適應度大小，選取適應度為前5%的染色體進入到下一代種群，其他的染色體采用輪盤賭算子進行選擇，產生新一代種群。

步驟5交叉運算。以交叉概率Pc對染色體進行兩點交叉操作[2]，在相互配對的兩個染色體中隨機設置兩個交叉點，然后交換其所設定的兩個交叉點之間的部分基因。

步驟6變異運算。對種群中的染色體以變異概率Pm隨機選取進行變異操作[2]，產生出新一代個體，得到下一代種群。

步驟7檢驗是否滿足終止條件。采用最大迭代次數或個體適應度無法再進行有效的改進作為算法的終止條件。如果滿足終止條件，則終止計算輸出最優方案；否則，返回步驟3。

5 案例分析

5.1 深圳地鐵線網概況

筆者將2014年深圳地鐵線網作為研究對象，線網由5條線路、131座車站(含13座換乘站)組成。簡化后的線網拓撲如圖5，圖5中箭頭表示線路的上下行方向。

圖5 深圳地鐵線網拓撲Fig. 5 Network topology of Shenzhen metro

5.2 基礎數據及模型參數

深圳地鐵線網的乘客刷卡數據、發車間隔時間、區間運行時間、列車停站時間、最早發車時間等數據均從地鐵公司獲取。首班車時間段接近早高峰，根據客流特點和運營要求，首班車時段換乘站停站時間設定其上下限分別為1 min和0.5 min；發車時間間隔在高峰和平峰之間，取3～7 min之間。深圳地鐵換乘站的乘客平均換乘走行時間通過調查得到，如表1。當乘客換乘等車時間大于Tij,C時，視為首班車時段的換乘失敗行為，換乘失敗懲罰值60 min。

表1 乘客換乘走行時間Table 1 Passenger transfer walking time

基于AFC刷卡數據，通過考慮乘客車內時間與換乘時間(包括換乘走行時間和換乘等車時間)的時間效用Logit模型將客流分配到有效路徑之上，任意OD對的有效路徑為最短路和次短路。最短路和次短路分配的客流量可以達到95%以上。將所有客流量分配到最短和次短路上較為符合實際的客流情況，誤差在可接受范圍之內[17]。

模型的成本參數主要有兩個：時間費用轉換系數δ和線路i上每發出一列班車的發車成本Gi。時間費用轉換系數=深圳市人均月薪/月平均工作時長(數據來自2014年深圳社保網中的深圳社保局通知)，經計算得出δ取值為44元/h，即0.73元/min。發車成本包含電力成本、設備損耗以及人力成本等，筆者主要考慮列車牽引的電力成本，根據文獻[16]，牽引一列車的電力成本為12元/km。

5.3 首班車銜接優化結果分析

5.3.1 遺傳算法的迭代過程

遺傳算法在MATLAB中編程執行。算法的參數值設置如下：種群規模取值為200；交叉概率值設定為0.8；變異概率設定為0.05；最大迭代次數為500次。代入模型的參數，輸入相應的數據，得出優化的決策變量值與首班車時段時刻表。圖6表示模型的目標函數值在迭代過程中的變化。由圖6可知，在100代之前目標函數值降低較快，在400代之前達到收斂。

圖6 總成本的迭代過程Fig. 6 Iteration process of total cost

5.3.2 成本分析

首班車時段模型的優化結果如表2。首班車時段優化前乘客換乘等車成本為77 687元，線路發車成本為26 628元，總成本為128 612元。經過優化后，乘客換乘等車時間成本為64 004元(降低了17.6%)，線網發車成本為15 552元(減少了41.6%)，總成本為99 556元(降低了22.6%)。模型對成本的優化效果較為顯著。

表2 優化前后的成本對比Table 2 Comparison of cost before and after optimization

5.3.3 乘客換乘失敗分析

首班車不存在線網時空的可達性問題，但是首班車會出現換乘等待時間過長的情況，筆者將這一情況同樣視為換乘失敗。由于AFC刷卡數據只記錄了乘客的進出站信息，但無法直接得到乘客換乘失敗的狀態?；谀Ｐ蛯Q乘失敗的定義，將客流數據與現狀時刻表進行匹配運算，得出優化前后的乘客換乘失敗情況，如表3。首班車時段的乘客換乘失敗成本從優化前的24 297元降到了20 000元，換乘失敗人數從555人減少到了457人，優化率達到了17.7%。可見該優化模型能有效改善首班車的換乘失敗行為。

表3 優化前后乘客換乘失敗比較Table 3 Comparison of passenger transfer failure before andafter optimization

5.4 敏感性分析

由于區間運行時間與列車的設計車速與運行能耗關系密切，因此，筆者僅對發車間隔、停站時間和發車時間3個運營參數進行敏感性分析。

5.4.1 發車間隔

為了分析發車間隔對首班車時段列車間換乘協調的影響，將停站時間與區間運行時間固定，調整線路的發車間隔，優化結果如表4 。通過調整發車間隔，可以實現網絡間的換乘協調，減少乘客的換乘等車時間成本、換乘失敗成本和發車成本。發車間隔的調整對換乘等車時間成本和發車成本影響較大，而對換乘失敗人數的影響較小。調整發車間隔可以降低換乘人數，但是減少的幅度比較接近。

表4 發車間隔敏感性分析Table 4 Sensitivity analysis of departure interval

5.4.2 停站時間

為了分析優化結果對停站時間的敏感性，將發車間隔和區間運行時間固定，對停站時間進行調整，優化結果如表5。換乘乘客的換乘等車成本和換乘失敗人數對停站時間較為敏感。由于線網中存在多個換乘站，通過對列車的停站時間進行調整，可使多個換乘站的列車同時實現協調銜接。停站時間對發車成本的影響較小。

表5 停站時間敏感性分析Table 5 Sensitivity analysis of stopping time

5.4.3 發車時間

首班車最早發車時刻約束直接影響時刻表的優化效果，分析該參數對時刻表優化效果的影響，可以為運營公司選擇各線路的發車時刻提供依據。首班車發車時間約束在原時刻表基礎上分別提前3、6、9、12、15 min，分析不同取值下目標函數的優化效果(如圖7)。取值的含義為，與現行時刻表的最早發車時刻 06:30 相比，優化時刻表最早發車時刻的變化量。

圖7 發車時間敏感性分析Fig. 7 Sensitivity analysis of departure time

隨著地鐵網絡首班車最早發車時刻的提前，目標函數優化效果更加明顯，可減少換乘失敗人數。首班車發車時間提前得越早，換乘銜接失敗的人數越少，但首班車發車時間的提前會導致企業運營成本增加。因此，首班車發車時間需兼顧網絡服務水平與企業運營成本，運營企業應根據實際情況決定線路首班車的發車時間。

6 結 語

筆者遵循城市軌道交通早間運營時段的客流特性，研究列車間的換乘銜接優化問題，在滿足相關運營要求和時刻表模型約束的基礎上，考慮首班車換乘失敗行為，以乘客換乘等車成本和線路發車成本最小為目標，構建首班車時段的時刻表優化模型。筆者設計的遺傳算法可以有效求解首班車時刻表優化問題。筆者通過深圳地鐵網絡進行實證分析，驗證了模型的可行性。結果表明，該模型能有效地生成城市軌道交通首班車時段列車協調銜接時刻表，為相關部門提供決策支持。但是，筆者簡化了乘客的路徑選擇問題，基于最短路和次短路搜索有效路徑。隨著軌道交通網絡規模的擴大，可供選擇的換乘路徑增加，乘客對路徑選擇也存在差異性。在線網運營成本中只考慮了線路的發車成本，而運營成本由多項成本構成。這些問題還有待深入研究。