城市軌道交通時(shí)刻表優(yōu)化技術(shù)框架及關(guān)鍵技術(shù)環(huán)節(jié)*

汪 林 張 寧 邵家玉 王宏博

(1.東南大學(xué)自動(dòng)化學(xué)院,210018,南京; 2.東南大學(xué)智能運(yùn)輸系統(tǒng)研究中心,210018,南京;3.北京城建設(shè)計(jì)發(fā)展集團(tuán)股份有限公司,100045,北京//第一作者,碩士研究生)

?

城市軌道交通時(shí)刻表優(yōu)化技術(shù)框架及關(guān)鍵技術(shù)環(huán)節(jié)*

汪 林1張 寧2邵家玉1王宏博3

(1.東南大學(xué)自動(dòng)化學(xué)院,210018,南京; 2.東南大學(xué)智能運(yùn)輸系統(tǒng)研究中心,210018,南京;3.北京城建設(shè)計(jì)發(fā)展集團(tuán)股份有限公司,100045,北京//第一作者,碩士研究生)

時(shí)刻表優(yōu)化技術(shù)是城市軌道交通運(yùn)營(yíng)管理所涉及的一項(xiàng)關(guān)鍵技術(shù),其實(shí)施好壞直接影響到城市軌道交通運(yùn)營(yíng)的各個(gè)環(huán)節(jié)。針對(duì)當(dāng)前實(shí)際運(yùn)營(yíng)過(guò)程中,列車時(shí)刻表的優(yōu)化調(diào)整顯著受制于斷面客流預(yù)估精度的現(xiàn)狀,借助城市軌道交通AFC(自動(dòng)售檢票)系統(tǒng)采集的乘客交易信息,提出了一種基于客流信息的城市軌道交通時(shí)刻表優(yōu)化技術(shù)框架,并對(duì)其核心模塊功能實(shí)現(xiàn)的關(guān)鍵技術(shù)環(huán)節(jié)進(jìn)行了闡述,探討了基于客流特性參數(shù)的發(fā)車模型。

城市軌道交通; 時(shí)刻表優(yōu)化; 有序樣本聚類; 混合遺傳算法

First-author′s address School of Automation,Southeast University,210018,Nanjing,China

隨著城市軌道交通的迅猛發(fā)展,其路網(wǎng)結(jié)構(gòu)日趨復(fù)雜,客流量日益增大。城市軌道交通系統(tǒng)能否正常、高效地運(yùn)營(yíng),最大限度地發(fā)揮其骨干作用,不僅取決于軌道和車輛等基礎(chǔ)設(shè)施條件,更有賴于運(yùn)營(yíng)管理及其技術(shù)手段的先進(jìn)性。

在城市軌道交通系統(tǒng)中,編制運(yùn)營(yíng)調(diào)度計(jì)劃是運(yùn)營(yíng)管理的基礎(chǔ)。運(yùn)營(yíng)調(diào)度計(jì)劃的核心是列車時(shí)刻表。列車時(shí)刻表是運(yùn)營(yíng)公司組織列車運(yùn)營(yíng)的具體作業(yè)計(jì)劃,指導(dǎo)著城市軌道交通運(yùn)營(yíng)的全過(guò)程,其設(shè)計(jì)的好壞直接影響到線上列車的調(diào)度,進(jìn)而影響乘客的出行和運(yùn)營(yíng)公司的效益。因此,系統(tǒng)地構(gòu)建基于客流信息的城市軌道交通時(shí)刻表優(yōu)化技術(shù)具有如下現(xiàn)實(shí)意義:①可利用當(dāng)前(近期)同類特征日的客流數(shù)據(jù)對(duì)現(xiàn)行時(shí)刻表進(jìn)行合理優(yōu)化,為城市軌道交通日常調(diào)度調(diào)整提供了新思路、新方法;②可與短時(shí)客流預(yù)測(cè)技術(shù)相結(jié)合,為未來(lái)一定時(shí)期內(nèi)行車計(jì)劃時(shí)刻表的制定提供技術(shù)支撐。

1 時(shí)刻表優(yōu)化技術(shù)框架構(gòu)建及核心模塊解析

本文所構(gòu)建的城市軌道交通時(shí)刻表優(yōu)化技術(shù)框架主要由客流數(shù)據(jù)提取/預(yù)處理模塊、站間客流分配律提取模塊、站臺(tái)乘客到達(dá)率提取模塊、調(diào)度模型構(gòu)建/解析模塊、優(yōu)化結(jié)果輸出/驗(yàn)證模塊組成。各模塊功能界定如下:客流數(shù)據(jù)提取/預(yù)處理模塊負(fù)責(zé)對(duì)原始客流數(shù)據(jù)進(jìn)行預(yù)處理,提取后續(xù)環(huán)節(jié)所需的有效乘客交易信息;站間客流分配律提取模塊、站臺(tái)乘客到達(dá)率提取模塊以預(yù)先提取的有效乘客交易信息、視頻監(jiān)測(cè)器采集的通道(樓梯)客流量/乘客步速數(shù)據(jù)、站廳平面布置圖標(biāo)注的通道(樓梯)尺寸/乘客進(jìn)站路徑作為模塊輸入,轉(zhuǎn)換得到后續(xù)建模所需的客流特性參數(shù);調(diào)度模型構(gòu)建/解析模塊作為本框架的核心,承擔(dān)了基于客流特性參數(shù)的調(diào)度模型建立以及優(yōu)化求解功能;優(yōu)化結(jié)果輸出/驗(yàn)證模塊能夠?qū)⒄{(diào)度模型的求解結(jié)果轉(zhuǎn)換為相應(yīng)的列車時(shí)刻表,以供運(yùn)營(yíng)調(diào)度部門參考。本體系框架及各模塊間耦合關(guān)系如圖1所示。

圖1 城市軌道交通時(shí)刻表優(yōu)化技術(shù)應(yīng)用框架

1.1 客流數(shù)據(jù)提取/預(yù)處理模塊

該模塊的輸入數(shù)據(jù)來(lái)源于城市軌道交通自動(dòng)售檢票(AFC)系統(tǒng)采集的歷史上某線路完整的乘客交易信息。由于該交易記錄過(guò)于龐大且對(duì)本文研究有所冗余,故須編寫(xiě)程序?qū)λ栊畔?單向出站交易記錄及有效數(shù)據(jù)項(xiàng))進(jìn)行提取,并進(jìn)行有效性驗(yàn)證。

