基于Markov的出租車載客點推薦

宋芝明 袁健

摘 ?要： 針對出租車尋客時間過長，尋客失敗問題，提出一種基于Markov的載客點推薦模型。首先，采用Markov算法結合各參數構建評估函數;然后，通過對行車時間和距離參數的計算，為出租車提供具有時間和距離約束的載客點序列，從而確保出租車以最大概率找到乘客，縮短空載時間。實驗結果表明，該模型在出租車尋客率上有了較高的提升。

關鍵詞： Markov算法;出租車載客率;尋客等待時間;行車距離閾值;等待時間閾值;評價函數

中圖分類號： TP301.6 ? ?文獻標識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.06.032

本文著錄格式：宋芝明，袁健. 基于Markov的出租車載客點推薦[J]. 軟件，2019，40（6）：140143+172

【Abstract】： To solve the problem of passenger-finding time is too long and the strategy of passenger is unsuccessful， a recommendation model of taxi passenger-finding Locations based on Markov was proposed. Firstly， the Markov algorithm is used to combine the parameters to construct the evaluation function. Then， provide a sequence of passenger-finding locations with constraints between time and distance for taxi by calculating the travel time and distance parameters， to ensure that the taxi finds the passengers with the higher probability and short waiting time. The experimental results show that the model has a higher improvement on passenger-finding rate.

【Key words】： Markov algorithm; Passenger-finding rate; Passenger-finding time; Driving distance threshold; Waiting time threshold; Evaluation function

0 ?引言

人出租車在城市公共交通中發揮著重要作用。隨著社會的發展，城市人口的增長，交通壓力越來越嚴重，出租車空載，乘客打車難的問題屢見不鮮。如何為出租車提供載客點推薦，提高出租車的運營效率是城市交通問題的一項亟待解決的重要課題。目前在許多城市，出租車已經配備了GPS設備來記錄出租車的行為，如地點，時間，狀態和行車軌跡等信息。因此，近年來基于出租車交通數據進行了越來越多的研究。 例如 城市計算[1]，路線規劃[2]，異常駕駛檢測[3]等。文獻[11]和[14]分別對當前軌跡數據的常用數據處理方法以及出租車推薦系統基本框架進行了闡述。文獻[4]和[9，13]通過改進行車路線優化出租車運行效率。文獻[10]通過分析乘客的行為模式劃分功能區，進而構建時間-地點-位置關

系圖，為出租車提供載客點推薦，在出租車尋客推薦上已有取得較多的研究成果（諸如文獻[5，7，8， 12，15]），此類文獻均是通過各種方法為出租車提供載客點推薦。然而，目前的研究只是為當前出租車提供一個載客地點，沒有考慮到出租車在該載客點尋客失敗的情況。針對這一不足，本文提出了一種基于Markov的出租車載客點推薦模型，研究內容主要是通過評估函數出租車臨近載客點以及后續載客點進行評估，來獲得最佳載客點序列，確保出租車以最短時間找到乘客。

1 ?Markov決策過程

出租車尋客的載客點選擇過程可以被認為是隨機決策過程，它可以進一步通過Markov決策過程來描述。該過程包括能夠轉換狀態的一系列狀態和工作。Markov決策過程（Markov Decision Process 簡稱MDP）必須遵循Markov屬性，即下一個狀態僅與當前狀態和所采取的的動作相關，并且與先前的狀態和動作無關。每個動作都有一個返回值。對于每個狀態，下一步需要是最佳的，以便能夠在有限的步驟中最大化總收益。

MDP由三元組組成：M=（S， A， R）， 分別表示：狀態集，動作集和返回值集。若M序列為{（s0， a0， r0），（s1， a1， r1），（s2， a2， r2）…}，假設初始代理狀態為sstart =s0 ，那么a0就會被選中。執行該操作后代理狀態就會由s0轉為s1并獲得一個返回值r0（s0， a0）。然后狀態s1再次執行動作a1，代理轉移狀態到s2并獲得返回值r1（s1， a1）。依次類推，直到終止條件達成，狀態變為send。

2 ?參數屬性設置

