馮慧芳，柏鳳山，徐有基

(西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，蘭州730070)

0 引言

隨著網(wǎng)絡(luò)通信技術(shù)、定位導(dǎo)航技術(shù)及衛(wèi)星遙感技術(shù)的發(fā)展和廣泛應(yīng)用，獲取海量時空數(shù)據(jù)變得越來越容易，這些時空大數(shù)據(jù)記錄了移動對象(人、車、飛機(jī)、貨物等)的時空變化.具有時空屬性的大數(shù)據(jù)的產(chǎn)生為長時間、高精度、高效地跟蹤研究個體時空移動特征提供了可能[1-2].通過數(shù)據(jù)挖掘技術(shù)分析這些時空大數(shù)據(jù)，研究個體時空移動特征，能夠?yàn)槌鞘幸?guī)劃與管理[3]、交通監(jiān)控與預(yù)測[4]、旅游監(jiān)測與分析[5]等眾多領(lǐng)域的研究提供方法和決策指導(dǎo).

基于車輛的軌跡時空數(shù)據(jù)挖掘研究是目前國內(nèi)外城市大數(shù)據(jù)研究的熱點(diǎn)之一.車輛軌跡數(shù)據(jù)的分析和建模不僅為了解人們的移動模式提供了新的角度，也為以數(shù)據(jù)為中心的智慧城市的構(gòu)建、規(guī)劃與管理提供支撐[6-7].文獻(xiàn)[8]根據(jù)歷史GPS數(shù)據(jù)建立了一種復(fù)雜度較低的交通流量預(yù)測模型，并用真實(shí)車輛GPS數(shù)據(jù)對預(yù)測模型進(jìn)行了性能評價(jià).文獻(xiàn)[9]則是利用出租車軌跡數(shù)據(jù)創(chuàng)建一種新的軌跡路段出行時間模型，并采用紐約出租車數(shù)據(jù)驗(yàn)證了模型的有效性.文獻(xiàn)[10]使用出租車GPS歷史數(shù)據(jù)，通過對空車到達(dá)過程建模，預(yù)測單個乘客等候出租車需要時間.文獻(xiàn)[11]用浮動車GPS數(shù)據(jù)分析了羅馬南部EUR區(qū)交通流特征，并采用貝葉斯網(wǎng)絡(luò)、神經(jīng)網(wǎng)絡(luò)和季節(jié)ARIMA(Seasonal AutoRegressive Moving Average)對短時車輛速度的預(yù)測能力做了比較研究.文獻(xiàn)[12]根據(jù)GPS數(shù)據(jù)建立了能夠刻畫出行需求、速度和出行線路方向等特征的城市移動模型，應(yīng)用該模型可預(yù)測城區(qū)道路交通能力.文獻(xiàn)[13]以車輛軌跡數(shù)據(jù)為基礎(chǔ)，提出了一種基于車輛軌跡大數(shù)據(jù)的道路網(wǎng)快速變化發(fā)現(xiàn)與更新方法，該方法相比常規(guī)方法能正確判斷道路變化類型、區(qū)分真實(shí)變化與語義變化.

為了更好地理解城市交通狀態(tài)，本文以典型河谷型城市蘭州市為例，以出租車GPS軌跡數(shù)據(jù)為數(shù)據(jù)源，結(jié)合城市道路網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特征和交通流特性，建立基于有向加權(quán)復(fù)雜網(wǎng)絡(luò)的城市交通網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識別模型.

1 基于有向加權(quán)復(fù)雜網(wǎng)絡(luò)的城市路網(wǎng)模型

1.1 有向加權(quán)城市路網(wǎng)模型的構(gòu)建

復(fù)雜網(wǎng)絡(luò)模型用G=(V,E)表示，其中，V={v1,v2,…,vN}為節(jié)點(diǎn)集合，E={e1,e2,…,ew}為邊集合，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目為N=||V，邊數(shù)為W=||E，網(wǎng)絡(luò)鄰接矩陣用A(G)=(aij)N×N表示.對有向有權(quán)網(wǎng)絡(luò)，節(jié)點(diǎn)i到 j之間存在一條邊，則aij=wij；否則，aij=0.一般情況下，wij≠wji，即有向加權(quán)網(wǎng)絡(luò)的鄰接矩陣一般不對稱.

