基于候客点规划的空闲出租车路线推荐算法

陈冬梅，卜霄菲，黄 河，杜 扬，高国举，孙玉娥

（1.苏州大学 计算机科学与技术学院，江苏 苏州 215006；2.沈阳师范大学 软件学院，沈阳 110034；3.苏州大学 轨道交通学院，江苏 苏州 215137）

0 概述

随着定位技术和4G/5G 技术的发展，装备全球定位系统（Global Position System，GPS）设备的出租车越来越多［1-3］。通过对该类设备采集得到的海量轨迹数据进行挖掘分析，可以在改善出租车服务质量方面提供更好的数据支撑，令出租车服务更加舒适、快捷，使出租车成为更多乘客的出行选择［4］。然而，在面临日益增长的乘客需求和出租车供给不平衡的矛盾时，如何为空闲司机规划路线，以最短时间和最短距离接载到乘客，成为学术界关注的热点问题［5-7］。

传统的空闲出租车路线推荐主要有2 种方式：载客点推荐［8-10］和载客路线推荐［5-7］。载客点推荐一般是通过对历史轨迹数据的上下车事件进行聚类从而发现乘客需求较多的载客点，当司机发出请求时，可以推荐司机前往最近的接载点。例如文献［8］通过历史轨迹数据检测停车点，从而并向空闲司机推荐这些停车点以最快的时间接载到乘客。文献［9］通过将底层道路网络聚类成多个路段集群，根据每个集群的特征评估其寻客潜力并进行推荐。然而，该类方法忽略了前往这些载客热点的路线并不唯一的问题，在没有经验知识的情况下，司机如何选择效益最高的路线是一个难以解决的问题。

为解决接载点推荐存在的问题，近几年的研究工作主要集中在为空闲司机推荐接载路线，原因是相比较只推荐接载点而言，直接推荐完整的路径可以为无经验的司机减少闲逛距离，从而减少空闲时的花费成本。其中，文献［5］提出路段的净利润函数，向司机推荐潜在利润最大的路线。文献［6］在文献［5］的工作基础上提出了一个基于蒙特卡洛搜索树思想的路线推荐方法，实现了动态的接载概率。文献［7］提出自适应最短预期闲逛路线的推荐方法，能够根据位置的容量和接载概率推荐路线。

目前存在的路线推荐方法主要是为空闲司机推荐一条完整的驾驶路线，直到司机接载到乘客或者遇到终点路段才停止推荐。但该方式忽略了真实路网环境下某些路段的可等待因素。例如餐饮服务集中地区、大型商场周围、地铁公交车站附近以及学校周边的可停车路段，这些路段都会在特定的时间段（如车站到达、地铁换乘、上课放学等时段）出现大量乘车需求。当司机在某时段经过这些路段时，传统方法依然会继续推荐行驶路线，却没有预判到该路段未来某段时间的乘车需求对司机决策的影响。例如当司机经过地铁站附近的路段时，如果该地铁站在未来1 min 刚好到站则会出现大量换乘乘客，此时司机选择停车等待可能会更快接到乘客。相反，如果司机选择继续行驶，则会导致空闲出租车的闲逛距离过长，工作收益降低。相比较传统的路线推荐方法而言，考虑路段等待因素不仅可以帮助司机更快地接载到乘客，而且可以帮助司机降低因闲逛产生的油费损耗，从而进一步减少能源消耗以及废气排放造成的空气污染［11-12］。此外，通过考虑路段的可等待因素还可以帮助乘客减少因换乘产生的等待时间，在提高搭载双方工作效率的同时，进一步缓解交通拥堵的压力，对提高城市的流动性具有重要意义［13-14］。

本文针对当前路线推荐方法存在忽略路段可等待因素的问题，提出一种基于候客点规划的空闲出租车路线推荐机制。通过分析出租车行驶过程产生的轨迹数据，将轨迹点和真实路段建立联系。同时，处理出租车行走路段的历史搭载信息，从而构建接载概率预测模型。基于已有数据，以推荐花费成本更小的路线策略为准则，提出一种考虑等待时间的路线推荐算法，并在真实的出租车轨迹数据集上验证该算法的有效性。

