李思佳，蘇凡軍

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

0 引 言

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

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

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

1 準(zhǔn)備工作

1.1 路網(wǎng)定義

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

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

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

圖1表示路段網(wǎng)絡(luò)。在此圖中，每個(gè)節(jié)點(diǎn)代表一個(gè)道路段。請注意，每個(gè)邊只有一個(gè)方向。這是因?yàn)閷?shí)際不允許出租車司機(jī)在相同的單一路段來回行駛，這在現(xiàn)實(shí)生活中不推薦，并且很有可能導(dǎo)致交通堵塞和事故。然而，出租車司機(jī)可以繞過三個(gè)路段形成循環(huán)，例如節(jié)點(diǎn)r4，r5和r6，駕駛員可以通過此路線形成循環(huán)。

圖1 路段網(wǎng)絡(luò)的示例

1.2 利潤計(jì)算

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

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

(1)

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

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

(2)

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

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

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

(3)

(4)

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

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

(5)

從段r中的第i個(gè)歷史拾取事件中還可以獲得式(2)中的In(i,r)。此外，道路長度L(r)和實(shí)時(shí)行駛時(shí)間T(r)可以從歷史數(shù)據(jù)中估算。因此，凈利潤m(r)可以通過式(3)計(jì)算。每個(gè)路段r的T(r)、m(r)和P(r)的值預(yù)先存儲在相應(yīng)的路段網(wǎng)絡(luò)(圖1)節(jié)點(diǎn)中。

凈利潤的平均增長率定義為τ，表示在路線中增加一個(gè)路段時(shí)的利潤增加?？梢酝ㄟ^式(6)計(jì)算。

(6)

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

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

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

圖2 路線推薦生成過程

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

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

(7)

2 PTRA推薦算法設(shè)計(jì)

2.1 算法框架

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

該文構(gòu)建了一個(gè)基于收益目標(biāo)的空載出租車推薦算法。圖3為提出的PTRA算法框架。PTRA框架分為兩個(gè)階段：離線挖掘階段和在線推薦階段。該框架特點(diǎn)如下：

圖3 PTRA推薦算法框架

(1)提出的算法分為離線挖掘階段和在線推薦階段兩個(gè)階段。在離線挖掘階段，基于出租車歷史軌跡數(shù)據(jù)集，通過所定義的凈利潤公式計(jì)算每個(gè)路段的相關(guān)信息，并且用DBCSCAN聚類方法發(fā)現(xiàn)具有高利潤的路段的區(qū)域，這些高利潤區(qū)域的信息存儲在路段網(wǎng)絡(luò)中。在在線推薦階段，當(dāng)上一個(gè)乘客下車后，出租車司機(jī)提出推薦請求，出租車的位置是查詢節(jié)點(diǎn)，系統(tǒng)自動獲取出租車當(dāng)前位置和當(dāng)前所處時(shí)間段，根據(jù)當(dāng)前位置推薦潛在高收益路段的區(qū)域，

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

2.2 算法功能實(shí)現(xiàn)

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

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

r2,n-1)

(8)

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

目前有許多針對軌跡數(shù)據(jù)挖掘的聚類方法，如基于環(huán)狀的聚類、基于模型的聚類、基于網(wǎng)格的聚類、基于密度的聚類等[13]，而類似于K-means這種以距離為標(biāo)準(zhǔn)的聚類并不適用于尋找載客密度大的區(qū)域。為了尋找高利潤路段的區(qū)域，該文選用較為高效且可以靈活設(shè)置聚類數(shù)量的經(jīng)典劃分聚類算法DBSCAN[14]，其中最小包含點(diǎn)數(shù)(MinPts)和掃描半徑(Eps)分別設(shè)置為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為未標(biāo)記狀態(tài)

2.For roadList中每一個(gè)載客路段 road

3. If road為標(biāo)記狀態(tài)

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

5. Else

6.設(shè)置road為標(biāo)記狀態(tài)

7.令N為road的Eps半徑內(nèi)的所有載客路段集合

8. IfN中的載客路段小于MinPts個(gè)數(shù)

9.標(biāo)記road為噪聲

10. Else

11.創(chuàng)建高收益路段Highroad

12.添加road到Highroad中

13. ForN中每個(gè)載客路段road

14. If road處于非標(biāo)記狀態(tài)

15.標(biāo)記unRoad

16.篩選unRoad在Eps鄰域內(nèi)的載客路段集合newRoad

17. If newRoad內(nèi)的載客路段數(shù)量小不少于MinPts