我們首先介紹了算法中參數的解決方案和閾值參數的設置，然后描述了我們的方法的實現并分析時間和空間的復雜性。

2.1 ?算法參數解決方案

從第二節，我們可以看出，解決評估函數的關鍵是直到每個載客點的返回值，即載客點的出租車空載率。同時，我們還需要給出乘客在初始載客點和后續載客點的等待時間，因為不可能讓出租車總是等候，我們應該給出參考時間。

A.出租車空載率解決方案

出租車的空載率可以理解為單位時間內，在該地區范圍內空載出租車數量變化與出租車總數量的變化。每個時間段空載率是不同的。例如，8.am～9.am 與3.pm～4.pm之間空載率是不同的，因為早上8點處于上班高峰期。因此，出租車空載率可以定義為 ，是同時間段內r載客點的空載出租車數量。|t|是時間段的長度，在本文算法中是60分鐘。

B.尋客等待時間

出租車到達和離開，乘客上下車，這些事件與非均勻泊松分布過程（NHPP）一致。

我們定義了NHPP的參數。因此，事件數量的NHPP分布規律如（4）所示。Noccur（t）表示在t期間乘客數目。

2.2 ?閾值參數

讓出租車總是不停地改變他們的尋客位置是不切實際的，出租車實際上希望不要走得太遠并且可以在附近找到乘客，因此對于行車距離應該設定一個閾值。同樣出租車也希望在最短時間內找到乘客，所以尋客等待時間也應該有一個閾值。當出租車尋客超過距離閾值或者等待時間閾值時，尋客操作應該中止，前往下一載客點。

2.2.1 ?行駛距離閾值設置

如果行駛距離閾值設置太小，乘客到鄰近載客點的長度可能大于閾值，所以他可能只推薦0個或一個載客點。如果設置的太大，則會推薦相鄰的多個載客點，可能導致行駛距離過長。因此，我們對所有載客點其對應臨近載客點距離進行統計，得出超過93%的載客點間距離小于4 km，然后取兩點間距離一半2 km作為出租車行駛距離閾值。

2.2.2 ?等待時間閾值設置

等待時間閾值更加復雜，不同時間段等待時間不同，因此，不同時間段應設置不同的等待時間。我們用當前時間段所有出租車尋客等待時間50%以上節點的等待時間平均值作為閾值。但是在行駛過程中，出租車也可能找到乘客，所以他們花的時間也被認為是尋客等待時間。

2.3 ?評價函數

從第1節的描述，算法描述： 和我們分別使用算法PFR和PFLWT來計算它們，算法原理圖如圖1所示。該算法實際上是一個遞歸迭代的過程。最后，將整個等待方案的返回值返回。

在圖1中，首先，推薦出租車前往最近的載客點r。然后我們的算法考慮相鄰的載客點：r1，r2。并分別計算它們的返回值。最后，我們推薦出租車轉移到返回值最大的載客點。

但是，r1載客點的返回值不僅與該點的出租車載客率有關，而且與后續相鄰載客點的返回值有關。因此，在滿足距離和等待時間閾值的情況下，我們還應該考慮連接到r1：r11，r12和連續遞歸的其他載客點。當考慮第三層時，如果此時距離和等待時間閾值不滿足，則將停止向下遞歸，并且必須返回到第二層并返回在r11，r12上最大的出租車載客率（即返回值），然后計算r1的返回值（r2的返回類似）并將其返回到第一層。這部分是算法PFR的工作。最后，在第一級計算整個解的返回值。這部分是算法PFLWT的工作。主算法的偽代碼在算法1和算法2中示出。

ALGORITHM 1： Passenge-finding Rate （PFR）

Input： Current passenger-finding locations r， Current time period TS， Total taxi travel distance d， Waiting time t， Traveling distance threshold ΔD， Waiting time threshold ΔT

Output： Return value of traveling sequence

1 if d>ΔD or t>ΔT then

2 ?return 0;

3 end

4 max =0;

5 t = t + ;

6 d = d + ;

7 for each ? nearby r do

