潘曉芳 周順平 楊林 萬波

(1.中國地質(zhì)大學(xué)(武漢) 信息工程學(xué)院，湖北 武漢 430074；2.信陽師范學(xué)院 地理科學(xué)學(xué)院，河南 信陽 464000)

OD約束的出租車經(jīng)驗?zāi)Ｐ团c路徑規(guī)劃*

潘曉芳1,2周順平1?楊林1萬波1

(1.中國地質(zhì)大學(xué)(武漢) 信息工程學(xué)院，湖北 武漢 430074；2.信陽師范學(xué)院 地理科學(xué)學(xué)院，河南 信陽 464000)

從出租車軌跡中提取司機(jī)經(jīng)驗并應(yīng)用于大眾出行引導(dǎo)是出租車軌跡數(shù)據(jù)的重要應(yīng)用領(lǐng)域.在經(jīng)驗提取上，為了避免傳統(tǒng)方法中因忽視OD而導(dǎo)致結(jié)果不準(zhǔn)確的問題，提出了OD約束的經(jīng)驗?zāi)Ｐ?ODCEM).以深圳市為例，分別用傳統(tǒng)的經(jīng)驗?zāi)Ｐ?、ODCEM及最短路徑模型進(jìn)行實驗.結(jié)果顯示:ODCEM在經(jīng)驗提取和路徑推薦時能夠成功地模擬出租車司機(jī)的經(jīng)驗;3種方法的比較中，ODCEM推薦的路徑在通行時間和平均通行速度上體現(xiàn)出93.3%和76.7%以上的優(yōu)勢，通行長度位于其他兩種模型推薦的路徑之間.最后對約束的尺度進(jìn)行了討論.結(jié)果顯示,約束尺度為2 km×2 km時效果比較理想.

OD約束；出租車軌跡；經(jīng)驗?zāi)Ｐ?；路徑?guī)劃

隨著科技的進(jìn)步，大量的軌跡數(shù)據(jù)日益積累[1]，據(jù)統(tǒng)計，93%的軌跡數(shù)據(jù)是有規(guī)律性和重復(fù)性的[2]，這些軌跡數(shù)據(jù)為研究人類行為提供了基礎(chǔ)素材.出租車軌跡是由安裝在出租車上的傳感器在移動過程中采樣得到的GPS數(shù)據(jù)，近年來，利用出租車軌跡數(shù)據(jù)進(jìn)行城市交通的研究日益增多.出租車司機(jī)長期頻繁穿梭于城市的各個角落，很多時候，他們出行的線路往往比導(dǎo)航軟件規(guī)劃的路徑更為優(yōu)秀[2].所以，出租車司機(jī)的出行經(jīng)驗非常值得借鑒，學(xué)者已經(jīng)在此方面開展了大量的研究[3-11].

從目前的研究來看，學(xué)者普遍將路徑頻繁出行[3]、經(jīng)常走[4]、路段通行頻次高[5-7]、路段平均通行次數(shù)[8-9]多、經(jīng)常愿意走[10]等作為經(jīng)驗的認(rèn)定和經(jīng)驗等級建立的標(biāo)準(zhǔn)，而經(jīng)驗提取方法則通過將全部出租車軌跡與路網(wǎng)進(jìn)行匹配，然后統(tǒng)計每條道路上出租車軌跡的數(shù)目(即通行總頻次)，以此作為該道路的經(jīng)驗值大小.這種方法能夠反映城市道路的交通狀況，但是缺少對出行起止地的考慮，不同的出發(fā)地(Origin)和目的地(Destination)(簡稱OD)對司機(jī)線路的選擇至關(guān)重要，在沒有考慮出行OD的情況下，道路上的通行總頻次(即道路的交通流量)受諸多因素的影響，例如Jiang[11]認(rèn)為城市中有良好連通性和處于中心地位的路段流量較大，吳健生等[12]研究發(fā)現(xiàn)，等級高、位于城市中心的路段交通流量大，辛飛飛等[13]認(rèn)為出租車在路網(wǎng)上的覆蓋強(qiáng)度具有明顯的時變規(guī)律，另外，城市功能區(qū)類型、人口密度等因素也是道路交通流量的重要影響因素.而實際上，在確定出行OD后，與該OD方向無關(guān)的道路就與本次出行沒有任何關(guān)系(即使其通行總頻次很高).因此，在利用出租車軌跡提取經(jīng)驗的過程中，如果能夠?qū)ζ鹬裹c進(jìn)行有效的約束，將會提高經(jīng)驗的準(zhǔn)確性.