我們采用主方法構(gòu)建路網(wǎng)拓?fù)鋄14]，即以現(xiàn)實(shí)道路網(wǎng)絡(luò)的物理結(jié)構(gòu)為基礎(chǔ)，將道路的交叉口抽象為網(wǎng)絡(luò)中的節(jié)點(diǎn)，交叉口之間的路段映射為節(jié)點(diǎn)間的連邊，建立城市交通網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)模型.由于道路分為單向和雙向車道，因此根據(jù)車道類型構(gòu)建有向復(fù)雜網(wǎng)絡(luò)，方向代表車流方向，也表示了復(fù)雜網(wǎng)絡(luò)中邊的有向性.

1.2 網(wǎng)絡(luò)邊權(quán)的計(jì)算

在交通流理論中，交通流特性參數(shù)主要由流量、速度、密度這3個重要參數(shù)刻畫，這3個參數(shù)是相互影響的，并已驗(yàn)證得出三者間的量化關(guān)系[15]：流量等于速度和密度的乘積.由此可知，如果通過相應(yīng)的技術(shù)得到交通流速度，就可以根據(jù)相應(yīng)的公式和一些與道路相關(guān)的固定參數(shù)計(jì)算出密度及流量信息.因此，本文將路段平均速度這一交通流基礎(chǔ)參數(shù)作為構(gòu)建的有向復(fù)雜網(wǎng)絡(luò)的邊的權(quán)重.

出租車GPS軌跡數(shù)據(jù)中包括車輛ID、經(jīng)度、緯度、瞬時速度、記錄時間、方向角及車輛狀態(tài)信息.本文利用軌跡數(shù)據(jù)中所包含的速度信息進(jìn)行計(jì)算，得到路段i的平均速度為

式中：mj表示第j輛出租車在i條路段上返回的軌跡數(shù)據(jù)的總次數(shù)；uijk表示第j輛出租車在i條路段上返回的第k個點(diǎn)的瞬時速度.

1.3 網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識別算法

DWNodeRank算法是文獻(xiàn)[16]借鑒了著名的google排名算法PageRank算法提出的一種有向加權(quán)復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)重要性排名算法.該算法既考慮了節(jié)點(diǎn)的局部連接屬性，同時從整體上考慮了網(wǎng)絡(luò)連接關(guān)系對節(jié)點(diǎn)重要性的影響.具體步驟如下.

Step 1根據(jù)構(gòu)建的有向加權(quán)復(fù)雜網(wǎng)絡(luò)寫出其鄰接矩陣A，A=(wij)n×n.

Step 2對鄰接矩陣進(jìn)行歸一化處理，即將鄰接矩陣A的每一行除以該行非零向量之和，得到歸一化矩陣，該矩陣元素表示了一個節(jié)點(diǎn)到另一個節(jié)點(diǎn)的轉(zhuǎn)移概率，定義為概率轉(zhuǎn)移矩陣.如果網(wǎng)絡(luò)中存在懸虛節(jié)點(diǎn)(網(wǎng)絡(luò)中不存在指向其他節(jié)點(diǎn)邊的節(jié)點(diǎn)稱為懸虛節(jié)點(diǎn))，則重新計(jì)算概率轉(zhuǎn)移矩陣，其中η為布爾向量，如果該節(jié)點(diǎn)為懸虛節(jié)點(diǎn)，其值為1；否則，為0.

Step 3求概率轉(zhuǎn)移矩陣的轉(zhuǎn)置矩陣M=T.

Step 4計(jì)算DWNodeRank矩陣R，該矩陣，其中α為阻尼系數(shù)，α=0.85.該矩陣中值為1的特征值對應(yīng)的特征向量是其平穩(wěn)分布.

Step 5使用冪法迭代的思想求解DWNodeRank矩陣的平穩(wěn)分布，然后將得到的結(jié)果排序后即為網(wǎng)絡(luò)節(jié)點(diǎn)重要性的排序.

冪法迭代的具體實(shí)現(xiàn)步驟為：