1 相关工作

目前关于出租车路线推荐方法主要有2 种：向出租车司机推荐接载热点及向出租车司机推荐完整路线。

针对第1 种推荐方式，YUAN 等［13-14］通过学习乘客的移动模式和司机接载行为的知识，建立概率模型进行停车点的推荐，使司机能以最短的时间接载到乘客。WANG 等［9］提出一 种基于排序的ELM 模型，该模型可以根据道路集群的拾取频率来评估所有道路集群的寻客潜力并向出租车司机推荐具有最高寻客潜力的Top-k 道路集群。VERMA 等［15］基 于强化学习方法，利用蒙特卡抽样建模经验司机的行为，并通过司机的行为偏好捕捉乘客的需求变化，为闲逛司机推荐长期利益最大化的区域。CHEN 等［16］提出利用空闲状态计算接载点的利润并结合DBSCAN 聚类算法提取高利润的乘客区域推荐给空闲司机。LI 等［17］基于司机目的点偏好这一因素提出基于目地点概率最大化的推荐算法PROMISE，为空闲司机推荐满足目的区域的一系列接载点。LI 等［18］提出一种改进的ARIMA 方法，预测热点区域乘客移动的时空区域，从而挖掘出乘客的移动模式。HWANG 等［19］通过建立ON-OFF 模型获取乘客下车位置和下一位乘客上车位置之间的关系，并估计出推荐点的期望利益。然而，这些推荐方法基本都是基于位置点的推荐而非实际的完整路线，而这对司机在找到乘客之前如何减少闲逛时间十分重要。

针对第2 种推荐方式，向出租车司机推荐完整路线，QU 等［5］提出一种Cost-Effective 的路线推荐系统，该系统首先提出一个净利润函数（乘客收益-出租车花费）来评估每个路段的潜在收益。基于递归树的思想生成寻找乘客的候选路径，并利用净利润函数计算每个候选路径的收益，并将收益最大的路径推荐给空闲出租车司机。GARG 等［6］提出一个基于蒙特卡罗搜索树的寻客策略，目的是令空闲司机与预期乘客之间的闲逛距离最小化。JI 等［11］将最小化空闲时间作为学习目标，提出一个自适应的深度强化学习策略，并进行路线推荐。该工作通过深度网络融合多个实时的内外部特征，并为每个候选路径学习一个评价分数。同时，利用强化学习策略进行学习，实时捕捉候选路径的推荐分数，并将分数最高的路线推荐给空闲司机。QU 等［7］提出一个出租车收益的路线推荐方法即自适应最短预期闲逛路线（ASER）。该方法通过设计概率网格发现潜在的接载位置和动态的接载概率，然后利用卡尔曼滤波方法预测每个网格的接载概率和容量，并在大数据应用平台下开发新的数据结构框架以提高推荐效率。LUO 与LV 等［20-21］基于接载乘客的概率和容量问题，也提出一种出租车路线推荐方法，为一组司机推荐最优的路线，目的是最小化平均闲逛驾驶距离。RONG 等［22-23］基于马尔科夫决策模型为出租车司机推荐长期利润最大化的路线。尽管当前存在的空闲出租车路线推荐工作已经解决了一些问题，但是这些方法均忽略了真实路网环境下某些路段的可等待因素，使推荐的路线因载客概率较低、行驶距离较长而花费成本变高。

2 模型构建

2.1 符号说明

定义1（节点）节点是指某2 个路段相交的点，可以表示为s=(id，lat，lon)，其中：id 是该节点的唯一标识符；lat 和lon 分别表示该节点所在的经纬度信息。