文中的研究重點就是基于出租車軌跡數(shù)據(jù)，構(gòu)建基于OD約束的經(jīng)驗?zāi)Ｐ?ODCEM)，并進(jìn)行相應(yīng)的出行路徑規(guī)劃.

1 基本思想和定義

1.1 基本思想

文中的技術(shù)路線如圖1所示，分為4個階段.第1階段是對出租車軌跡數(shù)據(jù)的預(yù)處理.由于地面建筑物的遮擋及設(shè)備的不穩(wěn)定性，可能會導(dǎo)致部分GPS信號異常，因此軌跡記錄存在一些重復(fù)、漂移、速度及時間錯亂甚至數(shù)據(jù)丟失等問題；另外，由于出租車車輛異常、駕駛員操作不當(dāng)?shù)?，也會產(chǎn)生一些異常記錄.因此，數(shù)據(jù)預(yù)處理階段主要是去除各種情況下的異常記錄.第2階段是地圖匹配.由于GPS誤差，收集到的軌跡點并沒有完全落在道路上，因此需要進(jìn)行地圖匹配，建立出租車軌跡與對應(yīng)道路的關(guān)系.第3階段是路網(wǎng)重建.通過文中提出的模型，計算道路上的出租車的通行頻次、通行時間及路段長度等基本信息，構(gòu)建經(jīng)驗道路網(wǎng)絡(luò).第4階段是路徑推薦，在新的經(jīng)驗路網(wǎng)下，根據(jù)Dijkstra算法，為用戶推薦OD約束下的經(jīng)驗路徑，并進(jìn)行有效性驗證.

圖1 技術(shù)線路Fig.1 Technical route

1.2 基本定義

定義1 軌跡(Trajectory).軌跡由安裝在出租車上的GPS在出租車運動過程中產(chǎn)生的一系列隨時間變化的點組成，Trajectory={p1，p2，…，pn}，其中每個點pi一般由出租車車牌號、地理坐標(biāo)(經(jīng)度，維度)、時間、載客狀態(tài)、速度、方向等信息組成，即pi=(ID,VEHICLENUMBER,LON,LAT,DATE,DIRECTION,SPEED,FLAG).

定義2 子軌跡(Trip).根據(jù)出租車在運動過程中是否載客可將其軌跡劃分為載客軌跡和空載軌跡，每次上客點到下客點之間的載客軌跡的集合為一個子軌跡，即Trip={p1，p2，…，pn|?pi·FLAG=LOAD,1≤i≤n}，其中n表示子軌跡包含點的個數(shù)，pi·FLAG為第i個點的載客狀態(tài)，LOAD表示載客，EMPTY表示空載.

如圖2所示，假設(shè)一條出租車軌跡Trajectory={p1，p2，…，p19}，實心點表示載客點，空心點表示空載點，則其子軌跡為trip1，trip2和trip3.

圖2 子軌跡劃分Fig.2 Division of sub-trajectory

