关于出租车载客地点序列推荐技术的研究

陈轶非 李治军 姜守旭

摘要：在大城市中，出租车已成为实现智能交通运输系统不可或缺的一环。然而，由于一些出租车司机的驾驶经验，和对城市活动的熟悉程度的不足，使得其在寻找乘客时会采取毫无目的的随机漫游策略。这就导致了出租车司机的收益不高，同时也造成了能源的消耗以及环境的污染。针对此问题，将提出出租车载客地点的推荐模型，使得模型给出的推荐地点序列能获得较高的期望收益。具体来说，将基于出租车GPS轨迹数据建立出租车载客地点的马尔科夫决策过程模型，并给出求解该模型的2种算法。仿真实验结果显示，与典型的TopK方法相比，给出的推荐结果能更好地提高单位时间内出租车司机的收益。

关键词：智能交通系统； 马尔科夫决策过程； 空间数据挖掘； 轨迹数据处理

中图分类号：TP391 文献标识码：A文章编号：2095-2163（2013）06-0070-04

0引言

在人们日常的出行活动中，出租车正扮演着越来越重要的角色。如今，已经有数量众多的现代人选择出租车来作为其代步的出行方式。根据最近一份关于纽约出租车服务的调查[1]，结果显示有41%的调查者每周都会乘坐出租车，有25%的调查者甚至每天都会乘坐出租车。然而，为了方便人们的出行，一些大城市（如纽约、东京、伦敦和北京）都会有大量的空载出租车随机行驶在城市区域中。这些空载出租车的随机行驶不仅会浪费出租车的汽油，造成环境的污染，而且会造成城市中额外的交通事故。因此，怎样规划空载出租车的行驶路线使其快速发现乘客，提高出租车的利用率，从而有效减轻资源消耗和环境污染，则成为一个亟待解决的严峻挑战。

近年来，为了出租车的调度和安全，许多大城市（如纽约、北京和新加坡）中的出租车均配置了GPS传感器。这些出租车会以一定的频率（如2分钟）向数据中心报告其当前所处的位置[2]。除了地理位置和时间戳信息，出租车的载客状态信息也会通过重量传感器或者出租车的计程器被记录下来。因此，每天都会产生大量的伴随着出租车载客状态的GPS轨迹信息。这些轨迹信息的产生也引发了学术界对出租车地点推荐问题的关注和兴趣。文献[3]提出了一个推荐出租车司机至一系列载客点的模型，目的是使得出租车司机的收益最大化。该模型使用了skyline路径查询的方法，同时将问题形式化为移动序列推荐（mobile sequential recommendation）问题。文献[4]提出了出租车司机寻找乘客的学习策略（漫游/等待）。该文献使用了L1-Norm SVM的学习方法筛选得出用于寻找乘客策略的分类特征。文献[5]提出了一种能预测出租车收益地点的方法。该方法建立了空间-时间收益地图，并根据历史数据计算出的潜在收益将临近区域内的司机在该地图上进行评分。

与上述研究类似，本文也将提出一种基于GPS轨迹信息的出租车载客地点推荐系统。其中，系统的输入为空载出租车当前的地理位置和时间，输出为预推荐的一系列的载客地点，使得这些载客地点能够实现单位时间内的收益最大化。但与已有研究不同的是，本文将建立基于马尔科夫决策过程[6]（Markov Decision Process， MDP）的推荐模型，同时将融合2方面的特征：

（1）能以较大的概率发现乘客；

（2）推荐地点离当前地点的距离不是太远（否则物质上和时间上的开销都较大）。

实验结果表明，模型给出的推荐结果将有助于减少出租车随机漫游的时间，为出租车司机带来更多的收益。

1预备知识

整个MDP过程可表示如下：S0a0S1a1S2a2…，所能获得的总的回报为R（s0，a0）+γR（s1+a1）+γ2R（s2，a2）+…。MDP的优化目标就是采取某组策略（动作），使得该回报值最大化。