定义2（路段）1 条完整的路径可以被多个节点s分割成多个路段序列r，其中每个路段均由2 个节点确定，即r=(sstart，send)。如果该路段不是终点路段，则与其相连的其他路段称为它的邻居路段，可以表示为

定义3（路线）路线R由一系列相连的路段组成，可以表示为R={r1→r2→…→rn}，满足对于∀i，1≤i≤n，，且该路 线的起点 为R_start=，该路线的终点为R_end=

定义4（路网）1 个路网可以表示为有向图G(V，E，D)，其中：V表示所有节点的集合{s1，s2，…，sn；E={ri→j|si(idi，lati，loni)，sj(idj，latj，lonj)∈V} }表 示所有有向路段的集合；D表示为每个路段物理距离长度的集合，可由Haversine 式（1）计算得出：

其中：φ是节点s的纬度；λ是节点s的经度；RRadius为地球半径（6 371 km）。

定义5（轨迹）轨迹是按时间序列排序的一系列GPS 采样点组成的集合，可以表示为Tr={p1→p2→…→pn}，其中每个采样点表示为pi={lat，lon，time，empty，speed}记录着采样点的位置信息、时间戳、载客状态、速度等信息。对于出租车的载客状态可以由式（2）表示：

从出租车的轨迹数据中进一步挖掘出租车是否处于停车状态，并通过该状态标识可停车路段。对于2 个连续的GPS 采样点pi和pi+1，利用Haversine 公式计算这2 个采样点之间的距离与时间间隔，当距离小于预先定义的距离阈值且时间间隔大于采集间隔时，认为此时出租车的状态为停车状态，意味着司机经过该路段时可以选择停留。值得注意的是，本文定义的停车路段是司机在该路段等待有需求的乘客。在现实生活中，这类场景多数会出现在周围有车站、商场附近、居民区等的路段。

定义6（时变的接载概率）由于不同道路环境、不同天气以及不同时段等因素的影响，对于某一路段的乘客需求在不断变化，因此对于任意的某一路段r在时间间隔[τ1，τ2]内的搭载概率为：

2.2 问题描述

定义7当出租车司机放下乘客处于空闲状态时，可以发出寻客请求。根据空闲司机发出请求的路段r1和请求时间t，为空闲出租车司机推荐1 个效益最大化的接载路线R*={r1，r2，…，rL}，使得空闲司机选择这条行驶路径接载到乘客时的闲逛距离、闲逛时间和花费成本最小，其中L表示选择路径的长度。

由于司机的花费成本涉及到司机在接载到乘客之前所行驶的距离和所花费的时间，因此对于每个路段的潜在花费成本可以根据式（4）得出：

其中：p(ri，[τ1，τ2])表示在该路段接载到乘客的概率；Frent是出租车司机租赁出租车的费用；Fgas是出租车行驶d(r)距离所花费的汽油费；tp(r)是出租车穿过该路段所花费的时间；tw(r)是出租车停留在该路段所花费的时间；t=tw+tp是出租车司机在该路段上花费的总时间。

对于每个路段的潜在收益可根据式（5）得出：

因此对于每个路段的净收益可由式（6）计算得出：

由该公式可以看出影响司机收益的重要因素是在闲逛时所花费的时间和距离。因此，如果想要提高司机的收益，需要不断减小司机在闲逛时所花费的成本，即Minimise(Cost(r，t))。

基于以上定义，对于任意推荐路线R={r1，r2，r3，…，rL}可以计算其花费成本函数为：

式（7）表示对于推荐的路径R来说，当出租车司机在路段rL接到乘客时，所花费的成本最小。

以往的推荐算法是推荐一个连续驾驶路线，只考虑经过路段的当前接载概率，若经过该路段没有接载到乘客，则会继续推荐路线，导致闲逛距离变长，花费成本变高。而本文算法考虑了路段的可等待因素。当出租车司机经过靠近地铁站、车站、学校等地方的路段时，能够预判未来某个时刻可能发生的事件，比如由于地铁到站而出现大量换乘乘客。本文算法推荐的具体步骤如下：1）根据历史GPS 轨迹信息为每个路段统计出最长等待时间；2）设定司机在某路段等待的时间阈值是3 min，单位时间间隔是1 min；3）当空闲司机在r1路段发出请求时，对于r1的邻居路段{r2，r3，r4}以及等候间隔有2 种方案选择。这2 种方案具体如下：