定義3 OD約束下的軌跡(ODC-T).OD約束下的軌跡指的是經(jīng)過限定的出發(fā)地、目的地的子軌跡集合.即ODC-Trajectory={trip1,trip2,…,tripm},其中tripk={p1，p2，…，pn|?B(pi,O)∧B(pj,D),i

如圖3所示，trip1，trip2，…，trip66條子軌跡經(jīng)過的節(jié)點序列分別為trip1(V1,V2,V3,V6,V9)、trip2(V1,V2,V3,V4,V10)、trip3(V1,V5,V6)、trip4(V1,V5,V9)、trip5(V1,V5,V8,V9)和trip6(V1,V7,V8,V9,V10).假設(shè)節(jié)點V1和V9為約束的起止O、D，則OD約束下的軌跡分別為trip1、trip4、trip5和trip6.

圖3 OD約束下的軌跡與路段經(jīng)驗Fig.3 Trajectory and segment experience of OD constraint

定義4 OD約束的路段經(jīng)驗(ODC-SE).指在OD約束下，路段Si上所有出租車的通行次數(shù)，也就是ODC-Trajectory經(jīng)過路段Si的次數(shù).

計算ODC-SE時，對每一條路段Si，判斷ODC-Trajectory中的tripj是否經(jīng)過Si，如果經(jīng)過，則Si的路段經(jīng)驗值SEsi加1.判斷tripj經(jīng)過Si的方法是通過判斷tripj中的軌跡點pk是否在Si上，如果tripj中存在任意一個軌跡點pk在路段pk上，tripj經(jīng)過路段Si.

圖3所示4條ODC-Trajectory中,trip1經(jīng)過路段S1、S2、S5、S6；trip4經(jīng)過路段S7、S9；trip5經(jīng)過路段S7、S10；trip6經(jīng)過路段S11、S12、S13、S14.根據(jù)定義5，路段S3、S4和S8上沒有ODC-Trajectory，其路段經(jīng)驗為0，路段S7和S13上有兩條ODC-Trajectory，其路段經(jīng)驗為2，其他路段的路段經(jīng)驗均為1.

定義5 經(jīng)驗路網(wǎng)(ERN).經(jīng)驗路網(wǎng)G=(V;S;SE)，V為道路節(jié)點集合，S路段集合，SE為OD約束下的路段經(jīng)驗集合.圖3區(qū)域?qū)?yīng)的經(jīng)驗路網(wǎng)如圖4所示.

圖4 經(jīng)驗路網(wǎng)Fig.4 Experience network

2 ODCEM的建立

2.1 建模方法

在實際研究中很難實現(xiàn)任意兩點之間經(jīng)驗的提取，因此，文中采用基于格網(wǎng)的方法，將研究區(qū)域進(jìn)行正方形格網(wǎng)劃分，每個網(wǎng)格表示一個約束區(qū)域O或D，得到一個空間矩陣Gridcell×Gridcell Matrix.為了研究不同時間的軌跡特征，在空間矩陣上增加時間維度，假設(shè)以T小時為基本單元，則一天被劃分為24/T個軌跡段，從而構(gòu)建OD約束的軌跡立方體(ODC-TC)，如圖5所示.

圖5 軌跡立方體Fig.5 Trajectory cube

隨時間推移的出租車軌跡可以用該ODC-TC進(jìn)行模擬，ODC-TC中每個單元表示一個格網(wǎng)約束區(qū)域在時間段內(nèi)的所有軌跡點集合，為研究方便，取T=2，將一天劃分為12個時段，約束區(qū)域的大小在3.4節(jié)中討論.這里先假設(shè)約束區(qū)域的邊長為d，研究區(qū)域的范圍為(Xmin,Ymin,Xmax,Ymax)，則研究區(qū)平面將被劃分為coln行、rown列，行、列的計算公式為

(1)

(2)

因此，任意一點p(x,y)所在網(wǎng)格的行、列號為

(3)

(4)

在確定研究區(qū)范圍、約束點坐標(biāo)及出行時間后，利用ODC-TC提取ODC-SE的過程如圖6表示.

圖6 提取ODC-SE的過程Fig.6 Process of extracting ODC-SE

建模主要思想為：首先，由式(1)、(2)得到研究區(qū)行列值；接著，在ODC-TC中提取所需要的軌跡點層，在該層內(nèi)將約束點坐標(biāo)利用式(3)、(4)轉(zhuǎn)換為約束區(qū)域O、D的行列號；然后，根據(jù)定義3得到OD約束下的軌跡ODC-T；最后，根據(jù)定義4計算ODC-SE.算法描述如下.

算法名稱：ODC-SE提取算法

算法輸入：軌跡點文件(tp)，道路線文件(road)，起止地Po、Pd，時間段T

算法輸出：OD約束的路段經(jīng)驗

算法描述：

∥子軌跡、時間軌跡層、OD約束軌跡的初始化

TrajectoryL=?；TrajectoryT=?；ODC-Trajectory=?；

步驟1 根據(jù)式(1)、(2)計算區(qū)域的行、列值;

