考慮動態(tài)客流需求和大小交路模式的城市軌道交通列車開行方案優(yōu)化

代存杰，李引珍，展宗思，柴　獲

(1.蘭州交通大學 機電技術研究所，甘肅 蘭州　730070；2.蘭州交通大學 交通運輸學院，甘肅 蘭州　730070；3.西安市地下鐵道有限責任公司，陜西 西安　710016)

列車開行方案是城市軌道交通運營組織的重要工作，列車發(fā)車時刻表是開行方案設計的核心內(nèi)容，需要根據(jù)客流需求的分布特征科學制訂。由于列車運行路線上存在區(qū)段客流不均衡、客流斷面突變現(xiàn)象，因此應基于不同的列車交路模式，設計合理的列車發(fā)車時刻表，對列車開行方案進行優(yōu)化，以減少乘客等待時間、提高列車滿載率。

國內(nèi)外學者在列車發(fā)車時刻表優(yōu)化方面做了諸多研究，Serafini等[1]建立了時間約束下周期性事件調(diào)度模型，并應用于列車發(fā)車時刻表的設計；Kwan等[2]考慮列車運營費用和乘客滿意度，利用啟發(fā)式算法對列車發(fā)車時刻表進行優(yōu)化；Liebchen[3]在既有圖解模型的基礎上對柏林地鐵系統(tǒng)的列車發(fā)車周期進行了優(yōu)化；Kroon等[4]通過調(diào)整列車運行的補償時間和相鄰列車之間的緩沖時間，提高列車發(fā)車時刻表在隨機擾動下的魯棒性；廖勇[5]將客流到達車站的過程視為隨機過程，據(jù)此對城際列車發(fā)車間隔進行優(yōu)化。

在城市軌道交通的實際運營過程中，不同時段內(nèi)不同車站的乘客到站數(shù)量存在差異，致使客流需求存在時間和空間上的不均衡性。若乘客到站數(shù)量服從均勻分布或泊松分布，則周期性的發(fā)車間隔時間可減少乘客等待時間[6]。在具有時變特征的客流需求下，固定發(fā)車間隔時間會導致部分乘客的等待時間過長[7]。

根據(jù)客流需求在時間上分布不均衡的特征，Cury等[8]以乘客滿意度和列車運營成本為目標建立模型，得到非固定的列車發(fā)車間隔時間；Albrecht[9]根據(jù)列車運力確定最優(yōu)發(fā)車頻率后，設計了面向乘客需求的列車發(fā)車時刻表；Niu等[10]考慮擁擠情況下的客流時變特征，建立城市軌道交通列車發(fā)車時刻表的優(yōu)化模型；Barrena等[11]以乘客平均等待時間最小為目標，對動態(tài)客流需求下的列車發(fā)車時刻表優(yōu)化；Hassannayebi等[12]考慮客流需求和列車行程時間的不確定性，設計了兩階段模擬方法以生成魯棒的列車發(fā)車時刻表。

針對客流需求空間分布的不均衡性，常采用不同的列車開行方案以適應客流空間分布特征[13]；程婕等[14]以列車輸送能力與客流空間分布的最佳匹配為原則，建立了列車開行方案優(yōu)化的多目標0-1規(guī)劃模型；王媛媛等[15]以乘客出行成本及企業(yè)運營成本最小為目標，構建大小交路模式下列車開行方案的優(yōu)化模型；凌俊等[16]根據(jù)城市軌道交通客流不均衡情況，對非高峰期列車開行方案進行研究。

但是，這些既有研究多從單一方面對城市軌道交通列車開行方案進行優(yōu)化，沒有同時考慮客流需求的時間和空間分布不均衡特征以及列車交路模式。為此，本文考慮客流需求的時間和空間分布特征，對大小交路模式下列車開行方案優(yōu)化進行研究。

1　問題描述

1.1　動態(tài)客流需求分析

動態(tài)客流需求分析的核心工作是分析客流需求的時間和空間分布規(guī)律。影響客流在時間上變化的主要因素為乘客的出行行為，乘客的日常出行行為在1天內(nèi)是不同的，導致1天內(nèi)客流是動態(tài)變化的，但在1天內(nèi)的出行行為又具有一定的規(guī)律性，所以，同一車站各時段內(nèi)的客流密度基本是確定的，不同車站的客流變化規(guī)律不同。

