PTRA：一個面向空載出租車的路線推薦算法

李思佳，蘇凡軍

(上海理工大學 光電信息與計算機工程學院，上海 200093)

0 引 言

出租車服務為人們的日常生活提供了巨大的便利，同時，現代化城市的發展也給出租車行業帶來了巨大的變化。然而，一些大城市如紐約地區，乘客在繁忙時段等待出租車接載的有效平均等待時間超過13分鐘[1]，很多出租車常處于空載狀態。因此，在乘客下車后如何使這些出租車司機以合理的方式接載新的乘客，并且為這些出租車司機提供有效的路線推薦就顯得十分有意義。

目前有很多研究通過向出租車推薦潛在載客點和最優行駛路線來緩和上述矛盾，第一種是熱點推薦，熱點是一個很可能接到客戶的區域[2-5]；第二種是熱線推薦，即專注于最快駕駛路線[6-10]的研究，熱線推薦是從當前位置到目的地的最快駕駛路線；還有一種是在出租車司機和乘客的需求之間取得平衡[11-12]。但是多數的研究采用路線最短或是載客概率最大的標準對出租車司機進行推薦，忽略了實時交通對推薦結果的影響，對熱門區域的路線進行重復推薦，解決出租車空載率高、利潤率低的問題。

針對以上關于傳統出租車司機路線推薦研究的不足，該文提出了一個以收益最大化為目標的空載出租車推薦算法PTRA(profit-based taxi recommendation algorithm)。PTRA基于利潤最大化來推薦路線，司機通過遵循路線建議找到具有最大潛在利潤的路線并接到乘客，這一點使得提出的推薦算法比其他現有的路線推薦算法更實用。

1 準備工作

1.1 路網定義

定義1(路段)：路段ri為任意兩個相鄰路口p,q之間的路段，表示為ri(p,q)。對于任意路段ri，與起點r.start和終點r.end相關聯。此外，與路段ri相鄰的段形成一個集r.next[]，如果r.end=ri.start，它滿足?ri.next[]。