方案1在请求路段等待1～3 min，接到乘客；

方案2在请求路段等待1～3 min 后，选择前往下一个路段。

对于某个司机在某一路段的选择可由式（8）表示：

其表达含义是选择最小花费的行驶路段以及等待时间时的方案。因此，对于所有行驶时间小于Tmin，驾驶路段不超过L的候选路径R={R1，R2，…，Rn}，本文的目标是选择1 个花费成本最小的候选路径R*，满足：

3 算法设计

如图1 所示，基于候客点规划的空闲出租车路线推荐方法主要分为3 个步骤：1）进行数据预处理，利用最短路径匹配算法将GPS 轨迹匹配到真实的路网环境中，并依据连续2 个GPS 点之间的距离和时间属性识别可停车路段，将停车时间超过5 min 的路段标记出来；2）根据每个路段发生接载事件的特征，利用改进的多层感知机有效地预测不同天、不同时段以及不同天气情况下的接载概率；3）根据每个路段的接载概率，设计考虑等待时间的最小成本优化路径算法，从而进行有效的路线推荐，实现效益最大化。

图1 出租车路线推荐框架Fig.1 Framework of taxi route recommendation

3.1 路段匹配算法

在实际的数据采集过程中，由于设备的精度误差、路网障碍物、信号强弱因素的影响，GPS 设备采集到的轨迹点往往散落在道路周围而无法匹配到具体的路段上。本文首要解决的问题是为轨迹数据匹配具体的路段，并根据状态位的表示为每个路段统计载客次数和空载次数，具体的算法描述及操作过程如下：

算法1路段匹配

结合实例（如图2）对路段匹配算法1 进行分析。对于待处理轨迹点p2，首先根据路网数据为其划分1 个缓冲区buffe，如图2（a）所示。该缓冲区由当前点p2为中心点，radius 作为半径进行划分。接着找到与该缓冲区相交的所有路段作为p2的候选路段candiSeg（算法1 第5 行）。然后对候选路段candiSeg进行判断：情况1，如果候选路段为空则返回null，匹配失败；情况2，如果只包含一个候选路段则直接返回该路段作为匹配路段（如算法1 第6～9 行所示）；情况3，如果存在多个候选路段，如图2（a）所示，candiSeg={r1，r2，r3}，则继续进行判断。遍历所有候选路段candiSeg，通过最短距离函数finddis 计算出与p2点距离最近的所有路段NearSeg 并判断：情况1，若只包含1 个最近路段则直接返回该路段作为匹配路段（如算法1 第10～14 行所示）；情况2，若存在多个最近路段，如图2（b）所示，nearSeg=｛r1，r2｝，则继续利用最小角度函数findangle 计算与行驶方向夹角最小的路段作为匹配路段（如算法1 第15～17 行所示），如图2（c）所示。最后，返回最佳匹配路段Machsegment=r1，如图2（d）所示。

图2 道路匹配实例Fig.2 Example of road matching

3.2 基于历史数据的接载概率预测

在路线推荐问题中，有效预测不同路段的接载概率非常重要。由于不同位置、不同时段、不同天气等因素的影响，潜在的接载概率不断发生变化。以不同地区为例，图3 分别表示了上海市虹桥机场和上海市南京步行街在不同时刻发生接载事件的情况，从图3（a）可以看出，在上午04：00—08：00 时，有较多乘客选择前往机场，并在机场下车。同一时段也可以发现，从机场选择搭载出租车出行的需求比较少，导致在该时段有大量出租车空闲。因此，即使是机场这样的接载热点，此时的接载概率也非常低。而在晚上20：00 以后情况则刚好相反，该时段内大量乘客到达机场并选择前往市区，接载概率变高，可以将该地区推荐给空闲司机。