影響客流在空間上變化的主要因素是車站覆蓋的客流集散點的規(guī)模和數(shù)量不同，因而各車站的乘降人數(shù)不同，致使各斷面客流空間分布的不平衡；同時，新的居民住宅區(qū)入住和新的軌道交通線路投入運營，也會使車站乘降人數(shù)發(fā)生較大的變化。

為表達不同時段內(nèi)的動態(tài)客流需求特征，定義如下參數(shù)：U={1,2,…,2N}為車站序號集合，其中1,2,…,N為上行方向車站編號，N+1,N+2,…,2N為下行方向車站編號，且車站1與2N；2與2N-1；…；N與N+1分別共用同一個站臺；T為城市軌道交通日運營時間長度，δ為單位時間，列車發(fā)車時間點t∈T，且t=nδ，n為正整數(shù)；u∈U和v∈U為單個車站的編號，且v>u；ρu,v(t)為時間點t從u出發(fā)前往v的客流密度，當u∈{1,2,…,N}且v∈{N+1,N+2,…,2N}時，ρu,v(t)=0；Πu,v(t)為列車開始運營時間點0到時間點t之間從u出發(fā)前往v的累計客流需求。

Πu,v(t)與ρu,v(t)的關系表達式為

(1)

(2)

圖1　車站u的累計客流需求

(3)

(4)

(5)

對式(5)求和可得時段[t1,t2]內(nèi)從車站u出發(fā)的累計客流需求為

(6)

1.2　大小交路模式列車發(fā)車時間間隔分析

在大小交路模式下確定列車開行方案時，為避免列車在線路中的行車沖突，通常取固定發(fā)車間隔時間，不同交路列車的開行數(shù)量為嚴格的倍數(shù)關系，但這種固定發(fā)車間隔時間會導致客流需求低峰期時的運力浪費或客流需求高峰期時的運力不足[18]。在列車運行控制技術可行的前提下，大小交路列車的開行只要滿足最大、最小追蹤間隔約束，可根據(jù)客流需求特征動態(tài)設定非固定的發(fā)車間隔時間[20]，使列車交路方案確定的輸送能力與客流需求空間特征達到最佳匹配。

2　多目標優(yōu)化模型

2.1　假設條件

根據(jù)城市軌道交通實際運營情況首先作如下假設：①各站乘客服從“先到先服務”的原則；② 乘客不選擇列車交路類型，即可能登乘時則登乘；③列車在各站停靠時間和站間行駛時間是確定的；④不存在列車越行和會讓的情況。

2.2　參數(shù)定義

2.3　模型建立

根據(jù)假設條件和相關參數(shù)定義，計算模型的相關參數(shù)，具體如下。

(7)

列車j從車站u的出發(fā)時間為

(8)

(9)

當車站u無滯站乘客存在時，可成功登乘列車j的乘客數(shù)量γj,u為

(10)

(11)

(12)

γj,u=A-(Cj-u-1-Oj,u)

(13)

此時，部分乘客需要等待列車j+1，則Bj,u為

Bj,u=Wj,u-γj,u

(14)

(15)

當列車為小交路運行時，列車需要在車站u′清客，則該部分乘客在車站u′的等待時間為

(16)

(17)

在整個日運營時間長度T內(nèi)，根據(jù)式(6)可得車站u的累計客流需求為

(18)

由此可計算所有乘客的平均等待時間?，即

(19)

(20)

(21)

考慮客流需求的動態(tài)特征和大小交路模式特點，以減少乘客平均等待時間、提高列車平均滿載率、減少列車總走行公里數(shù)為優(yōu)化目標，建立城市軌道交通列車開行方案的多目標混合整數(shù)非線性優(yōu)化模型為

(22)

s.t.

(23)

(24)

(25)

(26)

(27)

