基于城市軌道交通大數(shù)據(jù)的站點(diǎn)客流存量反演與客流去向預(yù)測(cè)

劉 嬋，黃天印，江 渝

(1.復(fù)旦大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，上海 200433；2.上海申通地鐵集團(tuán)有限公司，上海 201103；3.上海財(cái)經(jīng)大學(xué) 數(shù)學(xué)學(xué)院，上海 200433)

隨著我國(guó)城市規(guī)模不斷擴(kuò)大和經(jīng)濟(jì)建設(shè)飛速的發(fā)展，城市化進(jìn)程在逐步加快.以軌道交通為骨干的公共交通體系在為城市居民提供安全、快速、舒適的交通環(huán)境的同時(shí)，也成為了解決大城市交通擁堵、環(huán)境污染問題的主要途徑.近幾年國(guó)內(nèi)城市軌道交通行業(yè)實(shí)現(xiàn)超常規(guī)高速發(fā)展，預(yù)計(jì)到2020年年底全國(guó)擁有軌道交通的城市將達(dá)到50個(gè)，總通車?yán)锍虒⑦_(dá)到近6000km，總投資將達(dá)4萬億元的規(guī)模.截至2018年12月，上海市城市軌道交通路網(wǎng)共有415個(gè)站點(diǎn)，里程長(zhǎng)達(dá)673km，幾乎覆蓋了整個(gè)城市，運(yùn)營(yíng)里程已經(jīng)躋身世界第一.軌道交通路網(wǎng)規(guī)模日益龐大、結(jié)構(gòu)日益復(fù)雜，對(duì)路網(wǎng)的安全運(yùn)營(yíng)管理提出了一個(gè)極大的挑戰(zhàn).利用軌道交通進(jìn)出站大數(shù)據(jù)，實(shí)時(shí)掌握路網(wǎng)中各個(gè)站點(diǎn)的客流存量和各條線路上的客流負(fù)載信息，及時(shí)準(zhǔn)確地對(duì)路網(wǎng)超負(fù)載的可能位置和時(shí)間作出預(yù)警，進(jìn)而通過限流、調(diào)整行車間隔等手段有效控制引導(dǎo)客流，從而有效防控事故風(fēng)險(xiǎn)、提高乘客乘車舒適度，是路網(wǎng)精細(xì)化管理中最重要的課題.

該問題的數(shù)學(xué)建模與算法主要是在每個(gè)乘客都選擇最短出行路徑的假設(shè)下(參見文獻(xiàn)[1])，利用乘客進(jìn)出任意兩個(gè)站點(diǎn)的公共交通卡記錄數(shù)據(jù)來實(shí)現(xiàn).特別需要解決如何通過大數(shù)據(jù)將客流量分配到各條最短路徑上，從而準(zhǔn)確反演各個(gè)站點(diǎn)的實(shí)時(shí)客流存量和有效預(yù)測(cè)客流去向.文獻(xiàn)[2-11]討論了用于確定最短出行路徑的K短路搜索算法和Dial算法，以及計(jì)算客流去向分配比率的Logit模型等.雖然這些算法都很有效，但模型中多設(shè)定了諸多變量并通過日常問卷產(chǎn)生的數(shù)據(jù)來進(jìn)行計(jì)算，還沒有能夠充分利用現(xiàn)有的交通卡進(jìn)出站大數(shù)據(jù)來進(jìn)行反演或者預(yù)測(cè)的研究.

本文利用圖論中交通/流量網(wǎng)絡(luò)的概念對(duì)軌道交通路網(wǎng)進(jìn)行了拓?fù)浣?，?duì)各個(gè)站點(diǎn)通過閘機(jī)進(jìn)/出站客流量和通過線路到達(dá)/離開客流建立了客流守恒公式.基于該守恒公式和大數(shù)據(jù)機(jī)器學(xué)習(xí)算法對(duì)路網(wǎng)每個(gè)站點(diǎn)進(jìn)出站數(shù)據(jù)進(jìn)行分析和挖掘，得到了將路網(wǎng)客流量“分配”到每對(duì)進(jìn)出站點(diǎn)間K條最短路徑上的比率，進(jìn)而建立了反演各個(gè)站點(diǎn)客流存量和對(duì)線路客流負(fù)載進(jìn)行預(yù)測(cè)的數(shù)值算法.

1 反演預(yù)測(cè)模型和算法的建立