图3 不同地区不同时段接载需求变化Fig.3 Changes in pick-up demand over time in different regions

如图3（b）所示，对于商业区来说，供需不平衡主要发生在08：00—12：00，此时前往该地区的乘客较多，离开的人数比较少，可以看出在白天前往商业区的需求比较大，而晚上情况相反，更多的乘客选择从步行街离开，并前往不同的地方。因此，为有效学习这些因素对接载概率的影响，本文构建了一种基于多指标输入的多层感知机模型（Multi-Layer Perceptron Model，MLP）进行接载概率的预测。

针对接载概率预测问题，大多数研究认为接载概率的变化往往与时间序列呈现紧密的关系，并利用传统的多层感知机方法，将单一的时间序列作为输入数据，设计滞后步长并进行接载概率的预测。然而通过前文的实例分析可以发现，影响路段接载概率的因素十分复杂（比如天气、高平峰时段等）。这些复杂的因素与路段的接载概率呈现非线性相关，仅通过自身的时间序列进行建模无法捕捉到真正的变化规律。因此，为提高预测精度，本文将提取多个相关因素如日期属性、天气、高平峰时段、时间间隔、接载数量和空载数量作为模型的输入，然后通过建立一个实时的接载概率预测模型，进行预测与分析。

为合理预测不同路段的接载概率，本文首先对空闲出租车在路段的行驶条件做出相应的假设。假设1：空闲出租车在巡航路段均为单向行驶，不会存在倒车；假设2：空闲出租车不会在同一路段震荡行驶（走走停停）。基于上述假设条件，本文对所选取的因素进行量化处理。比如：日期属性（1 代表工作日、2 代表周末、0 代表国家法定节假日）；天气（-1代表雨天、1 代表晴天、0 代表多云）；高平峰（07：00—10：00 用1 表示、17：00—20：00 用2表示、其余时段用0 表示）；时间间隔（以1min 为间隔划分工作时间段05：00—23：00 共1 140 个间隔）、接载数量（每个间隔内载客次数）、空载数量（每个间隔内空载次数）。将量化后的特征作为模型的输入，模型的输出即为预测不同路段的接载概率。对于感知机模型来说，不同的神经元个数以及不同的激活函数影响着训练模型的复杂程度。本文选取上海市淮海中路这一路段，提取出该路段在30 天内发生接载事件的特征数据，并以其80%的数据作为训练数据，剩余20%作为测试数据。经过多次训练发现，当训练的网络层数选择3 层，神经元的个数选择256，激活函数选择ReLU 时效果最佳。该模型的预测结果如图4 所示，从图中可以看出预测值和真实值的分布较为一致，验证了预测模型的稳定性。

图4 预测结果对比Fig.4 Comparison of forecast results

为进一步验证基于多指标输入的多层感知机模型的性能，本文利用只考虑时间序列的感知机模型作为对比，并使用MAE、MAPE、R2作为指标对预测效果进行评估，结果如表1 所示。由表1 可知，改进后的多层感知机在MAE、MAPE、R2指标上分别提高了0.5%、13%和16%。

表1 预测精度Table 1 Prediction accuracy

3.3 考虑等待时间的路线推荐算法

在3.1 节、3.2 节中对路段数据的处理使每个路段不仅包含了节点的经纬度信息，还包含了历史的接载情况、穿行该路段的距离以及时间。依据这些信息可以利用式（4）和式（8）计算出每个路段的花费成本，然后根据推荐算法推荐效益最好的路线。

算法2考虑等待时间的路线推荐