約束條件中：式(23)和式(24)分別為最小和最大發(fā)車間隔時間分別滿足最小和最大追蹤列車間隔時間約束；式(25)為車輛運力供需比約束，即開行列車的輸送能力不小于客流需求量；式(26)和式(27)分別為列車j與相鄰列車j-1和j+1在車站u′的追蹤列車間隔時間不小于最小追蹤列車間隔時間Imin，以保證小交路運行的列車j在折返站u′折返后的運行安全。

3　求解算法設計

在對模型求解時，需要根據(jù)客流特征動態(tài)安排列車的交路模式和發(fā)車時間，此問題屬于組合優(yōu)化問題，可用遺傳算法有效地求解[10]。由于各求解目標并不統(tǒng)一，只能根據(jù)各目標的優(yōu)化準則得到非支配解。因此，本文將快速非支配遺傳算法NSGA-Ⅱ與自適應鄰域搜索方法相結合對模型求解，并對遺傳操作中的交叉和變異算子進行改進。

NSGA-Ⅱ為多目標進化算法，降低了非支配排序遺傳算法的復雜性，具有運行速度快、收斂性好的優(yōu)點，成為其他多目標優(yōu)化算法的基準[21]。本文在標準NSGA-Ⅱ的基礎上，設計多點動態(tài)交叉操作，并結合啟發(fā)式鄰域搜索機制，對染色體的變異操作進行改進，以產(chǎn)生性能更優(yōu)的新染色體，加快算法的求解速度。

3.1　編碼設計

考慮列車發(fā)車時間的離散性，對染色體采用0-1編碼方式。染色體中的每個基因表示時段T內(nèi)的單位時間點，對應編碼0或1?；蛑禐?表示該時間點有列車出發(fā)，基因值為0表示在對應時間點無列車出發(fā)。設間隔時間基準δ=1(min)，Imin=3δ，Imax=10δ，染色體結構如圖2所示。

二進制編碼可表示單一交路模式的列車離散發(fā)車間隔時間，為適應大小交路模式，在設計染色體編碼時需要考慮交路類型。在染色體的基因信息中加入開行列車的交路模式，0表示該時刻沒有列車發(fā)出，1表示該時刻有交路類型1的列車發(fā)出，2表示該時刻有交路類型2的列車發(fā)出。大小交路模式的染色體結構在圖2的基礎上變?yōu)槿鐖D3所示。

圖2　染色體結構

圖3　大小交路模式的染色體結構

3.2　選擇操作

針對染色體種群，利用快速非支配排序策略計算每條染色體的層級序號r(·)和擁擠距離d(·)。 根據(jù)r(·)和d(·)可以比較2條染色體的優(yōu)劣。將染色體x1和染色體x2進行比較，如果x1優(yōu)于x2，則x1至少滿足下面2種條件之一：①r(x1)>r(x2)； ②r(x1)=r(x2),d(x1)>d(x2)。

3.3　交叉算子設計

在傳統(tǒng)單點交叉的基礎上，設計動態(tài)多點交叉操作。雖然這種交叉方式可能會破壞優(yōu)秀染色體的結構，但會提高算法對整個解空間的搜索能力，比單點交叉表現(xiàn)出更好的收斂性能[22]。

圖4　動態(tài)多點交叉操作

在交叉操作后，只保留滿足約束條件的子代染色體。將可行子代染色體放入新的種群，用來與父代染色體所在種群進行非支配比較，達到精英保留和種群優(yōu)化的目的。

3.4　變異算子設計

在設計染色體變異算子時，結合自適應鄰域搜索機制對染色體進行啟發(fā)式變異，分為染色體破壞操作和染色體修復操作。

1)染色體破壞操作

破壞操作是用來減少開行的列車數(shù)量或?qū)⒘熊囉纱蠼宦愤\行模式變?yōu)樾〗宦愤\行模式，以提高列車的滿載率，避免運力過剩，同時減少列車走行公里數(shù)。操作步驟如下。

2)染色體修復操作

修復操作是用于增加開行列車數(shù)量，或根據(jù)折返站前后連續(xù)客流斷面的平均值，進行列車大小交路調(diào)整，以減少乘客的等待時間。操作步驟如下。

4　算例及結果分析

