PTRA：一个面向空载出租车的路线推荐算法

李思佳，苏凡军

(上海理工大学 光电信息与计算机工程学院，上海 200093)

0 引 言

出租车服务为人们的日常生活提供了巨大的便利，同时，现代化城市的发展也给出租车行业带来了巨大的变化。然而，一些大城市如纽约地区，乘客在繁忙时段等待出租车接载的有效平均等待时间超过13分钟[1]，很多出租车常处于空载状态。因此，在乘客下车后如何使这些出租车司机以合理的方式接载新的乘客，并且为这些出租车司机提供有效的路线推荐就显得十分有意义。

目前有很多研究通过向出租车推荐潜在载客点和最优行驶路线来缓和上述矛盾，第一种是热点推荐，热点是一个很可能接到客户的区域[2-5]；第二种是热线推荐，即专注于最快驾驶路线[6-10]的研究，热线推荐是从当前位置到目的地的最快驾驶路线；还有一种是在出租车司机和乘客的需求之间取得平衡[11-12]。但是多数的研究采用路线最短或是载客概率最大的标准对出租车司机进行推荐，忽略了实时交通对推荐结果的影响，对热门区域的路线进行重复推荐，解决出租车空载率高、利润率低的问题。

针对以上关于传统出租车司机路线推荐研究的不足，该文提出了一个以收益最大化为目标的空载出租车推荐算法PTRA(profit-based taxi recommendation algorithm)。PTRA基于利润最大化来推荐路线，司机通过遵循路线建议找到具有最大潜在利润的路线并接到乘客，这一点使得提出的推荐算法比其他现有的路线推荐算法更实用。

1 准备工作

1.1 路网定义

定义1(路段)：路段ri为任意两个相邻路口p,q之间的路段，表示为ri(p,q)。对于任意路段ri，与起点r.start和终点r.end相关联。此外，与路段ri相邻的段形成一个集r.next[]，如果r.end=ri.start，它满足∀ri.next[]。

