基于區(qū)域劃分的出租車(chē)統(tǒng)一推薦算法

呂紅瑾　夏士雄　楊旭　黃丹

摘要：針對(duì)在極端天氣或交通繁忙時(shí)乘客無(wú)法快速搭乘出租車(chē)到達(dá)目的地的問(wèn)題，提出一種基于區(qū)域劃分的出租車(chē)統(tǒng)一推薦算法，不僅提供普通打車(chē)服務(wù)，同時(shí)提供拼車(chē)服務(wù)。首先，將區(qū)域作為旅程標(biāo)識(shí)，在旅程匹配方面化不可能為可能；其次，在拼車(chē)服務(wù)中算法將兩對(duì)路線相近的乘客進(jìn)行即時(shí)匹配，幫乘客拼車(chē)共乘；最后，選取繞遠(yuǎn)時(shí)間比例最小的出租車(chē)推薦給用戶。使用包含14747輛出租車(chē)的全球定位系統(tǒng)（GPS）數(shù)據(jù)對(duì)算法進(jìn)行評(píng)估，與CallCab系統(tǒng)相比雖然在減少的總里程數(shù)上下降了10%左右，但每次拼車(chē)平均只需要多花費(fèi)6%的時(shí)間，且降低的送達(dá)乘客總里程數(shù)同樣達(dá)到30%，不僅大幅度減少汽車(chē)尾氣的排放，同時(shí)在用戶更加關(guān)注的時(shí)間消耗方面表現(xiàn)更佳。

關(guān)鍵詞：拼車(chē)；區(qū)域劃分；全球定位系統(tǒng)數(shù)據(jù)；MapReduce；里程數(shù)

中圖分類(lèi)號(hào)：TP311

文獻(xiàn)標(biāo)志碼：A

0引言

在大都市的日常生活中，出租車(chē)在所有的交通工具中扮演著一個(gè)重要的角色，例如在紐約，有超過(guò)100家公司經(jīng)營(yíng)著1.3萬(wàn)臺(tái)出租車(chē)以滿足每天66萬(wàn)多次出租車(chē)搭載請(qǐng)求[1-2]。然而在早晚高峰時(shí)間段，大量的乘客依舊無(wú)法快速搭乘空閑出租車(chē)。在高峰時(shí)段，乘客有時(shí)需要等待30min以上才可以搭乘空出租車(chē)離開(kāi)[2]。本文提出基于區(qū)域劃分的出租車(chē)統(tǒng)一推薦算法，包括空閑出租車(chē)服務(wù)和拼車(chē)服務(wù)，其中拼車(chē)服務(wù)可以大幅度緩解以上問(wèn)題，同時(shí)降低了車(chē)輛的空駛率，司機(jī)在同一時(shí)間段內(nèi)可以多載一位付費(fèi)乘客，多獲得一筆車(chē)費(fèi)；另一方面，乘客的出行費(fèi)用也會(huì)相應(yīng)降低。

雖然拼車(chē)服務(wù)具有如此多的優(yōu)點(diǎn)，但幾乎所有的出租車(chē)推薦系統(tǒng)均集中于空閑出租車(chē)的推薦，沒(méi)有真正在拼車(chē)領(lǐng)域進(jìn)行相關(guān)探究[3-7]，即使存在對(duì)于拼車(chē)模式的研究，也無(wú)法完全滿足大量實(shí)時(shí)用戶的拼車(chē)請(qǐng)求[8]。并且與空閑出租車(chē)服務(wù)不同，提供拼車(chē)服務(wù)的出租車(chē)無(wú)法隨意地將乘客送往其所要到達(dá)的任意目的地。在拼車(chē)服務(wù)中，乘客需要找到可搭乘的出租車(chē)，可搭乘的含義即出租車(chē)中已經(jīng)存在的乘客的目的地與新乘客的目的地方向相似。一個(gè)目的地方向?yàn)槟戏降某丝筒粫?huì)認(rèn)為一輛準(zhǔn)備開(kāi)往北方的出租車(chē)是其所愿意搭乘的出租車(chē)，因?yàn)槿舫俗顺鲎廛?chē)則意味著要多耗費(fèi)大量的時(shí)間。