定義2(路線)：路徑R是一系列連接的路段，即R=ri→ri+1→…→rn，其中rk+1.start=rk.end(1≤k

定義3(路網)：路網G可以由圖G=表示，其中V={ri}是由所有路段組成的節點集，有向邊集E是實際道路的映射。

圖1表示路段網絡。在此圖中，每個節點代表一個道路段。請注意，每個邊只有一個方向。這是因為實際不允許出租車司機在相同的單一路段來回行駛，這在現實生活中不推薦，并且很有可能導致交通堵塞和事故。然而，出租車司機可以繞過三個路段形成循環，例如節點r4，r5和r6，駕駛員可以通過此路線形成循環。

圖1 路段網絡的示例

1.2 利潤計算

對于任意一個路段r，凈利潤m(r)由兩個部分組成，即潛在成本c(r)和潛在收益b(r)。

潛在成本c(r)的計算如式(1)：

(1)

其中，P(r)是接收乘客的收益段r中的能力，L(r)是段r的長度，Oil是每單位距離(如：每公里)的油價，T(r)是通過段r的行進時間，且T(r)對實時交通狀況很敏感，OppCost是每單位時間(如：每分鐘)的機會成本，CarDam(L(r),T(r))是時間路程內對車輛的損耗。由實際可知，交通堵塞將帶來T(r)的增加，從而導致T(r)·OppCost和CarDam(L(r),T(r))增大。

潛在成本b(r)的計算如式(2)：

(2)

其中，Cr是在給定時間段內段r中的接載乘客數量，In(i,r)是接載第i個乘客的收入。

路段r的凈利潤m(r)，通過式(3)計算。

m(r)=b(r)-c(r)

(3)

(4)

基于以上所述，進一步定義每條路線R的凈利潤。路線R的凈利潤是R中包含的路段凈利潤m(ri)的總和，通過不接載先前路段中的任何乘客(即r1至ri-1)的可能性加權。

從r1開始給出路線R=r1→r2→…→rn，路線的凈利潤可以通過式(5)計算。

(5)

從段r中的第i個歷史拾取事件中還可以獲得式(2)中的In(i,r)。此外，道路長度L(r)和實時行駛時間T(r)可以從歷史數據中估算。因此，凈利潤m(r)可以通過式(3)計算。每個路段r的T(r)、m(r)和P(r)的值預先存儲在相應的路段網絡(圖1)節點中。

凈利潤的平均增長率定義為τ，表示在路線中增加一個路段時的利潤增加。可以通過式(6)計算。

(6)

由實際可知，在n>5之后，凈利潤的平均增長率非常低。因此，該文設n=5。

定義4(路線最大凈利潤)。

圖2表示高利潤路段區域的生成過程。

圖2 路線推薦生成過程

如圖2所示，給定出租車司機的當前位置Loctaxi∈r，固定巡航長度n和一組候選路線，其中R滿足從r開始，且?R∈。路線R*∈，則路線的最大凈利潤為：

R*=Hmax{M(R,r,n)}

(7)

2 PTRA推薦算法設計

2.1 算法框架

由于道路永遠不是靜態的，考慮實際生活中可能會出現一些特殊情況，如天氣原因，或者一些大型賽事(如演唱會、體育賽事等)，乘客對出租車數量的需求會在某段時間內某個區域范圍內增長，因此基礎的建議模型必須始終保持最新，以適應以上特殊情況。

該文構建了一個基于收益目標的空載出租車推薦算法。圖3為提出的PTRA算法框架。PTRA框架分為兩個階段：離線挖掘階段和在線推薦階段。該框架特點如下：

圖3 PTRA推薦算法框架

(1)提出的算法分為離線挖掘階段和在線推薦階段兩個階段。在離線挖掘階段，基于出租車歷史軌跡數據集，通過所定義的凈利潤公式計算每個路段的相關信息，并且用DBCSCAN聚類方法發現具有高利潤的路段的區域，這些高利潤區域的信息存儲在路段網絡中。在在線推薦階段，當上一個乘客下車后，出租車司機提出推薦請求，出租車的位置是查詢節點，系統自動獲取出租車當前位置和當前所處時間段，根據當前位置推薦潛在高收益路段的區域，

(2)路線推薦區別于其他推薦系統的一個很大不同是，像音樂、電影或是商品的推薦皆可被重復推薦給不同的用戶，而路線推薦在給出租車司機推薦時需要考慮重復推薦帶來的影響，該文結合出租車在實際接載情況反饋當前區域的需求情況，不斷更新潛在高收益路段的區域，對熱門區域的路段可進行重復推薦，即推薦給該區域的不同司機。

2.2 算法功能實現

通過觀察式(5)，得出凈利潤公式的特殊形式：

M(R,r1,n)=m(r1)+(1-P(r1))M(R-r1,

r2,n-1)

(8)

其中，R=r1→r2→…→rn。實際上，凈利潤的特殊形式可以通過遞歸算法來實現。為此，對于路段r1，可以將從r1開始的所有路線候選表示為遞歸樹結構。路段ri的遞歸樹Yri，其中每個節點代表路段并且根節點是ri。此外，對于遞歸樹中的每個節點ri，它具有子節點集ri.next[]。對于給定r的遞歸樹，通過遞歸n-1次來獲得長度為n的路線。

目前有許多針對軌跡數據挖掘的聚類方法，如基于環狀的聚類、基于模型的聚類、基于網格的聚類、基于密度的聚類等[13]，而類似于K-means這種以距離為標準的聚類并不適用于尋找載客密度大的區域。為了尋找高利潤路段的區域，該文選用較為高效且可以靈活設置聚類數量的經典劃分聚類算法DBSCAN[14]，其中最小包含點數(MinPts)和掃描半徑(Eps)分別設置為3 000和60。

以下為DBSCAN算法偽代碼:

算法：High profit road algorithm on DBSCAN

Input：A list of pick-up locations road roadList={r1,r2,…,rn},Eps,MinPts

1.初始化roadList中所有road為未標記狀態

2.For roadList中每一個載客路段 road

3. If road為標記狀態

4.返回步驟2尋找下一個載客路段

5. Else

6.設置road為標記狀態

7.令N為road的Eps半徑內的所有載客路段集合

8. IfN中的載客路段小于MinPts個數

9.標記road為噪聲

10. Else

11.創建高收益路段Highroad

12.添加road到Highroad中

13. ForN中每個載客路段road

14. If road處于非標記狀態

15.標記unRoad

16.篩選unRoad在Eps鄰域內的載客路段集合newRoad

17. If newRoad內的載客路段數量小不少于MinPts

18.將newRoad加入到N中

19. If unRoad不屬于任何路段

20.將unRoad加入到Highroad中

Output: Clustering result

3 實驗分析

3.1 實驗數據

實驗采集的數據集來源于滴滴出行“蓋亞”數據開放計劃[15]，數據集包含?？谑?017年10月份的滴滴網約車2 664 253條訂單數據，由訂單ID、起點、終點等信息組成，計算與每個路段相關的歷史載客概率和凈利潤。對于每條道路，記錄中間點的幾個坐標，并且還存在一些噪聲點。在去除噪聲點后，該文選擇了2 149條具有高拾取概率的道路進行實驗。然后，使用這些路段中的起點和終點來構建道路緩沖區。訂單信息如表1所示。

表1 網約車訂單信息

續表1

通過將道路網數據集的提取坐標與出租車數據集相匹配，可以獲得86 588個有效的載客信息，這些活動可以位于路段中，因此這兩個數據組合在一起，每個拾取點映射到構建的道路緩沖區。為了實現所提出的算法，還需要計算這些路段中每個路段的拾取概率和凈利潤。這已經在第1節中介紹過了。

3.2 實驗分析

(1)參數Δt對PTRA的影響。

考慮不同時段對Δt的設置，該文將一天分為6個時間段(00:00-04:00,04:00-08:00,08:00-12:00,12:00-16:00,16:00-20:00,20:00-24:00)，設置不同的Δt，驗證它們(2 min,5 min,8 min,11 min)在不同時間段的表現力。實驗結果如圖4所示，5 min的間隔在08:00-12:00，16:00-20:00的效益表現力更好，考慮到系統計算成本和推薦效果，將這兩個時間段的Δt設置為5 min，而其他數段則將Δt設置為11 min。

圖4 不同時間間隔的利潤收益

(2)凈利潤的比較。

對于任意一個司機，定義司機開始位置為Loc0，空載巡游時間為Δt，司機在位置Loc1處成功接到乘客，行駛Δt'時間，并在Loc2處將乘客放下。讓ri,j表示位置Loci和Locj之間的路段，事件E可被表示為(r01-r12,Δt'-Δt)。將這樣連續的“巡游→載客→放下”一系列過程定義為事件Event，事件Event可被表示為(r01-r12,Δt'-Δt)。該文提出的算法從最接近Loc0的Loc'處開始，并返回一系列推薦的潛在載客點和路段。推薦駕駛路線的性能通過單位時間的平均凈利潤pd來衡量，將其與經驗不足的出租車司機的單位時間平均凈利潤進行比較，事件Event單位時間平均凈利潤pE和單位時間的平均凈利潤pd通過計算可得：

(9)

(10)

對于給定位置，該文提出的算法可以推薦具有高效益的區域路段，并特別適用于沒有經驗的出租車司機，因為他們缺乏本地路線圖的意識和可以獲利路線的駕駛知識。為了驗證所提算法的有效性，根據10月份所有司機的平均凈利潤將所有出租車司機分為兩類。數據集中排名前10%的出租車司機被視為“經驗豐富”的出租車司機，而其他則為“缺乏經驗”出租車司機。因此，經驗豐富的司機的駕駛路線被用作訓練組。對于沒有經驗的駕駛員的推薦駕駛路線的統計實驗結果如表2所示，PTRA推薦結果優于缺乏經驗的駕駛員的實際利潤。

表2 凈利潤結果比較

首先繪制每小時路線凈利潤的分布圖，即特定利潤值的事件數量，如圖5所示，基于直方圖的統計表示，推薦的路線的單位間凈利潤與沒有經驗的出租車司機進行比較。柱狀圖的白色條顯示了推薦結果的凈利潤，陰影條顯示了沒有經驗的出租車司機的利潤。從圖中可以看出，推薦的路線主要定位于較大的值。這表明此推薦機制為缺乏經驗的司機提供比實際利潤更高的路線?？偠灾撍惴梢詭椭鷽]有經驗的出租車司機找到更好的路線，從而最大限度地提高他們的潛在利潤。

圖5 凈利潤統計

4 結束語

為了提高司機收益和減少出租車空載巡游的時間，該文以收益利潤為目標提出了一個空載出租車推薦算法PTRA。該算法根據出租車當前位置結合當前路段反饋的實際路況為出租車司機提供高收益路線，可對熱門區域路線進行多次推薦。實驗結果表明，該算法能幫助沒有經驗的司機找到具有高收益路段的區域。