定义2(路线)：路径R是一系列连接的路段，即R=ri→ri+1→…→rn，其中rk+1.start=rk.end(1≤k

定义3(路网)：路网G可以由图G=表示，其中V={ri}是由所有路段组成的节点集，有向边集E是实际道路的映射。

图1表示路段网络。在此图中，每个节点代表一个道路段。请注意，每个边只有一个方向。这是因为实际不允许出租车司机在相同的单一路段来回行驶，这在现实生活中不推荐，并且很有可能导致交通堵塞和事故。然而，出租车司机可以绕过三个路段形成循环，例如节点r4，r5和r6，驾驶员可以通过此路线形成循环。

图1 路段网络的示例

1.2 利润计算

对于任意一个路段r，净利润m(r)由两个部分组成，即潜在成本c(r)和潜在收益b(r)。

潜在成本c(r)的计算如式(1)：

(1)

其中，P(r)是接收乘客的收益段r中的能力，L(r)是段r的长度，Oil是每单位距离(如：每公里)的油价，T(r)是通过段r的行进时间，且T(r)对实时交通状况很敏感，OppCost是每单位时间(如：每分钟)的机会成本，CarDam(L(r),T(r))是时间路程内对车辆的损耗。由实际可知，交通堵塞将带来T(r)的增加，从而导致T(r)·OppCost和CarDam(L(r),T(r))增大。

潜在成本b(r)的计算如式(2)：

(2)

其中，Cr是在给定时间段内段r中的接载乘客数量，In(i,r)是接载第i个乘客的收入。

路段r的净利润m(r)，通过式(3)计算。

m(r)=b(r)-c(r)

(3)

(4)

基于以上所述，进一步定义每条路线R的净利润。路线R的净利润是R中包含的路段净利润m(ri)的总和，通过不接载先前路段中的任何乘客(即r1至ri-1)的可能性加权。

从r1开始给出路线R=r1→r2→…→rn，路线的净利润可以通过式(5)计算。

(5)

从段r中的第i个历史拾取事件中还可以获得式(2)中的In(i,r)。此外，道路长度L(r)和实时行驶时间T(r)可以从历史数据中估算。因此，净利润m(r)可以通过式(3)计算。每个路段r的T(r)、m(r)和P(r)的值预先存储在相应的路段网络(图1)节点中。

净利润的平均增长率定义为τ，表示在路线中增加一个路段时的利润增加。可以通过式(6)计算。

(6)

由实际可知，在n>5之后，净利润的平均增长率非常低。因此，该文设n=5。

定义4(路线最大净利润)。

图2表示高利润路段区域的生成过程。

图2 路线推荐生成过程

如图2所示，给定出租车司机的当前位置Loctaxi∈r，固定巡航长度n和一组候选路线，其中R满足从r开始，且∀R∈。路线R*∈，则路线的最大净利润为：

R*=Hmax{M(R,r,n)}

(7)

2 PTRA推荐算法设计

2.1 算法框架

由于道路永远不是静态的，考虑实际生活中可能会出现一些特殊情况，如天气原因，或者一些大型赛事(如演唱会、体育赛事等)，乘客对出租车数量的需求会在某段时间内某个区域范围内增长，因此基础的建议模型必须始终保持最新，以适应以上特殊情况。

该文构建了一个基于收益目标的空载出租车推荐算法。图3为提出的PTRA算法框架。PTRA框架分为两个阶段：离线挖掘阶段和在线推荐阶段。该框架特点如下：

图3 PTRA推荐算法框架

(1)提出的算法分为离线挖掘阶段和在线推荐阶段两个阶段。在离线挖掘阶段，基于出租车历史轨迹数据集，通过所定义的净利润公式计算每个路段的相关信息，并且用DBCSCAN聚类方法发现具有高利润的路段的区域，这些高利润区域的信息存储在路段网络中。在在线推荐阶段，当上一个乘客下车后，出租车司机提出推荐请求，出租车的位置是查询节点，系统自动获取出租车当前位置和当前所处时间段，根据当前位置推荐潜在高收益路段的区域，

(2)路线推荐区别于其他推荐系统的一个很大不同是，像音乐、电影或是商品的推荐皆可被重复推荐给不同的用户，而路线推荐在给出租车司机推荐时需要考虑重复推荐带来的影响，该文结合出租车在实际接载情况反馈当前区域的需求情况，不断更新潜在高收益路段的区域，对热门区域的路段可进行重复推荐，即推荐给该区域的不同司机。

2.2 算法功能实现

通过观察式(5)，得出净利润公式的特殊形式：

M(R,r1,n)=m(r1)+(1-P(r1))M(R-r1,

r2,n-1)

(8)

其中，R=r1→r2→…→rn。实际上，净利润的特殊形式可以通过递归算法来实现。为此，对于路段r1，可以将从r1开始的所有路线候选表示为递归树结构。路段ri的递归树Yri，其中每个节点代表路段并且根节点是ri。此外，对于递归树中的每个节点ri，它具有子节点集ri.next[]。对于给定r的递归树，通过递归n-1次来获得长度为n的路线。

目前有许多针对轨迹数据挖掘的聚类方法，如基于环状的聚类、基于模型的聚类、基于网格的聚类、基于密度的聚类等[13]，而类似于K-means这种以距离为标准的聚类并不适用于寻找载客密度大的区域。为了寻找高利润路段的区域，该文选用较为高效且可以灵活设置聚类数量的经典划分聚类算法DBSCAN[14]，其中最小包含点数(MinPts)和扫描半径(Eps)分别设置为3 000和60。

以下为DBSCAN算法伪代码:

算法：High profit road algorithm on DBSCAN

Input：A list of pick-up locations road roadList={r1,r2,…,rn},Eps,MinPts

1.初始化roadList中所有road为未标记状态

2.For roadList中每一个载客路段 road

3. If road为标记状态

4.返回步骤2寻找下一个载客路段

5. Else

6.设置road为标记状态

7.令N为road的Eps半径内的所有载客路段集合

8. IfN中的载客路段小于MinPts个数

9.标记road为噪声

10. Else

11.创建高收益路段Highroad

12.添加road到Highroad中

13. ForN中每个载客路段road

14. If road处于非标记状态

15.标记unRoad

16.筛选unRoad在Eps邻域内的载客路段集合newRoad

17. If newRoad内的载客路段数量小不少于MinPts

18.将newRoad加入到N中

19. If unRoad不属于任何路段

20.将unRoad加入到Highroad中

Output: Clustering result

3 实验分析

3.1 实验数据

实验采集的数据集来源于滴滴出行“盖亚”数据开放计划[15]，数据集包含海口市2017年10月份的滴滴网约车2 664 253条订单数据，由订单ID、起点、终点等信息组成，计算与每个路段相关的历史载客概率和净利润。对于每条道路，记录中间点的几个坐标，并且还存在一些噪声点。在去除噪声点后，该文选择了2 149条具有高拾取概率的道路进行实验。然后，使用这些路段中的起点和终点来构建道路缓冲区。订单信息如表1所示。

表1 网约车订单信息

续表1

通过将道路网数据集的提取坐标与出租车数据集相匹配，可以获得86 588个有效的载客信息，这些活动可以位于路段中，因此这两个数据组合在一起，每个拾取点映射到构建的道路缓冲区。为了实现所提出的算法，还需要计算这些路段中每个路段的拾取概率和净利润。这已经在第1节中介绍过了。

3.2 实验分析

(1)参数Δt对PTRA的影响。

考虑不同时段对Δt的设置，该文将一天分为6个时间段(00:00-04:00,04:00-08:00,08:00-12:00,12:00-16:00,16:00-20:00,20:00-24:00)，设置不同的Δt，验证它们(2 min,5 min,8 min,11 min)在不同时间段的表现力。实验结果如图4所示，5 min的间隔在08:00-12:00，16:00-20:00的效益表现力更好，考虑到系统计算成本和推荐效果，将这两个时间段的Δt设置为5 min，而其他数段则将Δt设置为11 min。

图4 不同时间间隔的利润收益

(2)净利润的比较。

对于任意一个司机，定义司机开始位置为Loc0，空载巡游时间为Δt，司机在位置Loc1处成功接到乘客，行驶Δt'时间，并在Loc2处将乘客放下。让ri,j表示位置Loci和Locj之间的路段，事件E可被表示为(r01-r12,Δt'-Δt)。将这样连续的“巡游→载客→放下”一系列过程定义为事件Event，事件Event可被表示为(r01-r12,Δt'-Δt)。该文提出的算法从最接近Loc0的Loc'处开始，并返回一系列推荐的潜在载客点和路段。推荐驾驶路线的性能通过单位时间的平均净利润pd来衡量，将其与经验不足的出租车司机的单位时间平均净利润进行比较，事件Event单位时间平均净利润pE和单位时间的平均净利润pd通过计算可得：

(9)

(10)

对于给定位置，该文提出的算法可以推荐具有高效益的区域路段，并特别适用于没有经验的出租车司机，因为他们缺乏本地路线图的意识和可以获利路线的驾驶知识。为了验证所提算法的有效性，根据10月份所有司机的平均净利润将所有出租车司机分为两类。数据集中排名前10%的出租车司机被视为“经验丰富”的出租车司机，而其他则为“缺乏经验”出租车司机。因此，经验丰富的司机的驾驶路线被用作训练组。对于没有经验的驾驶员的推荐驾驶路线的统计实验结果如表2所示，PTRA推荐结果优于缺乏经验的驾驶员的实际利润。

表2 净利润结果比较

首先绘制每小时路线净利润的分布图，即特定利润值的事件数量，如图5所示，基于直方图的统计表示，推荐的路线的单位间净利润与没有经验的出租车司机进行比较。柱状图的白色条显示了推荐结果的净利润，阴影条显示了没有经验的出租车司机的利润。从图中可以看出，推荐的路线主要定位于较大的值。这表明此推荐机制为缺乏经验的司机提供比实际利润更高的路线。总而言之，该算法可以帮助没有经验的出租车司机找到更好的路线，从而最大限度地提高他们的潜在利润。

图5 净利润统计

4 结束语

为了提高司机收益和减少出租车空载巡游的时间，该文以收益利润为目标提出了一个空载出租车推荐算法PTRA。该算法根据出租车当前位置结合当前路段反馈的实际路况为出租车司机提供高收益路线，可对热门区域路线进行多次推荐。实验结果表明，该算法能帮助没有经验的司机找到具有高收益路段的区域。