基于實時路況的top-k載客熱門區(qū)域推薦

吳濤,毛嘉莉,謝青成,楊艷秋,王錦

(1.西華師范大學(xué)計算機學(xué)院,四川南充637000; 2.中國人民武裝警察部隊警官學(xué)院電子技術(shù)系,成都610000)

基于實時路況的top-k載客熱門區(qū)域推薦

吳濤1,毛嘉莉1,謝青成1,楊艷秋2,王錦1

(1.西華師范大學(xué)計算機學(xué)院,四川南充637000; 2.中國人民武裝警察部隊警官學(xué)院電子技術(shù)系,成都610000)

為降低城市出租車的空載率,緩解路網(wǎng)交通擁堵壓力,亟需設(shè)計有效的出租車載客熱門區(qū)域推薦方法.針對傳統(tǒng)的出租車相關(guān)推薦方法忽略實際路況導(dǎo)致推薦精度較低的現(xiàn)狀,提出了一個兩階段的載客熱門區(qū)域?qū)崟r推薦算法.首先,離線挖掘階段,基于出租車歷史軌跡數(shù)據(jù)集提取基于時段屬性的載客熱門區(qū)域;隨后,在線推薦階段,根據(jù)出租車請求位置及時間,結(jié)合實時路況設(shè)計潛在空載時間開銷函數(shù)Tcost對載客熱門區(qū)域進(jìn)行評測排序,繼而發(fā)現(xiàn)Top-k載客熱門區(qū)域.基于出租車軌跡數(shù)據(jù)集的實驗結(jié)果表明,結(jié)合實時交通狀況的Top-k載客熱門區(qū)域推薦方法以確保較小潛在空載時間開銷,相較于傳統(tǒng)的出租車推薦方法具有較好的有效性與魯棒性.

潛在空載時間開銷函數(shù);實際路況;熱門區(qū)域;推薦

0 引言

隨著城市規(guī)模的不斷擴(kuò)大,城市居民的出行需求日益增長,出租車的數(shù)量急劇增多.近年來隨著網(wǎng)約車平臺(滴滴、優(yōu)步)的出現(xiàn),出租車行業(yè)在日趨激烈的市場競爭中面臨著空載率高的嚴(yán)峻現(xiàn)實,城市路網(wǎng)中大部分時段存在大量空載出租車為尋找乘客而漫無目的地在周邊道路巡游;與此同時,城市的部分區(qū)域在特定時段因乘客爆發(fā)式激增使得出租車供不應(yīng)求,乘客面臨著打車?yán)щy的問題.這種方式不僅導(dǎo)致了大量的資源浪費,同時也帶來了不少負(fù)面影響,如交通擁堵、環(huán)境污染等.因此,提高出租車的載客率,保證其在較小開銷下的盈利模式已成為智能交通管理的一個有力措施.隨著智能交通系統(tǒng)的發(fā)展,感知設(shè)備如車載GPS(Global Positioning System)在出租車中得到了普及,這些設(shè)備以一定的時間間隔持續(xù)不斷地向出租車信息管理中心發(fā)送出租車的位置信息,包括時間戳、經(jīng)緯度坐標(biāo)、載客狀態(tài)、速度等數(shù)據(jù).這些數(shù)以萬計的數(shù)據(jù)中蘊含著豐富的乘客及出租車司機的行為特征信息,通過對這些數(shù)據(jù)進(jìn)行挖掘分析可以發(fā)現(xiàn)出租車運行軌跡的潛在時空特性,如發(fā)現(xiàn)載客熱門區(qū)域[1-2]、載客熱點[3-4]等(如圖1中的紅色標(biāo)注點Hotspot 1、Hotspot 2、Hotspot 3),當(dāng)出租車司機于某地點(如圖1中的藍(lán)色標(biāo)注點Anxin mansion)提出載客推薦請求時,可向其推薦距離較近的城市載客熱門區(qū)域,以提高出租車司機的客源尋找效率,解決出租車載客率低的問題.

在傳統(tǒng)的出租車相關(guān)推薦系統(tǒng)中[1-5],多數(shù)研究忽略了實時交通對推薦效果的影響,在推薦過程中采用基于距離最近或基于載客概率最大的原則對出租車司機進(jìn)行推薦,如圖1中,載客熱門區(qū)域Hotspot 1因與出租車當(dāng)前位置Anxin mansion的路段距離相較于Hotspot 2、Hotspot 3稍大,或由于其載客概率小于Hotspot 2、Hotspot 3,在推薦過程中時常被認(rèn)為劣于Hotspot 2、Hotspot 3,甚至被舍棄.然而,結(jié)合實際交通情況分析后發(fā)現(xiàn),基于位置Anxin mansion到Hotspots 2、Hotspot 3的部分路段在當(dāng)前時段擁塞狀況嚴(yán)重(圖中標(biāo)記為“紅色”的路段為擁堵路段),若將Hotspot 2、Hotspot 3對出租車司機進(jìn)行推薦,不僅將導(dǎo)致出租車空載行駛時間過長,降低工作效率,同時進(jìn)一步加重了城市交通負(fù)擔(dān),使得城市交通形勢更加嚴(yán)峻.

因此,針對以上傳統(tǒng)出租車相關(guān)推薦系統(tǒng)所面臨的問題,本文在載客熱門區(qū)域推薦時考慮結(jié)合實時的交通路況信息,構(gòu)建并實施了一個兩階段的實時載客熱門區(qū)域推薦算法:①離線挖掘階段,通過對出租車歷史軌跡數(shù)據(jù)的深度挖掘提取基于不同時段,區(qū)分工作日、休息日的載客熱門區(qū)域;②在線推薦階段,根據(jù)數(shù)據(jù)中心實時到達(dá)的出租車軌跡數(shù)據(jù)流分析最新時段的道路交通情況,結(jié)合實時交通狀況進(jìn)行top-k載客熱門區(qū)域推薦,從根本上解決出租車載客率低、乘客打車難、出租車空載時間長等難題,緩解道路擁堵,進(jìn)一步推進(jìn)智能交通建設(shè),本文的主要貢獻(xiàn)如下.