本文算法首先將全球定位系統(tǒng)（Global Positioning System， GPS）經(jīng)緯度點(diǎn)對(duì)轉(zhuǎn)化為區(qū)域，并通過(guò)MapReduce計(jì)算模型[9-12]獲取以區(qū)域標(biāo)識(shí)的旅程信息和特定時(shí)刻特定區(qū)域的通過(guò)時(shí)間；然后，以三種不同的標(biāo)準(zhǔn)篩選出相比于其他實(shí)時(shí)出租車(chē)更有可能去往乘客目的地方向的出租車(chē)；最后，相比距離，本文算法以乘客更加關(guān)注的時(shí)間為標(biāo)準(zhǔn)，計(jì)算實(shí)時(shí)出租車(chē)的繞遠(yuǎn)時(shí)間比例并推薦繞遠(yuǎn)時(shí)間比例最小的實(shí)時(shí)出租車(chē)給乘客；本文最后對(duì)算法進(jìn)行了相關(guān)評(píng)測(cè)。

1研究背景

1.1設(shè)備信息

出租車(chē)實(shí)時(shí)GPS跟蹤器會(huì)不斷地發(fā)送GPS數(shù)據(jù)給后臺(tái)，每一個(gè)GPS數(shù)據(jù)都由六部分組成，分別表示：車(chē)牌號(hào)、時(shí)間、經(jīng)度、緯度、狀態(tài)和速度。

如圖1所示：在L1點(diǎn)、L2點(diǎn)狀態(tài)值為0表示出租車(chē)沒(méi)有搭載乘客；在L3點(diǎn)狀態(tài)值從0變?yōu)?，認(rèn)為出租車(chē)完成了一次搭載乘客動(dòng)作；在L4點(diǎn)時(shí)狀態(tài)值為1而在L5點(diǎn)時(shí)變?yōu)?，認(rèn)為出租車(chē)完成一次旅程，乘客下車(chē)，出租車(chē)?yán)^續(xù)行駛[13]。

通過(guò)持續(xù)跟蹤一輛出租車(chē)的GPS數(shù)據(jù)，再根據(jù)狀態(tài)值的改變判定旅程的開(kāi)始與結(jié)束，可以獲得旅程的起點(diǎn)、終點(diǎn)以及中間地點(diǎn)。根據(jù)這種方法，推薦算法可以通過(guò)原始GPS數(shù)據(jù)獲取所有旅程信息。

1.2情景演示

對(duì)于普通搭載空出租車(chē)的服務(wù)眾所周知，本文就不在此詳細(xì)介紹，本文重點(diǎn)介紹拼車(chē)服務(wù)。

從圖2中可知，一名乘客在S2點(diǎn)等待一輛出租車(chē)，其目的地是D2，此時(shí)乘客以起點(diǎn)S2、目的地D2作為基本信息提出搭乘請(qǐng)求。推薦算法基于實(shí)時(shí)GPS數(shù)據(jù)，在其周?chē)鸁o(wú)法找到空閑出租車(chē)，但是可以找到即將通過(guò)S2的已經(jīng)存在乘客的出租車(chē)T，其起點(diǎn)為S1，所以出租車(chē)T可以作為潛在的可進(jìn)行拼車(chē)服務(wù)的出租車(chē)。

乘客在S2點(diǎn)搭乘出租車(chē)T，基于先上先服務(wù)的原則，出租車(chē)T首先應(yīng)該將已上車(chē)的乘客送達(dá)目的地D1（D1的位置并不確定，需要通過(guò)歷史數(shù)據(jù)獲得），之后從D1再開(kāi)往D2。乘客無(wú)論選擇普通搭載服務(wù)還是拼車(chē)服務(wù)，都需要等待出租車(chē)的到來(lái)，當(dāng)?shù)却龝r(shí)間超過(guò)本次旅程的時(shí)間，那么乘客會(huì)放棄搭車(chē)，所以算法將旅程時(shí)間作為隨機(jī)等待時(shí)間的上限。

乘客搭載出租車(chē)T進(jìn)行拼車(chē)，那么到達(dá)目的地的時(shí)間為：TD=等待時(shí)間+（S2→D1）+（D1→D2）；若進(jìn)行普通搭車(chē)請(qǐng)求，到達(dá)目的地時(shí)間為：TP=等待時(shí)間+（S2→D2）。通過(guò)繞遠(yuǎn)時(shí)間比例=（TD-TP）/TP來(lái)區(qū)分不同實(shí)時(shí)出租車(chē)的效用。對(duì)于空閑出租車(chē)，其D1=D2繞遠(yuǎn)時(shí)間比例為0。

