基于網(wǎng)格化的出租車(chē)空載尋客路徑推薦

高 瞻 余 辰 向鄭濤 陳宇峰*

1(湖北汽車(chē)工業(yè)學(xué)院電氣與信息工程學(xué)院 湖北 十堰 442002)2(華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 湖北 武漢 430074)

0 引 言

現(xiàn)代化城市建設(shè)日新月異，人們交通出行方式更加多樣化，為方便人們隨時(shí)快速地到達(dá)任意目的地，打車(chē)服務(wù)顯得尤為重要，出租車(chē)作為出現(xiàn)較早且保存至今的交通出行工具，在城市交通中扮演著十分重要的角色。目前的出租車(chē)由于區(qū)域供需比不平衡、調(diào)度不合理、載客路徑規(guī)劃不智能也造成了較多的社會(huì)問(wèn)題，如：市民打車(chē)難、空載出租車(chē)司機(jī)尋客難等，這些問(wèn)題直接導(dǎo)致了大量乘客的打車(chē)需求得不到滿(mǎn)足，出租車(chē)司機(jī)載客效率低掙不到錢(qián)，以及由于出租車(chē)空載巡游造成的資源浪費(fèi)和環(huán)境污染等。

針對(duì)這些問(wèn)題，學(xué)者們已經(jīng)做了大量的研究，如袁晶等[1-2]通過(guò)北京出租車(chē)GPS軌跡數(shù)據(jù)分析學(xué)習(xí)乘客的移動(dòng)模式和出租車(chē)司機(jī)搭客卸客的行為，以利益最大化、路線最快、最高概率載客、最短等待隊(duì)列多種路徑推薦方式，設(shè)計(jì)出租車(chē)推薦系統(tǒng)，推薦最佳等待地點(diǎn)搭載乘客；以最大可能發(fā)現(xiàn)空閑車(chē)輛和最小平均等待時(shí)間兩種top-k的策略，設(shè)計(jì)乘客推薦系統(tǒng)，為乘客推薦步行距離區(qū)域最近的停車(chē)點(diǎn)。唐爐亮等[3]提出了出租車(chē)上下客時(shí)空分布的線密度探測(cè)模型，獲取城市出租車(chē)上下客的時(shí)空分布規(guī)律，理解和認(rèn)知了城市空間的動(dòng)態(tài)性。文獻(xiàn)[4]從大量復(fù)雜的出租車(chē)GPS軌跡數(shù)據(jù)中，搜素和挖掘有效信息，設(shè)計(jì)打車(chē)推薦系統(tǒng)(Taxi-RS)，通過(guò)該系統(tǒng)可以提供給乘客一個(gè)特定的搭乘地點(diǎn)以及搭乘的概率和等待時(shí)間。文獻(xiàn)[5]引入出租車(chē)駕駛經(jīng)驗(yàn)作為關(guān)鍵因素分析，設(shè)計(jì)位置到位置圖模型(OFF-ON Model)分析乘客下車(chē)位置與下一個(gè)乘客上車(chē)位置之間的關(guān)系，為出租車(chē)推薦更有利的巡航位置。文獻(xiàn)[6]針對(duì)出租車(chē)拼車(chē)服務(wù)，采用區(qū)域劃分，將區(qū)域作為旅程的標(biāo)識(shí)，找出可能去往乘客目的地的出租車(chē)，將具有最小繞遠(yuǎn)時(shí)間比例的車(chē)輛推薦給用戶(hù)，減少了行駛里程和時(shí)間花費(fèi)。

出租車(chē)推薦系統(tǒng)相關(guān)的文獻(xiàn)中，以相似的目標(biāo)主要考慮的因素包含：當(dāng)前位置與推薦位置之間的距離、等待下一位乘客的時(shí)間、乘客上下車(chē)位置關(guān)系、預(yù)期的行程費(fèi)用等。本文在前人相關(guān)研究的基礎(chǔ)上，綜合考慮了城市地理特點(diǎn)、打車(chē)訂單分布等因素計(jì)算載客核心點(diǎn)，基于空載出租車(chē)在駛向載客核心點(diǎn)途中載客概率最大化問(wèn)題，研究空載出租車(chē)尋客路徑推薦，使出租車(chē)在較短的尋客距離內(nèi)最大概率地搭載到乘客。首先，對(duì)相關(guān)研究進(jìn)行分析，提出本文需要解決的問(wèn)題。然后，針對(duì)問(wèn)題進(jìn)行建模，根據(jù)網(wǎng)約車(chē)的訂單數(shù)據(jù)分布特點(diǎn)提出了基于環(huán)形切割的聚類(lèi)算法，以及基于網(wǎng)格化的出租車(chē)曼哈頓路徑模型。最后，通過(guò)實(shí)驗(yàn)對(duì)本文提出的方法進(jìn)行驗(yàn)證與分析。

