段宗濤, 陳欣欣, 康 軍, 溫興超, 尉青青

?

基于Hadoop的出租車服務(wù)策略①

段宗濤1,2, 陳欣欣1, 康 軍1,2, 溫興超1, 尉青青1

1(長安大學(xué)信息工程學(xué)院, 西安 710064)2(陜西省道路交通智能檢測與裝備工程研究中心, 西安 710064)

出租車服務(wù)策略是出租車司機(jī)群體智慧的體現(xiàn), 隱藏在大規(guī)模的出租車GPS軌跡數(shù)據(jù)中. 基于大數(shù)據(jù)分析工具, 針對出租車GPS軌跡數(shù)據(jù)進(jìn)行服務(wù)策略挖掘, 提取好的服務(wù)策略指導(dǎo)司機(jī)營運(yùn)可以提高司機(jī)收入和營運(yùn)效率. 乘客搜索策略是出租車服務(wù)策略的主要內(nèi)容, 在對GPS軌跡數(shù)據(jù)進(jìn)行清洗之后導(dǎo)入HDFS, 首先提取司機(jī)個(gè)人軌跡, 并對其收入進(jìn)行量化, 然后對乘客搜索策略建模, 根據(jù)模型利用hadoop平臺統(tǒng)計(jì)出司機(jī)對各種策略的使用情況, 結(jié)果表明, 收入較高的司機(jī)在乘客搜索策略選擇上與收入一般的司機(jī)有顯著差異.

智能交通系統(tǒng); 服務(wù)策略挖掘; 出租車GPS軌跡; hadoop; mapreduce

1 前言

移動(dòng)傳感設(shè)備(比如智能手機(jī)和GPS導(dǎo)航儀)的普遍存在, 使得用大量的電子足跡描述人的行為成為可能, 這些電子足跡給我們提供了理解人在各種情景下的行為模式和發(fā)現(xiàn)潛在智能的獨(dú)特視角[1].

在很多城市, 出租車都配備了GPS裝備, GPS裝備將定時(shí)給服務(wù)器上傳出租車的實(shí)時(shí)信息, 包括出租車ID、經(jīng)緯度、時(shí)間戳、瞬時(shí)速度、方向角、是否載客等. GPS軌跡數(shù)據(jù)中隱含著出租車司機(jī)的服務(wù)行為, 包括他們從空車狀態(tài)采取什么策略搜索乘客和在載客狀態(tài)采取什么策略輸送乘客等. 每個(gè)司機(jī)的服務(wù)行為都不同, 取決于司機(jī)在特定情況(時(shí)間、空間)下個(gè)人的服務(wù)策略. 比如, 在下客以后, 有的司機(jī)會在較近的地方等待新乘客, 而有的司機(jī)會到較遠(yuǎn)的地方搜索新乘客. 出租車司機(jī)采取的策略對載客時(shí)間和載客距離產(chǎn)生直接的影響, 從而引起收入和燃料消耗以及碳排放量的不同. 好的服務(wù)策略不僅會帶來較高的運(yùn)行收入, 還會提高整個(gè)出租車服務(wù)系統(tǒng)的效率, 更好地滿足乘客的出行需求. 因此, 研究出租車司機(jī)的服務(wù)策略將有益于司機(jī)、乘客和交通管理、規(guī)劃部門[2].

本文的數(shù)據(jù)是西安市出租車調(diào)度系統(tǒng)采集的GPS數(shù)據(jù); 由于傳統(tǒng)關(guān)系型數(shù)據(jù)庫在數(shù)據(jù)量不斷增加時(shí),往往只能向上擴(kuò)展, 而且代價(jià)非常昂貴; 而Hadoop可以線性向外擴(kuò)展. 在Hadoop平臺上, 首先通過數(shù)據(jù)預(yù)處理、提取白班、夜班司機(jī)個(gè)人GPS軌跡; 然后對單個(gè)司機(jī)進(jìn)行性能量化, 挖掘有效的服務(wù)策略(主要探討乘客搜索策略).