以西安地鐵2號線為研究對象，此線路共設有21座車站，北客站至韋曲南站為方向上行。列車在各區(qū)間的運行時間、在各站的?？繒r間見表1。

韋曲南站的停留時間為大交路列車在該站進行折返作業(yè)時間，會展中心站的停留時間分別為小交路列車的折返作業(yè)時間和大交路列車的停靠時間。大交路列車的走行公里數(shù)為L2=53.0 km，小交路列車的走行公里數(shù)為L1=39.8 km，日運營時間為06:10至23:15，即T=1 025 min。

地鐵2號線的運營車輛采用B型車、3動3拖6輛編組方式，列車定員為1 468人，終點站均采用站后折返；北客站最小全折返時間為5.7 min，韋曲南站最小全折返時間為4.3 min。最小追蹤列車間隔時間Imin=3 min，最大追蹤列車間隔時間為Imax=10 min，大交路的運營周期時間為104.0 min，小交路的運營周期時間為82.6 min。

根據(jù)地鐵自動售檢票系統(tǒng)，可得到某日運營時間內(nèi)地鐵2號線各站累計到達客流需求變化曲線(以30 min為時間粒度提取)，如圖5所示。

表1　列車站間運行時間和各站?？繒r間

*為小交路折返站

圖5　累計到達客流需求變化曲線

設置染色體的種群規(guī)模為200，最大迭代次數(shù)為300，交叉概率為0.8，動態(tài)交叉點個數(shù)為5，變異概率為0.15。取ε=0.2；當s>ε時，d=rand(30,50)，m=rand(20,30)； 當s≤ε時，m=rand(30,50)，d=rand(20,30)。經(jīng)過計算，可得到大小交路模式下列車發(fā)車時間優(yōu)化結果。在生成的非支配解集中，解的空間分布如圖6所示。

在非支配解集中，取各個目標函數(shù)的最優(yōu)值時，對應的列車開行方案見表2。

解析非支配解集中的任一非支配解，都可得到列車在始發(fā)站出發(fā)時刻及對應的列車運行圖。以解集中的非極值解(3.26,85.53%,8.63)為例，對應的開行列車總數(shù)為170列，其中大交路開行列車總數(shù)為142列，小交開行路列總數(shù)為28列，在u=1的列車發(fā)車時刻及運行情況如圖7所示。

圖6　非支配解的空間分布圖

優(yōu)化目標?/min λ/%l/103km開行列車總數(shù)/列其中大交路開行列車總數(shù)/列其中小交路開行列車總數(shù)/列?2 9577 819 4318914544 λ7 1599 917 461411392l6 5699 877 451421366

圖7　列車發(fā)車時刻及運行圖

分析圖5和圖7可知：列車開行方案中發(fā)車間隔時間的大小與客流需求的變化是吻合的，如早高峰和晚高峰時段，客流量較大，則列車發(fā)車間隔時間較小，并且同時開行大、小交路列車；在平峰或低峰時段，客流量較小，則列車發(fā)車間隔時間較大，且僅開行大交路列車。

將大小交路模式下的列車開行方案設置為固定追蹤列車間隔時間，并設最小追蹤列車間隔時間Imin=5 min，最大追蹤列車間隔時間為Imax=10 min。對模型求解后生成非支配解集，當各目標函數(shù)分別取最優(yōu)值時，得到固定追蹤列車間隔時間條件下的開行方案見表3。

表3　固定追蹤列車間隔時間的列車開行方案參數(shù)

對比表2和表3可知：固定追蹤列車間隔時間與非固定追蹤列車間隔時間條件下對各優(yōu)化目標取極值時，乘客平均等待時間增加34.24%，列車平均滿載率降低0.04%，列車總走行公里數(shù)提高0.13%。因此，根據(jù)客流的動態(tài)需求采用非固定列車追蹤間隔時間，可以降低乘客的平均等待時間，減小列車開行總數(shù)，從而更好地滿足乘客和運營企業(yè)雙方的利益。