1 問(wèn)題分析

目前我國(guó)許多城市因?yàn)榈乩硖攸c(diǎn)、環(huán)城公路、工業(yè)生產(chǎn)、人口分布等因素以“環(huán)”進(jìn)行區(qū)域劃分，例如目前北京被劃分為六個(gè)環(huán)，成都被劃分為五個(gè)環(huán)。容易發(fā)現(xiàn)，位于同一環(huán)形區(qū)域內(nèi)，不同方位的人口密度、交通狀況等特征具有較大的相似性，而不同環(huán)之間則存在明顯的差異，即呈現(xiàn)出環(huán)內(nèi)相似、環(huán)間不同的特點(diǎn)。這直接影響了城市居民的分布情況，進(jìn)而使打車(chē)需求量也呈現(xiàn)相似特點(diǎn)。同時(shí)，隨著現(xiàn)代化城市建設(shè)的發(fā)展，城市交通道路變得交錯(cuò)縱橫，呈現(xiàn)出“網(wǎng)”狀結(jié)構(gòu)，車(chē)輛去往同一目的地的路徑出現(xiàn)了更多的選擇，這使得通過(guò)網(wǎng)格化來(lái)研究出租車(chē)路徑具有了現(xiàn)實(shí)意義。

本文數(shù)據(jù)集來(lái)源于滴滴出行“蓋亞”數(shù)據(jù)開(kāi)放計(jì)劃[7]，數(shù)據(jù)集包含成都市2016年11月的滴滴網(wǎng)約車(chē)訂單數(shù)據(jù)約620萬(wàn)條、軌跡數(shù)據(jù)約10億條。本文主要對(duì)其中的OD(Origin-Destination)數(shù)據(jù)進(jìn)行研究，數(shù)據(jù)信息如表1所示。

表1 網(wǎng)約車(chē)訂單信息表

基于網(wǎng)約車(chē)、出租車(chē)軌跡數(shù)據(jù)或OD數(shù)據(jù)相關(guān)的研究已經(jīng)較為豐富了，部分學(xué)者致力于軌跡數(shù)據(jù)或OD數(shù)據(jù)聚類(lèi)算法或路徑規(guī)劃算法的優(yōu)化[8-12]，也有許多學(xué)者著重于出租車(chē)調(diào)度與資源利用最大化問(wèn)題[13-14]。學(xué)者們通過(guò)不同的角度來(lái)考慮出租車(chē)路徑的推薦，其中最簡(jiǎn)單、常見(jiàn)的方法是基于最短距離或最節(jié)省時(shí)間的路徑規(guī)劃方法。載客核心點(diǎn)的計(jì)算和推薦方面，大多數(shù)的研究沒(méi)有考慮載客核心點(diǎn)與區(qū)域面積、乘客訂單數(shù)量的關(guān)系；載客路徑推薦方面，更多地考慮了不同策略的路徑規(guī)劃算法，針對(duì)空載出租車(chē)駛向載客核心點(diǎn)的過(guò)程中實(shí)現(xiàn)載客概率最大化問(wèn)題研究的相對(duì)較少。本文將從上述2個(gè)方面展開(kāi)研究，綜合考慮相關(guān)因素對(duì)空載出租車(chē)載客路徑推薦方法進(jìn)行改進(jìn)。