Hadoop是一個(gè)分布式系統(tǒng)架構(gòu), 由Apache軟件基金會開發(fā), 廣泛應(yīng)用于大數(shù)據(jù)存儲和分析處理場景[3]. 主要包括HDFS(Hadoop分布式文件系統(tǒng))和MapReduce(分布式計(jì)算框架). HDFS的優(yōu)點(diǎn)是高容錯(cuò)性, 高擴(kuò)展性、并且對硬件的要求比較低. 它提供對應(yīng)用程序數(shù)據(jù)的高吞吐量訪問, 適用于超大數(shù)據(jù)集的存儲. MapReduce編程框架的優(yōu)點(diǎn)是, 用戶不需要了解分布式系統(tǒng)底層的細(xì)節(jié), 就能夠開發(fā)分布式應(yīng)用程序[4]. MapReduce計(jì)算過程: 1)讀取輸入數(shù)據(jù), 對數(shù)據(jù)進(jìn)行“分片”(分片大小一般為HDFS塊大小, 默認(rèn)128M), 每一個(gè)map任務(wù)處理一個(gè)“分片”, 多個(gè)map同時(shí)工作. 2) map: 每一個(gè)map任務(wù)處理一個(gè)“分片”根據(jù)map函數(shù)處理數(shù)據(jù), 對每條記錄以形式輸出到本地文件. 3) shuffle: 將各個(gè)map輸出數(shù)據(jù)按key分組歸結(jié)到一起, 發(fā)往一個(gè)reducer. 此過程非常耗費(fèi)資源, 如設(shè)置了combiner, 先在各節(jié)點(diǎn)按key本地合并, 減少網(wǎng)絡(luò)I/O; 默認(rèn)使用hash partitioner均勻分配數(shù)據(jù)到不同的reduce節(jié)點(diǎn). 4) reduce: 對key相同的多個(gè)value進(jìn)行規(guī)約操作. 本文的司機(jī)個(gè)人軌跡提取、收入量化、服務(wù)策略挖掘等都是在Hadoop平臺上開發(fā)完成.

2 數(shù)據(jù)預(yù)處理

本文基于西安市出租車調(diào)度系統(tǒng)采集的GPS數(shù)據(jù); 記錄的每個(gè)字段都為varchar, 數(shù)據(jù)格式依次為: “序號” “車輛牌照” “時(shí)間” “經(jīng)度” “緯度” “水平速度” “方向” “狀態(tài)位”(0 無狀態(tài)位 1 防劫 2 簽到 3 簽退 4 空車 5 重車 6 點(diǎn)火 7 熄火). 數(shù)據(jù)示例如圖1.

圖1 GPS軌跡數(shù)據(jù)示例

原始數(shù)據(jù)保存在Oracle數(shù)據(jù)庫中, 采用Sqoop(Sqoop是一個(gè)用來將Hadoop和關(guān)系型數(shù)據(jù)庫中的數(shù)據(jù)相互轉(zhuǎn)移的工具, 可以將關(guān)系型數(shù)據(jù)庫中的數(shù)據(jù)導(dǎo)進(jìn)Hadoop的HDFS中, 也可以將HDFS的數(shù)據(jù)導(dǎo)進(jìn)到關(guān)系型數(shù)據(jù)庫中)將數(shù)據(jù)庫中的數(shù)據(jù)導(dǎo)進(jìn)到Hadoop的HDFS中進(jìn)行存儲, 以便我們的數(shù)據(jù)處理和分析.

由于城市中建筑物對信號傳輸過程的影響, 以及GPS 測量精度等, 造成GPS在定位時(shí)存在較大誤差, 使得原始GPS數(shù)據(jù)中存在一些異常數(shù)據(jù), 包括速度遠(yuǎn)高于正常行駛速度的異常數(shù)據(jù)等; 以及在沒有GPS信號的地方, 比如地下車庫、隧道等地點(diǎn), 會產(chǎn)生重復(fù)值、字段空缺值問題. 這樣的數(shù)據(jù)無法直接進(jìn)行數(shù)據(jù)挖掘, 或挖掘結(jié)果差強(qiáng)人意[5].