步驟2 根據(jù)式(3)、(4)計算約束起止地Po、Pd所在的行列號gcIDo、gcIDd

while(tp！=NULL)

if(pi==EMPTY)and(pi+1==LOAD) and (pn-1==LOAD)andpn==EMPTY)

tripi={pi+1,…,pn-1}

TrajectoryL=TrajectoryL∪{tripi};

步驟3 while(TrajectoryL！=NULL)

if((tripi·startdate>Tstart)and(tripi·enddate

TrajectoryT=TrajectoryT∪{tripi};

步驟4 while(TrajectoryT！=NULL)

對每一個tripi:

if(pjin gcIDoandpkin gcIDd)

ODC-Trajectory=ODC-Trajectory∪{tripi};

步驟5 對road中的每個字段根據(jù)定義5計算路段經(jīng)驗.

2.2 OD約束的路段經(jīng)驗系數(shù)

在基于軌跡提取經(jīng)驗的研究中，學(xué)者普遍使用時間、距離、速度及經(jīng)驗認(rèn)知[6-7，9]等來規(guī)劃路徑，因此，本研究也將路段經(jīng)驗、路段長度和路段通行時間作為OD約束的路段經(jīng)驗系數(shù)的主要影響因子.

路段的平均通行速度的計算不受約束條件的影響，應(yīng)使用全部軌跡數(shù)據(jù)進(jìn)行計算.Jiang等[14-15]使用浮動車數(shù)據(jù)對路段平均速度的計算做了詳細(xì)的研究，路段Si上的平均通行速度為

(5)

式中，m表示統(tǒng)計時間段內(nèi)路段Si上的通行的出租車總數(shù)，n表示路段Si上采樣點個數(shù)，Δl表示兩個采樣點之間的距離，Δt表示兩個采樣點之間的時間.

路段Si的平均通行時間為

(6)

式中，LSi表示路段Si的長度，VSi表示路段Si上的平均通行速度.

OD約束的路段經(jīng)驗系數(shù)表示為

CEPSi=w1×SESi+w2×LSi+w3×TSi

(7)

其中,w1、w2、w3分別為權(quán)重系數(shù)，且w1+w2+w3=1.對式(7)進(jìn)行歸一化處理(根據(jù)研究區(qū)數(shù)據(jù)特點，路段經(jīng)驗、路段長度和通行時間的數(shù)量級別差異較大，因此對路段長度和通行時間進(jìn)行了取對數(shù)操作)：

(8)

式中，SESmax與SESmin分別表示ODC-SE的最大值和最小值，LSmax和LSmin分別表示路段長度的最大值和最小值，TSmax和TSmin分別表示通行時間的最大值和最小值.

根據(jù)式(8)對路段的經(jīng)驗系數(shù)CEPSi的定義，路徑推薦問題可以轉(zhuǎn)換為：用戶設(shè)定出行起止地后，采用最短路徑算法[16]尋找一條路徑route，使該路徑的總經(jīng)驗值CEProute最小,

(9)

由于OD約束后會出現(xiàn)大量路段沒有軌跡的情況，即SESi=SESmin=0，因此路段的經(jīng)驗系數(shù)達(dá)到最大，即權(quán)重系數(shù)w1，此時，該路段的經(jīng)驗系數(shù)CEPSi主要由路段的長度及通行時間決定，即尋路的依據(jù)是路段長度和通行時間，這與日常路徑推薦方法是相吻合的.實驗中，取w1=0.8,w2=w3=0.1.

按照傳統(tǒng)的經(jīng)驗提取方法，在無OD約束的情況下用相同的權(quán)重系數(shù)建立經(jīng)驗?zāi)Ｐ?EM)，以及最短路徑模型(SP)，在實驗與討論部分進(jìn)行比較分析.

3 實驗與討論

3.1 實驗環(huán)境