本文以小時(shí)為時(shí)間粒度研究出租車(chē)訂單數(shù)據(jù)的分布和遷移。選取任意1小時(shí)的OD數(shù)據(jù)，利用百度Echarts組件提供的heatmap類(lèi)型的數(shù)據(jù)可視化接口，讀取數(shù)據(jù)起點(diǎn)經(jīng)緯度(on_lon、on_lat)繪制熱力圖，如圖1所示。從圖中發(fā)現(xiàn)越靠近城市內(nèi)環(huán)區(qū)域的網(wǎng)約車(chē)訂單越密集，外環(huán)則反之，打車(chē)需求量與地理分布有密切聯(lián)系。針對(duì)城市道路“環(huán)”形區(qū)域劃分、“網(wǎng)”狀道路特點(diǎn)，本文將對(duì)OD數(shù)據(jù)進(jìn)行環(huán)形切分，充分考慮每個(gè)環(huán)形區(qū)域訂單數(shù)量和區(qū)域面積因素合理計(jì)算每個(gè)區(qū)域載客核心點(diǎn)的數(shù)量，使聚類(lèi)結(jié)果更為合理、分布更加均勻，以保證出租車(chē)從任意位置駛向最近的載客核心點(diǎn)的平均空載行駛距離較短。對(duì)OD數(shù)據(jù)進(jìn)行網(wǎng)格化處理，將具有較短路徑且擁有最大乘客數(shù)量的一條路徑推薦給出租車(chē)司機(jī)，實(shí)現(xiàn)出租車(chē)空載駛向載客核心點(diǎn)的途中載客概率最大化，避免行駛途中經(jīng)過(guò)的小區(qū)域乘客被忽視。

圖1 成都市OD數(shù)據(jù)熱力圖

為實(shí)現(xiàn)上述目標(biāo)，下面兩個(gè)問(wèn)題將在后面著重探討：

? 對(duì)于環(huán)形切分后的區(qū)域，如何合理地建立區(qū)域面積、區(qū)域訂單數(shù)量與載客核心點(diǎn)數(shù)量關(guān)系，計(jì)算每個(gè)區(qū)域的聚類(lèi)數(shù)量。

? 如何進(jìn)行網(wǎng)格化并找到空載行駛途中載客概率最大的路徑。

2 系統(tǒng)建模

2.1 基于環(huán)形切分的聚類(lèi)方法

載客核心點(diǎn)是乘客數(shù)量比較密集的區(qū)域中心點(diǎn)，一般位于火車(chē)站、汽車(chē)站、大型商場(chǎng)、公司、學(xué)校、娛樂(lè)場(chǎng)所等附近，出租車(chē)司機(jī)比較容易載到乘客或在非打車(chē)高峰時(shí)段停車(chē)等候乘客。因此，在做出租車(chē)空載路徑推薦之前，需要先利用聚類(lèi)算法找到載客核心點(diǎn)作為出租車(chē)空載尋客的目標(biāo)點(diǎn)。

通過(guò)分析成都市出租車(chē)訂單分布情況可以發(fā)現(xiàn)以下特征：環(huán)中心區(qū)域?qū)儆谑兄行牡囟?，是人們活?dòng)的核心區(qū)域，打車(chē)需求非常大，但隨著環(huán)半徑的增加訂單數(shù)量呈現(xiàn)遞減趨勢(shì)；相同環(huán)內(nèi)，不同區(qū)域的訂單數(shù)量分布比較相似；隨著環(huán)半徑的增加，環(huán)內(nèi)區(qū)域面積不斷擴(kuò)大，交通狀況會(huì)更加通暢，使出租車(chē)相比于市中心的擁堵地段相同時(shí)間內(nèi)行車(chē)距離更大、油耗更少，允許出租車(chē)有更長(zhǎng)的空載尋客里程。基于此，筆者提出環(huán)形切分的聚類(lèi)方法計(jì)算載客核心點(diǎn)。

根據(jù)成都市環(huán)狀地理特點(diǎn)，環(huán)形切分如圖2所示。對(duì)于每個(gè)環(huán)狀區(qū)域，利用歷史訂單數(shù)據(jù)選擇合適的聚類(lèi)算法找出載客核心點(diǎn)。軌跡數(shù)據(jù)挖掘的聚類(lèi)方法包含：劃分法、層次法、基于密度的方法、基于網(wǎng)格的方法、基于模型的方法等。聚類(lèi)算法的選擇不是本文研究的重點(diǎn)，為了高效地處理大量的歷史訂單數(shù)據(jù)，同時(shí)將區(qū)域面積和打車(chē)需求量與聚類(lèi)數(shù)量建立聯(lián)系，本文選用較為高效且可以靈活設(shè)置聚類(lèi)數(shù)量的經(jīng)典劃分聚類(lèi)算法K-means。