計(jì)算中需要的實(shí)時(shí)已存在乘客出租車(chē)T的起點(diǎn)S1和可能目的地D1都無(wú)法從現(xiàn)有的設(shè)備中獲得。但隨著GPS數(shù)據(jù)的積累，推薦算法可以從大量的出租車(chē)GPS數(shù)據(jù)中獲得算法所需要的信息，具體過(guò)程接下來(lái)將進(jìn)行詳細(xì)介紹。

2算法流程

2.1算法概述

算法會(huì)根據(jù)用戶特定的起始地、目的地、請(qǐng)求時(shí)間與歷史GPS數(shù)據(jù)庫(kù)信息，實(shí)時(shí)推薦某輛已有乘客出租車(chē)為用戶提供“花費(fèi)較短繞遠(yuǎn)時(shí)間”的拼車(chē)服務(wù)。

算法主要面臨著兩個(gè)難題：

1）根據(jù)現(xiàn)有的設(shè)備，無(wú)法直接獲取已有乘客出租車(chē)的目的地，如果無(wú)法預(yù)測(cè)已有乘客出租車(chē)的目的地，那么拼車(chē)服務(wù)將無(wú)法實(shí)現(xiàn)。針對(duì)此問(wèn)題，算法反向跟蹤已有人出租車(chē)GPS數(shù)據(jù)，獲取其搭載乘客起點(diǎn)，以用戶起點(diǎn)作為旅程中間點(diǎn)匹配歷史旅程信息，獲取相應(yīng)的可能目的地。

2）用戶提出請(qǐng)求時(shí)，周?chē)鷮?shí)時(shí)一般會(huì)存在多輛出租車(chē)，如何區(qū)分不同出租車(chē)的優(yōu)劣，并對(duì)其優(yōu)劣程度進(jìn)行量化為用戶推薦最優(yōu)選擇是又一個(gè)難題。本文算法站在用戶的角度，對(duì)于時(shí)間消耗給予最大限度的關(guān)注，采用繞遠(yuǎn)時(shí)間比例對(duì)實(shí)時(shí)出租車(chē)進(jìn)行對(duì)比，下文會(huì)進(jìn)行詳細(xì)敘述。

算法在前期會(huì)對(duì)歷史GPS數(shù)據(jù)進(jìn)行處理，獲取旅程路線信息和區(qū)域時(shí)間信息。針對(duì)用戶的特定請(qǐng)求，算法主要進(jìn)行了三步處理：獲取實(shí)時(shí)出租車(chē)信息；針對(duì)各個(gè)實(shí)時(shí)出租車(chē)，判定可能目的地，計(jì)算出租車(chē)對(duì)應(yīng)的繞遠(yuǎn)時(shí)間比例；最后推薦繞遠(yuǎn)時(shí)間比例最小的出租車(chē)為用戶提供拼車(chē)服務(wù)。

2.2前期準(zhǔn)備

2.2.1旅程信息

推薦算法根據(jù)海量的GPS數(shù)據(jù)，持續(xù)跟蹤每輛出租車(chē)可以得到所有每次旅程的起點(diǎn)、終點(diǎn)以及中間地點(diǎn)。通過(guò)這樣的方式，推薦算法首先從海量的GPS數(shù)據(jù)中取得了出租車(chē)所有的旅程信息，之后根據(jù)已經(jīng)得知的出租車(chē)起點(diǎn)（作為旅程的起點(diǎn)）、用戶起點(diǎn)（作為中間經(jīng)過(guò)地點(diǎn)）可以推測(cè)出可能的目的地。如圖3所示，可能目的地D1有多種可能，使用虛線描述。

因此推薦算法需要先對(duì)原始GPS數(shù)據(jù)集進(jìn)行處理，獲得旅程信息，旅程信息的獲得是這整個(gè)推薦算法的關(guān)鍵。

2.2.2區(qū)域與區(qū)域時(shí)間

如果采用GPS經(jīng)緯度點(diǎn)對(duì)作為匹配旅程的標(biāo)志，那么會(huì)造成幾乎無(wú)法匹配到具有相同起點(diǎn)和中間地點(diǎn)的旅程，因?yàn)樵谕粋€(gè)GPS經(jīng)緯度點(diǎn)進(jìn)行搭車(chē)的情況幾乎沒(méi)有。