我們利用圖論對(duì)研究的實(shí)際問題建立相應(yīng)的數(shù)學(xué)模型.

1.1 交通/流量網(wǎng)絡(luò)

上海軌道交通的部分路網(wǎng)結(jié)構(gòu)如圖1(a)所示.根據(jù)這個(gè)路網(wǎng)結(jié)構(gòu)我們可以用圖論建立交通網(wǎng)絡(luò)/流量網(wǎng)絡(luò)(參見文獻(xiàn)[12])，即建立如圖1(b)所示的有向圖G=(S,s,t,E).這里：(S,s,t)是頂點(diǎn)集；S是模擬M個(gè)現(xiàn)實(shí)站點(diǎn)S1,S2,…,SM的集合；s是流量只出不進(jìn)的虛擬頂點(diǎn)即源點(diǎn)(source)s1,s2,…,sM組成的集合；t是流量只進(jìn)不出的虛擬頂點(diǎn)即匯點(diǎn)(sink)t1,t2,…,tM組成的集合；E是邊集.

由于有3類頂點(diǎn)，在邊集E的邊上定義3類流量函數(shù)：

2) 從源點(diǎn)si進(jìn)入站點(diǎn)Si(i=1,2,…,M)的進(jìn)站(客)流量函數(shù)Ii；

3) 從站點(diǎn)Si進(jìn)入?yún)R點(diǎn)ti(i=1,2,…,M)的出站(客)流量函數(shù)Oi.

同時(shí)，可以定義邊集E的任一條邊上的容量函數(shù)(即最大流量函數(shù))為c(e)(?e∈E).顯然這里的流量函數(shù)fi,j(或Ii,Oi)和容量函數(shù)c(e)與時(shí)間相關(guān).在固定時(shí)刻t，應(yīng)該滿足以下兩個(gè)條件：

1) 容量限制(Capacity constraints)：每條邊e上的流量函數(shù)fi,j(或Ii,Oi)≤c(e);

2) (客)流守恒(Flow conservation)：對(duì)于每個(gè)站點(diǎn)Si，t時(shí)刻前后流量函數(shù)滿足：

(1)

式(1)等號(hào)左(或右)邊值即為站點(diǎn)Si在t時(shí)刻的客流存量，記為Ci(t).客流存量的概念在軌道交通網(wǎng)絡(luò)管理決策中扮演了重要角色.一方面，它衡量了軌道交通路網(wǎng)的承載能力；另一方面，它可以反映軌道交通網(wǎng)絡(luò)的繁忙程度，從而為軌道交通限流等舉措提供參考.

正確反演實(shí)時(shí)客流存量Ci(t)是本文需要解決的主要問題.從監(jiān)測(cè)和實(shí)時(shí)記錄的角度看，軌道交通網(wǎng)絡(luò)中可以獲取的數(shù)據(jù)非常有限.可能獲得的原始數(shù)據(jù)主要是乘客出入站點(diǎn)使用公共交通卡的記錄，每條記錄可以包含的信息僅為：卡號(hào)、每次軌道交通出行的金額、進(jìn)出的站點(diǎn)及相應(yīng)時(shí)間(如表1所示).但是由于上海軌道交通除個(gè)別站點(diǎn)外實(shí)行的是“不出站換乘”，將進(jìn)出站數(shù)據(jù)應(yīng)用到式(1)中也只能確定Ii(t)和Oi(t)，無法確定fi,j或者fj,i的信息.

表1 公共交通卡出入站記錄Tab.1 Public transport card entry and exit records

1.2 離散時(shí)間表示

但是當(dāng)我們對(duì)時(shí)間作離散化，并考慮如下假設(shè)：

假設(shè)1為描述軌道交通網(wǎng)絡(luò)中客流流動(dòng)過程，假設(shè)：

1) 所有軌道交通線路上所有軌道交通的發(fā)車間隔、運(yùn)行速度均相同，并記發(fā)車間隔為Δt；

3)t0

4) 初始時(shí)刻記為t0，結(jié)束運(yùn)營(yíng)的時(shí)間記為tN+1；

5) 相鄰站點(diǎn)間距離相同，列車行駛需要耗時(shí)Δt，即假設(shè)以相鄰站點(diǎn)距離中點(diǎn)為界，即使乘客在列車上，也等同于在兩個(gè)站點(diǎn)中的一個(gè)站點(diǎn)上；