圖2 環(huán)形切分示意圖

訂單數(shù)據(jù)的數(shù)量和分布直接影響載客核心點(diǎn)的數(shù)量和分布情況，因此，筆者首先假設(shè)相鄰兩個(gè)環(huán)形區(qū)域之間載客核心點(diǎn)的數(shù)量與其對(duì)應(yīng)區(qū)域內(nèi)的訂單數(shù)量成正比，即：訂單數(shù)量越大的環(huán)形區(qū)域內(nèi)的載客核心點(diǎn)數(shù)量越多。通常，市區(qū)中心區(qū)域訂單數(shù)量十分密集而邊緣區(qū)域的訂單數(shù)據(jù)相對(duì)較少，為了避免城市中心區(qū)域核心點(diǎn)數(shù)量過(guò)多，而外環(huán)區(qū)域的載客核心點(diǎn)數(shù)量過(guò)于稀少，筆者引入?yún)^(qū)域面積作為影響載客核心點(diǎn)數(shù)量的另一個(gè)關(guān)鍵因素，并認(rèn)為相鄰兩個(gè)環(huán)形區(qū)域之間載客核心點(diǎn)的數(shù)量與其對(duì)應(yīng)區(qū)域面積也成正比關(guān)系。根據(jù)上述觀點(diǎn)，為了簡(jiǎn)化模型和計(jì)算，本文將聚類(lèi)數(shù)量、訂單數(shù)據(jù)、區(qū)域面積3者之間的關(guān)系模型設(shè)計(jì)如下(參數(shù)說(shuō)明見(jiàn)表2)：

(1)

為避免較大的資源消耗，城市區(qū)域出租車(chē)平均空載尋客距離通常應(yīng)該在3公里以?xún)?nèi)，市中心地段由于打車(chē)需求量比較大，平均空載尋客距離應(yīng)小于1公里。為了計(jì)算出每個(gè)環(huán)形區(qū)域的聚類(lèi)數(shù)量，首先需要計(jì)算整個(gè)區(qū)域總的載客核心點(diǎn)數(shù)量以及第一個(gè)環(huán)形區(qū)域的載客核心點(diǎn)數(shù)量C1。因此，文中分為2種情況計(jì)算，當(dāng)單獨(dú)考慮市中心區(qū)域，即最內(nèi)環(huán)時(shí)，出租車(chē)平均尋客半徑為1 km，那么在半徑為1 km的圓域內(nèi)至少存在一個(gè)載客核心點(diǎn)，則可由式(2)計(jì)算出C1(計(jì)算結(jié)果向下取整)；當(dāng)考慮整個(gè)城市區(qū)域時(shí)，空載出租車(chē)的平均尋客半徑不超過(guò)3 km，那么在半徑為3 km的圓域內(nèi)至少存在一個(gè)載客核心點(diǎn)，則可由式(3)得到市區(qū)總的載客核心點(diǎn)數(shù)量。

(2)

(3)

2.2 出租車(chē)空載尋客曼哈頓路徑模型

文獻(xiàn)[15]為研究路由算法給出了曼哈頓路徑的定義，本文類(lèi)似地給出出租車(chē)空載尋客曼哈頓路徑的定義如下：

定義1如果兩個(gè)經(jīng)緯度位置點(diǎn)之間的一條路徑，它從起點(diǎn)到終點(diǎn)僅僅使用兩個(gè)方向并且這兩個(gè)方向?yàn)榉窍喾捶较?，那么這條路徑就被稱(chēng)作出租車(chē)空載尋客曼哈頓路徑，文中簡(jiǎn)稱(chēng)曼哈頓路徑。