為了將不可能化為可能，本文采用區(qū)域劃分的方法，將區(qū)域作為旅程的標(biāo)識(shí)，即將多個(gè)相近GPS經(jīng)緯度點(diǎn)對(duì)轉(zhuǎn)換為同一區(qū)域。在持續(xù)跟蹤同一出租車(chē)GPS數(shù)據(jù)時(shí)，同一個(gè)區(qū)域內(nèi)會(huì)包含此出租車(chē)多個(gè)GPS記錄，最晚時(shí)間與最早時(shí)間的差可以作為此出租車(chē)通過(guò)這個(gè)區(qū)域的時(shí)間消耗[14]。

通過(guò)區(qū)域劃分，推薦算法以多個(gè)區(qū)域編號(hào)標(biāo)記一次搭載旅程，在旅程匹配方面化不可能為可能。劃分區(qū)域后，整個(gè)旅程只在起點(diǎn)和終點(diǎn)區(qū)域存在很小的時(shí)間誤差，更加接近現(xiàn)實(shí)情況。

2.3計(jì)算繞遠(yuǎn)時(shí)間比例

對(duì)于普通拼車(chē)服務(wù)，繞遠(yuǎn)時(shí)間比例為0。對(duì)于拼車(chē)服務(wù)，當(dāng)接收到用戶的拼車(chē)請(qǐng)求之后，推薦算法為了推薦一輛出租車(chē)給此特定乘客，會(huì)進(jìn)行以下四步運(yùn)算：

1）根據(jù)用戶起點(diǎn)和時(shí)間，獲取實(shí)時(shí)已有乘客出租車(chē)車(chē)牌號(hào)，根據(jù)時(shí)間反跟蹤其GPS數(shù)據(jù)，獲取其出發(fā)區(qū)域。

2）已知出租車(chē)起點(diǎn)區(qū)域，將新用戶起點(diǎn)作為旅程中間區(qū)域，與旅程信息相比較，獲得可能的出租車(chē)目的地。

3）對(duì)目的地進(jìn)行篩選。平均分配每個(gè)目的地概率，計(jì)算該出租車(chē)對(duì)應(yīng)的繞遠(yuǎn)時(shí)間比例。

4）比較所有實(shí)時(shí)出租車(chē)，推薦繞遠(yuǎn)時(shí)間比例最小的一輛出租車(chē)給乘客，完成一次請(qǐng)求任務(wù)。

對(duì)于用戶來(lái)說(shuō)，最好的推薦選項(xiàng)即為最有可能去往其目的地方向的出租車(chē)。假設(shè)對(duì)于某特定用戶請(qǐng)求而言，可能目的地Db相比可能目的地Da擁有更小的繞遠(yuǎn)時(shí)間比例，此時(shí)有實(shí)時(shí)兩輛出租車(chē)：出租車(chē)T1可能目的地有10個(gè)，8個(gè)為Da，2個(gè)為Db；出租車(chē)T2可能目的地也有10個(gè)，6個(gè)為Da，4個(gè)為Db。雖然兩輛出租車(chē)均更有可能去往Da，但站在用戶角度，只關(guān)心具有更小繞遠(yuǎn)時(shí)間比例的Db，所以相比T1，算法會(huì)推薦T2給乘客。

所以，本文對(duì)出租車(chē)可能目的地集合進(jìn)行篩選的三種模式均站在用戶角度，只關(guān)心相比其他實(shí)時(shí)出租車(chē)，推薦車(chē)輛是否具有最小的繞遠(yuǎn)時(shí)間比例，以具有更小的繞遠(yuǎn)時(shí)間比例作為篩選的依據(jù)。

圖4是整個(gè)算法的操作流程；圖5則針對(duì)“計(jì)算繞遠(yuǎn)時(shí)間比例”的三種不同模式，使用示意圖展示其不同。下面對(duì)這三種模式進(jìn)行詳細(xì)的描述：

3數(shù)據(jù)處理