2出租车载客地点的MDP模型的建立

2.1状态集合的建立

首先，将建立MDP的状态。可令状态s表示为三元组s=（p，t，x），其中p表示出租车所在的地点，t表示出租车所处的时刻，x表示出租车当前的载客状态：x=0未载客

1载客。现在将对出租车所处的时空状态进行离散化处理。

首先，将出租车的空间位置信息表示在有限的道路网络内，这样p就可以抽象成某种空间实体，如其所属的某条路段r，或者离出租车最近的路口c等；如果没有城市道路网络的精确数据，也可以将虚拟的道路网络划分成固定大小的网格，将p表示为出租车所在的网格，如此就将连续的空间地点离散成为有限个空间状态的集合。

其次，将时间维度也离散成有限的时间区间。一般地，由于城市中的许多活动均带有一定的周期性，如上下班，火车到站等；同时，这些活动在工作日和双休日内的发生时刻又有着各自的规律性，因此，对时间也将依据2个维度进行划分：

（1）按照周几（1-7）或是工作日和双休日进行划分；

（2）按照一天内的时间区间进行划分。

对于（2）的划分，可以取相等的时间间隔，如Δt=1小时将每天划分成[00：00～01：00），[01：00～02：00）等24个时间区间；或者根据一些相关的特征来划分时间段，如将一天划分成早晨上班高峰时段，工作时段，下午下班高峰时段，晚间时段等。这样，t就可以表示在这些离散的区间内。于是，将时间也离散成了有限的状态。

2.2动作集合的建立

根据空间状态的建立方法，可以将一个动作定义为：选取和当前地点相邻的某个抽象点（该点和之前空间状态的建立方法相对应，如该抽象点可以是某个相邻的路段r，或者是某个相邻的网格）。因此，总的动作集合A便可定义为空间点集P的一个子集：AP。在此，点p与p′“相邻”的定义为：p无需经过其他抽象点（路段，网格等）便可以直接到达p′，并简记为p→p′。于是，当出租车处于某个抽象点p时，所能选取的动作集合可以表示为{p′|p|→p′}。令s（i）表示选取状态s=（p，t，x）中的第i个分量，那么，一个状态s的动作集合A（s）则表示为A（s）={p′|p=s（1），p|→p′}。这样，便建立了总体的动作集合A，以及每个状态下的可行的动作子集A（s）。

2.3转移函数的建立

在建立状态集合S和动作集合A后，便可以将出租车的每个GPS轨迹点对应至相应的s和a上，再利用极大似然估计法，便可以求出每个转移函数Psa（s′）的近似估计值P^sa（s′），计算公式如下：

P^sa（s′）=状态s下执行a到达状态s′的次数状态s下执行的a次数（1）

如果样本数不足，使得P^sa（s′）=00，就可以认为不存在该概率分布的先验知识，于是将其设置为简单的均匀分布，即P^sa（s′）=1|B|，其中B={s|s（1）=a}。由此即能较准确地估计得到所有情形下的状态转移函数。

2.4回报函数的建立

和转移函数类似，在运行MDP之前，回报函数也是未知的。因此，也可以利用采样的方法，对回报函数进行估计。本文将采用一种简单的均值方法，计算公式如下：

R^（s，a）=∑ni=1Ri（s，a）n（2）

其中，n为观察到在状态s采取动作a的总次数，Ri（s，a）表示第i次观察得到的回报值。而观测值Ri（s，a）则可以根据实际的出租车收益情况进行估计。举例来说，如果从P点执行动作a=p′到达p′，那么根据出租车在p和p′时是否处于载客状态，可以将Ri（s，a）分成以下4种情况讨论。令出租车在点p的载客状态记为xp，p和p′的欧几里得距离记为dist（p，p′），则Ri（s，a）的定义如下：

其中，r为出租车平均每公里挣得的收益（即乘客所支付的费用），c为出租车平均每公里的开销（油费，零件损耗等），表示异或运算。第3部分中的1/2则基于一个均匀分布的假设，即改变状态的地点是均匀分布在p和p′之间的。这就对应于先验知识未知或缺少的情况。

如果样本数不足，得到R^（s，a）=00的形式，则将该R^（s，a）设置为-c×dist（p，p′），即假设在该情况下，无法拉到乘客。

综上，利用式（2）和（3）便能估计得到每个R（s，a）的值。

2.5折价因子的建立

折价因子控制了当前的决策对未来的影响程度，或者是希望以多大的权重将未来的收益累加到当前的即时收益中。一般均设置为一个不以时间变化的常数。本文依照学术界的主流做法，取γ=0.95，即表示未来收益的权重非常大。

3出租车载客地点的MDP模型的求解

在建立MDP模型后，本节将讨论如何对MDP模型进行求解。为求解得到最优化的MDP策略和回报值，需再定义如下2个概念：

（1）确定性策略（deterministic policy）π：S→A，定义了在某一状态s∈S下需采取的动作π（s）∈A；更一般的策略π可定义为随机策略（stochastic policy）：S→∏（A），其中，∏（A）表示的是在动作集合A上的概率分布空间，π（s，a）表示的是在状态下采取动作a的概率。

（2）策略π的值函数（value function）Vπ（s）定义为Vπ：S→R，表示从状态s出发采取策略π所能获得的加权总回报值的期望：Vπ（s1）=E[R（s1，π（s1））+γR（s2，π（s2））+γ2R（s3，π（s3））+…|π]，其中si∈S为在时刻i所处的状态。MDP的目标便是求出最优策略π*，使得π*的值函数Vπ*（s1）=maxπ{E[R（s1，π（s1））+γR（s2，π（S2））+γ2R（s3，π（S3））+…|π]}

为求解基于MDP模型，需基于以下2个重要定理：

定理1（贝尔曼方程[7]）给定MDP模型M=（S，A，P，γ，R）和策略π：S→A，则对所有的s∈S，a∈A，Vπ满足以下关系：

其中，在迭代阶段，可以使用同步更新和异步更新两种方法对V进行迭代更新操作。

在同步更新中，可以计算得到每个状态s∈S下的新的V（s）值，再用这些值覆盖所有旧的V（s）的值。在这种情况下，该算法可以看做是实现了“贝尔曼备份”的操作，对当前值函数进行了一次值估计，然后将该估计值映射到新的值函数中。

在异步更新中，可根据某种顺序循环操作所有的状态s，并在每一次的循环中即时更新状态s对应的V（s）。

4实验分析

4.1数据来源

本文采用的GPS出租车轨迹数据集[8]来自于清华大学复杂工程系统实验室（Complex Engineered Systems Lab），这些数据通过实验室所部署的传感器网络系统采集得到。该数据集采获了北京市大约28 000辆出租车在1个月内行驶轨迹的GPS数据，大约覆盖了北京市42%的出租车数量（总数目约为67 000辆），因此该数据集构建了一个极具代表性的样本空间。同时，从时间的角度，这份数据集覆盖了工作日、双休日，以及节假日。这就真实地反映了出租车在不同时段、不同交通情形下（拥堵、畅通）的活动模式。

本文同时也节取北京的交通道路网络做为实验对象，该网络有106 579个道路节点，以及141 380个道路区间。因此，本文的数据以及实验对象均为真实可靠的。

4.2数据预处理

对于海量的数据源，将进行一些预处理过程：

（1）行程发现。根据出租车的计程器数据，可以知道出租车是否载客的状态（X载客=1 or 0），由此可以将行程定义为从X载客变化起的时刻ts至X载客保持该状态直至结束的时刻te，在此段时间te-ts内所行驶的轨迹，可以将所有司机驾驶的GPS轨迹划分成一段段如上定义的行程。

（2）地图匹配。将利用一种对低样本率的轨迹也具有良好表现性能的匹配算法IVMM[9]，凭此可将每段行程上的点匹配至真实的地图中，从而将行程信息转换为一些实际的路段信息。

4.3实验结果

为了衡量MDP模型序列推荐的性能，本文将进行仿真实验。实验中将根据统计的结果模拟得到各个地点的状态转移函数Psa（s′），并以载客距离比例、载客时间比例两个不同的值作为推荐性能的衡量指标。同时，将以TopK算法为参照算法，以对比MDP的性能。实验结果如图1、图2所示。

首先，分析图1，在乘车需求高峰时段，MDP的载客时间比例大于TopK，而在低谷时段，MDP的载客时间比例却略小于TopK。原因在于乘车需求较小的时段，TopK给出的地点常常更容易遇到载客，而MDP却由于需考虑到前往这些地点的路途开销，因此算法将直接建议在附近局部最优的地点停留，而非前往全局最优的地点。

其次，分析图2。可以发现，无论在哪个时间段内，MDP的载客距离比例始终要大于TopK，原因就在于TopK通常需要前往全局最优点，而MDP只选择局部最优的位置。特别地，在乘车需求较低的时段内，两者的差距会变得更大。而载客的距离往往决定了实际的打车费用，因此，从实际收益的角度来看，MDP的性能要好于TopK。

5结束语

为了使出租车司机能获得较高的期望收益，本文针对出租车司机载客地点选择问题进行了研究。在基于出租车GPS轨迹数据的基础上，建立了解决出租车载客地点序列推荐问题的马尔科夫决策过程模型，并给出求解该模型的两种算法。仿真实验结果显示，与典型的TopK方法相比，本文给出的推荐结果能更好地提高出租车司机单位时间内的收益值，因此验证了模型的有效性。不过该模型却依然有其局限性，即没有考虑环境的动态因素，而只考虑了单个司机的情形。如果有多个出租车司机均选择了相同的推荐地点，那么极有可能造成出租车司机之间在推荐地点竞争乘客的情形，同时也容易造成推荐地点路段的拥堵。因此，在未来的工作中，将进一步研究多个出租车司机并存的环境中如何选择载客地点的问题。这可以通过引入博弈论、随机博弈等理论加以深入研究。

参考文献：

[1]New York City Taxi and Limousine Commission. Taxi of Tomorrow Survey Results， Feb 2011. http：//www.nyc.gov/html/tlc/downloads/pdf/tot_survey_results_02_10_11.pdf.

[2]YUAN J， ZHENG Y， XIE X， et al. Driving with knowledge from the physical world[C]//Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM， 2011： 316-324.

[3]GE Y， XIONG H， TUZHILIN A， et al. An energy-efficient mobile recommender system[C]// Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM， 2010： 899-908.

[4]LI B， ZHANG D， SUN L， et al. Hunting or waiting？ Discovering passenger-finding strategies from a large-scale real-world taxi dataset[C]//Pervasive Computing and Communications Workshops （PERCOM Workshops）， 2011 IEEE International Conference on. IEEE， 2011： 63-68.

[5]POWELL J W， HUANG Y， BASTANI F， et al. Towards reducing taxicab cruising time using spatio-temporal profitability maps[M]. Advances in Spatial and Temporal Databases. Springer Berlin Heidelberg， 2011： 242-260.

[6]PUTERMAN M L. Markov decision processes： discrete stochastic dynamic programming[M]. New York， Wiley， 2009.

[7]SUTTON R S， BARTO A G. Reinforcement learning： An introduction[M]. Cambridge： MIT press， 1998.

[8]Complex Engineered Systems Lab Taxi Dataset. http：//sensor.ee.tsinghua.edu.cn/datasets.

[9]YUAN J， ZHENG Y， ZHANG C， et al. An interactive-voting based map matching algorithm[C]//Mobile Data Management （MDM）， 2010 Eleventh International Conference on. IEEE， 2010： 43-52.