圖1 載客熱門區(qū)域推薦示例Fig.1 The examples of hotspots recommendation

(1)本文提出了一個兩階段的出租車載客熱門區(qū)域?qū)崟r推薦算法,包括離線挖掘和在線推薦兩個階段.首先,在離線挖掘階段,根據(jù)出租車歷史軌跡數(shù)據(jù)發(fā)現(xiàn)載客熱門區(qū)域集合;其次,在在線推薦階段,根據(jù)當(dāng)前時間戳結(jié)合載客熱門區(qū)域的時段屬性遴選出候選載客熱門區(qū)域集;最后,設(shè)計潛在空載時間開銷函數(shù)Tcost對各載客熱門區(qū)域進(jìn)行評測,完成top-k推薦.

(2)針對當(dāng)下各城市的交通擁堵情況形勢嚴(yán)峻,而現(xiàn)有的出租車相關(guān)推薦研究忽視了城市路網(wǎng)的實時交通狀況使得推薦精度較低.本文通過設(shè)計潛在空載時間開銷函數(shù)Tcost,將出租車載客熱門區(qū)域推薦問題轉(zhuǎn)化為對載客熱門區(qū)域潛在空載時間開銷的計算,在推薦過程中考慮了實時的交通情況.基于實際出租車軌跡數(shù)據(jù)集的實驗驗證了本文提出的載客熱門區(qū)域推薦算法的準(zhǔn)確性和有效性.

1 相關(guān)工作

目前基于軌跡數(shù)據(jù)挖掘的出租車相關(guān)推薦研究已成為國內(nèi)外的研究熱點之一.2014年, Qu[3]等人基于最大收益化原則,為出租車司機推薦了由一系列載客熱點排列形成的尋客路線,將推薦問題轉(zhuǎn)化為移動序列推薦(Mobile Sequence Recommendation,MSR)問題;文獻(xiàn)[4]從出租車軌跡中提取載客熱點,并利用出租車歷史軌跡數(shù)據(jù)集構(gòu)建概率模型,為出租車司機推薦到達(dá)載客熱點的路徑以最大概率搭載到下一位乘客.以上研究忽視了不同時段對載客熱點的影響.考慮到出車司機的不同尋客策略,文獻(xiàn)[5]基于大規(guī)模出租車軌跡數(shù)據(jù)集,采用支持向量機模型發(fā)現(xiàn)了高效的尋客方案,并結(jié)合時空特性對缺乏經(jīng)驗的出租車司機進(jìn)行推薦;文獻(xiàn)[2]主要基于4 000多條歷史軌跡數(shù)據(jù)集發(fā)現(xiàn)載客熱門區(qū)域,并通過改進(jìn)的ARIMA方法預(yù)測乘客分布特征完成對出租車司機的推薦;文獻(xiàn)[1]根據(jù)時間、天氣、出租車地理位置的上下文信息對出租車的需求分布進(jìn)行預(yù)測,設(shè)計了熱度值函數(shù)作為各載客熱門區(qū)域的評價標(biāo)準(zhǔn).同時,也有研究[6]基于出租車軌跡流數(shù)據(jù),預(yù)測在短時間范圍內(nèi)的出租車乘客的空間分布特征.當(dāng)然,也有部分研究致力于為乘客的服務(wù),如文獻(xiàn)[7]中基于不同時段、是否為工作日以及天氣情況等3個因素,采用基于樸素貝葉斯分類器的方法預(yù)測空載出租車數(shù)量.齊觀德等[8]使用出租車軌跡歷史數(shù)據(jù),預(yù)測乘客在某時某地等候出租車需要的時間.以上出租車相關(guān)推薦服務(wù)的研究中,在對出租車司機進(jìn)行推薦的過程中主要基于載客概率最大或駕駛距離最短等推薦原則,卻忽略了實際交通情況對推薦效果的影響.

針對以上傳統(tǒng)出租車相關(guān)推薦研究的不足,本文結(jié)合路網(wǎng)實際交通狀況對出租車司機進(jìn)行載客熱門區(qū)域推薦服務(wù),實時交通路況的評測也就作為另一個與本文相關(guān)的工作.由于出租車隨機性、動態(tài)性的特點,其運行狀態(tài)能很好地反映城市的交通情況,因此Mao等[9]通過對實時到達(dá)的出租車軌跡流進(jìn)行聚類分析,在無路網(wǎng)數(shù)據(jù)的情況下判斷交通擁塞路段.文獻(xiàn)[10]中,通過對出租車軌跡數(shù)據(jù)的挖掘,分析了北京市的交通擁堵情況.Han[11]等結(jié)合路網(wǎng)數(shù)據(jù),設(shè)計了NEAT-a-road-network識別方法,快速準(zhǔn)確地將移動對象的軌跡進(jìn)行聚類,以識別道路擁堵路段情況.以上研究主要基于出租車軌跡數(shù)據(jù)并應(yīng)用于城市路網(wǎng)中交通情況的預(yù)測及判斷,不僅有利于政府部門對城市路網(wǎng)的規(guī)劃,還能為乘客及司機的出行提供建議.

本文結(jié)合實時路況對出租車司機進(jìn)行載客熱門區(qū)域的推薦,不僅能提高出租車的載客率,同時也有利于城市交通,進(jìn)一步推進(jìn)智能城市的建設(shè).