實驗使用的GIS軟件為MAPGIS K9 SP3和ArcGIS 10.0，數(shù)據(jù)庫軟件為SQLServer 2008和Oracle 11 g，軟件開發(fā)環(huán)境為Visual Studio 2010.選擇深圳市為研究區(qū)，用深圳市2011年11月1號至7號的出租車(共12 448輛)軌跡數(shù)據(jù)(共7 594萬條)對文中提出的模型進(jìn)行驗證，路網(wǎng)為深圳市道路交通圖，共101 794條路段.在實驗過程中，從深圳市機(jī)場、車站、酒店、休閑娛樂地等POI中隨機(jī)選擇組成30對OD，基本覆蓋到了深圳市的每個區(qū)，如圖7所示.實驗中首先使用2 km×2 km的約束區(qū)，選取5個工作日上午7：00-9：00軌跡數(shù)據(jù)，對研究區(qū)30對OD進(jìn)行分析.

圖7 研究區(qū)路網(wǎng)及POIsFig.7 Road network and POIs of study area

3.2 OD約束下的軌跡與路段經(jīng)驗

首先，選取深圳寶安國際機(jī)場—深圳大學(xué)作為起止地，圖8(a)、8(b)顯示的分別是EM與ODCEM兩種模型的軌跡，可以看到，在EM中(圖8(a))各道路上都有大量的軌跡分布，給定約束OD后(圖8中星形符號)很難找到清晰的經(jīng)驗軌跡；在ODCEM中(圖8(b))約束OD之間的軌跡較為清晰，而其他道路上的軌跡則非常少.

接著，計算兩種模型下的路段經(jīng)驗，結(jié)果表明，在EM中，路段經(jīng)驗分散(范圍為0～13 668，標(biāo)準(zhǔn)差SD=163.2)，道路等級高或路網(wǎng)密度大的區(qū)域路段經(jīng)驗值高，例如商業(yè)區(qū)和主干道，而在ODCEM中，路段經(jīng)驗比較集中(范圍為0～392，標(biāo)準(zhǔn)差SD=4.6)，OD范圍外的路段經(jīng)驗大多為0，OD范圍內(nèi)的路段經(jīng)驗也比EM中低得多.任意選擇A、B兩個區(qū)域內(nèi)的70條路段(A位于OD范圍內(nèi)，B位于OD范圍外，如圖8(b)所示，其中，區(qū)域A包含392條路段，區(qū)域B包含299條路段)，分別統(tǒng)計ODCEM和EM下的路段經(jīng)驗，其結(jié)果如圖9(a)、9(b)所示.可以看出，EM在區(qū)域A和B中均有很高的路段經(jīng)驗，而ODCEM的路段經(jīng)驗在區(qū)域B幾乎全部為0.這是因為區(qū)域B內(nèi)的路段與本次出行無關(guān)，該區(qū)域的路段上沒有ODC-T，而EM由于沒有限制約束條件，因此依然存在很高的路段經(jīng)驗.

圖8 EM與ODCEM的軌跡Fig.8 Trajectories of EM and ODCEM

圖9 ODCEM與EM的路段經(jīng)驗Fig.9 Road experience of ODCEM and EM

最后，將道路的行政等級圖(10(a))與EM、ODCEM的路段經(jīng)驗等級圖(10(b)、10(c))進(jìn)行對比，發(fā)現(xiàn)EM的經(jīng)驗等級與該區(qū)域的道路等級更為相似.進(jìn)一步將兩種模型的路段經(jīng)驗與道路等級進(jìn)行相關(guān)性分析，結(jié)果為：EM的經(jīng)驗值與道路等級的相關(guān)性系數(shù)為0.393，即在0.01水平上顯著相關(guān)，而ODCEM的經(jīng)驗值與道路行政等級相關(guān)性系數(shù)僅為0.065.

圖10 道路、EM、ODCEM等級圖Fig.10 Levels of road,EM and ODCEM

3.3 OD約束下的經(jīng)驗路徑

分別用EM和ODCEM進(jìn)行路徑規(guī)劃，生成的路徑如圖11(a)和圖11(b)所示.對比圖10(b)和圖11(a)可以看出，EM模型將路線規(guī)劃在總的路段經(jīng)驗較高的路段上，而圖10(c)和圖11(b)則顯示ODCEM將路徑規(guī)劃在ODC-SE較高的路段上.對比圖11(a)和圖11(b)還可以發(fā)現(xiàn)，EM的路徑比較繞遠(yuǎn)，大大超出OD范圍(這主要是因為出行OD范圍外的路段也有較高的經(jīng)驗值)，而ODCEM的路徑則與其約束下的軌跡、約束下的道路等級相吻合.