算法2 描述了考虑等待时间的最小成本推荐方法的伪代码。该算法首先从空闲司机的请求中获取司机所在的当前路段r和当前时间t，并根据所在路段位置和时间信息得到一系列的邻居路段c_rneighbor和当前路段的接载概率p（如算法2 第1～5 行所示）。然后，基于图搜索算法中的广度优先搜索算法策略对当前路段的每个选择（等待时间间隔，路段选择），并计算其潜在的花费成本（如算法2 第6 行所示），选择花费成本最小的方案（等待间隔，路段）作为当前的选择（如算法2 第7～12 行所示）。该过程被不断重复直到推荐的路段长度超过L或者推荐的搜索总时间超过T时，则停止推荐并得出最小成本的推荐路线。

为解释、验证本文提出的算法，下面将通过一个具体实例进行说明。如图5 所示，假设每个路段的行驶时间为30 s，路段的等待间隔为2 min，行驶距离为120 m，其单位时间的租赁费为0.1，汽油费为0.01。当司机在r4路段在上午08：15 发出寻客请求时，由于直接穿行r4和r5路段的花费最小，因此直接到达s6节点时间为上午08：16。此时对于传统推荐算法而言，如果在r5路段未接到乘客，则会继续选择下一个行驶路段。假设选择的行驶路段为r3，此时的花费成本为4.2。而根据式（8）可知，本文推荐的算法在该路段节点选择等待2 min 接载到乘客所花费的成本最小，为1.2。原因是该路段在上午08：18时刻会有公交车到站，出现大量换乘乘客，乘客需求增加，导致该路段的接载概率提高，使得空闲司机更容易接载到乘客。

图5 考虑等待时间的路线推荐案例Fig.5 Route recommendation case considering waiting time

4 实验结果与分析

4.1 实验数据及实验环境

出租车数据：本文所采用的实验数据来自上海10 694 名出租车司机在2015 年4 月1 日—2015 年4 月30 日生成的轨迹数据，其中每条数据的采集频率是10 s，采集内容包含司机编号、位置、时间、速度、状态等，详细信息如表2 所示。

表2 上海市出租车GPS 轨迹数据示例Table 2 Example of GPS trajectories data taxis in Shanghai

从OpenStreetMap 中获取上海市真实道路网络的所有信息，其中包含465 735 个节点和197 758 个路段，并且在处理数据的过程中为每个路段标记其穿行时间、穿行距离和历史接载数据。

本文实验采用的性能评估和分析代码是用python语言编写，并在Intel®CoreTMi5-8250 CPU@1.60 GHz，8 GB内存64 位Windows10 系统上运行。

4.2 对比算法

为评估本文所提算法，采用以下4 种算法作为对比，进一步验证该算法的有效性。

1）MNP 算法。为空闲司机推荐完整路线，通过净利润函数计算每个路段的潜在效益，并分别利用暴力法和递归策略筛选出最佳的推荐路线［5］。

2）InExperience 算法。利用历史轨迹数据计算每个司机的历史收入，把收入最低的前10%的司机作为无经验司机，并选择其空闲时所行驶的路线作为对比。

3）Random 算法。采用随机方式为每种决策编号，并通过随机函数选择路线。

4）WTR 算法。本文提出的基于候客点规划的空闲出租车路线推荐算法。

4.3 对比指标

本文选择提升性能比rimprove作为实验的性能指标，其含义为相比较其他算法所提升的百分比。当获得一个司机请求时，从不同算法推荐路线所需要的花费成本、闲逛时间和闲逛距离3 个方面进行性能验证，计算式如式（10）～式（12）所示：

式（10）表示本文推荐的算法WTR 与对比算法相比，在花费成本这一指标上所改善的性能百分比。式（11）表示本文推荐的WTR 算法相比较对比算法，在闲逛时间这一指标上所改善的性能百分比。式（12）表示本文推荐的WTR 算法相比较对比算法，在闲逛距离这一指标上所改善的性能百分比。

4.4 实验结果

