基于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.