針對(duì)出租車(chē)路徑推薦的建模方式很多，如：基于最短距離的模型[16]、基于節(jié)省成本的模型[17]、基于出租車(chē)經(jīng)驗(yàn)的模型[18]等。相比這些模型，本文提出的曼哈頓路徑模型側(cè)重于出租車(chē)空載行駛路徑上的載客概率問(wèn)題，通過(guò)曼哈頓路徑算法讓出租車(chē)在相對(duì)較短的空載尋客里程前提下，駛向載客核心點(diǎn)的途中擁有最大的概率搭載到乘客。

城市交通道路錯(cuò)綜復(fù)雜，呈現(xiàn)出如圖3所示的網(wǎng)狀結(jié)構(gòu)，使得我們可以在實(shí)際道路中找到許多與曼哈頓路徑匹配或相似的路徑。因此，在解決空載出租車(chē)路徑推薦時(shí)，通過(guò)網(wǎng)格化方法研究出租車(chē)空載巡游曼哈頓路徑有了現(xiàn)實(shí)意義，尤其是利用網(wǎng)約車(chē)收集的數(shù)據(jù)做路徑推薦時(shí)，由于大部分實(shí)際打車(chē)訂單數(shù)據(jù)的起點(diǎn)位置是在馬路邊上，故依據(jù)訂單起止點(diǎn)數(shù)據(jù)推薦出的曼哈頓路徑與實(shí)際道路有較高的匹配度。

圖3 成都市城市道路圖

首先，通過(guò)2.1節(jié)所述算法計(jì)算出載客核心點(diǎn)作為空載出租車(chē)行駛的目標(biāo)點(diǎn)。然后，利用通過(guò)高斯投影算法[16]將經(jīng)緯度轉(zhuǎn)化為平面直角坐標(biāo)系，并以長(zhǎng)度100 m進(jìn)行網(wǎng)格化處理，根據(jù)對(duì)應(yīng)的歷史數(shù)據(jù)計(jì)算網(wǎng)格內(nèi)的訂單數(shù)量作為當(dāng)前時(shí)刻該區(qū)域打車(chē)需求的預(yù)測(cè)值。最后，將各網(wǎng)格中心點(diǎn)作為行駛路線的中間節(jié)點(diǎn)，在所有曼哈頓路徑中檢索出擁有最大載客概率的行駛路線作為最終的推薦路徑。

(a) 曼哈頓路徑(b) B繞A坐標(biāo)旋轉(zhuǎn)到B*圖4 曼哈頓路徑圖

3 推薦系統(tǒng)實(shí)現(xiàn)

OD數(shù)據(jù)具有較強(qiáng)的時(shí)空屬性，因此在進(jìn)行路徑推薦之前，需要對(duì)時(shí)間和空間兩個(gè)屬性進(jìn)行相關(guān)預(yù)處理工作。針對(duì)空間屬性，主要的預(yù)處理工作是對(duì)環(huán)形劃分半徑Ri進(jìn)行初始化，Ri是環(huán)形模型的重要參數(shù)，在系統(tǒng)建模時(shí)根據(jù)城市地理的環(huán)形半徑進(jìn)行設(shè)定，系統(tǒng)運(yùn)行后將保持不變。針對(duì)時(shí)間屬性，系統(tǒng)選取的時(shí)間粒度為1小時(shí)，即通過(guò)歷史數(shù)據(jù)中相同時(shí)段的數(shù)據(jù)作為當(dāng)前時(shí)段的訂單需求量進(jìn)行計(jì)算。首先，根據(jù)該時(shí)刻對(duì)應(yīng)的訂單數(shù)據(jù)進(jìn)行一次環(huán)形聚類(lèi)，并存儲(chǔ)計(jì)算出的載客核心點(diǎn)數(shù)量及位置分布；其次，對(duì)地圖進(jìn)行網(wǎng)格化處理工作，統(tǒng)計(jì)并存儲(chǔ)該時(shí)刻每個(gè)網(wǎng)格中的訂單數(shù)量。