為了分析列車在大小交路模式與單一大交路模式下的運行方案差異，使用相同的客流數(shù)據(jù)和遺傳操作參數(shù)，得到單一大交路模式下列車運行數(shù)據(jù)的非支配解。為使數(shù)據(jù)具有可比性，分別在生成的非支配解集中取近似相同的列車平均滿載率，計算不同模式下乘客平均等待時間、列車總走行公里數(shù)和開行列車總數(shù)。并將其與大小交路模式下的結果進行對比，見表4和表5。

表4　單一大交路模式下不同時的列車開行方案參數(shù)

表5　大小交路模式下不同時的列車開行方案參數(shù)

注：()內(nèi)為大交路開行列車總數(shù)

由表4和表5可知：當開行列車的平均滿載率近似相等時，大小交路模式列車開行方案要明顯優(yōu)于單一大交路模式的列車開行方案；在開行列車總數(shù)相差無幾的情況下，單一大交路模式下的乘客平均等待時間遠高于大小交路模式下乘客平均等待時間。從計算過程的中間數(shù)據(jù)可知，在客流高峰時段，由于區(qū)段客流斷面的分布不均，單一大交路模式下共線路段的滯站乘客數(shù)量較大，致使乘客等待時間的增加。因此，考慮乘客出行需求的時間依賴特征，以及客流斷面分布不均的空間特征，開行大小交路模式列車，能夠同時減少乘客等待時間和列車總走行公里數(shù)。

5　結　論

(1)通過分析乘客出行需求的時間、空間分布特征，采用4參數(shù)Logistic函數(shù)對累計客流曲線分段擬合，推導出各車站在任意時間段內(nèi)客流需求量的計算公式。

(2)考慮運營企業(yè)和乘客雙方的不同需求，以最大、最小追蹤列車間隔時間和運力供需比為約束條件，以所有乘客平均等待時間最小、列車平均載客率最高、列車總走行公里最少為目標函數(shù)，建立城市軌道交通列車開行方案的多目標混合整數(shù)非線性優(yōu)化模型；結合自適應鄰域搜索策略，設計改進的NSGA-Ⅱ算法對模型求解，并根據(jù)大小交路模式的列車發(fā)車特點，設計特殊結構的編碼方式。

(3)以西安地鐵2號線某工作日的客流數(shù)據(jù)為例，對列車開行方案進行了優(yōu)化。結果表明，根據(jù)動態(tài)客流需求對大小路模式下的列車開行方案優(yōu)化，可有效減少乘客的平均等待時間，提高列車平均滿載率并減少列車總走行公里數(shù)，從而更好地滿足乘客和運營企業(yè)雙方利益訴求。

[1]SERAFINI P, UKOVICH W. A Mathematical Model for Periodic Scheduling Problems [J]. Siam Journal on Discrete Mathematics, 1989, 2(4):550-581.

[2]KWAN C M, CHANG C S. Application of Evolutionary Algorithm on a Transportation Scheduling Problem: the Mass Rapid Transit[C]//The 2005 IEEE Congress on Evolutionary Computation. Edinburgh: IEEE, 2005:987-994.

[3]LIEBCHEN C. The First Optimized Railway Timetable in Practice [J]. Transportation Science, 2008, 42(4): 420-435.

[4]KROON L, MAROTI G, HELMRICH M R, et al. Stochastic Improvement of Cyclic Railway Timetables [J]. Transportation Research Part B Methodological, 2008, 42(6):553-570.

[5]廖勇.公交化城際列車開行間隔優(yōu)化[J].鐵道學報,2010,32(1):8-12.

(LIAO Yong. The Headway Optimization of Intercity Trains of Mass Transit Type [J]. Journal of the China Railway Society, 2010, 32(1):8-12. in Chinese)

[6]KROON L, HUISMAN D, ABBINK E, et al. The New Dutch Timetable: the OR Revolution [J]. Interfaces, 2009, 39(1):6-17.

[7]CANCA D, ZARZO A, ALGABA E, et al. Confrontation of Different Objectives in the Determination of Train Scheduling [J]. Procedia-Social and Behavioral Sciences, 2011, 20(6):302-312.

[8]CURY J, GOMIDE F, MENDES M. A Methodology for Generation of Optimal Schedules for an Underground Railway System [J]. IEEE Transactions on Automatic Control, 1979, 25(2):217-222.