大數(shù)據(jù)處理工具有許多，例如Hadoop（主要包括MapReduce和Hadoop分布式文件系統(tǒng)（Hadoop Distributed File System， HDFS））、Spark和Storm。Storm適用于實(shí)時(shí)計(jì)算，而本文算法主要時(shí)間消耗為歷史GPS數(shù)據(jù)的批量處理，Hadoop更加適合。Hadoop在外存處理數(shù)據(jù)，Spark在內(nèi)存處理數(shù)據(jù)，Hadoop適合迭代處理，擅長(zhǎng)批量處理；相對(duì)而言Spark更適合流處理，不擅長(zhǎng)迭代處理。Spark處理速度確實(shí)比Hadoop快，但是對(duì)于服務(wù)器的內(nèi)存有著較大需求，算法為了保證能夠?qū)崟r(shí)地推薦出租車(chē)給用戶提供拼車(chē)服務(wù)，最終選擇Hadoop，這樣既可以減少歷史GPS數(shù)據(jù)批量處理的時(shí)間消耗，也可以保證充分的內(nèi)存空間應(yīng)對(duì)實(shí)時(shí)用戶請(qǐng)求的處理。

3.1前期準(zhǔn)備

原始數(shù)據(jù)集合由成千上萬(wàn)條GPS數(shù)據(jù)集合獲得。原始數(shù)據(jù)不能夠直接被推薦算法使用，需要進(jìn)行處理，以獲取旅程信息和區(qū)域時(shí)間。在進(jìn)行以下工作時(shí)，已經(jīng)對(duì)原始數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗操作，并按照時(shí)間增序?qū)?shù)據(jù)進(jìn)行排列，方便接下來(lái)的數(shù)據(jù)處理。

3.1.1旅程信息

從原始GPS數(shù)據(jù)中獲取旅程信息，需要對(duì)單個(gè)出租車(chē)進(jìn)行持續(xù)跟蹤，并且需要對(duì)其狀態(tài)進(jìn)行監(jiān)測(cè)，提取出連續(xù)狀態(tài)值為1（即有乘客）的連續(xù)區(qū)域集合。

如圖6、表1及表2所示，根據(jù)原始GPS數(shù)據(jù)集合，本文算法可獲取到以區(qū)域標(biāo)記的旅程信息，使用區(qū)域編號(hào)代替一個(gè)個(gè)GPS經(jīng)緯度點(diǎn)對(duì)描述整個(gè)旅程，如圖6所示，經(jīng)過(guò)區(qū)域劃分后，一次旅程變?yōu)椋?/p>

通過(guò)這種持續(xù)跟蹤與區(qū)域劃分的思想，將原始GPS數(shù)據(jù)集合轉(zhuǎn)化為用區(qū)域標(biāo)記的旅程信息。

3.1.2區(qū)域與區(qū)域時(shí)間

由表3、表4可以看出某輛出租車(chē)進(jìn)入?yún)^(qū)域Jd52Wd11的時(shí)間為0：01：36，駛出區(qū)域Jd52Wd11的時(shí)間為0：03：39，所以可以得知，這輛出租車(chē)經(jīng)過(guò)區(qū)域Jd52Wd11所耗費(fèi)時(shí)間為123s，依據(jù)同樣的方法可以獲得各個(gè)區(qū)域的時(shí)間。

需要格外注意的是，求區(qū)域時(shí)間時(shí)，無(wú)需考慮出租車(chē)狀態(tài)，因?yàn)榇钶d乘客與否對(duì)于通過(guò)區(qū)域的時(shí)間不會(huì)產(chǎn)生影響；并且計(jì)算區(qū)域時(shí)間時(shí)，同一區(qū)域不同時(shí)間段的時(shí)間消耗是不一樣的，所以本文采用時(shí)間段、區(qū)域兩個(gè)變量來(lái)確定某區(qū)域在某個(gè)時(shí)間段的時(shí)間消耗，更加貼近現(xiàn)實(shí)情況。

3.2數(shù)據(jù)處理流程

3.2.1旅程信息

通過(guò)Map階段獲得起點(diǎn)區(qū)域?yàn)槟程囟▍^(qū)域（出租車(chē)起點(diǎn)）的旅程信息，Reduce階段在Map的基礎(chǔ)上獲取中間區(qū)域包含某特定區(qū)域（用戶起點(diǎn)）的旅程，并最終輸出滿足兩個(gè)條件的旅程終點(diǎn)區(qū)域，這個(gè)終點(diǎn)區(qū)域即為出租車(chē)可能的目的地。

3.2.2區(qū)域時(shí)間