8 ? pf_rate = TAR（ ，TS，d+ ，t）;

9 if pf_rate > max then

10 ? ?max = pf_rate;

11 ? ?tempr= ;

12 ?end

13 end

14 DadRoad[tempr]=r;

15 return +（1? ）?max;

2.4 ?算法分析

在算法1中，如果出租車的行進距離大于閾值，或尋客時間大于等待時間閾值，算法終止并返回0。即r點沒有潛在乘客;那么，設置r后下一載客點為其臨近最大返回值的載客點。最后，返回r的值。在閾值的約束下，一般臨近載客點是兩個以上的，可以得出時間復雜度為O（N3）。空間復雜度為O（1）。

ALGORITHM 2： Passenge-finding Locattions and ? Wait Time（PFLWT）

Input： the passenge-finding locattions closest to taxi r， Current time period TS， Traveling distance threshold ΔD， Waiting time threshold ΔT

Output： location sequence and waiting time of each passenge-finding locattion

1 maxrate =0 ;

2 for each ?nearby r do

3 ?temp = TAR（ TS， ?， ）;

4 ?if temp > maxrate then

5 ? ?maxrate = temp;

6 ? ?tempr = ;

7 ?end

8 end

9 DadRoad[tempr]=r ;

10 LocationList = WR（r）;

11 TimeList= WT（RoadList，TS）;

12 return ?+ （1? ）?maxrate ;

在算法2中，我們首先使用FL算法找到靠近出租車的載客點r，然后選擇r附近擁有最大返回值的鄰近載客點作為其下一節點。最后運用PFL和WT算法得到載客點位置序列和在每個載客點的等待時間，以及整個策略的返回值。其復雜度同算法1。

3 ?實驗與分析

3.1 ?實驗設置

實驗采用上海市GPS出租車數據集，記錄大約1500輛出租車行駛軌跡信息。本實驗使用這些軌跡數據向出租車推薦載客點序列，并根據出租車尋客成功的概率來衡量本文方法的好壞，同時本文方法還提供了每個載客點的駐留等待時間。

實驗隨機模擬生成了100個出租車的位置和相應的旅行時間。然后根據提出的算法計算出租車的行駛順序，然后將它們與實際的出租車軌跡相比較，來檢查出租車是否能夠按照推薦序列成功找到乘客。

3.2 ?實驗結果

實驗使用2017年2月25日到2017年12月31日出租車軌跡數據作為我們參數的訓練數據。并以未來兩個月的數據來驗證數據集，以此來校正推薦算法。該實驗隨機生成了100個出租車載客點位置以及出租車的行駛時間。如圖2所示。出租車的位置在P點。假設出租車需要尋客的時間是2019年1月1日上午10：10。然后通過算法得到的載客點序列如圖2所示。出租車需要5分鐘行駛到最近載客點并在該點附近尋客7分鐘。如果他們沒有找到乘客，他們將繼續行駛4分鐘到載客點2并在附近尋6分鐘。通過這種模式出租車找到乘客的概率為87%。在真實數據集里，出租車處于在相同時間和相同位置條件下，采用本算法推薦的載客點序列尋客成功率高于其他臨近載客點尋客成功率。即實驗表明，通過本文提出的算法出租車有更大概率成功找到乘客。

3.3 ?實驗分析

本文算法有四個參數：出租車載客率，尋客等待時間，等待時間閾值，距離閾值。前三個是根據歷史數據計算得到。我們只討論行駛距離閾值，真實情況下是由出租車司機自己來決定。通過對上面的例子繪制距離閾值和載客點位置數之間的分布圖，如圖3所示。

從圖3可以看出，當距離閾值相對較小時，序列中等待點的數量1，這意味著只推薦最近的載客點，沒有其他載客點可以轉換，因為出租車可以行駛的距離太短了。隨著距離閾值的增加，出租車可以行駛的距離變長，可選的鄰近載客點數量也隨之增加。但是如果它持續增加，我們會發現載客點位置序列不再增加，這是因為太多的時間花費在行駛上，尋客等待時間很短。通過圖3還可以看出，本算法可以得到至少一個的載客點序列。選擇2 km作為距離閾值是合理的，因為這樣可以有較多的鄰近載客點供出租車選擇。