1.2 站間客流分配規(guī)律提取模塊

該模塊的主要功能是根據(jù)不同時(shí)段內(nèi)城市軌道交通進(jìn)站客流在出站站點(diǎn)間分布規(guī)律的差異。將一個(gè)完整的運(yùn)營(yíng)日劃分為若干個(gè)前后相繼的運(yùn)營(yíng)時(shí)段,并確定各運(yùn)營(yíng)時(shí)段內(nèi)的站間客流分配規(guī)律。其實(shí)現(xiàn)環(huán)節(jié)包括:

(1) 以客流數(shù)據(jù)提取及預(yù)處理模塊提供的有效乘客交易信息作為模塊輸入,計(jì)算單位時(shí)間間隔ΔT(擬選取10 min)內(nèi)站間客流OD(起訖點(diǎn))分配矩陣序列S。S={s1,s2,…,sk,…}(其中(sk)ij表示對(duì)應(yīng)時(shí)間間隔內(nèi)從第i站進(jìn)站的乘客在第j站出站的分配率)。

(2) 將當(dāng)前較流行的Fisher有序樣品聚類分析方法推廣到多維情形,根據(jù)單位時(shí)間間隔內(nèi)站間客流OD分配矩陣的聚類特性將運(yùn)營(yíng)日全天劃分為K個(gè)統(tǒng)計(jì)時(shí)段,并依此確定各時(shí)段時(shí)長(zhǎng)Tk及對(duì)應(yīng)的站間客流OD分配矩陣Ak(k= 1,2,…,K;K為劃分的運(yùn)營(yíng)時(shí)段數(shù);(Ak)ij表示第k時(shí)段內(nèi)從第i站進(jìn)站的乘客在第j站出站的分配率)。

1.3 站臺(tái)乘客到達(dá)率提取模塊

該模塊的主要功能是計(jì)算乘客通過(guò)閘機(jī)進(jìn)站的站點(diǎn)到達(dá)率,并在此基礎(chǔ)上考慮乘客站內(nèi)走行時(shí)間的影響,提取乘客到達(dá)站臺(tái)的規(guī)律。其實(shí)現(xiàn)環(huán)節(jié)包括:

(1) 以客流數(shù)據(jù)提取及預(yù)處理模塊提供的有效乘客交易信息作為模塊輸入,統(tǒng)計(jì)各站點(diǎn)給定時(shí)間間隔(擬選取15 min)內(nèi)乘客通過(guò)閘機(jī)進(jìn)站的平均到達(dá)率序列Lj。Lj={lj1,lj2,…,ljk,…}(j= 1,2,…,J;J為單線站點(diǎn)總數(shù)目;ljk表示對(duì)應(yīng)時(shí)間間隔內(nèi)乘客通過(guò)閘機(jī)進(jìn)入站點(diǎn)j的平均到達(dá)率)。

(2) 選取工程中廣泛使用的三次樣條插值函數(shù)對(duì)離散序列Lj進(jìn)行擬合,得到隨時(shí)間連續(xù)變化的乘客站點(diǎn)到達(dá)率rj(t)。

(3) 以視頻監(jiān)測(cè)器采集的通道(樓梯)客流量/乘客步速數(shù)據(jù)、站廳平面布置圖標(biāo)注的通道(樓梯)基本尺寸/乘客進(jìn)站路徑作為模塊輸入,計(jì)算乘客在各站點(diǎn)內(nèi)的平均走行時(shí)間δj;結(jié)合站內(nèi)走行時(shí)間的影響對(duì)站點(diǎn)到達(dá)率函數(shù)進(jìn)行修正,得出乘客站臺(tái)到達(dá)率函數(shù)Rj(t),近似有如下關(guān)系為Rj(t)=rj(t-δj)。

1.4 調(diào)度模型構(gòu)建/解析模塊

以站間客流分配律提取模塊和站臺(tái)乘客到達(dá)率提取模塊提供的客流特性參數(shù)(K、Tk、Ak、Rj(t))作為模塊輸入,構(gòu)建列車調(diào)度優(yōu)化模型并給出求解方程。其實(shí)現(xiàn)環(huán)節(jié)包括:

(2) 根據(jù)實(shí)際運(yùn)營(yíng)情況,選取平均滿載率θ和最大、最小發(fā)車間隔作為約束條件。

(4) 采用混合遺傳算法求解模型,得出優(yōu)化的分時(shí)發(fā)車間隔。

1.5 優(yōu)化結(jié)果輸出/驗(yàn)證模塊

該模塊的主要功能是將優(yōu)化模型求解所得的分時(shí)發(fā)車間隔轉(zhuǎn)換為列車時(shí)刻表,并可通過(guò)計(jì)算環(huán)節(jié)實(shí)現(xiàn)與現(xiàn)行發(fā)車時(shí)刻表各項(xiàng)指標(biāo)間的對(duì)比驗(yàn)證。其實(shí)現(xiàn)環(huán)節(jié)包括:

(1) 以調(diào)度模型構(gòu)建/解析模塊計(jì)算得出的分時(shí)發(fā)車間隔作為模塊輸入,按下式輸出各運(yùn)營(yíng)時(shí)段的發(fā)車時(shí)刻表:ti，k=tk+(i-1)×Δtk(其中i= 1,2,…,mk)。其中,ti,k表示第k時(shí)段的第i次車的發(fā)車時(shí)刻;tk表示第k時(shí)段的起始時(shí)刻,也是第k時(shí)段首班車的發(fā)車時(shí)刻;Δtk表示第k運(yùn)營(yíng)時(shí)段的發(fā)車間隔;mk表示第k時(shí)段總的發(fā)車次數(shù)。

(2) 將現(xiàn)行發(fā)車時(shí)刻表輸入該模塊,經(jīng)計(jì)算環(huán)節(jié)處理,得到優(yōu)化后的時(shí)刻表與現(xiàn)行發(fā)車時(shí)刻表各項(xiàng)指標(biāo)(如乘客平均候車時(shí)間、車內(nèi)實(shí)時(shí)平均乘客數(shù)、列車滿載率等)間的對(duì)比驗(yàn)證。

2 實(shí)現(xiàn)核心模塊功能涉及的關(guān)鍵技術(shù)環(huán)節(jié)