首先通過(guò)Map階段完成對(duì)相同車(chē)牌號(hào)的GPS數(shù)據(jù)進(jìn)行分類(lèi)，并輸出。在Reduce階段，循環(huán)遍歷特定車(chē)牌號(hào)所有GPS數(shù)據(jù)，駛出區(qū)域時(shí)間減去駛?cè)雲(yún)^(qū)域時(shí)間，得到此時(shí)刻的區(qū)域時(shí)間。之后對(duì)某區(qū)域特定時(shí)間段的區(qū)域時(shí)間求平均值，最終獲得此區(qū)域特定時(shí)間段的時(shí)間消耗。

3.2.3繞遠(yuǎn)時(shí)間比例計(jì)算

當(dāng)用戶以起點(diǎn)區(qū)域和目的地區(qū)域作為基礎(chǔ)信息提出搭乘出租車(chē)請(qǐng)求時(shí)，推薦算法根據(jù)實(shí)時(shí)數(shù)據(jù)，找到周?chē)鲎廛?chē)信息和起點(diǎn)區(qū)域。并根據(jù)出租車(chē)起點(diǎn)區(qū)域和用戶起點(diǎn)區(qū)域推算可能的目的地區(qū)域集合。之后對(duì)于三種不同模式大體步驟相同，如下所述：

1）縮減可能目的地集合：根據(jù)不同模式的要求在Map階段，篩選出滿足模式要求的可能目的地，去除不滿足的目的地。

2）計(jì)算：在Reduce階段計(jì)算所有滿足條件目的地的繞遠(yuǎn)時(shí)間比例，平均分配概率，計(jì)算該出租車(chē)對(duì)應(yīng)的繞遠(yuǎn)時(shí)間比例。

3.2.4在線推薦

計(jì)算出多個(gè)實(shí)時(shí)出租車(chē)的繞遠(yuǎn)時(shí)間比例后，進(jìn)行比較，選出繞遠(yuǎn)時(shí)間比例最小的出租車(chē)推薦給乘客，完成本次推薦任務(wù)。

4算法測(cè)試與評(píng)估

為了檢測(cè)算法的性能，本文采用了14727臺(tái)出租車(chē)組成的1.74GB出租車(chē)數(shù)據(jù)進(jìn)行檢測(cè)，其中包含了450萬(wàn)條GPS原始數(shù)據(jù)集合[14]。在使用此GPS數(shù)據(jù)集合進(jìn)行測(cè)試時(shí)，會(huì)出現(xiàn)諸如出租車(chē)速度不為0但經(jīng)緯點(diǎn)對(duì)無(wú)變化等錯(cuò)誤情況，這些現(xiàn)象可能由于設(shè)備故障、傳輸失真、人為因素等產(chǎn)生，在對(duì)數(shù)據(jù)處理之前需要對(duì)這些不合理現(xiàn)象進(jìn)行處理，提高實(shí)驗(yàn)結(jié)果的準(zhǔn)確性。

4.1測(cè)試綜述

算法將原始GPS數(shù)據(jù)分為五份，其中一份作為實(shí)時(shí)數(shù)據(jù)，從中提取出的旅程信息作為用戶的請(qǐng)求，例如某次旅程在X0時(shí)刻Y0區(qū)域開(kāi)始，在X1時(shí)刻Y1區(qū)域結(jié)束，那么此次旅程可以轉(zhuǎn)化為一次從X0時(shí)刻Y0區(qū)域到X1時(shí)刻Y1區(qū)域的用戶搭乘請(qǐng)求。根據(jù)請(qǐng)求信息，算法首先在實(shí)時(shí)數(shù)據(jù)集合中找到周?chē)膶?shí)時(shí)出租車(chē)，根據(jù)出租車(chē)起點(diǎn)區(qū)域和用戶的起點(diǎn)區(qū)域Y0找到可能的目的地區(qū)域集合，之后根據(jù)不同模式的要求篩選滿足條件的可能目的地，并進(jìn)行計(jì)算推薦操作。

測(cè)試時(shí)采用兩種性能進(jìn)行評(píng)測(cè)：一個(gè)是繞遠(yuǎn)時(shí)間比例，算法會(huì)將繞遠(yuǎn)時(shí)間比例最小的出租車(chē)推薦給乘客；第二個(gè)是減少的里程數(shù)。隨著汽車(chē)的增多，空氣污染越來(lái)越嚴(yán)重，與分別送兩名乘客到達(dá)目的地的總里程數(shù)相比，拼車(chē)服務(wù)送達(dá)兩名乘客會(huì)減少出租車(chē)所走的總里程數(shù)，減少汽車(chē)尾氣的排放，對(duì)環(huán)境保護(hù)有極大的推動(dòng)作用。