2 問題描述

本文將城市路網(wǎng)表示為一個圖(后文簡稱“路網(wǎng)圖”),G=〈V,E〉.提取路段交叉口或路段終點作為路網(wǎng)圖中的結(jié)點集合V,而路網(wǎng)圖中的有向邊集E則為實際道路的映射,并將路徑定義如下.

定義1(路徑)路徑R為一組起始位置Pstart和終止位置Pend之間的有序路段交點序列,R=Pstart→P1→P2→P3→…→Pn→Pend,并且滿足邊ePi,Pi+1∈G.E,1≤i≤n.

定義2(出租車軌跡)出租車軌跡Tr是指該出租車基于時間的有序GPS采樣點序列, Tr=p1,…,pi,…,pn.其中每個GPS采樣點pi(1≤i≤n)包括位置數(shù)據(jù)pi.lon、pi.lat以及出租車位于該位置的時間戳pi.t,載客狀態(tài)pi.s,速度pi.v,角度pi.b等信息,且滿足?i＜j, pi.t＜pj.t.

定義3(載客熱門區(qū)域)載客熱門區(qū)域H是指某個連續(xù)時段內(nèi)出租車發(fā)生載客事件較為密集的城市區(qū)域,該區(qū)域為任意形狀,并且具有時段屬性Tduration=〈Tstart,Tend〉.

不同于傳統(tǒng)的載客熱門區(qū)域挖掘方法,本文考慮不同時段內(nèi)載客點分布的規(guī)律性,為載客熱門區(qū)域定義時段屬性:在其對應(yīng)的時段Tduration內(nèi),該區(qū)域被視為載客熱門區(qū)域,而超過時段Tduration時,則不再被視為載客熱門區(qū)域.因此,在對出租車司機進(jìn)行推薦時,應(yīng)結(jié)合當(dāng)前時間戳遴選出候選載客熱門區(qū)域,如定義4.

定義4(候選載客熱門區(qū)域)候選載客熱門區(qū)域為載客熱門區(qū)域的延伸定義,給定時間戳T,如果某載客熱門區(qū)域的時段屬性Tduration滿足Tstart≤T＜Tend,則該載客熱門區(qū)域為基于時間T的候選載客熱門區(qū)域.

出租車司機于不同的載客熱門區(qū)域主要有兩種尋客方式:第一,出租車司機在載客熱門區(qū)域中以駐車或排隊的方式被動性地等待乘客前來搭載,這種方式通常發(fā)生在乘客客流量呈現(xiàn)較強規(guī)律性變化或乘客以集中式出現(xiàn)的載客熱門區(qū)域,如火車站、飛機場等;第二,出租車司機在載客熱門區(qū)域中以巡游的方式自主性地尋找乘客.這種情況通常發(fā)生在地理范圍較大、乘客分布較分散的載客熱門區(qū)域,如某大型景點,公園等.基于以上兩種不同的尋客方式,本文將出租車以空載狀態(tài)自進(jìn)入載客熱門區(qū)域起,至在該區(qū)域搭載到下一位乘客止所經(jīng)歷的時間定義為候客時間,如定義5.

定義5(候客時間)候客時間Twait是指出租車在t0時刻由空載狀態(tài)進(jìn)入某載客熱門區(qū)域H起直到t1時刻在該區(qū)域搭載到下一位乘客所經(jīng)歷的時間.即Twait=t1-t0,且滿足0≤Twait≤tmax,其中tmax為人為定義的最長候客時間(本文取tmax=30 min).具體公式為

式(1)中若出租車由空載狀態(tài)進(jìn)入該區(qū)域經(jīng)歷tmax后還處于空載狀態(tài),或者在該區(qū)域經(jīng)歷時間不到tmax便由空載狀態(tài)離開該區(qū)域,則不對以上情況的候客時間進(jìn)行定義.

定義6(空載時間開銷)空載時間開銷Tcost指出租車由載客狀態(tài)為空載狀態(tài)起直到下一次跳變?yōu)檩d客狀態(tài)止所經(jīng)歷的時間.

對于多數(shù)載客熱門區(qū)域而言,其空載時間開銷值Tcost主要依賴于實時的路段交通情況,若出租車當(dāng)前位置到載客熱門區(qū)域的路段交通擁塞情況較嚴(yán)重,則其相應(yīng)的空載時間開銷值Tcost越大.因此,本文將對出租車司機進(jìn)行載客熱門區(qū)域的推薦轉(zhuǎn)化為對各載客熱門區(qū)域的空載時間開銷值Tcost的評測問題.同時考慮部分載客熱門區(qū)域需要以排隊方式搭載乘客,或在到達(dá)該區(qū)域后不能及時地搭載到下一位乘客,如火車站,飛機場等.因此本文將空載時間開銷Tcost視為由出租車當(dāng)前位置到載客熱門區(qū)域的時間和候客時間組成.

定義7(問題定義)基于實時路況的top-k載客熱門區(qū)域推薦是指給定出租車當(dāng)前位置Pcurrent,提交推薦請求的時間戳Tcurrent,基于時間戳Tcurrent的一系列候選載客熱門區(qū)域集H={h1,h2,…,hi,…,hn},推薦算法為出租車司機推薦k個潛在空載時間開銷值最小的載客熱門區(qū)域,即

不同于傳統(tǒng)的出租車相關(guān)推薦研究,本文通過對載客熱門區(qū)域潛在空載時間開銷值的評測,結(jié)合實時路況對出租車司機進(jìn)行推薦,使得推薦的載客熱門區(qū)域與出租車當(dāng)前位置的交通狀況良好.基于以上對推薦問題的定義可知,發(fā)現(xiàn)載客熱門區(qū)域以及如何計算載客熱門區(qū)域的潛在空載時間開銷成為本文考慮的首要問題.后面將對這兩部分的內(nèi)容進(jìn)行詳細(xì)闡述.