(1)建立有向加權(quán)復(fù)雜網(wǎng)絡(luò)鄰接矩陣A，計(jì)算矩陣P,,M.

(2)根據(jù)DWNodeRank算法的Step4求出矩陣Rank.

(3)設(shè)Rank的初始迭代向量x=(x0,x1,…,xn)T，其中xi為節(jié)點(diǎn)vi的DWNodeRank初始值.

(4)迭代計(jì)算r=Rx.

(5)若‖‖x-r＜ε，迭代結(jié)束，返回r；否則，x=r，返回(4)，循環(huán)迭代.其中ε為迭代精度，一般設(shè)為10-8.

(6)迭代結(jié)束后得到的向量r就是DWNodeRank矩陣，將其結(jié)果按從大到小排序，即可得到網(wǎng)絡(luò)節(jié)點(diǎn)重要性的排序，最終識別網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn).

2 實(shí)驗(yàn)結(jié)果與分析

2.1 出租車GPS數(shù)據(jù)及其預(yù)處理

出租車GPS軌跡數(shù)據(jù)為蘭州市2017年3月6～12日連續(xù)7天的3 000輛出租車數(shù)據(jù)，這7天當(dāng)中5天是工作日，另外2天是休息日，正好可以反映工作日和休息日城市交通狀況和居民出行特征，數(shù)據(jù)集具有一定代表性.原始數(shù)據(jù)是由出租車上的GPS裝置定時向蘭州市城市交通運(yùn)輸管理處的出租車調(diào)度監(jiān)管信息中心發(fā)送數(shù)據(jù)，由中心系統(tǒng)數(shù)據(jù)處理后存入服務(wù)器的Oracle數(shù)據(jù)庫中.GPS軌跡數(shù)據(jù)包括車輛ID、經(jīng)度、緯度、瞬時速度、記錄時間、車頭朝向及車輛載客信息.軌跡點(diǎn)采樣時間間隔為30 s，數(shù)據(jù)集大小約10.6 G.

在出租車GPS數(shù)據(jù)采集中不可避免的會產(chǎn)生偏差，比如終端設(shè)備故障、傳輸故障等，使得直接采集的GPS數(shù)據(jù)或多或少都是不完整的、不一致的，必須對原始GPS數(shù)據(jù)進(jìn)行預(yù)處理.GPS數(shù)據(jù)預(yù)處理主要包括數(shù)據(jù)清理和路網(wǎng)拓?fù)淦ヅ?數(shù)據(jù)清理就是通過處理GPS數(shù)據(jù)中的離群點(diǎn)、缺失值、冗余值等解決原始數(shù)據(jù)的不完整性和不一致性問題.由于GPS系統(tǒng)定位精度的問題，出租車GPS數(shù)據(jù)存在一定的誤差，使得軌跡點(diǎn)往往并不完全在道路上，因此需要真實(shí)的城市路網(wǎng)地圖數(shù)據(jù)對其進(jìn)行匹配糾正.本文通過MNTG(Minnesota Traffic Generator)[17]獲取蘭州市城區(qū)路網(wǎng)拓?fù)湫畔ⅲ捎脦缀翁匦缘姆椒╗18]對租車軌跡數(shù)據(jù)進(jìn)行路網(wǎng)拓?fù)淦ヅ?具體流程如圖1所示.圖2為蘭州市城區(qū)部分路網(wǎng)拓?fù)浜?輛出租車部分GPS軌跡數(shù)據(jù)，其中黑色線表示路網(wǎng)，黑色點(diǎn)表示出租車軌跡點(diǎn).

圖1 GPS數(shù)據(jù)預(yù)處理流程Fig.1 GPS data processing flow chart

圖2 部分路網(wǎng)拓?fù)浜?輛出租車部分GPS軌跡數(shù)據(jù)Fig.2 Part of the road network topology and part of the GPS data for a taxi

2.2 城市交通狀態(tài)分析

我國公安部于2002年公布了《城市交通管理評價(jià)指標(biāo)體系》，以機(jī)動車行程平均速度為參數(shù)對城市道路交通擁堵進(jìn)行量化定義[19]，具體級別如表1所示.