2.1 有效乘客交易信息提取

乘客交易原始數(shù)據(jù)的采集要求全面、充分、準(zhǔn)確。能否在數(shù)量龐大、種類繁多的乘客交易數(shù)據(jù)中提取出所需信息,對(duì)后續(xù)模塊的功能實(shí)現(xiàn)有著至關(guān)重要的影響。

當(dāng)乘客通過(guò)閘機(jī)進(jìn)出站點(diǎn)時(shí),城市軌道交通檢票設(shè)備自動(dòng)生成相應(yīng)的交易記錄,記載本次交易的交易類型、站點(diǎn)編號(hào)、設(shè)備編號(hào)、交易時(shí)間、本次出行進(jìn)入軌道交通系統(tǒng)的時(shí)間和站點(diǎn)等一系列當(dāng)前交易的相關(guān)信息,并將其上傳到城市軌道交通AFC系統(tǒng)的實(shí)時(shí)數(shù)據(jù)庫(kù)中[1]。考慮到乘客出站交易記錄中包含了進(jìn)站站點(diǎn)的相關(guān)信息,故可根據(jù)交易類型關(guān)鍵字對(duì)所有出站交易記錄進(jìn)行提取待用;其次,由于本文研究只涉及城市軌道交通線路某一個(gè)開(kāi)行方向,故需根據(jù)站間OD矢量方向?qū)λ谐稣窘灰子涗涍M(jìn)行上、下行分流;最后,鑒于出站交易記錄的數(shù)據(jù)項(xiàng)對(duì)本文研究有所冗余,可編制數(shù)據(jù)處理程序?qū)灰子涗浿械挠行?shù)據(jù)項(xiàng)進(jìn)行提取,以減輕后續(xù)模塊數(shù)據(jù)處理的負(fù)擔(dān)。

2.2 運(yùn)營(yíng)日統(tǒng)計(jì)時(shí)段劃分

從城市軌道交通實(shí)際運(yùn)營(yíng)效果來(lái)看,分時(shí)段等間隔發(fā)車方式體現(xiàn)了調(diào)度管理的靈活性和可操作性的統(tǒng)一,是城市軌道交通運(yùn)營(yíng)部門廣為采用的一種發(fā)車模式。通常的調(diào)度策略是在客流高峰期縮短發(fā)車間隔,以提高發(fā)車頻率的方式來(lái)滿足客流需求;在客流低谷期延長(zhǎng)發(fā)車間隔,通過(guò)減少發(fā)車次數(shù)以節(jié)約運(yùn)營(yíng)成本。交通調(diào)度優(yōu)化方面的研究大多借鑒了這一發(fā)車模式,以分時(shí)發(fā)車間隔為決策變量,依據(jù)不同的優(yōu)化目的構(gòu)建相應(yīng)的目標(biāo)函數(shù),通過(guò)模型求解得出優(yōu)化的發(fā)車方案[2-4]。

較常見(jiàn)的運(yùn)營(yíng)時(shí)段劃分方法,是根據(jù)交通線路特征區(qū)間斷面客流在時(shí)域內(nèi)的變化特征將運(yùn)營(yíng)日全天劃分為客流高峰時(shí)段、正常時(shí)段、低谷時(shí)段、過(guò)渡時(shí)段等若干運(yùn)營(yíng)時(shí)段[5]。鑒于斷面客流數(shù)據(jù)無(wú)法由歷史交易信息直接統(tǒng)計(jì)而只能借助站臺(tái)—列車交互模型進(jìn)行估算[6],本文根據(jù)單位時(shí)間間隔內(nèi)站間客流OD分配矩陣的聚類特性來(lái)進(jìn)行運(yùn)營(yíng)時(shí)段的劃分,體現(xiàn)了線路上各站點(diǎn)區(qū)域客流吸引能力的時(shí)空分布。值得注意的是,在提取單位時(shí)間間隔內(nèi)站間客流OD分配矩陣序列時(shí),單位時(shí)間間隔ΔT的選取可采取“試湊法”,即根據(jù)聚類分析的結(jié)果選擇使得類內(nèi)相似度較大而類間差異較明顯的待選方案,并依此計(jì)算各運(yùn)營(yíng)時(shí)段起訖及相應(yīng)的站間客流OD分配矩陣Ak。