3 推薦模型

3.1 算法框架

本文構(gòu)建了一個兩階段的載客熱門區(qū)域推薦算法,框架如圖2所示.首先,在離線挖掘部分,結(jié)合出租車歷史軌跡數(shù)據(jù)集,采用改進(jìn)的DBSCAN聚類方法發(fā)現(xiàn)區(qū)別工作日、休息日且具有時段屬性的載客熱門區(qū)域,這些載客熱門區(qū)域以凸多邊形的方式進(jìn)行存儲,并且隨著出租車軌跡流的不斷積累每隔一定時間(如1 month)進(jìn)行更新維護(hù);其次,第二階段為在線推薦部分,當(dāng)出租車司機于某地點完成一次載客交易后提出推薦請求,系統(tǒng)將自動獲取出租車的位置信息以及當(dāng)前時間戳,根據(jù)當(dāng)前時間戳遴選出候選載客熱門區(qū)域,同時結(jié)合實時到達(dá)的出租車軌跡流完成對各路段的實際擁塞情況的評測,進(jìn)一步計算出租車當(dāng)前位置到各候選載客熱門區(qū)域的空載穿行時間,然后基于出租車歷史軌跡數(shù)據(jù)集預(yù)測各候選載客熱門區(qū)域的候客時間,最后結(jié)合空載穿行時間和候客時間完成對各候選載客熱門區(qū)域的潛在空載時間開銷Tcost的評測完成top-k推薦.

圖2 出租車載客熱門區(qū)域推薦模型框架圖Fig.2 Framework of hotspot recommendation

3.2 基于歷史軌跡的載客熱門區(qū)域提取

考慮區(qū)別工作日、休息日,一天中的不同時段對載客熱門區(qū)域的影響,本文將出租車歷史軌跡數(shù)據(jù)劃分為工作日以及休息日兩個部分,并將一天分為12個時間片{00:00-01:00, 01:00-02:00,…,22:00-23:00,23:00-24:00},采用改進(jìn)的DBSCAN聚類方法進(jìn)行分時段的聚類完成對載客熱門區(qū)域的提取.如圖3所示.

圖3 北京市機場、火車站、中學(xué)區(qū)域各時段平均載客頻數(shù)Fig.3 The average passenger frequency of airport,train station and school

載客熱門區(qū)域作為本文的推薦元素,如定義3中為出租車在某個連續(xù)時段內(nèi)發(fā)生載客事件較為密集的區(qū)域,即在該區(qū)域中發(fā)生載客事件概率較大,因此將該區(qū)域作為候客地點向出租車司機進(jìn)行推薦.這些區(qū)域通常具有特定的人群移動規(guī)律和功能特征,如可能代表一個商圈,或者是一個學(xué)校、景點等,且通常具有時段屬性.結(jié)合定義3旨在發(fā)現(xiàn)某一連續(xù)時段內(nèi)載客點密度較大的區(qū)域,如對于經(jīng)驗豐富的出租車司機而言,通常能清楚火車站各班次火車到站時間、電影院電影放映結(jié)束的時段或者學(xué)校的放學(xué)時間,由于在這些時段內(nèi)該區(qū)域發(fā)生載客事件較頻繁,因此出租車司機通常選擇對應(yīng)時段屬性的載客熱門區(qū)域作為候客地點.如圖3,由于深夜通往市區(qū)的公交、地鐵停運,位于郊區(qū)的機場在晚上23:00點至凌晨00:00點被視為載客熱門區(qū)域,即機場作為載客熱門區(qū)域的時段屬性可被定義為Tduration=〈23:00,24:00〉.

本文通過從歷史出租車軌跡數(shù)據(jù)集中提取出載客狀態(tài)由空載狀態(tài)跳變?yōu)檩d客狀態(tài)的GPS采樣點,將此點作為出租車載客點.基于上文中對載客熱門區(qū)域的定義和分析,本文采用改進(jìn)的DBSCAN聚類算法對提取出的載客點進(jìn)行時空聚類.該方法將傳統(tǒng)的DBSCAN聚類算法在時空域上進(jìn)行擴(kuò)展,將載客點分布于時空立體空間中進(jìn)行聚類,通過兩個參數(shù)εtemporal和εspatio分別作為時間維度和空間維度的度量半徑,如圖4所示,不僅考慮了空間屬性的相似性,同時也考慮了時間維度的相似性.采用時空密度作為實體空間相似性的度量標(biāo)準(zhǔn),將時空簇視為一系列由低密度區(qū)域(噪聲)分割開的高密度連通區(qū)域.由于改進(jìn)的DBSCAN聚類算法在聚類過程中考慮了時間維度上的相似性,使得聚類結(jié)果為在某一連續(xù)時段內(nèi)數(shù)據(jù)點密度較大的的時空簇.即位于同一個簇中的載客點不僅在地理位置上鄰近,在時間維度上也是較鄰近的,最終達(dá)到在某一連續(xù)時間段和密度較大的聚類目標(biāo).偽代碼如算法1(Algorithm 1)所示.

圖4 時空鄰近域Fig.4 Space-time adjacency domain

算法1的基本時間復(fù)雜度為O(n2),若對于數(shù)據(jù)結(jié)構(gòu)如KD樹,由于其可以有效檢索特定點給定距離內(nèi)的所有點,其時間復(fù)雜度便降低到O(n log n).由于其中每個點只需要維持少量數(shù)據(jù),即簇標(biāo)號和每個點的標(biāo)識,其空間復(fù)雜度為O(n).

