基于網格化的出租車空載尋客路徑推薦

高 瞻 余 辰 向鄭濤 陳宇峰*

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

0 引 言

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

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

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

1 問題分析

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

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

表1 網約車訂單信息表

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

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

圖1 成都市OD數據熱力圖

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

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

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

2 系統建模

2.1 基于環形切分的聚類方法

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

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

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

圖2 環形切分示意圖

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

(1)

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

(2)

(3)

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

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

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

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

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

圖3 成都市城市道路圖

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

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

3 推薦系統實現

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

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

圖5 路徑推薦算法流程圖

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

圖6 用戶路徑推薦結果

(4)

通過遞歸算法計算所有曼哈頓路徑及路徑上的訂單總數量，輸出訂單數量最多的路徑，可以得到如下3條等價的最優路徑：

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

系統隨機選取其中一條作為最終的推薦路徑，通過APICloud設計手機端系統，Android手機運行后的顯示效果如圖6所示。從圖中可以發現，由于網格化處理后產生的曼哈頓路徑只有兩個方向，因此推薦的路徑與地圖中實際道路存在偏差。實際上，通過本算法推薦給空載出租車司機的是一條具有最優載客行駛方向的路徑。

4 實驗及結果分析

4.1 環形區域聚類算法結果分析

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

表3 相關實驗數據

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

圖7 環形切分聚類與直接聚類對比

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

4.2 路徑推薦算法結果分析

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

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

(5)

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

(a)

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

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

5 結 語

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

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