表1 我國城市道路交通擁堵評價(jià)標(biāo)準(zhǔn)當(dāng)前工況Table 1 Evaluation criteria of urban road traffic congestion in China

由表1可知，平均速度小于20 km/h的路段為擁堵路段，定義全天24 h中速度小于20 km/h的路段占總路段的比例為擁堵路段比，用該參數(shù)衡量城市交通擁堵情況.圖3為星期一和星期日全天24 h的擁堵路段比變化趨勢.

圖3 擁堵路段占比Fig.3 The proportion of congested roads

從圖3中可看出星期一擁堵路段比的變化趨勢：7:00-8:00和17:00-18:00為路段擁擠的高峰期；12:00下班時間和14:00上班時間有擁堵小高峰，但與7:00-8:00和17:00-18:00相比較，擁堵有所緩解，這主要是因?yàn)槲缧輹r間相對較短，部分離家遠(yuǎn)的人選擇不回家；19:00以后，擁堵路段的占比逐漸下降.按理說在23:00-6:00這段時間應(yīng)該很少有堵車路段，但是我們的統(tǒng)計(jì)結(jié)果顯示擁堵路段比仍約12%，這是由于我們采用路段平均速度度量擁堵情況，而且在深夜和凌晨這個時間段內(nèi)，由于路上光線不好，出租車司機(jī)駕駛非常小心，行駛速度相對較慢，故仍能統(tǒng)計(jì)到擁堵路段.

星期日與星期一擁堵路段比的變化趨勢明顯不同：星期一7:00的擁堵路段比為0.4，星期日僅為0.18，這說明在周末，一定比例的人還是選擇早晨留在家里休息；星期日8:00-14:00擁堵路段比整體為上升趨勢，這說明出門的人在不斷增加，而且出門時間相對隨意；19:00以后，擁堵路段逐漸下降.通過對工作日和休息日的GPS數(shù)據(jù)分析，我們發(fā)現(xiàn)圖3路段擁堵的總體趨勢與人們的日常生活規(guī)律基本一致.

路段平均速度反映了交通的擁堵狀況，即平均速度越小，道路越擁堵.由于篇幅所限，我們只呈現(xiàn)了星期一7:00和23:00兩個時間的可視化交通狀態(tài)，如圖4所示.兩者對比發(fā)現(xiàn)，7:00擁堵路段明顯較多，而且主要集中在西站什字、城關(guān)區(qū).

2.3 城市路網(wǎng)關(guān)鍵節(jié)點(diǎn)識別

首先，以現(xiàn)實(shí)道路網(wǎng)絡(luò)的物理結(jié)構(gòu)為基礎(chǔ)，建立路網(wǎng)絡(luò)拓?fù)?然后，根據(jù)道路屬性(單向或雙向車道)構(gòu)建有向網(wǎng)絡(luò)，并以各個路段不同方向的車輛平均速度為有向網(wǎng)絡(luò)的邊的權(quán)重，最終將城市路網(wǎng)抽象為一個有向加權(quán)復(fù)雜網(wǎng)絡(luò).最后，根據(jù)DWNodeRank算法，對路網(wǎng)拓?fù)渲械年P(guān)鍵節(jié)點(diǎn)進(jìn)行識別研究.

以小時為時間粒度，分析每個小時路網(wǎng)拓?fù)渲械年P(guān)鍵節(jié)點(diǎn)，研究結(jié)果表明隨著時間的變化，交通狀態(tài)和網(wǎng)絡(luò)節(jié)點(diǎn)的排名都在變化，但網(wǎng)絡(luò)節(jié)點(diǎn)排名變化較小，也就是說節(jié)點(diǎn)的重要性基本保持穩(wěn)定狀態(tài).分析連續(xù)7天的數(shù)據(jù)也得出同樣的結(jié)論.