注意算法1中為評估各載客點在時空屬性上的相似性,本文采用地球球面距離作為其在空間屬性上的相似度度量函數(shù),兩個載客點pi和pj的地球球面距離計算公式為

其中,R為地球的近似半徑,取R=6 370.996 81 km.

將載客點在時間屬性上的相似性度量函數(shù)定義為

基于以上改進(jìn)的DBSCAN聚類算法,區(qū)別工作日、休息日,將提取出的載客點按其時間戳分為24個時間片進(jìn)行時空聚類,生成各時間片中時空密度較高的出租車載客點集合,其聚類結(jié)果即時空簇便為某個連續(xù)時段內(nèi)載客事件發(fā)生較為頻繁的區(qū)域.本文采用Graham掃描法(Graham Scan)[12],發(fā)現(xiàn)各時空簇在空間屬性上的凸包(Convex Hull),以凸多邊形表示載客熱門區(qū)域的幾何屬性,實現(xiàn)對時空簇到地理幾何數(shù)據(jù)的轉(zhuǎn)化,同時計算出各時空簇的簇心,代表該載客熱門區(qū)域?qū)Τ鲎廛囁緳C進(jìn)行推薦,最后將該時空簇所處于的時間片作為其時段屬性.

隨著城市的擴(kuò)展以及變遷,載客熱門區(qū)域的分布也隨之變化.因此隨著出租車軌跡數(shù)據(jù)的積累,載客熱門區(qū)域應(yīng)每隔一定時間(如1 month)進(jìn)行增量式更新維護(hù),以更準(zhǔn)確地獲取發(fā)生變化或新增加的載客熱門區(qū)域.

3.3 在線推薦

3.3.1 潛在空載時間開銷函數(shù)

基于以上載客熱門區(qū)域提取辦法,準(zhǔn)確獲取到區(qū)分工作日、休息日中各時段的載客熱門區(qū)域集,該部分工作以離線的方式進(jìn)行處理.在線推薦階段中,根據(jù)當(dāng)前時間戳Tcurrent遴選基于Tcurrent的候選載客熱門區(qū)域,然后對各候選載客熱門區(qū)域的潛在空載時間開銷Tcost進(jìn)行計算.本節(jié)內(nèi)容主要介紹潛在空載時間開銷函數(shù)Tcost的構(gòu)造及計算方法.

實際生活中,出租車司機主要以快速搭載到下一位乘客以此提高工作效率作為其選擇候客地點的主要因素.考慮如下情況,出租車司機在完成一次載客交易后如何能以最短時間搭載到下一位乘客,通常會考慮以下兩個因素.

(1)面對日益龐大的城市交通網(wǎng)絡(luò),道路擁堵的情況時有發(fā)生,尤其在大城市會更為普遍.因此出租車司機會選擇距離當(dāng)前位置較近且交通狀況良好的載客熱門區(qū)域,從而避開交通擁堵路段減少出租車的空載穿行時間.

(2)考慮不同功能特征的載客熱門區(qū)域,其候客時間也存在較大區(qū)別,如火車站人流量大且相對集中,其候客時間稍長;而對于公園、商場等由于其乘客分布較為分散,候客時間則較短.當(dāng)然對于空載出租車司機而言,通常會選擇候客時間較短的載客熱門區(qū)域作為其候客的區(qū)域,以最短時間搭載到下一位乘客,提高工作效率.

本文結(jié)合以上兩個因素,對于一個基于位置Pcurrent、當(dāng)前時間戳為Tcurrent的出租車司機而言,能知道處于當(dāng)前時間戳Tcurrent的實際路段交通狀況以及各載客熱門區(qū)域的候客時間Twait,基于最短時間搭載到下一位乘客作為其選擇載客熱門區(qū)域的策略.本文設(shè)計潛在空載時間開銷函數(shù)Tcost對基于時間戳Tcurrent的候選載客熱門區(qū)域進(jìn)行評測,公式為

3.3.2 空載穿行時間預(yù)測

空載穿行時間Tdrive作為潛在空載時間開銷評測函數(shù)Tcost的組成部分之一,可被理解為出租車當(dāng)前位置到載客熱門區(qū)域的時間,其值主要由實時的路段交通情況決定,同時,由于多數(shù)出租車司機通常選擇兩位置間的最短路徑行駛,因此本文將候選載客熱門區(qū)域hi的簇心hceni與當(dāng)前位置Pcurrent之間的最短路徑作為出租車到hi的候選路徑,并結(jié)合該路徑所包含的路段交通情況完成空載穿行時間的預(yù)測.

(2)將路網(wǎng)圖G做以下臨時操作:刪除邊e Pm.s,Pn.s,e Pm.e,Pn.e,添加臨時頂點P start,P end,臨時邊e Pm.s,Pstart,e Pstart,Pn.s,e Pm..e,Pend,e Pend,Pn.e.

(3)基于臨時更改后的路網(wǎng)圖,采用Dijkstra算法[13]作為尋路策略,完成對基于起始位置到終止位置之間的最短路徑Rshort的計算.

基于以上最短路徑的計算方法,我們將獲取基于出租車當(dāng)前位置Pcurrent到各候選載客熱門區(qū)域的最短路徑Pathi=Pcurrent→P1→P2→…→Pn→,最后根據(jù)該路徑中各路段的實際交通狀況計算平均速度,完成對空載穿行時間Tdrive的計算,公式為

所謂經(jīng)驗決策是決策者憑借經(jīng)驗制定決策的活動和過程，［7］經(jīng)驗決策主要的推理過程是邏輯學(xué)中的類比推理，其最為主要的推理過程是:

本文通過基于滑動窗口的軌跡流聚類方法[9]獲得各路段基于時間Tcurrent的實時平均速度,該方法通過將實時到達(dá)的出租車軌跡數(shù)據(jù)流進(jìn)行增量式聚類,并且能刪除過時數(shù)據(jù)(即離時間戳Tcurrent較遠(yuǎn)的軌跡數(shù)據(jù))對聚類結(jié)果的影響,因此該聚類結(jié)果可作為當(dāng)前時段各路段交通狀況的評測指標(biāo).

3.3.3 候客時間預(yù)測

候客時間作為潛在空載時間開銷評測函數(shù)Tcost的另一個組成部分,本文采用基于樸素貝葉斯分類器[14]的方法對載客熱門區(qū)域的候客時間進(jìn)行預(yù)測.

不同的載客熱門區(qū)域在不同的時段候客時間不同,同時還考慮到是否為工作日對載客熱門區(qū)域候客時間也有影響,即對于候選載客熱門區(qū)域hi,由于候客時間受時間段Tperiod以及是否為工作日D的影響.根據(jù)貝葉斯定理,該候選載客熱門區(qū)域hi候客時間Twait為yi的后驗概率為

將1 d分為24個時間段,則Tperiod={00:00-01:00,01:00-02:00,…,22:00-23:00,23:00-24:00},并且區(qū)別工作日、休息日D={workday,weekend}.作為載客熱門區(qū)域,其候客時間當(dāng)然不可能是無限大的,即如果候客時間大于最長候客時間tmax,則認(rèn)為推薦失敗.因此我們將候客時間[0,tmax]平均分為m個時間桶(本文設(shè)置tmax=30 min,m=30),則時間桶yi取值為

基于yi的取值,載客熱門區(qū)域的候客時間Twait的預(yù)測則轉(zhuǎn)化為yi的極大后驗概率,表示的公式為

結(jié)合公式(7)中P(Tperiod,D)對于yi的不同取值是固定的,因此轉(zhuǎn)化為

由于變量Tperiod、Twait之間相互獨立,互不影響,因此公式(10)最后做轉(zhuǎn)化為

根據(jù)公式(11),將歷史出租車軌跡數(shù)據(jù)作為訓(xùn)練集,給定候選載客熱門區(qū)域hi,時間段Tperiod以及是否為工作日D,我們將能對該候選載客熱門區(qū)域的候客時間Twait進(jìn)行預(yù)測.其中時間段Tperiod主要依賴于當(dāng)前時間Tcurrent以及潛在空載行駛時間Tdrive,即Tperiod為Tcurrent+Tdrive對應(yīng)的時段獲得.并且公式(11)中先驗概率P(Twait=yi)、條件概率P(Tperiod|Twait=yi)、P(D|Twait=yi)都可通過計算訓(xùn)練集中相應(yīng)事件所占的比例進(jìn)行估計,其計算公式為公式(12)、(13)、(14).

Twait=yi表示在該載客熱門區(qū)域中搭載到下一位乘客并且候客時間Twait在時間桶yi中的事件,則有

對于一個載客熱門區(qū)域hi,由于其作為多邊形的方式進(jìn)行存儲,提取與該多邊形有交點的出租車歷史軌跡,得到出租車到達(dá)該載客熱門區(qū)域的時間t0,以及載客狀態(tài)跳變?yōu)椤?”的時間t1.因此,出租車在該載客熱門區(qū)域的候客時間Twait=t1-t0(如定義5).公式(12)中表示在載客熱門區(qū)域hi中,出租車搭載到下一位乘客并且候客時間Twait在時間桶yi中發(fā)生的數(shù)量;表示在載客熱門區(qū)域hi中,出租車以空載狀態(tài)進(jìn)入該載客熱門區(qū)域發(fā)生的數(shù)量.同理,根據(jù)貝葉斯公式,條件概率可表示為

公式(13)中ΓTperiod(0～1;(t1-t0)∈yi)表示在載客熱門區(qū)域hi中,在時間段Tperiod中,出租車搭載到下一位乘客并且候客時間Twait在時間桶yi中的數(shù)量;公式(14)中yi;D)表示在載客熱門區(qū)域hi中,出租車搭載到下一位乘客并且候客時間Twait在時間桶yi中發(fā)生日期為D的數(shù)量.

3.3.4 top-k推薦

基于以上對空載時間開銷函數(shù)Tcost的構(gòu)造及計算方法的描述,本文將對基于當(dāng)前時間Tcurrent的候選載客熱門區(qū)域進(jìn)行空載時間開銷的評測,即候選載客熱門區(qū)域的空載時間開銷值越小,則出租車當(dāng)前位置到該候選載客熱門區(qū)域的路段交通情況越好,出租車司機于該載客熱門區(qū)域?qū)⒛芤愿痰臅r間搭載到下一位乘客.解決了傳統(tǒng)出租車相關(guān)推薦研究忽視了實際交通狀況的缺陷.同時,為了避免“若處于相同位置的多輛出租車司機同時發(fā)出推薦請求時,推薦系統(tǒng)的推薦結(jié)果為同一載客熱門區(qū)域”這一情況,本文將空載時間開銷值最小的前k個載客熱門區(qū)域?qū)Τ鲎廛囁緳C進(jìn)行推薦以供其挑選.

4 實驗

4.1 實驗環(huán)境及數(shù)據(jù)集