6) 忽略軌道交通到達(dá)站點(diǎn)與再次發(fā)車的時(shí)間間隔；

7) 時(shí)間段[tj-1,tj)進(jìn)站的客流必將搭上tj時(shí)刻到站的軌道交通；

8) 同站換乘耗時(shí)Δt；

9) 時(shí)間段[tj-1,tj)從相鄰站點(diǎn)坐車抵達(dá)的出站乘客，在tj時(shí)刻出站，[t0,t1]內(nèi)沒有出站乘客；

10) 站點(diǎn)間線路客流量的最大承載量為無窮大，進(jìn)站出站的最大客流限制也是無窮大，即容量函數(shù).

c(e)≡∞ ?e∈E.

表2 離散時(shí)間下單個(gè)乘客的乘車軌跡Tab.2 The track of a single passenger in discrete time

這樣，時(shí)間段(tk-1,tk]內(nèi)站點(diǎn)Si聚集的客流有兩個(gè)來源：一個(gè)是該時(shí)間段內(nèi)通過閘機(jī)進(jìn)入Si的；另一個(gè)是搭乘列車在tk到達(dá)(或途經(jīng))站點(diǎn)Si的客流.同樣地，該站點(diǎn)下個(gè)時(shí)間段(tk,tk+1]的客流去向包括tk+1時(shí)刻通過閘機(jī)從Si出站的，以及搭乘tk+1時(shí)刻到站的軌道交通前往鄰接站點(diǎn)的.根據(jù)表2，tk時(shí)刻各個(gè)流量函數(shù)可以表示按乘客卡號(hào)進(jìn)行加和：

(2)

這里δx,y={1(x=y)，或0(x≠y)}是Kronecker函數(shù).記tk時(shí)刻前剛進(jìn)站的乘客數(shù)量為a，此刻剛隨車到達(dá)并出站的乘客數(shù)量為c，僅在此刻途徑Si站、不是剛進(jìn)站也不是要出站的乘客數(shù)量為b，則易知Ii(tk)=a，Oi(tk+1)=c，

流量函數(shù)能滿足客流守恒式(1)，且相應(yīng)的客流存量為

(3)

1.3 基于公共交通卡數(shù)據(jù)的客流存量反演與客流去向預(yù)測(cè)

從式(3)可以看到，如果我們由單個(gè)乘客數(shù)據(jù)(id,Sin,Sout,tk1,tk2)可以重構(gòu)出乘車軌跡表2的話，那么就可以計(jì)算出流量函數(shù)(2)，從而得到tk時(shí)刻的客流存量：

這就是我們需要解決的問題1：客流存量反演問題.

單純根據(jù)單個(gè)乘客的離散數(shù)據(jù)DAid來具體確定該乘客選擇的具體路線幾乎是不可能的.但是，盡管每個(gè)人的情況千差萬別，存在諸如坐過站、坐錯(cuò)車等情況，乘客選擇路線基本上還是基于路線長(zhǎng)度、換乘時(shí)間和線路的擁堵程度等因素.通過基于概率統(tǒng)計(jì)的大數(shù)據(jù)分析技術(shù)，對(duì)某類乘客的大概率行為進(jìn)行分析，考察該類乘客在固定站點(diǎn)區(qū)間上的路線選擇分布，而不是考察單個(gè)乘客的路線選擇，這為我們解決問題提供了思路，即我們對(duì)單個(gè)乘客數(shù)據(jù)(id,Sin,Sout,tk1,tk2)按照相同出入站點(diǎn)和相同進(jìn)站時(shí)刻(Sin,Sout,tk1)進(jìn)行分組，則對(duì)于每個(gè)離散時(shí)刻tk(k=0,1,…,N+1)，存在sk組數(shù)據(jù)：

其中：sf指在tk時(shí)刻在Sin站點(diǎn)進(jìn)站乘車且有相同終點(diǎn)站Sout的乘客數(shù)量.注意到sk≤M×M，即分組數(shù)據(jù)的組數(shù)不超過進(jìn)出站(Sin,Sout)組合數(shù)的總數(shù)，因此矩陣ODk的維數(shù)是有限的.

由于每組分組數(shù)據(jù)(sf,Sin,Sout)可選的線路總是有限的，假設(shè)途經(jīng)站點(diǎn)一樣但出站時(shí)刻不同的線路定義為不同路線，有fΓ位乘客選擇了路線Γ，每個(gè)乘客的線路軌跡可記為多元函數(shù)Γ：