在數(shù)據(jù)預(yù)處理過程中, 首先對重復(fù)數(shù)據(jù)進(jìn)行去重; 對包含異常速度:<0 或>120的值進(jìn)行剔除. 對于GPS軌跡誤差:時(shí)刻: 坐標(biāo)(,);時(shí)刻: 坐標(biāo)(,); 經(jīng)緯度之差>閾值;則認(rèn)為是異常值.

3 個(gè)人軌跡提取

首先, 對出租車GPS軌跡數(shù)據(jù)進(jìn)行切分, 提取單個(gè)司機(jī)個(gè)人軌跡數(shù)據(jù). 一輛出租車一般由白班、夜班兩個(gè)司機(jī)共同運(yùn)營; 兩個(gè)司機(jī)的行為模式不同, 所以提取單個(gè)司機(jī)的GPS軌跡以便分析單個(gè)司機(jī)的服務(wù)策略[6]. 在MapReduce編程框架下實(shí)現(xiàn), 主要分為map過程(對整個(gè)文件進(jìn)行分片, 然后對每個(gè)分片執(zhí)行map函數(shù)中的操作)和reduce過程(接收map產(chǎn)生的數(shù)據(jù)塊, 按reduce函數(shù)中的操作對數(shù)據(jù)進(jìn)行規(guī)約), 以車牌后3位為partition依據(jù)重寫partitioner, 盡量使數(shù)據(jù)均勻的分配到集群各個(gè)節(jié)點(diǎn)進(jìn)行計(jì)算, 重寫多文件輸出格式MultipleOutputFormat, 使每個(gè)key輸出一個(gè)文件. 算法偽代碼:

算法1

輸入: 清洗后的GPS軌跡數(shù)據(jù)輸出: 個(gè)人(白班司機(jī))的GPS軌跡數(shù)據(jù) 1. GetGpsMap: 2. If time stamps between 05:00 and 07:00 {3. If(state==7){早換班}4. 得到早換班時(shí)間后的軌跡5. }6. If time stamps between 17:00 and 18:00 {7. If(state==7){ //晚換班}8. 得到晚換班時(shí)間前的軌跡9. }10. If time stamps between 07:00 and 17:00{得到時(shí)間段內(nèi)的軌跡}11. GetGpsReduce: 12. 按車牌、日期及白班為文件名輸出白班軌跡

4 收入量化

利用Hadoop對出租車司機(jī)收入進(jìn)行量化; 計(jì)算出租車司機(jī)每趟乘客輸送過程中累積的距離, 然后計(jì)算司機(jī)的大致收入. 即通過司機(jī)的GPS軌跡數(shù)據(jù)中相鄰時(shí)間經(jīng)緯度變化, 計(jì)算此間隔的距離, 累積一天(白班或夜班)得到該司機(jī)的行駛距離, 從而得到司機(jī)大致收入. 數(shù)據(jù)為前文所述的GPS軌跡數(shù)據(jù), 提取出白班司機(jī)軌跡, 量化白班司機(jī)個(gè)人的收入. 需要注意linux系統(tǒng)默認(rèn)的ulimit參數(shù)中open files、stack size、max user processes, 以及l(fā)imits.conf中的nproc限制等需要根據(jù)數(shù)據(jù)適量調(diào)大以滿足大規(guī)模數(shù)據(jù)讀寫和產(chǎn)生大量文件需求[7]. 算法2為鏈?zhǔn)阶鳂I(yè), 第一個(gè)job完成后, 結(jié)果作為第二個(gè)job的輸入; 分布式計(jì)算過程: 首先用TextInputFormat從HDFS讀取數(shù)據(jù), 然后數(shù)據(jù)分片, 對各分片進(jìn)行map, 然后把key相同的map結(jié)果拉取到同一節(jié)點(diǎn), 進(jìn)行reduce.

算法2

輸入: 輸入按時(shí)間排序的單個(gè)司機(jī)GPS軌跡數(shù)據(jù)輸出: 累積計(jì)算產(chǎn)生的收入 1. SalaryMapper1: 2. 切分?jǐn)?shù)據(jù)3. while(state==5){4. 累積計(jì)算處于載客狀態(tài)的每兩個(gè)相鄰時(shí)間間隔GPS點(diǎn)的距離， GetDistace(olon, olat, lon, lat)5. }6. SalaryReducer1:7. 累積計(jì)算每一趟載客的距離，并計(jì)算收入8. SalaryMapper2: 9. 切分?jǐn)?shù)據(jù)10. SalaryReducer2: 11. 累積計(jì)算白班司機(jī)一天白班收入

