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)。……