圖11 EM和ODCEM路徑Fig.11 Routes of EM and ODCEM

接下來分別用EM、ODCEM及SP3種模型對30對OD進(jìn)行路徑規(guī)劃，任選其中4對的結(jié)果如圖12所示，可以看出，SP路徑距離最短，EM路徑比較繞遠(yuǎn)，ODCEM路徑長度居中.

圖12 任意4對OD的3種模型路徑圖Fig.12 Routes of 3 models for 4 random OD pairs

為了驗證3種模型規(guī)劃的路徑上經(jīng)驗的高低，利用ODC-Trajectory計算每條路徑單位距離的軌跡點的數(shù)量，稱之為軌跡覆蓋度：

(10)

式中，numroutei表示路徑i上的經(jīng)驗軌跡點的數(shù)量，Lengthroutei表示路徑i的長度.

分別計算統(tǒng)計30對OD在不同路徑上的軌跡覆蓋度、路徑長度、通行時間和平均通行速度，結(jié)果如圖13(a)至13(d)所示.總體來看，ODCEM的軌跡覆蓋度最高，通行時間最短，通行速度最快，通行距離位于EM和SP之間.

圖13 30對OD的軌跡覆蓋度，通行長度，通行時間和通行速度
Fig.13 Trajectory coverage,travel distance,travel time and travel speed of 30 OD pairs

統(tǒng)計結(jié)果(見表1)也顯示：83.3%以上的ODCEM軌跡覆蓋度大于SP和EM，即ODCEM是實際出租車軌跡最多的路徑；在路徑長度上,ODCEM中86.7%比EM短，但都長于SP；在通行時間上，93.3%以上的ODCEM都比EM及SP節(jié)省時間；在通行速度上，ODCEM中有76.7%比EM快，且全部優(yōu)于SP.

表1 30對OD的ODCEM優(yōu)秀率Table 1 Excellence rate of ODCEM in 30 pairs of OD

這說明，在通行距離上，SP無可比擬，但本研究中提出的ODCEM在充分?jǐn)M合司機(jī)經(jīng)驗的基礎(chǔ)上，運行時間和通行速度都比較優(yōu)秀.從速度上看，也存在個別EM速度較高的情況，主要是因為這些路徑處于路況較好的外環(huán)道路上，是以更多的時間和更長的距離換取的高速度，這不符合出租車出行的規(guī)律(出租車出行會更多地考慮出行的距離)，實際上增大了出行成本.因此，文中提出的ODCEM在充分考慮出租車司機(jī)經(jīng)驗的基礎(chǔ)上兼顧到了出行的時間、距離及速度，是一種行之有效的經(jīng)驗提取模型.

3.4 約束尺度分析

根據(jù)格網(wǎng)劃分的原則，約束點格網(wǎng)的大小要適中，過大會影響結(jié)果的精度，過小則在數(shù)據(jù)存儲和運算上效率不高.實驗中分別以1 km×1 km、2 km×2 km、4 km×4 km、6 km×6 km的格網(wǎng)大小進(jìn)行討論.在4種情況下，30對OD的ODCEM路徑的總長度、總時間統(tǒng)計結(jié)果如圖14所示.

由圖14可以看出：路徑總長度及通行總時間都隨著格網(wǎng)的增大而增大，說明隨著約束尺度的增加，模型的準(zhǔn)確性有所下降，導(dǎo)致路徑長度和時間的增加.這說明，約束尺度應(yīng)該越小越好，但是如果約束尺度過小，精確約束下的子軌跡數(shù)也必將減少.為了進(jìn)一步驗證不同約束尺度下子軌跡數(shù)目的變化，實驗中增加了OD對的個數(shù)(隨機(jī)選擇50個POI，產(chǎn)生50×50=2 500個OD對)，程序運行時間及子軌跡為0的OD對所占的百分比如圖15所示.可以看出，約束尺度為1 km×1 km時33%的OD對之間子軌跡為0，隨著約束尺度的增加，在2 km×2 km時迅速下降到13%，之后繼續(xù)下降直到6 km×6 km時的3.5%，如果約束尺度繼續(xù)增加，直到整個研究區(qū)為一個網(wǎng)格，即無約束的經(jīng)驗?zāi)Ｐ停藭r不存在子軌跡為0的OD對.因此，約束尺度過小，會導(dǎo)致精確約束下的子軌跡為0，也無法獲取有效的經(jīng)驗.另外，程序運行時間隨著約束尺度的增加而增加.