5 乘客搜索策略挖掘

5.1 乘客搜索策略模型

分別從收入較高和一般的司機(jī)群體的GPS軌跡數(shù)據(jù)里挖掘乘客搜索. 出租車實(shí)際服務(wù)策略建模, 主要探討即乘客搜索策略. 乘客搜索策略, 考慮司機(jī)在搜索新乘客時(shí)影響出租車司機(jī)決策的實(shí)際因素. 出租車司機(jī)可能會傾向于在一個(gè)的區(qū)域等待(酒店和火車站)或者在一個(gè)較小的范圍內(nèi)搜索或者去一個(gè)較遠(yuǎn)的熟悉的區(qū)域搜索乘客. 基于此把乘客搜索策略分為: 本地等待、本地搜索、遠(yuǎn)距離搜索三種策略. 定義為: 出租車司機(jī)在當(dāng)前乘客下車之后, 搜索下一個(gè)乘客的累積軌跡長度(當(dāng)前乘客下車后到下一個(gè)乘客上車, 每兩個(gè)相鄰點(diǎn)距離之和). 如果<=1500m且等待時(shí)間<=5min即認(rèn)為本地搜索;<=1500m且等待時(shí)間>5min即認(rèn)為本地等待;>1500m認(rèn)為遠(yuǎn)程搜索. 一個(gè)有經(jīng)驗(yàn)的出租車司機(jī)可能會綜合考慮交通狀況和時(shí)空特性等因素, 快速搜索到乘客[8].

5.2 乘客搜索策略挖掘

近兩年足球這項(xiàng)運(yùn)動(dòng)越來越受到國家的重視，校園足球火爆一時(shí)，各個(gè)地方出現(xiàn)了大小規(guī)模不同的青少年足球培訓(xùn)機(jī)構(gòu)，這都形成了良好的足球?qū)W習(xí)氛圍.長春市各個(gè)高校也應(yīng)該緊貼時(shí)代，加強(qiáng)教師足球水平培訓(xùn)，形成自己鮮明特色的大學(xué)足球課程.

算法3通過兩個(gè)job來完成乘客搜索策略的挖掘. 在GetStrategyMap1中, 計(jì)算乘客下車后出租車司機(jī)搜索乘客時(shí)離下車點(diǎn)的距離, 然后在GetStrategyReduce1中確認(rèn)搜索策略類型, 并在GetStrategyMap2中使用GetStrategyReduce1的輸出結(jié)果進(jìn)行計(jì)算, 改變輸出格式, 最后在GetStrategyReduce2中使用多文件輸出格式輸出. 分布式計(jì)算過程同算法2.

算法3

輸入: 輸入按時(shí)間排序的單個(gè)司機(jī)GPS軌跡數(shù)據(jù)輸出: 搜索策略類別 1. GetStrategyMap1: 2. 切分?jǐn)?shù)據(jù)3. if ((oldstate==5)&& (state==4) {4. 上一個(gè)乘客下車，開始搜索乘客5. While(state==4){6. 計(jì)算每個(gè)點(diǎn)距離開始搜索的點(diǎn)的距離7. Distance=GetDistace(olon, olat, lon, lat)8. }9. GetStrategyReduce1: 10. If(Distance> 10000){遠(yuǎn)距離搜索}11. If(Distance <= 1000){本地等待}12. Else{本地搜索}13. }14. GetStrategyMap2:15. 切分?jǐn)?shù)據(jù)，保證輸出格式16. GetStrategyReduce2: 17. 按車牌多文件輸出

