基于Markov的出租車載客點(diǎn)推薦

宋芝明 袁健

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

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

中圖分類號(hào)： TP301.6 ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.06.032

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

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

1 ?Markov決策過程

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

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

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

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

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

從第二節(jié)，我們可以看出，解決評(píng)估函數(shù)的關(guān)鍵是直到每個(gè)載客點(diǎn)的返回值，即載客點(diǎn)的出租車空載率。同時(shí)，我們還需要給出乘客在初始載客點(diǎn)和后續(xù)載客點(diǎn)的等待時(shí)間，因?yàn)椴豢赡茏尦鲎廛嚳偸堑群颍覀儜?yīng)該給出參考時(shí)間。

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

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

B.尋客等待時(shí)間

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

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

2.2 ?閾值參數(shù)

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

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

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

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

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

2.3 ?評(píng)價(jià)函數(shù)

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

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

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

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

3.1 ?實(shí)驗(yàn)設(shè)置

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

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

3.2 ?實(shí)驗(yàn)結(jié)果

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

3.3 ?實(shí)驗(yàn)分析

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

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

4 ?結(jié)束語

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

參考文獻(xiàn)

[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.