宋芝明 袁健

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

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

中圖分類號： TP301.6 ? ?文獻標(biāo)識碼： 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 ?引言

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

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

1 ?Markov決策過程

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

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

2 ?參數(shù)屬性設(shè)置

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

2.1 ?算法參數(shù)解決方案

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

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

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

B.尋客等待時間

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

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

2.2 ?閾值參數(shù)

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

2.2.1 ?行駛距離閾值設(shè)置

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

2.2.2 ?等待時間閾值設(shè)置

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

2.3 ?評價函數(shù)

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

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

但是，r1載客點的返回值不僅與該點的出租車載客率有關(guān)，而且與后續(xù)相鄰載客點的返回值有關(guān)。因此，在滿足距離和等待時間閾值的情況下，我們還應(yīng)該考慮連接到r1：r11，r12和連續(xù)遞歸的其他載客點。當(dāng)考慮第三層時，如果此時距離和等待時間閾值不滿足，則將停止向下遞歸，并且必須返回到第二層并返回在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中，如果出租車的行進距離大于閾值，或?qū)た蜁r間大于等待時間閾值，算法終止并返回0。即r點沒有潛在乘客;那么，設(shè)置r后下一載客點為其臨近最大返回值的載客點。最后，返回r的值。在閾值的約束下，一般臨近載客點是兩個以上的，可以得出時間復(fù)雜度為O（N3）。空間復(fù)雜度為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附近擁有最大返回值的鄰近載客點作為其下一節(jié)點。最后運用PFL和WT算法得到載客點位置序列和在每個載客點的等待時間，以及整個策略的返回值。其復(fù)雜度同算法1。

3 ?實驗與分析

3.1 ?實驗設(shè)置

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

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

3.2 ?實驗結(jié)果

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

3.3 ?實驗分析

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

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

4 ?結(jié)束語

本論文提出了一種MDP方法，用于確定出租車載客點位置，并為兩個評價函數(shù)提供求解算法。通過案例研究和真實數(shù)據(jù)集的實驗評估表明，本文提出的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.