我們提取每天每小時重要性排名前50的節(jié)點(diǎn)，共有50×24×7個節(jié)點(diǎn)，再按這些節(jié)點(diǎn)出現(xiàn)頻數(shù)進(jìn)行由高到低排序，最終得到排名前50的關(guān)鍵節(jié)點(diǎn)，如圖5所示，其中西固區(qū)分布3個，安寧區(qū)分布8個，七里河區(qū)分布11個，其余28個全部分布在城關(guān)區(qū).排名前10的關(guān)鍵節(jié)點(diǎn)對應(yīng)的城區(qū)具體位置如表2所示，由此可見城關(guān)區(qū)交通流比較密集，而且容易擁堵.究其原因，一方面，城關(guān)區(qū)常住人口密度大；另一方面，城關(guān)區(qū)是行政區(qū)的中心地帶，甘肅省和蘭州市的政府職能部門、企業(yè)主管部門等均設(shè)立于此.

圖4 可視化交通狀態(tài)圖(星期一)Fig.4 Visualize traffic status(Monday)

圖5 排名前50的關(guān)鍵節(jié)點(diǎn)分布圖Fig.5 Top 50 key nodes distribution

表2 排名前10關(guān)鍵節(jié)點(diǎn)對應(yīng)的城區(qū)具體位置Table 2 Ranking the top 10 hub nodes corresponding to the city location

3 結(jié) 論

結(jié)合城市道路網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特征和交通流特性，本文提出了基于有向加權(quán)復(fù)雜網(wǎng)絡(luò)和DWNodeRank算法相結(jié)合的城市路網(wǎng)關(guān)鍵節(jié)點(diǎn)識別方法，并利用蘭州市連續(xù)7天出租車GPS軌跡數(shù)據(jù)，以小時為時間粒度，對工作日和休息日中城市交通狀態(tài)進(jìn)行可視化時空分析.研究方法和結(jié)果將為交通管理部門規(guī)劃、設(shè)計(jì)和管理提供科學(xué)的指導(dǎo)，對蘭州市城市交通的持續(xù)健康發(fā)展具有重要意義.

本文利用連續(xù)7天的出租車GPS軌跡數(shù)據(jù)進(jìn)行分析，該數(shù)據(jù)集并不能完全覆蓋城市道路網(wǎng)絡(luò)，且軌跡數(shù)據(jù)集種類比較單一，使得通過統(tǒng)計(jì)得到的路段平均速度存在一定誤差.另外，雖然本文充分利用了出租車數(shù)據(jù)包含的速度信息，但只考慮了速度，因素較為單一.接下來我們將結(jié)合更多的機(jī)動車GPS數(shù)據(jù)，特別是城市公交車運(yùn)營數(shù)據(jù)，挖掘GPS軌跡中的位置、狀態(tài)和時間等信息，深入分析城市交通狀態(tài)及其可視化呈現(xiàn).

[1]高強(qiáng),張鳳荔,王瑞錦,等.軌跡大數(shù)據(jù)：數(shù)據(jù)處理關(guān)鍵技術(shù)研究綜述[J].軟件學(xué)報(bào),2017,28(4)：959-993.[GAO Q,ZHANG F L,WANG R J,et al.Trajectory big data：A review of key technologies in data processing[J].Journal of Software,2017,28(4)：959-993.]

[2]趙竹珺,吉根林.時空軌跡分類研究進(jìn)展[J].地球信息科學(xué)學(xué)報(bào),2017,19(3)：289-297.[ZHAO Z J,JI G L.Research progress of spatial-temporal trajectory classification[J].Journal of Geo-information Science,2017,19(3)：289-297.]

[3]HAO J,ZHU J,ZHONG R.The rise of big data on urban studies and planning practices in China：Review and open research issues[J].Journal of Urban Management,2015(4)：92-124.

[4]ZHOU Z,DOU W,JIA G,et al.A method for real-time trajectory monitoring to improve taxi service using GPS big data[J].Information&Management,2016(53)：964-977.

[5]ZHENG W,HUANG X,LI Y.Understanding the tourist mobility using GPS：Where is the nextplace?[J].Tourism Management,2017(59)：267-280.