以上預(yù)處理工作完成以后，當(dāng)出租車(chē)用戶(hù)實(shí)時(shí)請(qǐng)求路徑推薦時(shí)，獲取出租車(chē)當(dāng)前位置的經(jīng)緯度輸入系統(tǒng)，利用如圖5所示路徑推薦算法進(jìn)行計(jì)算。根據(jù)車(chē)輛經(jīng)緯度，首先計(jì)算出具有最短距離的載客核心點(diǎn)作為出租車(chē)空載行駛目標(biāo)點(diǎn)；然后計(jì)算車(chē)輛所在的網(wǎng)格中心點(diǎn)與目標(biāo)點(diǎn)所在網(wǎng)格中心點(diǎn)形成的直線與坐標(biāo)軸的夾角，如果不是45°，則以車(chē)輛所在的網(wǎng)格為中心進(jìn)行旋轉(zhuǎn)；最后，通過(guò)遞歸算法遍歷出租車(chē)與目標(biāo)點(diǎn)之間小區(qū)域內(nèi)的所有的曼哈頓路徑，找到訂單數(shù)據(jù)量最大的路徑推薦給出租車(chē)司機(jī)，以實(shí)現(xiàn)空載出租車(chē)最大概率的載到乘客。

圖5 路徑推薦算法流程圖

如圖6所示，在下午3點(diǎn)半左右的時(shí)候，隨機(jī)選取一個(gè)經(jīng)緯度點(diǎn)模擬出租車(chē)當(dāng)前位置坐標(biāo)，系統(tǒng)自動(dòng)選取歷史數(shù)據(jù)中下午3點(diǎn)到4點(diǎn)之間的訂單數(shù)據(jù)作為當(dāng)前該區(qū)域的打車(chē)需求量進(jìn)行計(jì)算，匹配出距離最近的載客核心點(diǎn)作為該出租車(chē)空載行駛的終點(diǎn)。經(jīng)過(guò)網(wǎng)格化處理后，系統(tǒng)自動(dòng)生成如式(4)所示的矩陣A，i和j表示網(wǎng)格坐標(biāo)，a[i][j]表示網(wǎng)格中訂單的數(shù)量，其中車(chē)輛位置為a[0][0]，核心點(diǎn)位置為a[n-1][n-1]，起點(diǎn)與終點(diǎn)之間的曼哈頓路徑所經(jīng)過(guò)的網(wǎng)格數(shù)為2n-1，本實(shí)例中n=12，由于網(wǎng)格邊長(zhǎng)設(shè)置為100 m，那么起點(diǎn)與終點(diǎn)相距2.3 km左右，通過(guò)組合數(shù)計(jì)算知道，該網(wǎng)格中總共存在705 432條曼哈頓路徑。

圖6 用戶(hù)路徑推薦結(jié)果

(4)

通過(guò)遞歸算法計(jì)算所有曼哈頓路徑及路徑上的訂單總數(shù)量，輸出訂單數(shù)量最多的路徑，可以得到如下3條等價(jià)的最優(yōu)路徑：

O→a1,0→a2,0→a3,0→a4,0→a4,1→a5,1→a5,2→a6,2→a6,3→a6,4→a6,5→a6,6→a6,7→a7,7→a8,7→a8,8→a8,9→a9,9→a10,9→a11,9→a11,10→D

O→a1,0→a2,0→a3,0→a4,0→a4,1→a5,1→a6,1→a6,2→a6,3→a6,4→a6,5→a6,6→a6,7→a7,7→a8,7→a8,8→a8,9→a9,9→a10,9→a11,9→a11,10→D

O→a1,0→a2,0→a3,0→a4,0→a4,1→a4,2→a5,2→a6,2→a6,3→a6,4→a6,5→a6,6→a6,7→a7,7→a8,7→a8,8→a8,9→a9,9→a10,9→a11,9→a11,10→D

系統(tǒng)隨機(jī)選取其中一條作為最終的推薦路徑，通過(guò)APICloud設(shè)計(jì)手機(jī)端系統(tǒng)，Android手機(jī)運(yùn)行后的顯示效果如圖6所示。從圖中可以發(fā)現(xiàn)，由于網(wǎng)格化處理后產(chǎn)生的曼哈頓路徑只有兩個(gè)方向，因此推薦的路徑與地圖中實(shí)際道路存在偏差。實(shí)際上，通過(guò)本算法推薦給空載出租車(chē)司機(jī)的是一條具有最優(yōu)載客行駛方向的路徑。

4 實(shí)驗(yàn)及結(jié)果分析