[9]ALBRECHT T. Automated Timetable Design for Demand-Oriented Service on Suburban Railways [J]. Public Transport, 2009, 1(1):5-20.

[10]NIU H, ZHOU X. Optimizing Urban Rail Timetable under Time-Dependent Demand and Oversaturated Conditions [J]. Transportation Research Part C Emerging Technologies, 2013, 36(11):212-230.

[11]BARRENA E, CANCA D, COELHO L C, et al. Exact Formulations and Algorithm for the Train Timetabling Problem with Dynamic Demand[J]. Computers & Operations Research, 2014, 44(3):66-74.

[12]HASSANNAYEBI E, SAJEDINEJAD A, MARDANI S. Urban Rail Transit Planning Using a Two-Stage Simulation-Based Optimization Approach [J]. Simulation Modeling Practice & Theory, 2014, 49:151-166.

[13]TIAN Q, ZHANG J, WANG H. Equilibrium Properties of the Morning Peak-Period Commuting in a Many-to-One Mass Transit System [J].Transportation Research Part B, 2007,41(6):616-631.

[14]程婕,彭其淵,趙軍. 城市軌道交通列車交路優(yōu)化模型[J]. 西南交通大學學報, 2013, 48(6):1116-1121.

(CHENG Jie，PENG Qiyuan，ZHAO Jun. Train Routing Optimization Model for Urban Rail Transit [J]. Journal of Southwest Jiaotong University, 2013, 48(6):1116-1121. in Chinese)

[15]王媛媛,倪少權.城市軌道交通大小交路模式列車開行方案的優(yōu)化[J].鐵道學報,2013, 35(7):1-8.

(WANG Yuanyuan, NI Shaoquan. Optimization of Train Schedules of Full-Length Short-Turn Operation Modes in Urban Rail Transit[J]. Journal of the China Railway Society, 2013, 35(7):1-8. in Chinese)

[16]凌俊,胡雄,何紅弟,等.城市軌道交通非高峰期列車交路方案優(yōu)化[J].鐵道科學與工程學報, 2015(1):190-195.

(LING Jun, HU Xiong, HE Hongdi, et al. Optimization of the Train Routing Scheme during the Off-Peak Period in Urban Rail Transit[J]. Journal of Railway Science and Engineering, 2015(1):190-195. in Chinese)

[17]CANCA D, BARRENA E, ALGABA E, et al. Design and Analysis of Demand-Adapted Railway Timetables [J]. Journal of Advanced Transportation, 2014, 48(2):119-137.

[18]江志彬,徐瑞華,吳強,等. 計算機編制城市軌道交通共線交路列車運行圖[J].同濟大學學報:自然科學版, 2010, 38(5):692-696.

(JIANG Zhibin, XU Ruihua, WU Qiang, et al. Shared-Path Routing Timetable Computer Designing in Rail Transit System[J]. Journal of Tongji University: Natural Science, 2010, 38(5): 692-696. in Chinese)

[19]王彥棟. 大小交路套跑條件下網(wǎng)絡化城市軌道交通行車優(yōu)化模型研究[J].物流技術,2011, 30(21):71-74.

(WANG Yandong. Study on Optimization Model of Urban Transit Network Organization and Coordination with Long and Short Routing [J]. Logistics Technology, 2011, 30(21):71-74. in Chinese)

[20]FU L, DESSOUKY M. Models and Algorithms for Dynamic Headway Control [J]. Computers & Industrial Engineering, 2017, 103:271-281.

[21]LIN C H, LIN P L. Improving the Non-Dominated Sorting Genetic Algorithm Using a Gene-Therapy Method for Multi-Objective Optimization [J]. Journal of Computational Science, 2014, 5(2):170-183.

[22]席裕庚,柴天佑,揮為民.遺傳算法綜述[J].控制理論與應用,1996, 13(6):697-708.

(Xl Yugeng, CHAI Tianyou, YUN Weimin. Survey on Genetic Algorithm [J]. Control Theory and Applications, 1996, 13(6):697-708. in Chinese)