圖14 4種格網(wǎng)下30對OD的ODCEM總距離和總時間Fig.14 Total travel distance and travel time of ODCEM of 30 OD pairs under four different grid sizes

圖15 4種格網(wǎng)下軌跡為0的OD對百分比及程序運行時間Fig.15 Percentage of OD pairs with no trip and its program running time under four different grid sizes

綜合以上分析，在本研究背景下，2 km×2 km的約束點大小比較合適，在此約束尺度下，經(jīng)驗軌跡比較精確，數(shù)目適中，且程序運行效率在可接受的范圍內(nèi).

4 結(jié)語

文中提出OD約束的概念，建立相應(yīng)的OD約束經(jīng)驗?zāi)Ｐ停阅M司機(jī)的出行路線，在路徑規(guī)劃時兼顧出行的時間、距離及速度等因素，是一種行之有效的經(jīng)驗提取方法.在實驗中發(fā)現(xiàn)，研究區(qū)的約束大小為2 km×2 km時較為合理.

但是，實驗過程中對時間尺度的劃分比較粗略，也沒能處理跨越兩個時間段的軌跡，因此損失了部分軌跡信息；另外，如果能夠?qū)?jīng)驗數(shù)據(jù)庫進(jìn)行實時更新，結(jié)果將會更加準(zhǔn)確，這將是下一步研究的方向.

[1] 袁晶.大規(guī)模軌跡數(shù)據(jù)的檢索，挖掘及應(yīng)用 [D].合肥：中國科學(xué)技術(shù)大學(xué)，2012.

[2] SONG C,QU Z,BLUMN N,et al.Limits of predictability in human mobility [J].Science,2010,327(5968):1018-1021.

[3] GONG J F,YU Z,CHEN N N.An analysis of drivers’ route choice behavior in urban road networks based on GPS data [C]∥The First International Conference of Transportation Engineering.Chengdu:[s.n.],2007:515-520.

[4] YUAN J,ZHENG Y,ZHANG XIE W,et al. T-drive:driving directions based on taxi trajectories[OL/EB].[2011-12-31].http:∥www.docin.com/p-338527489.html.

[5] 唐爐亮，常曉猛，李清泉,等.基于蟻群優(yōu)化算法與出租車GPS數(shù)據(jù)的公眾出行路徑優(yōu)化 [J].中國公路學(xué)報,2011,24(2):89-95.

TANG Lu-lianng,CHANG Xiao-meng,LI Qing-quan,et al.Public travel route optimization based on ant colony optimization algorithm and taxi GPS data [J].China Journal of Highway and Transport,2011,24(2):89-95.

[6] LI Q Q,ZENG Z,ZHANG T,et al.Path-finding through flexible hierarchical road networks-An experiential approach using taxi trajectory data [J].International Journal of Applied Eearth Observation and Geoinformation,2011(13):110-119.

[7] 胡繼華，黃澤，鄧俊，等.融合出租車駕駛經(jīng)驗的層次路徑規(guī)劃方法 [J].交通運輸系統(tǒng)工程與信息,2013,13(1):185-192.

HU Ji-hua,HUANG Zhe,DENG Jun,et al.Hierarchical path planning method based on taxi driver experiences [J].Journal of Transportation Systems Engineering and Information Technology,2013,13(1):185-192.

[8] WEI L Y,ZHENG Y,PENG W C.Constructing popular routes from uncertain trajectories [C]∥18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Beijing:[s.n.],2012:195-203.

[9] 唐爐亮,常曉猛,李清泉.出租車經(jīng)驗知識建模與路徑規(guī)劃算法 [J].測繪學(xué)報.2010，39(4)：404-409.

TANG Lu-liang,CHANG Xiao-meng,LI Qing-quan.The knowledge modeling and route planning based on taxi’ experience [J].ActaGeodaetica et Cartographica Sinica,2010，39(4)：404-409.