4.1 環(huán)形區(qū)域聚類(lèi)算法結(jié)果分析

本文以滴滴網(wǎng)約車(chē)訂單數(shù)據(jù)為基礎(chǔ)進(jìn)行試驗(yàn)與分析，通過(guò)Python語(yǔ)言進(jìn)行計(jì)算和繪圖，結(jié)合百度ECharts可視化展示。初始化環(huán)形切分半徑Ri，統(tǒng)計(jì)每個(gè)環(huán)形區(qū)域內(nèi)網(wǎng)約車(chē)訂單數(shù)量，同時(shí)計(jì)算各環(huán)形區(qū)域面積，當(dāng)i=0時(shí)，R0=0，故N0、S0均為0，結(jié)合式(1)-式(3)可以得到本文中基于環(huán)形切分后每個(gè)環(huán)內(nèi)的聚類(lèi)數(shù)量。實(shí)驗(yàn)數(shù)據(jù)計(jì)算結(jié)果如表3所示。

表3 相關(guān)實(shí)驗(yàn)數(shù)據(jù)

在訂單數(shù)據(jù)和聚類(lèi)總數(shù)相同的情況下，利用本文所述算法與直接聚類(lèi)算法進(jìn)行比較，繪制可視化散點(diǎn)圖如圖7所示。其中，小圓點(diǎn)代表訂單，以不同的灰度代表經(jīng)過(guò)環(huán)形切分后的環(huán)形區(qū)域，黑色矩形點(diǎn)代表直接聚類(lèi)算法計(jì)算的核心點(diǎn)位置，黑色三角形點(diǎn)代表經(jīng)過(guò)環(huán)形切分的聚類(lèi)核心點(diǎn)位置。

圖7 環(huán)形切分聚類(lèi)與直接聚類(lèi)對(duì)比

從圖中可以發(fā)現(xiàn)，在總的聚類(lèi)數(shù)量相同的情況下，環(huán)形區(qū)域O1中矩形點(diǎn)數(shù)量和三角形點(diǎn)數(shù)量分別為11和6，而O2中對(duì)應(yīng)的數(shù)量分別為21和9，表明本文提出的基于環(huán)形切分的聚類(lèi)算法與不進(jìn)行任何數(shù)據(jù)處理直接采用K-means聚類(lèi)算法相比，有效阻止了大量載客核心點(diǎn)朝著訂單數(shù)量比較密集的城市中心區(qū)域分布，較大程度地避免了過(guò)多的出租車(chē)向城市中心地段聚集，而城市邊緣區(qū)域出租車(chē)數(shù)量嚴(yán)重不足的現(xiàn)象。同時(shí)可以看到三角形點(diǎn)的分布較矩形點(diǎn)更為均勻，這將有效避免出租車(chē)空載巡游距離過(guò)長(zhǎng)的現(xiàn)象。

4.2 路徑推薦算法結(jié)果分析

基于網(wǎng)格化的曼哈頓路徑算法，核心思想是保證最短網(wǎng)格距離的前提下尋找一條載客概率最大的路徑推薦給出租車(chē)司機(jī)。因此實(shí)驗(yàn)中，用載客概率作為衡量指標(biāo)，將文中所述推薦算法與經(jīng)典的基于最短距離的路徑規(guī)劃算法進(jìn)行比較分析。

載客概率定義為一條路徑所經(jīng)過(guò)的網(wǎng)格內(nèi)的訂單數(shù)量之和與該路徑起止點(diǎn)之間矩形區(qū)域訂單總數(shù)之比作為該路徑的載客概率，∑r[p][k]表示一條路徑所經(jīng)過(guò)的網(wǎng)格的訂單數(shù)量，則一條路徑上的載客概率P表示如下：

(5)