其中：SΓ(t)是t時(shí)刻該路線乘客途經(jīng)的站點(diǎn).注意到在進(jìn)出站時(shí)間段(tk1,tk2)以外的時(shí)刻，乘客途經(jīng)站點(diǎn)設(shè)為0，即

(4)

說明1這個(gè)Γ包括所有不同起點(diǎn)-終點(diǎn)但都經(jīng)過站點(diǎn)Si的線路.

這樣估計(jì)選擇各條路線Γ的客流人數(shù)fΓ是非常重要的，特別需要給定如下假設(shè)：

假設(shè)2給定起始站和終點(diǎn)站，1) 忽略實(shí)際中的特殊情況，如坐過站；2) 乘客傾向于用時(shí)少、少換乘的線路.

此外，利用式(3)預(yù)測(cè)tk+1時(shí)刻出站客流Oi與去往鄰接站點(diǎn)的客流fi,j是需要解決的問題2：客流去向預(yù)測(cè)問題.這里我們重新定義：

綜上所述，本文中需要解決的問題如下：

1.4 反演預(yù)測(cè)算法

根據(jù)前述討論，我們給出客流重構(gòu)算法如下：

1) 對(duì)于每個(gè)時(shí)刻tk，統(tǒng)計(jì)分組數(shù)據(jù)ODk；

2) 對(duì)于每一條分組數(shù)據(jù)，即矩陣ODk中的每一行，即(sf,Sin,Sout)，計(jì)算站點(diǎn)Sin與站點(diǎn)Sout之間的前K條最短路徑；

4) 由式(4)計(jì)算軌道交通交通流Ii(tk)和fj,i(tk)；

5) 由式(3)計(jì)算客流存量Ci(tk).

說明2對(duì)該重構(gòu)算法有具體說明如下：

1) 我們采用了貪心算法(Greedy algorithm)計(jì)算任意兩個(gè)站點(diǎn)Si與Sj之間的前K條最短路徑[12]；

2 數(shù)值測(cè)試

這里我們利用上海軌道交通路網(wǎng)數(shù)據(jù)對(duì)前述的客流存量反演與客流去向預(yù)測(cè)問題進(jìn)行數(shù)值測(cè)試.

2.1 客流存量反演

來進(jìn)行算法的誤差分析，即定義

為站點(diǎn)Si在tk+1時(shí)刻的出站量誤差.

根據(jù)客流重構(gòu)算法和說明2，我們利用2018年上半年上海軌道交通的“OD”表數(shù)據(jù)進(jìn)行測(cè)試：

1) 路線數(shù)K=3(K最短路徑算法一般假設(shè)K≤3，參見文獻(xiàn)[6])；

2)大數(shù)據(jù)分析得到傾向度(即線路選擇概率)：(p1,p2,p3)=(0.7,0.2,0.1).

反演得到的出站客流量如圖2所示，出站量誤差如圖3所示.由圖可以看到：出站客流量大，即有效樣本量大能夠有效提高反演的準(zhǔn)確度.

圖4給出了反演得到的某工作日上海最重要的幾個(gè)軌道交通站點(diǎn)客流存量的變化.存量絕對(duì)數(shù)值符合站點(diǎn)情況，時(shí)間方向的峰值也對(duì)應(yīng)早晚上下班高峰時(shí)間.氣泡圖圖5反映的是反演得到的全路網(wǎng)各站點(diǎn)的日均客流存量，反演的數(shù)值與實(shí)際情況相符.我們可以更直觀地看到圖4中各站點(diǎn)的客流存量大小與其周邊軌道交通結(jié)構(gòu)網(wǎng)的關(guān)系，當(dāng)然我們還可以繪制各個(gè)時(shí)刻各個(gè)站點(diǎn)的客流存量氣泡圖，并由此推斷客流分布的流向.這充分說明了客流存量這一指標(biāo)在軌道交通運(yùn)營(yíng)管理中的重要作用.

2.2 客流去向預(yù)測(cè)

致謝：感謝復(fù)旦大學(xué)數(shù)學(xué)科學(xué)學(xué)院研究生李瑋、劉小滿對(duì)本工作的幫助.感謝上海申通地鐵集團(tuán)有限公司信息中心的數(shù)據(jù)支持，以及上海久譽(yù)軟件系統(tǒng)有限公司的大力協(xié)助.