最后, 研究相關(guān)服務(wù)策略對司機(jī)收入的影響情況, 分析收入和出租車服務(wù)策略的相關(guān)關(guān)系. 發(fā)現(xiàn)能夠提高司機(jī)收入和出租車系統(tǒng)效率的服務(wù)策略, 更好地滿足乘客的出現(xiàn)需求.

6 實(shí)驗(yàn)與結(jié)論

本文基于大規(guī)模的GPS歷史數(shù)據(jù)(中國某城市約10000輛出租車2011年6月的數(shù)據(jù)), 發(fā)現(xiàn)高效的出租車服務(wù)策略. 首先, 我們分離出白班、夜班單個(gè)出租車司機(jī)的GPS軌跡. 第二, 量化出租車司機(jī)個(gè)人的收入. 第三, 我們探討出租車服務(wù)策略, 主要乘客搜索策略:本地等待、本地搜索、遠(yuǎn)程搜索. 最后, 評估服務(wù)策略和收入的關(guān)聯(lián)關(guān)系, 對比分析得出哪些策略有效. 挖掘出高效出租車司機(jī)的服務(wù)策略, 使用這些策略來提高司機(jī)服務(wù)水平. 實(shí)驗(yàn)環(huán)境: 使用Hadoop集群, 其中一臺為NameNode, 一臺為Secondary NameNode; 其余為計(jì)算節(jié)點(diǎn). GPS數(shù)據(jù)集一天約3千萬條記錄, 包含約1萬輛出租車.

我們從收入較高和收入一般的白班司機(jī)中, 各取樣500名, 進(jìn)行數(shù)據(jù)分析. 對比收入較高與收入一般的司機(jī)在搜索策略上的相同與不同之處, 分析收入與策略的關(guān)系.

圖2是表現(xiàn)一般與表現(xiàn)較好的白班司機(jī)各小時(shí)內(nèi)收入表現(xiàn)情況, 可以看出表現(xiàn)好的司機(jī), 各個(gè)小時(shí)的收入都顯著的高于表現(xiàn)一般的司機(jī).

圖3是表現(xiàn)一般的白班司機(jī)各小時(shí)內(nèi)服務(wù)策略使用的次數(shù)情況; 可以看出在各個(gè)時(shí)間段內(nèi)本地等待策略次數(shù)多于本地搜索次數(shù), 多于遠(yuǎn)程搜索次數(shù). 在7:00-8:00、13:00-14: 00、15:00-16:00、16:00-17:00時(shí)段, 本地搜索次數(shù)與本地等待次數(shù)相當(dāng), 其余時(shí)段相差較大.

圖4是表現(xiàn)一般與表現(xiàn)較好的白班司機(jī)各小時(shí)內(nèi)收入表現(xiàn)情況, 可以發(fā)現(xiàn)與圖4類似的情況. 不同之處在于, 遠(yuǎn)程搜索次數(shù)明顯多于表示一般的司機(jī).

圖4 表現(xiàn)較好的白班司機(jī)各小時(shí)內(nèi)采用策略的次數(shù)

對圖3、圖4的數(shù)據(jù)用t檢驗(yàn)進(jìn)一步分析表現(xiàn)一般與表現(xiàn)較好的白班司機(jī)采用策略的次數(shù)顯著性差異, 建立假設(shè)H0: u1=u2無差異, H1: u1<>u2 有差異, 取顯著性水平為0.05. 根據(jù)統(tǒng)計(jì)量(如公式1所示).

計(jì)算P值如下: Distant: 5.39232E-0.6;Hunt: 0.450986861;Wait: 0.83893276. 對于Distant策略, P＜0.05拒絕原假設(shè), 即表現(xiàn)一般與表現(xiàn)較好的白班司機(jī)采用distant策略次數(shù)有顯著差異; 對于hunt和wait策略接受原假設(shè), 即認(rèn)為表現(xiàn)一般與表現(xiàn)較好的白班司機(jī)采用hunt和wait策略次數(shù)無顯著差異.

7 總結(jié)