18.將newRoad加入到N中

19. If unRoad不屬于任何路段

20.將unRoad加入到Highroad中

Output: Clustering result

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)采集的數(shù)據(jù)集來源于滴滴出行“蓋亞”數(shù)據(jù)開放計(jì)劃[15]，數(shù)據(jù)集包含海口市2017年10月份的滴滴網(wǎng)約車2 664 253條訂單數(shù)據(jù)，由訂單ID、起點(diǎn)、終點(diǎn)等信息組成，計(jì)算與每個(gè)路段相關(guān)的歷史載客概率和凈利潤。對于每條道路，記錄中間點(diǎn)的幾個(gè)坐標(biāo)，并且還存在一些噪聲點(diǎn)。在去除噪聲點(diǎn)后，該文選擇了2 149條具有高拾取概率的道路進(jìn)行實(shí)驗(yàn)。然后，使用這些路段中的起點(diǎn)和終點(diǎn)來構(gòu)建道路緩沖區(qū)。訂單信息如表1所示。

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

續(xù)表1

通過將道路網(wǎng)數(shù)據(jù)集的提取坐標(biāo)與出租車數(shù)據(jù)集相匹配，可以獲得86 588個(gè)有效的載客信息，這些活動可以位于路段中，因此這兩個(gè)數(shù)據(jù)組合在一起，每個(gè)拾取點(diǎn)映射到構(gòu)建的道路緩沖區(qū)。為了實(shí)現(xiàn)所提出的算法，還需要計(jì)算這些路段中每個(gè)路段的拾取概率和凈利潤。這已經(jīng)在第1節(jié)中介紹過了。

3.2 實(shí)驗(yàn)分析

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

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

圖4 不同時(shí)間間隔的利潤收益

(2)凈利潤的比較。

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

(9)

(10)

對于給定位置，該文提出的算法可以推薦具有高效益的區(qū)域路段，并特別適用于沒有經(jīng)驗(yàn)的出租車司機(jī)，因?yàn)樗麄內(nèi)狈Ρ镜芈肪€圖的意識和可以獲利路線的駕駛知識。為了驗(yàn)證所提算法的有效性，根據(jù)10月份所有司機(jī)的平均凈利潤將所有出租車司機(jī)分為兩類。數(shù)據(jù)集中排名前10%的出租車司機(jī)被視為“經(jīng)驗(yàn)豐富”的出租車司機(jī)，而其他則為“缺乏經(jīng)驗(yàn)”出租車司機(jī)。因此，經(jīng)驗(yàn)豐富的司機(jī)的駕駛路線被用作訓(xùn)練組。對于沒有經(jīng)驗(yàn)的駕駛員的推薦駕駛路線的統(tǒng)計(jì)實(shí)驗(yàn)結(jié)果如表2所示，PTRA推薦結(jié)果優(yōu)于缺乏經(jīng)驗(yàn)的駕駛員的實(shí)際利潤。

表2 凈利潤結(jié)果比較

首先繪制每小時(shí)路線凈利潤的分布圖，即特定利潤值的事件數(shù)量，如圖5所示，基于直方圖的統(tǒng)計(jì)表示，推薦的路線的單位間凈利潤與沒有經(jīng)驗(yàn)的出租車司機(jī)進(jìn)行比較。柱狀圖的白色條顯示了推薦結(jié)果的凈利潤，陰影條顯示了沒有經(jīng)驗(yàn)的出租車司機(jī)的利潤。從圖中可以看出，推薦的路線主要定位于較大的值。這表明此推薦機(jī)制為缺乏經(jīng)驗(yàn)的司機(jī)提供比實(shí)際利潤更高的路線?？偠灾?，該算法可以幫助沒有經(jīng)驗(yàn)的出租車司機(jī)找到更好的路線，從而最大限度地提高他們的潛在利潤。

圖5 凈利潤統(tǒng)計(jì)

4 結(jié)束語

為了提高司機(jī)收益和減少出租車空載巡游的時(shí)間，該文以收益利潤為目標(biāo)提出了一個(gè)空載出租車推薦算法PTRA。該算法根據(jù)出租車當(dāng)前位置結(jié)合當(dāng)前路段反饋的實(shí)際路況為出租車司機(jī)提供高收益路線，可對熱門區(qū)域路線進(jìn)行多次推薦。實(shí)驗(yàn)結(jié)果表明，該算法能幫助沒有經(jīng)驗(yàn)的司機(jī)找到具有高收益路段的區(qū)域。