試驗(yàn)中，隨機(jī)選取一點(diǎn)作為出租車(chē)當(dāng)前位置，系統(tǒng)自動(dòng)匹配對(duì)應(yīng)的載客核心點(diǎn)作為出租車(chē)空載尋客的目標(biāo)點(diǎn)。利用基于最短距離的路徑規(guī)劃算法和本文所述算法的路徑經(jīng)緯度序列經(jīng)過(guò)高斯坐標(biāo)變換后繪制曲線如圖8所示。圖8(a)中是比較特殊的情況，最短路徑和推薦的曼哈頓路徑的載客概率均為40.1%，兩條曲線的特征匹配性很高，由于文中算法推薦的路徑與實(shí)際地圖存在偏差，故此時(shí)兩條曲線在實(shí)際地圖上為同一條路徑。圖8(b)中是更一般的情況，即兩條路徑完全不相同時(shí)，最短路徑的載客概率為40.9%，推薦的曼哈頓路徑的載客概率為53.0%，此時(shí)文中算法推薦的路徑相比于最短距離路徑載客概率提高了12.1%。

(a)

(b)圖8 路徑推薦結(jié)果對(duì)比

通過(guò)實(shí)驗(yàn)可知，在保證相同網(wǎng)格距離的情況下，即排除實(shí)際路徑規(guī)劃可能存在的繞遠(yuǎn)距離時(shí)，文中提出的算法載客概率不低于經(jīng)典的基于最短距離的路徑規(guī)劃算法。實(shí)際上，文中提出的算法在一個(gè)網(wǎng)格區(qū)域內(nèi)找到最大載客概率的路徑推薦給出租車(chē)司機(jī)，是以犧牲一定的空間效率來(lái)達(dá)到提升空載出租車(chē)載客概率的目的，但從空載出租車(chē)用戶(hù)體驗(yàn)和應(yīng)用效果考慮是值得的。

5 結(jié) 語(yǔ)

根據(jù)網(wǎng)約車(chē)訂單數(shù)據(jù)在環(huán)形城市區(qū)域中呈現(xiàn)出環(huán)內(nèi)相似、環(huán)間不同的數(shù)據(jù)分布特點(diǎn)，采用環(huán)形劃分，建立載客核心點(diǎn)數(shù)量與區(qū)域面積、訂單數(shù)量的關(guān)系模型，合理計(jì)算出各個(gè)環(huán)內(nèi)的聚類(lèi)數(shù)量，使得載客核心點(diǎn)分布相對(duì)均勻，不僅保證在核心點(diǎn)區(qū)域有較大數(shù)量的打車(chē)人數(shù)，也有效減少了出租車(chē)到載客核心點(diǎn)的平均空載距離。提出了網(wǎng)格化的出租車(chē)空載尋客曼哈頓路徑模型，通過(guò)坐標(biāo)變換使出租車(chē)與載客核心點(diǎn)之間始終具有飽和數(shù)量的候選曼哈頓路徑，基于遞歸遍歷算法找出載客概率最大的一條曼哈頓路徑推薦給空載的出租車(chē)用戶(hù)。實(shí)驗(yàn)表明，相同條件下，通過(guò)文中提出的算法推薦的路徑載客概率不低于經(jīng)典的基于最短距離的路徑規(guī)劃算法獲得的路徑。本文提出的方法為出租車(chē)空載尋客路徑推薦系統(tǒng)的研究提供了思路。

本文仍需要進(jìn)一步深入研究。首先，在數(shù)據(jù)的時(shí)間屬性方面，目前采用訂單數(shù)據(jù)的時(shí)間粒度為1小時(shí)，需要在未來(lái)工作中進(jìn)一步分析時(shí)間粒度對(duì)路徑推薦效果的影響。再者，目前系統(tǒng)實(shí)現(xiàn)的是基于網(wǎng)格化處理后推薦的一條具有最優(yōu)載客行駛方向的路徑，因此推薦的結(jié)果與真實(shí)地圖路徑存在偏差，未來(lái)將采用相關(guān)機(jī)器學(xué)習(xí)方法將經(jīng)緯度序列與實(shí)際路徑進(jìn)行匹配。最后，由于文中使用的數(shù)據(jù)集是成都市網(wǎng)約車(chē)數(shù)據(jù)，該城市網(wǎng)約車(chē)OD數(shù)據(jù)具有典型的環(huán)形分布特點(diǎn)，故文中只針對(duì)具有環(huán)形分布的情況展開(kāi)研究，后期若獲取到比較合適的其他省的數(shù)據(jù)，也會(huì)對(duì)非環(huán)形分布特點(diǎn)的城市進(jìn)行建模分析。