4.2具體測(cè)評(píng)

4.2.1繞遠(yuǎn)時(shí)間比例

本部分對(duì)在算法進(jìn)行測(cè)試時(shí)，24h不同時(shí)段三種不同模式繞遠(yuǎn)時(shí)間比例的變化情況進(jìn)行說(shuō)明解釋。圖7、8中橫軸刻度代表某一時(shí)間段，如刻度6，表示6：00：00—6：59：59時(shí)間段的平均屬性。

從圖7中可知，在一天24h內(nèi)，模式1與模式2的繞遠(yuǎn)時(shí)間比例都遠(yuǎn)遠(yuǎn)大于模式3，因?yàn)橄啾饶Ｊ?和模式2，模式3的篩選更加準(zhǔn)確所以產(chǎn)生更小的繞遠(yuǎn)時(shí)間消耗。在早高峰時(shí)間段（7：00—9：00）由于乘客的需求規(guī)律性不高，乘客目的地為分布于整個(gè)城市的各個(gè)工作地點(diǎn)，所以此時(shí)進(jìn)行拼車(chē)具有較大的時(shí)間消耗；在晚高峰時(shí)間段（18：00—21：00），此時(shí)大多數(shù)的居民結(jié)束一天的工作正是下班高峰期，拼車(chē)去往較為集中的居住地與娛樂(lè)場(chǎng)所的乘客需求較多，所以此時(shí)拼車(chē)算法表現(xiàn)最為良好。

4.2.2減少的公里數(shù)

本部分主要從減少里程數(shù)的角度對(duì)三種不同的模式進(jìn)行測(cè)試評(píng)估。

從圖8中可知：無(wú)論是哪種模式都可以較為明顯地減少總共的里程數(shù)，且基本都達(dá)到15%以上，三種模式在減少里程數(shù)上具有相同的變化情況。在早高峰與晚高峰時(shí)間段，搭乘出租車(chē)的旅程較多，所以減少的里程數(shù)相比其他時(shí)間段更加明顯，達(dá)到30%以上；在凌晨階段，由于乘客的目的地隨機(jī)性較大，所以減少的里程數(shù)相比于其他時(shí)間段比例較小。

具有相同目的（即減少出租車(chē)總里程數(shù)）的CallCab系統(tǒng)[15]在減少的總里程數(shù)上具有良好的表現(xiàn)，在繁忙時(shí)間段（7：00—9：00）甚至達(dá)到50%以上。相比CallCab，本文算法將區(qū)域時(shí)間作為基本點(diǎn)，更關(guān)注用戶到達(dá)目的地的時(shí)間消耗，最終目的是為了更快速地將用戶送達(dá)目的地，盡可能地減少拼車(chē)造成的時(shí)間消耗，所以相比基于距離的CallCab系統(tǒng)，會(huì)產(chǎn)生更少的時(shí)間消耗，但相對(duì)而言減少的總里程數(shù)效果會(huì)稍差。

5結(jié)語(yǔ)

本文分析、設(shè)計(jì)并且評(píng)估了基于區(qū)域劃分的出租車(chē)推薦算法，針對(duì)在極端天氣或交通繁忙時(shí)乘客無(wú)法快速搭乘出租車(chē)到達(dá)目的地的問(wèn)題，以降低乘客拼車(chē)時(shí)間消耗為著重點(diǎn)，為用戶推薦時(shí)間消耗最小的出租車(chē)。經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證，每次拼車(chē)平均只需要多花費(fèi)6%的時(shí)間，且降低的送達(dá)乘客總里程數(shù)達(dá)到30%，不僅能大幅度減少汽車(chē)尾氣的排放，同時(shí)在用戶更加關(guān)注的時(shí)間消耗方面的表現(xiàn)也更佳。

本文算法通過(guò)挖掘海量歷史GPS信息來(lái)獲取各個(gè)區(qū)域時(shí)間，然后為用戶推薦具有較短時(shí)間消耗的出租車(chē)，但對(duì)于GPS數(shù)據(jù)的挖掘依舊不夠充分，這將在以后的工作當(dāng)中進(jìn)行深入研究。

參考文獻(xiàn)：

[1]Taxi of tomorrow survey [EB/OL]. [2015-11-16]. http：//www.nyc.gov/html/tlc/downloads/pdf/tot_survey_results_02_10_11.pdf.