2.3 調(diào)度優(yōu)化模型構(gòu)建

城市軌道交通屬于城市公共交通的范疇,與道路公交存在相似之處。因此,國(guó)內(nèi)外學(xué)者通常借鑒道路公交調(diào)度優(yōu)化的研究方法對(duì)城市軌道交通調(diào)度問(wèn)題進(jìn)行研究。由于道路公交并非封閉的交通運(yùn)輸系統(tǒng),難以全面、精確地對(duì)實(shí)時(shí)客流數(shù)據(jù)進(jìn)行統(tǒng)計(jì),道路公交調(diào)度模型通常是基于某種假定的客流到達(dá)規(guī)律(如符合均勻分布、泊松分布等)來(lái)計(jì)算統(tǒng)計(jì)時(shí)段內(nèi)的上車人數(shù);下車人數(shù)同樣需要根據(jù)某種事先約定的下車方案(如正比于車內(nèi)實(shí)時(shí)乘客數(shù)等)來(lái)確定?，F(xiàn)有的城市軌道交通研究大多沿用了此類方法,并取得了一些研究成果[7-9]。隨著城市軌道交通AFC系統(tǒng)的普遍采用,乘客交易數(shù)據(jù)的全面采集和客流特征的準(zhǔn)確提取成為可能,故本文借助預(yù)先提取的客流特征參數(shù)來(lái)統(tǒng)計(jì)各站臺(tái)乘降人數(shù)、計(jì)算站臺(tái)乘客的總等待時(shí)間;同時(shí),在建模過(guò)程中充分考慮了客流的滯后效應(yīng),即根據(jù)每班次列車抵達(dá)各站臺(tái)的時(shí)間來(lái)確定相匹配的客流特征參數(shù),使模型構(gòu)建更為精確。

2.3.1 基于客流特性參數(shù)的發(fā)車模型構(gòu)建

2.3.1.1 模型假設(shè)及運(yùn)營(yíng)條件簡(jiǎn)化

實(shí)際運(yùn)營(yíng)過(guò)程中,城市軌道交通列車運(yùn)行所處環(huán)境復(fù)雜多變,在給定客流需求的前提下,仍然受到諸多不確定因素的影響。因此,在將實(shí)際情況抽象為數(shù)學(xué)模型時(shí),需結(jié)合運(yùn)營(yíng)調(diào)度的實(shí)際狀況,作如下幾點(diǎn)假設(shè):

(1) 本文研究基于單條無(wú)換乘城市軌道交通線路,并認(rèn)為其運(yùn)營(yíng)調(diào)度具有獨(dú)立性,與其他線路運(yùn)營(yíng)狀況無(wú)關(guān);

(2) 在同一條城市軌道交通線路上開(kāi)行的列車車型一致;

(3) 在同一時(shí)間段內(nèi),相鄰兩列列車發(fā)車時(shí)間間隔相等;

(4) 各站點(diǎn)乘客站臺(tái)到達(dá)率Rj(t)及各時(shí)段內(nèi)站間客流OD矩陣Ak均為已知;

(5) 列車按時(shí)刻表準(zhǔn)時(shí)從首站發(fā)車,車速恒定,途中沒(méi)有意外事故發(fā)生,而且列車在各站點(diǎn)的停站時(shí)間相同;

(6) 每趟列車經(jīng)過(guò)車站后,站臺(tái)上時(shí)不會(huì)滯留有乘客,即在站臺(tái)等待的乘客均會(huì)乘上最近一趟列車;

(7) 在站臺(tái)等待的乘客在上車前不會(huì)從站臺(tái)離開(kāi)。

2.3.1.2 參數(shù)定義及耦合關(guān)系解析

ξ為與εiL，k相對(duì)應(yīng)的運(yùn)營(yíng)時(shí)段編號(hào)；ωij，k表示在第k時(shí)段從首站發(fā)出的第i次列車在離開(kāi)車站j時(shí)車內(nèi)實(shí)時(shí)乘客數(shù)。

2.3.2 約束條件選取

(2) 最大、最小發(fā)車間隔約束(任意相鄰兩車之間的發(fā)車間隔要滿足最大、最小發(fā)車時(shí)間間隔約束):Tmin≤Δtk≤Tmax,Tmax表示相鄰兩列列車之間的最大發(fā)車間隔;Tmin表示相鄰兩列列車之間的最小發(fā)車間隔。

