高 瞻 余 辰 向鄭濤 陳宇峰*

1(湖北汽車工業(yè)學院電氣與信息工程學院 湖北 十堰 442002)2(華中科技大學計算機科學與技術學院 湖北 武漢 430074)

0 引 言

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

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

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

1 問題分析

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

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

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

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

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

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

為實現(xiàn)上述目標，下面兩個問題將在后面著重探討：

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

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

2 系統(tǒng)建模

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

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

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

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

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

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

(1)

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

(2)

(3)

2.2 出租車空載尋客曼哈頓路徑模型

文獻[15]為研究路由算法給出了曼哈頓路徑的定義，本文類似地給出出租車空載尋客曼哈頓路徑的定義如下：

定義1如果兩個經(jīng)緯度位置點之間的一條路徑，它從起點到終點僅僅使用兩個方向并且這兩個方向為非相反方向，那么這條路徑就被稱作出租車空載尋客曼哈頓路徑，文中簡稱曼哈頓路徑。

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

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

圖3 成都市城市道路圖

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

(a) 曼哈頓路徑(b) B繞A坐標旋轉到B*圖4 曼哈頓路徑圖

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

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

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

圖5 路徑推薦算法流程圖

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

圖6 用戶路徑推薦結果

(4)

通過遞歸算法計算所有曼哈頓路徑及路徑上的訂單總數(shù)量，輸出訂單數(shù)量最多的路徑，可以得到如下3條等價的最優(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)隨機選取其中一條作為最終的推薦路徑，通過APICloud設計手機端系統(tǒng)，Android手機運行后的顯示效果如圖6所示。從圖中可以發(fā)現(xiàn)，由于網(wǎng)格化處理后產(chǎn)生的曼哈頓路徑只有兩個方向，因此推薦的路徑與地圖中實際道路存在偏差。實際上，通過本算法推薦給空載出租車司機的是一條具有最優(yōu)載客行駛方向的路徑。

4 實驗及結果分析

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

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

表3 相關實驗數(shù)據(jù)

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

圖7 環(huán)形切分聚類與直接聚類對比

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

4.2 路徑推薦算法結果分析

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

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

(5)

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

(a)

(b)圖8 路徑推薦結果對比

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

5 結 語

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

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