本文實驗采用北京某地區(qū)2013年10月共30 d內(nèi)的出租車軌跡數(shù)據(jù)集,該數(shù)據(jù)集包含近30 000多輛出租車的真實GPS軌跡數(shù)據(jù).本文作為一個兩階段的推薦系統(tǒng),其中離線挖掘部分基于歷史數(shù)據(jù)發(fā)現(xiàn)載客熱門區(qū)域,在線推薦部分則需要通過出租車的實時軌跡流分析路網(wǎng)交通情況.因此實驗將數(shù)據(jù)集分為離線數(shù)據(jù)集C1、在線數(shù)據(jù)集C2.利用離線數(shù)據(jù)集C1發(fā)現(xiàn)載客熱門區(qū)域并作為載客熱門區(qū)域候客時間的訓(xùn)練集對候客時間進(jìn)行預(yù)測,并利用在線數(shù)據(jù)集C2模擬實時出租車軌跡流數(shù)據(jù),以對實時的交通路況進(jìn)行評測完成推薦.其中出租車的GPS數(shù)據(jù)格式如表1所示.實驗使用java語言實現(xiàn)算法的編寫,并在Windows 8.1操作系統(tǒng),機器配置為2.20 GHz Intel Core i5處理器和4 GB物理內(nèi)存的PC機上運行.

4.2 實驗分析

本文實驗選取北京市王府井百貨中心周圍區(qū)域作為實驗區(qū)域,并提取該區(qū)域中的軌跡數(shù)據(jù),即滿足東經(jīng)度lon∈[116.405 467?,116.436 109?]、北緯度lat∈[39.906 797?,39.926 151?].基于以上實驗區(qū)域,根據(jù)本文中的載客熱門區(qū)域生成方法,在時空聚類過程中選擇不同的參數(shù),并借助高德地圖接口對載客熱門區(qū)域進(jìn)行可視化操作,如圖5(b)、5(c)所示.

表1 出租車GPS數(shù)據(jù)格式Tab.1 Taxi GPS trajectory data format

由于載客熱門區(qū)域具有時段屬性,因此本文認(rèn)為只要具有不同時段屬性的載客熱門區(qū)域就應(yīng)該作為不同的個體存在.因此圖5(b)以及圖5(c)中重疊的多邊形則是由于不同的時段屬性造成的,不能將其視為同一個載客熱門區(qū)域.同時參數(shù)εspatio的設(shè)置對聚類結(jié)果影響較明顯,若εspatio值設(shè)置過大,聚類過程對噪聲數(shù)據(jù)不敏感,導(dǎo)致時空簇中空間密度較小,而區(qū)域范圍變大,如圖5(c).本文認(rèn)為載客熱門區(qū)域作為載客事件發(fā)生較頻繁的區(qū)域,聚類結(jié)果即時空簇中載客點分布較密集的載客熱門區(qū)域更具參考價值.

圖5 載客熱門區(qū)域可視化Fig.5 Hotspots visualization

本文作為首次考慮實際交通路況的推薦系統(tǒng),為了驗證推薦算法的有效性,考慮以下情形.

若某出租車位于位置P=(116.411 39?,39.910 533?)完成一次載客交易后提出推薦請求,系統(tǒng)當(dāng)前時間戳為T=9:00.該系統(tǒng)的推薦結(jié)果為k個空載時間開銷值較小的載客熱門區(qū)域,設(shè)置k=3,則推薦結(jié)果如圖6所示,本系統(tǒng)將以“H1、H2、H3”的排列次序?qū)Τ鲎廛囁緳C進(jìn)行推薦,其中載客熱門區(qū)域H1與位置P之間的最短路徑長約0.5 km,預(yù)計通行時間約60 s; H2與位置P之間的最短路徑長約1.1 km,預(yù)計通行時間約100 s;H3與位置P之間的最短路徑長約0.8 km,預(yù)計通行時間約150 s.雖然載客熱門區(qū)域H2的最短路徑距離稍大于載客熱門區(qū)域H3,而由位置P沿最短路徑駛向H3將途經(jīng)3個紅綠燈路口,時常造成路段擁堵,但由于位置P到H2的最短路徑的路段實時交通狀況良好,其空載行駛時間開銷值則越小,因此其空載時間開銷值則優(yōu)于載客熱門區(qū)域H3.

為驗證推薦方法的準(zhǔn)確性,我們計算推薦結(jié)果H1,H2,H3基于各時段的載客概率(Probability of take a passeger),如圖7、圖8、圖9.

載客熱門區(qū)域作為該系統(tǒng)的推薦元素,其基于當(dāng)前時間戳的載客發(fā)生事件概率越大,則說明系統(tǒng)推薦準(zhǔn)確性將越高,基于以上折線圖,我們發(fā)現(xiàn)載客熱門區(qū)域H1,H2,H3在時段08:00—10:00時其發(fā)生載客事件概率相較于其余時段都較高,因此出租車司機將這些載客熱門區(qū)域作為尋客目的地將更容易搭載到下一位乘客.

圖6 基于位置P、時間T的載客熱門區(qū)域top-k推薦可視化效果圖Fig.6 The top-k hotspots for taxi based on P and T

圖7 載客熱門區(qū)域H1的載客概率Fig.7 The probability of hotspot H1

圖8 載客熱門區(qū)域H2的載客概率Fig.8 The probability of hotspot H2

圖9 載客熱門區(qū)域H3的載客概率Fig.9 The probability of hotspot H3

最后,為驗證該推薦方法的有效性,將推薦結(jié)果H1,H2,H3基于實際數(shù)據(jù)集的平均空載時間開銷與傳統(tǒng)推薦方法(基于載客概率較大的推薦方法)的推薦結(jié)果的平均空載時間開銷進(jìn)行比較.提取出出租車歷史軌跡數(shù)據(jù)集中當(dāng)天處于08:30—09:30時間段內(nèi),出租車在位置P的載客狀態(tài)為空載狀態(tài),且在較短時間內(nèi)于預(yù)推薦的載客區(qū)域區(qū)域H1,H2,H3內(nèi)載客狀態(tài)值跳變?yōu)檩d客狀態(tài)的出租車軌跡.并計算這些軌跡的平均空載時間開銷.同理可得與傳統(tǒng)的推薦結(jié)果的平均空載時間開銷.如圖10所示,基于實時路況的載客熱門區(qū)域推薦相較于傳統(tǒng)的載客熱門區(qū)域推薦方法,因其主要考慮了實際的交通路況,其平均空載時間開銷優(yōu)于傳統(tǒng)的載客熱門區(qū)域推薦方法.