4 ?結束語

本論文提出了一種MDP方法，用于確定出租車載客點位置，并為兩個評價函數提供求解算法。通過案例研究和真實數據集的實驗評估表明，本文提出的MDP方法符合實際情況，出租車按照算法推薦的出租車載客點序列可以更高概率的找到乘客。同時本文提出的方法大大減少了出租車空載時間，改善了出租車運營的效率。

參考文獻

[1] Altomare A， Cesario E， Comito C， et al. Trajectory Pattern Mining for Urban Computing in the Cloud[J]. IEEE Transactions on Parallel & Distributed Systems， 2017， 28（2）： 586-599.

[2] Lei Shuo， Li Zexi， Wu Binglin， et al. Research on Multi-Objective Bus Route Planning Model Based on Taxi GPS Data[C]// ?International Conference on Cyber-enabled Distributed Computing & Knowledge Discovery. 2017.

[3] Hu Jie， Xu Li， He Xin， et al. Abnormal Driving Detection Based on Normalized Driving Behavior[J]. IEEE Transactions on Vehicular Technology， 2017， 66（8）： 6645-6652.

[4] Dong Hao， Zhang Xuedan， Dong Yuhan， et al. Recommend a Profitable Cruising Route for Taxi Drivers[C]//IEEE International Conference on Intelligent Transportation Systems. 2014.

[5] Xu Xiujuan， Zhou Jiangyu， Liu Yu， et al. Taxi-RS： Taxi- Hunting Recommendation System Based on Taxi GPS Data[J]. IEEE Transactions on Intelligent Transportation Systems， 2015， 16（4）： 1-12.

[6] Huang Zhenhua， Zhao Zhenqi， et al. PRACE： A Taxi Recommender for Finding Passengers with Deep Learning Approaches[J]. lecture notes in computer science 2017.

[7] Tang Jinjun， Jiang Han， Li Zhibin， et al. A Two-Layer Model for Taxi Customer Searching Behaviors Using GPS TrajectoryData[J]. IEEE Transactions on Intelligent TransportationSystems， 2016， 17（11）： 3318-3324.

[8] Wang Ran， Chou Zhixin， Lv Yan， et al. TaxiRec： recommending road clusters to taxi drivers using ranking-based extreme learning machines[C]//Sigspatial International Conference on Advances in Geographic Information Systems. ACM， 2015.

[9] Kong Xiangjie， Xia Feng， Wang Jinzhong， et al. Time- Location-Relationship Combined Service Recommendation Based on Taxi Trajectory Data[J]. IEEE Transactions on Industrial Informatics， 2017： 1-1.

[10] Hu Yuanhang， Yang Yujiu， Huang Biqing. A Comprehensive Survey of Recommendation System Based on Taxi GPS Trajectory[C]//2015 International Conference on Service Science （ICSS）. IEEE， 2015.

[11] Yuan Jing， Zheng Yu， Zhang Liuhang， et al. T-Finder： A Recommender System for Finding Passengers and Vacant Taxis[J]. IEEE Transactions on Knowledge and Data Engineering， 2013， 25（10）： 2390-2403.

[12] Rong Huigui， Zhou Xun， Yang Chang， et al. The Rich and the Poor：A Markov Decision Process Approach to Optimizing Taxi Driver Revenue Efficiency[J]. 2016.

[13] Gao Qiang， Zhang Fengli， Wang Ruijin， et al. Trajectory Big Data： A Review of Key Technologies in Data Processing [J]. Journal of Software 2017.

[14] Shang Jiandong， Li Panle， Liu Runjie， et al. Recommendation model of taxi passenger-finding locations based on weighted non-homogeneous Poisson model[J]. Journal of Computer Applications， 2018.

[15] Chen Pengpeng， Lv Hongjin， Gao Shouwan， et al. A Real-Time Taxicab Recommendation System Using Big Trajectories Data[J]. Wireless Communications and Mobile Computing， 2017， 2017： 1-18.