[2]The New York city taxicab fact book [EB/OL]. [2015-11-16]. http：//www.schallerconsult.com/taxi/taxifb.pdf.

[3]BALAN R K， NGUYEN K X， JIANG L. Real-time trip information service for a large taxi fleet [C]// MobiSys 11： Proceedings of the 9th International Conference on Mobile Systems. New York： ACM， 2011： 99-112.

[4]WU W， NG W S， KRISHNASWAMY S， et al. To taxi or not to taxi？ — enabling personalised and real-time transportation decisions for mobile users [C]// MDM 12： Proceedings of the 2012 IEEE 13th International Conference on Mobile Data Management. Washington， DC： IEEE Computer Society， 2012： 320-323.

[5]GE Y， XIONG H， TUZHILIN A， et al. An energy-efficient mobile recommender system [C]// KDD 10： Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2010： 899-908.

[6]LIU W， ZHENG Y， CHAWLA S， et al. Discovering spatiotemporal causal interactions in traffic data streams [C]// KDD 11： Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2011： 1010-1018.

[7]HUANG Y， POWELL J W. Detecting regions of disequilibrium in taxi services under uncertainty [C]// SIGSPATIAL 12： Proceedings of the 20th International Conference on Advances in Geographic Information Systems. New York： ACM， 2012：139-148.

[8]肖強(qiáng)，何瑞春，張薇，等.基于模糊聚類(lèi)和識(shí)別的出租車(chē)合乘算法研究[J]. 交通運(yùn)輸系統(tǒng)工程與信息，2014，14（5）：119-125. （XIAO Q， HE R C， ZHANG W， et al. Algorithm research of taxi carpooling based on fuzzy clustering and fuzzy recognition [J]. Journal of Transportation Systems Engineering and Information Technology， 2014， 14（5）： 119-125.）

[9]白竹，金曉紅.出租車(chē)GPS數(shù)據(jù)的應(yīng)用研究[J].黑龍江工程學(xué)院學(xué)報(bào)，2014，28（2）：50-54. （BAI Z， JIN X H. Research on the application of taxi GPS data[J]. Journal of Heilongjiang Institute of Technology， 2014， 28（2）： 50-54.）

[10]DEAN J， GHEMAWAT S. MapReduce： simplified data processing on large clusters [C]// OSDI 04： Proceedings of the 6th Conference on Symposium on Operating Systems Design & Implementation. Berkeley， CA： USENIX Association， 2004， 6： Article No. 10.

Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation， 2014， 51（1）： 107-113.）

[11]何賢國(guó)，孫國(guó)道，高家全，等.出租車(chē)GPS大數(shù)據(jù)的道路行車(chē)可視分析[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2014，26（12）：2163-2172. （HE X G，SUN G D，GAO J Q， et al. Visual analytics of road traffic with large scale taxi GPS data[J]. Journal of Computer-Aided Design & Computer Graphics， 2014， 26（12）： 2163-2172.）

[12]桂智明，向宇，李玉鑒. 基于出租車(chē)軌跡的并行城市熱點(diǎn)區(qū)域發(fā)現(xiàn)[J]. 華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，40（S1）：187-190. （GUI Z M， XIANG Y， LI Y J. Parallel discovering of city hot spot based on taxi trajectories [J]. Journal of Huazhong University of Science and Technology （Natural Science Edition）， 2012， 40（S1）： 187-190.）

[13]唐爐亮，鄭文斌，王志強(qiáng)，等.城市出租車(chē)上下客的GPS軌跡時(shí)空分布探測(cè)方法[J]. 地球信息科學(xué)學(xué)報(bào)，2015，17（10）：1179-1186. （TANG L L， ZHENG W B， WANG Z Q， et al. Space time analysis on the pick-up and drop-off of taxi passengers based on GPS big data[J]. Journal of Geo-Information Science， 2015， 17（10）： 1179-1186.）

[14]Data description for UrbanCPS [EB/OL]. [2015-11-20]. http：//www-users.cs.umn.edu/～tianhe/BIGDATA/.

[15]ZHANG D S， HE T， LIU Y， et al. CallCab： A unified recommendation system for carpooling and regular taxicab services [C]// IEEE Big Data 2013： Proceedings of the 2013 IEEE International Conference on Big Data. Piscataway， NJ： IEEE， 2013： 439-447.