圖10 平均空載時間開銷柱狀圖Fig.10 The histogram of average empty time cost

5 結(jié)語

為解決出租車網(wǎng)約車空載現(xiàn)象嚴(yán)重的問題,本文結(jié)合實時路況提出了一個top-k出租車載客熱門區(qū)域的推薦方法,該方法基于潛在空載時間開銷較小的推薦策略向出租車司機進(jìn)行實時推薦.實驗結(jié)果表明,由于考慮了實際道路的交通情況,能有效提升載客熱門區(qū)域推薦的準(zhǔn)確率.

[1]CHANG H W,TAI Y C,HSU Y J.Context-aware taxi demand hotspots prediction[J].International Journal of Business Intelligence and Data Mining,2010,5(1):3-18.

[2]LI X L,PAN G,WU Z H,et al.Prediction of urban human mobility using large-scale taxi traces and its applications[J].Frontiers of Computer Science,2012,6(1):111-121.

[3]QU M,ZHU H,LIU J,et al.A cost-ef f ective recommender system for taxi drivers[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2014:45-54.

[4]YUAN N J,ZHENG Y,ZHANG L,et al.T-Finder:A recommender system for f i nding passengers and vacant taxis[J].IEEE Transactions on Knowledge&Data Engineering,2013,25(10):2390-2403.

[5]LI B,ZHANG D Q,SUN L,et al.Hunting or waiting?Discovering passenger-f i nding strategies from a largescale real-world taxi dataset[C]//Proceedings of the Pervasive Computing and Communications Workshops (PERCOM Workshops),2011 IEEE International Conference on.IEEE,2011:63-68.

[6]MOREIRA-MATIAS L,GAMA J,FERREIRA M,et al.Predicting taxi–passenger demand using streaming data[J].IEEE Transactions on Intelligent Transportation Systems,2013,14(3):1393-1402.

[7]PHITHAKKITNUKOON S,VELOSO M,BENTO C,et al.Taxi-aware map:Identifying and predicting vacant taxis in the city[C]//AmI’10 Proceedings of the First International Joint Conference on Ambient Intelligence. 2010:86-95.

[8]齊觀德,潘遙,李石堅,等.基于出租車軌跡數(shù)據(jù)挖掘的乘客候車時間預(yù)測[J].軟件學(xué)報,2013,24(2):14-23.

[9]MAO J L,SONG Q G,JIN C Q,et al.TSCluWin:Trajectory stream clustering over sliding window[C]// DASFAA 2016:Database Systems for Advanced Applications.2016:133-148.

[10]WANG Z C,LU M,YUAN X R,et al.Visual traffi c jam analysis based on trajectory data.[J].IEEE Transactions on Visualization&Computer Graphics,2013,19(12):2159-2168.

[11]HAN B,LIU L,OMIECINSKI E.Road-network aware trajectory clustering:Integrating locality,f l ow,and density[J].IEEE Transactions on Mobile Computing,2015,14(2):416-429.

[12]GRAHAM R L.An effi cient algorith for determining the convex hull of a f i nite planar set[J].Information Processing Letters,1972,4(1):132-133.

[13]DIJKSTRA E D.A note on two problem in connexion with graphs[J].Numerische Mathematik,1959(1):269-271.

[14]MITCHELL T,BUCHANAN B,DEJONG G,et al.Machine learning[J].Annual Review of Computer Science, 1990(4):417-433.

(責(zé)任編輯:李藝)

Top-k hotspots recommendation algorithm based on real-time traffi c

WU Tao1,MAO Jia-li1,XIE Qing-cheng1,YANG Yan-qiu2,WANG Jin1
(1.College of Computer,China West Normal University,Nanchong Sichuan 637000,China; 2.Department of Electronic Technology,Offi cers College of PAP,Chengdu 610000,China)

To cut down the no-load rate of taxis and relieve the traffi c pressure,an ef f ective hotspot recommendation method of picking up passenger is necessitated.Aiming at the problem of lower recommendation precision of traditional recommendation technique due to ignoring the actual road situation,we propose a two-phase real-time hotspot recommendation approach for picking up passenger.In the phase of offl ine mining,timebased hotspots are extracted by mining the history taxi trajectory dataset.In the phase of online recommendation,according to the position and time of taxi requests,a potential no-passenger time cost evaluation function that based on real-time road situation is presented to evaluate and rank hotspots,and obtain top-k hotspots of picking up passenger.Experimental results on taxi trajectory data show that,our proposal ensure smaller potential no-load time overhead due to considering real-time traffi c conditions,and hence has good ef f ectiveness and robustness as compared to the traditional recommendation approached.

potential no-passenger time cost function;real-time traffi c;hotspot; recommendation

TP311

A

10.3969/j.issn.1000-5641.2017.05.017

1000-5641(2017)05-0186-15

2017-06-19

四川省教育廳重點基金項目(17ZA0381,13ZA0015);西華師范大學(xué)國家培育項目(16C005);西華師范大學(xué)英才科研基金(17YC158)

吳濤,男,碩士研究生,研究方向為基于位置的服務(wù).E-mail:850517937@qq.com.

毛嘉莉,女,副教授,碩士生導(dǎo)師,研究方向為基于位置的服務(wù).E-mail:maojl1231@163.com.