[10] 曾喆.面向?qū)Ш铰窂竭x擇的道路網(wǎng)絡(luò)經(jīng)驗層級模型研究 [D].武漢：武漢大學(xué)，2010.

[11] JIANG B.Street hierarchies:a minority of streets account for a majority of traffic flow [J].International Journnal of Geographical Informational Science,2009,23(8):1033-1048.

[12] 吳健生,黃力,劉瑜,等.基于手機(jī)基站數(shù)據(jù)的城市交通流量模擬 [J].地理學(xué)報,2012,67(12):1657-1665.

WU Jian-sheng,HUANG Li,LIU Yu,et al.Traffic flow simulation based on call detail records [J].Acta Geographica Sinica,2012,67(12):1657-1665.

[13] 辛飛飛,陳小鴻,林航飛.浮動車數(shù)據(jù)路網(wǎng)時空分布特征研究 [J].中國公路學(xué)報,2008,21(4):105-110.

XIN Fei-fei,CHEN Xiao-hong,LIN Hang-fei.Research on time space distribution characteristics of floating car data in road network [J].China Journal of Highway and Transport,2008,21(4):105-110.

[14] 姜桂艷，常安德，李琦，等.基于出租車GPS數(shù)據(jù)的路段平均速度估計模型 [J].西南交通大學(xué)學(xué)報,2011,46(4):638-644.

JIANG Gui-yan,CHANG An-de,LI Qi,et al.Estimation models for average speed of traffic flowbased on GPS data of taxi [J].Journal of Southwest Jiaotong University,2011,46(4):638-644.

[15] 朱廣宇,杜崇,張彭.基于基線漂移校正的旅行時間預(yù)測模型 [J].華南理工大學(xué)學(xué)報(自然科學(xué)報)，2016,44(8):131-138.

ZHU Guang-yu,DU Cong,ZHANG Peng.A travel time forecasting model based on baseline drift correction [J].Journal of South China University of Technology(Natural Science Edition),2016,44(8):131-138.

[16] CHERKASSKY B V,GOLDBERG A V,RADZIK T.Shortest paths algorithms:theory and experimental eva-luation [J].Mathematical Programming,1996,73(2):129-174.

s:Supported by the National Natural Science Foundation of China(41371422,41201385,41301426,41301427)

OriginDestinationConstraintExperienceModelofTaxiandPathPlanning

PANXiao-fang1,2ZHOUShun-ping1YANGLin1WANBo1

(1.Faculty of Information Engineering,China University of Geosciences (Wuhan),Wuhan 430074,Hubei,China;2.School of Geographic Sciences,Xinyang Normal University,Xinyang 464000,Henan,China)

Extracting the driver’s experience from taxi trajectories to guide the public travel is an important application of trajectory data.In order to avoid the inaccurate results caused by ignoring the origin and destination in the experience extracting process of traditional methods,this paper proposes an origin destination constraint experience model (ODCEM).Then,the traditional experience model,the ODCEM and the shortest path model are compared by the experiments in Shenzhen city.The results shows that (1) the ODCEM can successfully simulate the taxi driver’s travel experience during the experience extracting and the path planning;(2) in comparison with the other two methods,the ODCEM increases the travel time and the speed respectively by more than 93.3% and more than 76.7%;and (3) the travel distance of the ODCEM is between those recommended by the other two methods.Finally,the influence of the constraint scale is discussed.It is found that the desirable constraint size is 2 km×2 km.

origin destination constraint;taxi trajectory;experience model;path planning

2016-09-12

國家自然科學(xué)基金資助項目(41371422，41201385，41301426，41301427)

潘曉芳(1979-)，女，博士，講師，主要從事空間數(shù)據(jù)庫、GIS-T研究.E-mail：xfpanem@163.com

?通信作者:周順平(1967-)，男，教授，博士生導(dǎo)師，主要從事空間數(shù)據(jù)庫挖掘和地理信息系統(tǒng)軟件工程研究.E-mail：zhoushunping@mapgis.com

1000-565X(2017)08-0057-08

U 491

10.3969/j.issn.1000-565X.2017.08.009