2.3.3 優(yōu)化目標(biāo)函數(shù)設(shè)計(jì)

目標(biāo)函數(shù)中的權(quán)值系數(shù)應(yīng)根據(jù)優(yōu)化目標(biāo)的側(cè)重靈活選取,加權(quán)系數(shù)α、β分別反映乘客利益和運(yùn)營(yíng)公司利益在調(diào)度目標(biāo)中的地位。若調(diào)度首要考慮的是運(yùn)營(yíng)公司利益,那么應(yīng)使α<β;從公共服務(wù)的社會(huì)效益來(lái)看,應(yīng)更注重乘客的候車時(shí)間花費(fèi)和乘車體驗(yàn),因此本文建議模型中一般應(yīng)選用α>β。

3 結(jié)語(yǔ)

本文在充分吸收國(guó)內(nèi)外交通調(diào)度優(yōu)化研究成果的基礎(chǔ)上,借助城市軌道交通AFC系統(tǒng)采集的乘客交易信息,構(gòu)建城市軌道交通時(shí)刻表優(yōu)化技術(shù)框架,并對(duì)其核心模塊及功能實(shí)現(xiàn)進(jìn)行了具體闡述,以期為城市軌道交通運(yùn)營(yíng)調(diào)度提供參考。

[1] 王健,高朝暉,張寧,等. 南京軌道交通線網(wǎng)AFC系統(tǒng)的數(shù)據(jù)傳輸[J].都市快軌交通,2008,21(5):85.

[2] Andréde P,ROBIN L. Optimal timetables for public transportation [J].Transportation Research Part B,2001(35):789.

[3] 孫芙靈.公交調(diào)度中發(fā)車間隔的確定方法的探討[J].西安公路交通大學(xué)學(xué)報(bào),1997,17(28):44.

[4] 童剛.遺傳算法在公交調(diào)度中的應(yīng)用研究[J].計(jì)算機(jī)工程,2005,31(13):29.

[5] 陳茜,牛學(xué)勤,陳學(xué)武,等. 公交線路發(fā)車頻率優(yōu)化模型[J].公路交通科技,2004,21(2):103.

[6] 徐永實(shí),徐瑞華. 城市軌道交通線路客流分布的實(shí)時(shí)預(yù)測(cè)方法[J].同濟(jì)大學(xué)學(xué)報(bào)(自然科學(xué)版),2011,39(6):857.

[7] 章優(yōu)仕,金煒東. 基于遺傳算法的單線列車運(yùn)行調(diào)整體系[J].西南交通大學(xué)學(xué)報(bào)(自然科學(xué)版),2005,40(2):147.

[8] 任蘋(píng).混沌粒子群算法在高速旅客列車優(yōu)化調(diào)度中的應(yīng)用[C].2006 中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集.沈陽(yáng):東北大學(xué)出版社,2006,895-898.

[9] 牛惠民,陳明明,張明輝. 城市軌道交通列車開(kāi)行方案的優(yōu)化理論及方法[J].中國(guó)鐵道科學(xué),2011,32(4):128.

Technical Framework and Key Modules for Urban Rail Transit Timetable Optimization

WANG Lin, ZHANG Ning, SHAO Jiayu, WANG Hongbo

Timetable optimization technology is a key technology in urban rail transit operation and management, its implementation has direct impact on all aspects of rail transit operation. In the process of actual operation, optimization adjustment of train timetable is significantly limited by accurate prediction of the section passenger flow. With the collected passenger transaction information from urban rail transit AFC system, a technique application framework for optimization of rail transit timetable based on flow information is proposed, in which the core modules and function realization are discussed in detail. Various departure models based on passenger flow parameters are discussed.

urban rail transit; time table optimization; clustering of ordinal samples; hybrid genetic algorithm

*交通運(yùn)輸部建設(shè)科技項(xiàng)目(2015318J33080);江蘇省科技廳產(chǎn)學(xué)研聯(lián)合創(chuàng)新資金項(xiàng)目(BY2012197);南京地鐵專項(xiàng)科技項(xiàng)目(8550140042)

U 292.4

10.16037/j.1007-869x.2016.09.014

2014-10-31)