本文首先在上海市淮海中路附近（经度121.457 0°至121.486 8°，纬度31.219 8°至31.230 9°）随机生成规模大小分别为10 个、100 个、1 000 个空闲司机请求数据。然后，对每个司机的请求位置和时间分别利用本文提出的WTR 算法和对比算法进行相应的路线推荐。其中，路段限制参数L和时间限制参数T分别是5 km 和10 min。最后，根据式（10）～式（12）做出相应的计算，对比实验结果如图6 所示。

图6（a）表示空闲司机的推荐数量与推荐路线花费成本之间的实验结果，从图中可以看出本文考虑等待时间因素的推荐算法与算法MNP、InExperence、Random相比均有所提升。其中，当推荐次数为10 时，WTR 算法的花费成本相比较MNP、InExperience、Random 分别减少了44.6%、53.2%、49.45%。当推荐次数为100 时，分别减少了42.3%、51.5%、45.2%；当推荐次数等于1 000 时，分别减少了35.7%、40.1%、41%。对于整体的趋势而言，随着推荐次数的增加，推荐性能的百分比下降，这是因为随着空闲司机的增多，可接载的乘客数量变得越来越少，这对于所有的推荐方法来说都将很难找到乘客，因此推荐成本的差距会变得越来越小。

图6（b）表示空闲司机的推荐数量与推荐路线闲逛时间之间的实验结果，从图中可以看出本文考虑等待时间因素的推荐算法与算法MNP、InExperence 和Random 相比均有所提升。其中当推荐次数为10 时，WTR 算法的闲逛时间与算法MNP、InExperience、Random 相比分别减少了21.2%、33.3%、29.7%；当推荐次数为100 时，分别减少了18.3%、28.5%、12.2%；当推荐次数等于1 000时，分别减少了13.3%、12.2%、12.7%。随着推荐次数的增加，闲逛时间的提升百分比不断下降。这是因为随着乘客需求的减少，任何一种推荐方法都难以接载到乘客，其闲逛时间的差距也会逐渐减小。

图6 实验结果对比Fig.6 Comparison of experimental results

图6（c）表示空闲司机的推荐数量与推荐路线闲逛距离之间的实验结果，从图中可以看出本文提出的推荐算法WRT 与算法MNP、InExperence、Random 相比均有所提升。其中，当推荐次数为10 时，WTR 算法的闲逛距离与算法MNP，InExperience、Random 相比分别减少了41.7%、53%、48%；当推荐次数为100 时，分别减少了43.6%、57.3%、46.4%；当推荐次数为1 000 时，分别减少了46.4%、58.2%、76.1%。对于花费成本和闲逛时间的变化趋势，闲逛距离随着推荐次数的增加呈上升趋势，原因是本文算法考虑了等待时间因素，当推荐次数逐渐增加而乘客需求不断减少时，任何一种推荐方法都难以接到乘客。不同于MNP、InExperience、Random算法，本文所提算法在这种情况下更多选择了停留等待的决策来减少行驶距离所带来的成本。

由以上分析可以得出，本文所提基于候客点规划的空闲出租车路线推荐算法通过考虑某些路段的等待因素，可以让空闲司机更快地接载到乘客，从而减少司机的闲逛时间和闲逛距离，提高出租车的运输效率。

5 结束语

现有的空闲司机路线推荐算法在考虑真实路网环境时忽略了路段可等待因素，导致所推荐的路线花费成本较高。为此，本文提出一种基于候客点规划的空闲出租车路线推荐算法。通过处理出租车轨迹数据及统计每个路段的历史接载信息，将轨迹点与真实路段进行匹配，并利用改进的多层感知机对出租车的接载概率进行建模。此外，在考虑路段可等待因素的基础上设计一种路线推荐算法。在真实的上海出租车轨迹数据集上的实验结果表明，相较于MNP、InExperence、Random 等算法，本文所提算法在花费成本、巡航时间以及巡航距离方面均有明显减少。下一步将通过研究司机的目的地偏好，在本文工作基础上为空闲司机设计个性化的推荐机制。