出租車服務(wù)策略, 作為大量出租車司機(jī)的群體智慧, 隱藏在出租車GPS軌跡中. 分析GPS軌跡, 發(fā)現(xiàn)熟練司機(jī)的決策行為, 理解熟練司機(jī)的服務(wù)策略將給司機(jī)、乘客、和城市規(guī)劃者帶來益處. 比如, 好的服務(wù)策略可以減少空載率、減少乘客等車時(shí)間、減少碳排放等. 傳統(tǒng)的數(shù)據(jù)庫難以支撐這樣大量數(shù)據(jù)的分析, 而分布式大數(shù)據(jù)處理系統(tǒng)Hadoop可以存儲和處理這些數(shù)據(jù). 而且可以根據(jù)業(yè)務(wù)需求不斷線性擴(kuò)展集群存儲和計(jì)算規(guī)模.

分析結(jié)果表明, 收入較高的出租車司機(jī)和收入一般的出租車司機(jī)相比, 采取遠(yuǎn)距離搜索策略的次數(shù)有顯著性差異. 收入較高的出租車司機(jī)比收入一般的出租車司機(jī)在遠(yuǎn)距離搜索策略上更有經(jīng)驗(yàn).

1 Zhang D, Sun L, Li B, et al. Understanding taxi service strategies from taxi GPS traces. IEEE Trans. on Intelligent Transportation Systems, 2014, 16(1): 123–135.

2 Chen G, Jin X, Yang J. Study on spatial and temporal mobility pattern of urban taxi services. 2010 International Conference on Intelligent Systems and Knowledge Engineering (ISKE). IEEE. 2010. 422–425.

3 Apache軟件基金會.hadoop官方文檔http://hadoop.apache. org/. [2016-02-13].

4 White T. Hadoop權(quán)威指南.北京:清華大學(xué)出版社.

5 楊揚(yáng),姚恩建,潘龍,等.基于GPS數(shù)據(jù)的出租車路徑選擇行為研究.交通運(yùn)輸系統(tǒng)工程與信息,2015,15(1):81–86.

6 何雯,李德毅,安利峰,等.基于GPS軌跡的規(guī)律路徑挖掘算法.吉林大學(xué)學(xué)報(bào)(工學(xué)版),2014,44(6):1764–1770.

7 孫翎等.通過ulimit改善系統(tǒng)性能. http://www.ibm.com/ developerworks/cn/linux/l-cn-ulimit/.

8 李小龍.基于大規(guī)模出租車軌跡的乘客移動(dòng)行為的預(yù)測及其應(yīng)用[學(xué)位論文].杭州:浙江大學(xué),2012.

Taxi Service Strategy Based on Hadoop

DUAN Zong-Tao1,2, CHEN Xin-Xin1, KANG Jun1,2, WEN Xing-Chao1, YU Qing-Qing1

1(The Information Technology School, Chang’an University, Xi’an 710064, China)2(Shaanxi Road Traffic Detection and Equipment Engineering Research Center, Xi’an 710064, China)

Taxi service strategy is a group of taxi drivers’ wisdom embodied, hidden in the large-scale taxi GPS data. Mining GPS traces using big data analysis tools to find and understand the service strategies of skilled taxi drivers to guide other drivers can increase their salaries and improve the efficiency of taxi operation. Passenger searching strategy is the main content of taxi service strategies, which loads GPS traces data into HDFS after the data pre-processing; splits the data to get each driver’s personal GPS traces; calculates driver’s salary; models taxi driver’s service strategies; and then studies how the service strategies influence the driver’s salary. A case study indicates that, the differences between the taxi drivers who have better salaries and the drivers who have ordinary salaries are significant in terms of passenger searching strategy.

intelligent transportation systems; service strategies mining; taxi GPS traces; hadoop; mapreduce

國家自然科學(xué)基金(61303041);交通運(yùn)輸部基礎(chǔ)研究項(xiàng)目(2014319812150);陜西省工業(yè)攻關(guān)項(xiàng)目(2014K05-28,2015GY002);中央高校創(chuàng)新團(tuán)隊(duì)項(xiàng)目(310824153405)

2016-04-25;收到修改稿時(shí)間:2016-06-07

[10.15888/j.cnki.csa.005567]