[6]鄭宇.城市計(jì)算概述[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2015,40(1)：1-13.[ZHENG Y.Overview of urban computing[J].Geomatics and Information Science of Wuhan University,2015,40(1)：1-13.]

[7]牟乃夏,張恒才,陳潔,等.軌跡數(shù)據(jù)挖掘城市應(yīng)用研究綜述[J].地球信息科學(xué),2015,17(10)：1136-1142.[MOU N X,ZHANG H C,CHEN J,et al.A survey of urban application research on track data mining[J].JournalofGeo-information Science,2015,17(10)：1136-1142.]

[8]CASTRO P S,ZHANG D,LI S.Urban traffic modelling and prediction using large scale taxi GPS traces[M].Pervasive Computing,Springer Berlin Heidelberg,2012.

[9]ZHAN X,HASAN S,UKKUSUR S V,et al.Urban link travel time estimation using large-scale taxi data with partial information[J].Transportation Research Part C：Emerging Technologies,2013,33(2013)：37-49.

[10]齊觀德,潘遙,李石堅(jiān),等.基于出租車軌跡數(shù)據(jù)挖掘的乘客候車時間預(yù)測[J],軟件學(xué)報(bào),Journal of Software,2013,24(Sup2)：14-23.[QI D G,PAN Y,LI S J,et al.Predicting passengers’waiting time by mining taxi traces[J].Journal of Software,2013,24(Sup2)：14-23.]

[11]FUSCO G,COLOMBARONI C,ISAENKO N.Shortterm speed predictions exploiting big data on large urban road networks[J].Transportation Research Part C,2016,2016(73)：183-201.

[12]CUI J,LIU F,HU J,et al.Identifying mismatch between urban travel demand and transport network services using GPS data：A case study in the fast growing Chinese city of Harbin[J].Neurocomputing,2016,2016(181)：4-18.

[13]楊偉,艾廷華.基于車輛軌跡大數(shù)據(jù)的道路網(wǎng)更新方法研究[J].計(jì)算機(jī)研究與發(fā)展，2016,53(12)：2681-2693.[YANG W,AI T H.A method for road network updating based on vehicle trajectory big data[J].Journal of Computer Research and Development,2016,53(12)：2681-2693.]

[14]胡一竑,吳勤旻,朱道立.城市道路網(wǎng)絡(luò)的拓?fù)湫再|(zhì)和脆弱性分析[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2009,6(3)：69-76.[HU Y H,WU Q M,ZHU D L.Topological properties and vulnerability analysis of spatial urban street networks[J].Journal of Computer Research and Development,2009,6(3)：69-76.]

[15]NIK HASHIM NIK MUSTAPHA,NIK NUR WAHIDAH NIK HASHIM.Outflow of traffic from the national capital Kuala Lumpur to the north,south and east coast highways using flow,speed and density relationships[J].Journal of Traffic and Transportation Engineering,2016,6(3)：540-548.

[16]張琨,李配配,朱保平,等.基于PageRank的有向加權(quán)復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性評估方法[J].南京航空航天大學(xué)學(xué) 報(bào),2013,45(3)：429-434.[ZHANG K,LI P P,ZHU B P,etal.Evaluation method fornode importancein directed-weighted complexnetworks based on pagerank[J].Journal of Nanjing University of Aeronautics&Astronautics,2013,45(3)：429-434.]

[17]MOKBEL M F,et al.MNTG：An extensible web-based traffic generator[M].In：Nascimento M A,et al.(eds),Advances in Spatial and Temporal Databases,SSTD 2013.Lecture Notes in Computer Science,vol 8098.Springer,Berlin,Heidelberg,2013.

[18]馬云飛.基于出租車軌跡點(diǎn)的居民出行熱點(diǎn)區(qū)域與時空特征研究：以昆山市為例[D].南京：南京師范大學(xué)，2014.[MA Y F.Research on residents behavior of attractive areas and spatial-temporal feature based on taxi trajectory data：A case of kunshan city[D].Nanjing Normal University,2014.]

[19]中華人民共和國公共安全行業(yè)標(biāo)準(zhǔn).城市道路交通管理評價(jià)指標(biāo)體系[S].中華人民共和國公共安全行業(yè)標(biāo)準(zhǔn),2002.[People's Republic of China Public Safety Industry Standard.Evaluation index system of urban road traffic management[S].People's Republic of China Public Safety Industry Standard,2002.]