一种基于混合交通模式的出行路线推荐方法

摘要

本发明公开了一种基于混合交通模式的出行路线推荐方法，首先根据出租车和共享单车系统的历史行程数据，离线训练得到时间和站点状态预测模型，然后对于用户的在线请求，根据其步行意愿和骑车意愿构建一个混合交通模式网，同时设计行程时间比较算法，在混合交通模式网中结合之前训练得到的预测模型，得到推荐给用户的最快路径及相应的交通模式，最后根据基于行程时间经验风险的评价标准估计推荐路线的可信度。与现有的方法相比，本发明能够缓解乘车用户在出发点或目的地遇到的交通拥挤对行程时间的不利影响，为用户推荐最快的移动路线及相应的交通方式，并且在给出推荐结果的同时，给出该推荐路线的可信度评价。

说明书

技术领域

本发明属于出行路线规划技术领域，具体涉及一种基于混合交通模式的出行路线推荐方法的设计。

背景技术

近年来，GPS定位系统的发展与普及，使得为用户实时规划出行路线成为可能，不可否认，出行路线推荐已经成为了人们日常出行中不可或缺的一部分。出行路线推荐对用户出行来说是一个非常重要且有挑战性的问题，尤其是当城市交通进入上下班车流量高峰时刻，如果能够提前知道路段之间的行程时间就能够更好的规避交通拥挤路段，以达到减少行程时间，缓解城市交通压力的效果。

由于能够按需满足用户的出行需求以及在线预定客户端(如滴滴打车)的普及，出租车已经成为了人们日常生活中最重要的交通工具之一，其行程时间和交通状况息息相关的特性(路线交通状况越不好，用户花费的时间往往越多)使得为用户推荐行程时间最少路径成为一个研究难点。现有的基于出租车的出行路线推荐技术根据历史行程数据提前规避行程中的交通拥挤路段，尽可能的避免用户陷入交通拥挤，从而减少行程时间，缓解交通压力。但是，尽管能够提前规避行程的中间路段的交通拥挤，对于行程开始或结束遇到的交通拥挤，这些研究并没有给出好的解决方案。除此之外，对于推荐结果，现有技术只给出推荐的路线及对应的预测行程时间，而没有给出推荐的可信度。

共享单车(有桩)作为一种便捷的、绿色的新兴公共交通工具，越来越受到人们的欢迎。在共享单车系统中，用户能够在任意的单车站点租/还单车，极大的方便了人们的日常出行。研究表明，共享单车受交通状况影响较少，相较于出租车，共享单车往往能够花费更少的时间通过拥挤路段，但是对于长距离行程，共享单车的优势就很小了。

发明内容

本发明的目的是为了解决现有的基于出租车的出行路线推荐技术未考虑行程开始或结束遇到的交通拥挤情况，推荐结果并不准确，并且没有给出推荐的可信度的问题，提出一种基于混合交通模式的出行路线推荐方法，基于用户当前的地理位置和时间信息，为用户推荐最符合用户意愿的出行路线以及对应的交通方式，并给出该推荐的可信度评价。

本发明的技术方案为：一种基于混合交通模式的出行路线推荐方法，包括以下步骤：

S1、采集用户所在地区的出租车历史行程记录数据、共享单车历史行程记录数据以及单车站点状态历史记录数据。

S2、根据出租车历史行程记录数据，采用随机森林算法训练出租车行程时间预测模型，预测未来一个设定时间段内任意时刻乘坐出租车在用户所在地区任意两个位置之间的行程时间，得到出租车行程时间预测结果。

S3、根据共享单车历史行程记录数据，采用随机森林算法训练共享单车行程时间预测模型，预测未来一个设定时间段内任意时刻骑行共享单车在用户所在地区任意两个单车站点之间的行程时间，得到共享单车行程时间预测结果。

S4、根据单车站点状态历史记录数据，采用随机森林算法训练单车站点状态预测模型，预测未来一个设定时间段内任意时间槽用户能否在任意单车站点得到可用的单车或停车位，得到租车站点状态预测结果和还车站点状态预测结果。

S5、获取用户的查询请求数据。

S6、根据查询请求数据构建混合交通模式网，并根据出租车行程时间预测结果、共享单车行程时间预测结果、租车站点状态预测结果和还车站点状态预测结果，在混合交通模式网中采用行程时间比较算法得到行程时间最少的路线，将该路线及其预测行程时间和交通方式推荐给用户。

S7、根据推荐给用户的路线的预测行程时间，结合实时的行程记录，采用基于行程时间经验风险的评估函数计算得到推荐路线的可信度，并将其发送给用户。

进一步地，步骤S2包括以下分步骤：

S21、从出租车历史行程记录数据中提取出发点、目的地、一周的哪一天、小时、分钟、是否假期以及行程距离作为特征输入基于随机森林的出租车行程时间预测模型，将行程时间作为预测结果，并且使用均方差作为损失函数对出租车行程时间预测模型进行训练。

S22、采用训练好的出租车行程时间预测模型预测未来一个设定时间段内任意时刻乘坐出租车在用户所在地区任意两个位置之间的行程时间，得到出租车行程时间预测结果。

进一步地，步骤S3包括以下分步骤：

S31、从共享单车历史行程记录数据中提取出发点、目的地、一周的哪一天、小时、分钟、是否假期以及行程距离作为特征输入基于随机森林的共享单车行程时间预测模型，将行程时间作为预测结果，并且使用均方差作为损失函数对共享单车行程时间预测模型进行训练。

S32、采用训练好的共享单车行程时间预测模型预测未来一个设定时间段内任意时刻骑行共享单车在用户所在地区任意两个单车站点之间的行程时间，得到共享单车行程时间预测结果。

进一步地，步骤S4包括以下分步骤：

S41、将一天划分为144个时间槽，其中每个时间槽为10分钟。

S42、从单车站点状态历史记录数据中提取单车站点位置、时间槽、一周的哪一天、小时、是否节假日以及前一个时间槽的可用单车数量作为特征输入基于随机森林的单车站点状态预测模型，将时间槽的可用单车数量作为预测结果，并且使用均方差作为损失函数对单车站点状态预测模型进行训练。

S43、采用训练好的单车站点状态预测模型预测得到未来一个设定时间段内任意时间槽任意单车站点的可用单车数量。

S44、根据未来一个设定时间段内任意时间槽任意单车站点的可用单车数量计算得到租车站点状态预测结果和还车站点状态预测结果，计算公式为：

其中为租车站点状态预测结果，其值为1时表示单车站点b_i在t时刻有可用的共享单车供用户使用，其值为0时表示单车站点b_i在t时刻没有可用的共享单车供用户使用；为还车站点状态预测结果，其值为1时表示单车站点b_i在t时刻有可用的停车位供用户使用，其值为0时表示单车站点b_i在t时刻没有可用的停车位供用户使用；a_i表示单车站点b_i预测的可用单车数量，d_i表示单车站点b_i总的桩的数量，η为预测阈值。

进一步地，步骤S5中用户的查询请求数据包括用户的出发点p.o、目的地p.d、步行意愿参数p.w和骑行意愿参数p.k。

进一步地，步骤S6包括以下分步骤：

S61、在以用户的出发点p.o为圆心，步行意愿参数p.w为半径的圆内遍历单车站点，根据租车站点状态预测结果判断该步骤遍历的每个单车站点是否有可用的共享单车供用户使用，若是则设置一条从用户的出发点p.o到租车站点b_a的步行路线，进入步骤S62，否则直接进入步骤S62。

S62、在以用户的出发点p.o为圆心，骑行意愿参数p.k为半径的圆内遍历单车站点，根据还车站点状态预测结果判断该步骤遍历的每个单车站点是否有可用的停车位供用户使用，若是则设置一条从租车站点b_a到还车站点b_b的单车骑行路线，进入步骤S63，否则直接进入步骤S63。

S63、在以用户的目的地p.d为圆心，步行意愿参数p.w为半径的圆内遍历单车站点，根据还车站点状态预测结果判断该步骤遍历的每个单车站点是否有可用的停车位供用户使用，若是则设置一条从还车站点b_d到目的地p.d的步行路线，进入步骤S64，否则直接进入步骤S64。

S64、在以用户的目的地p.d为圆心，骑行意愿参数p.k为半径的圆内遍历单车站点，根据租车站点状态预测结果判断该步骤遍历的每个单车站点是否有可用的共享单车供用户使用，若是则设置一条从租车站点b_c到还车站点b_d的单车骑行路线，进入步骤S65，否则直接进入步骤S65。

S65、在用户的出发点p.o、目的地p.d以及所有单车站点两两之间均设置一条乘坐出租车路线。

S66、根据出租车行程时间预测结果、共享单车行程时间预测结果以及步行路线的时间，采用行程时间比较算法得到用户的出发点p.o到目的地p.d之间行程时间最少的路线，将该路线及其预测行程时间和交通方式推荐给用户。

进一步地，步骤S66中步行路线的时间t₁的计算公式为：

其中d表示步行路线起点到终点的曼哈顿距离，v_步为用户的预测步行速度。

进一步地，步骤S7中推荐路线的可信度CON的计算公式为：

其中t_pi→pi+1表示从位置节点pi到位置节点pi+1预测花费的时间，δ_pi→pi+1表示从位置节点pi到位置节点pi+1实际花费的时间，n为推荐路线的位置节点总数，E(·)表示期望，Δy_pi→pi+1表示所有用户经过路段pi→pi+1的时间误差均值。

其中N为不同时间槽经过路段pi→pi+1的用户数量，Δy_j,pi→pi+1表示用户j经过路段pi→pi+1时预测花费时间和实际花费时间的误差值，Var(·)表示方差，E²(Δy_pi→pi+1)表示误差均值的平方。

本发明的有益效果是：

(1)本发明创新性的将共享单车与出租车相结合，设计了一个基于混合交通模式的路线推荐方法，能够找到最快的行程路线以及对应的交通模式。

(2)本发明采用基于随机森林算法的预测模型对行程时间和单车站点状态进行预测，预测结果准确有效。

(3)本发明通过构建混合交通模式网形式化用户的出行路线选择，并根据行程时间比较算法寻找最佳路线，能够缓解乘车用户在出发点或目的地遇到的交通拥挤对行程时间的不利影响，为用户推荐最快的移动路线及相应的交通方式。

(4)本发明通过基于行程时间经验风险的评估函数对推荐路线的可信度进行评价，并将评价结果反馈给用户，能够为用户推荐最符合用户意愿且最合理的出行路线。

附图说明

图1所示为本发明实施例提供的一种基于混合交通模式的出行路线推荐方法流程图。

图2所示为本发明实施例提供的基于随机森林算法的行程时间预测示意图。

图3所示为本发明实施例提供的混合交通模式网示意图。

图4所示为本发明实施例提供的共享单车行程时间预测模型对比示意图。

图5所示为本发明实施例提供的不同方法行程时间对比示意图。

具体实施方式

现在将参考附图来详细描述本发明的示例性实施方式。应当理解，附图中示出和描述的实施方式仅仅是示例性的，意在阐释本发明的原理和精神，而并非限制本发明的范围。

本发明实施例提供了一种基于混合交通模式的出行路线推荐方法，如图1所示，包括以下步骤S1～S7：

S1、采集用户所在地区的出租车历史行程记录数据、共享单车历史行程记录数据以及单车站点状态历史记录数据。

本发明实施例中，出租车历史行程记录数据和共享单车历史行程记录数据均包括出发点、目的地、出发时间及到达时间，单车站点状态历史记录数据包括记录产生时刻及该时刻站点的可用单车数量(每个单车站点的总的车桩数量是固定的)。

S2、根据出租车历史行程记录数据，采用随机森林算法训练出租车行程时间预测模型，预测未来一个设定时间段内任意时刻乘坐出租车在用户所在地区任意两个位置之间的行程时间，得到出租车行程时间预测结果。

步骤S2包括以下分步骤S21～S22：

S21、如图2所示，从出租车历史行程记录数据中提取出发点、目的地、一周的哪一天(周几)、小时、分钟、是否假期以及行程距离作为特征输入基于随机森林的出租车行程时间预测模型，将行程时间作为预测结果，并且使用均方差(MSE)作为损失函数对出租车行程时间预测模型进行训练。

随机森林算法是一种集成学习方法，训练的时候使用有放回的随机抽样生成多个决策树，在预测阶段，通过考虑所有随机树的预测结果来得到最终的输出。

S22、采用训练好的出租车行程时间预测模型预测未来一个设定时间段内任意时刻乘坐出租车在用户所在地区任意两个位置之间的行程时间，得到出租车行程时间预测结果。

S3、根据共享单车历史行程记录数据，采用随机森林算法训练共享单车行程时间预测模型，预测未来一个设定时间段内任意时刻骑行共享单车在用户所在地区任意两个单车站点之间的行程时间，得到共享单车行程时间预测结果。

步骤S3包括以下分步骤S31～S32：

S31、如图2所示，从共享单车历史行程记录数据中提取出发点、目的地、一周的哪一天(周几)、小时、分钟、是否假期以及行程距离作为特征输入基于随机森林的共享单车行程时间预测模型，将行程时间作为预测结果，并且使用均方差作为损失函数对共享单车行程时间预测模型进行训练。

S32、采用训练好的共享单车行程时间预测模型预测未来一个设定时间段内任意时刻骑行共享单车在用户所在地区任意两个单车站点之间的行程时间，得到共享单车行程时间预测结果。

S4、根据单车站点状态历史记录数据，采用随机森林算法训练单车站点状态预测模型，预测未来一个设定时间段内任意时间槽用户能否在任意单车站点得到可用的单车或停车位，得到租车站点状态预测结果和还车站点状态预测结果。

步骤S4包括以下分步骤S41～S44：

S41、将一天划分为144个时间槽，其中每个时间槽为10分钟。

S42、从单车站点状态历史记录数据中提取单车站点位置、时间槽、一周的哪一天(周几)、小时、是否节假日以及前一个时间槽的可用单车数量作为特征输入基于随机森林的单车站点状态预测模型，将时间槽的可用单车数量作为预测结果，并且使用均方差作为损失函数对单车站点状态预测模型进行训练。

S43、采用训练好的单车站点状态预测模型预测得到未来一个设定时间段内任意时间槽任意单车站点的可用单车数量。

S44、根据未来一个设定时间段内任意时间槽任意单车站点的可用单车数量计算得到租车站点状态预测结果和还车站点状态预测结果，计算公式为：

其中为租车站点状态预测结果，其值为1时表示单车站点b_i在t时刻有可用的共享单车供用户使用，其值为0时表示单车站点b_i在t时刻没有可用的共享单车供用户使用；为还车站点状态预测结果，其值为1时表示单车站点b_i在t时刻有可用的停车位供用户使用，其值为0时表示单车站点b_i在t时刻没有可用的停车位供用户使用；a_i表示单车站点b_i预测的可用单车数量，d_i表示单车站点b_i总的桩的数量，η为预测阈值。

预测得到单车站点可用单车数量后，因为单车站点中总的桩的数量是固定的，所以也能得到可用停车位数量。虽然随机森林算法是较好的机器学习算法，但是因为单车站点的状态受多方面因素的影响，如天气、周围的活动等，因此单车站点状态预测模型不能够准确的估计单车站点中可用单车的数量，因此本发明实施例中通过计算该站点对用户是否可用的参数和这样就能较为准确的计算站点的可用性，能够有效预测在未来一段时间内的任意时间槽，用户能否在任意单车站点得到可用的单车或停车位。

S5、获取用户的查询请求数据。

本发明实施例中，用户的查询请求数据包括用户的出发点p.o、目的地p.d、步行意愿参数p.w和骑行意愿参数p.k。其中步行意愿参数p.w表示用户愿意从出发点p.o或目的地p.d步行的距离，骑行意愿参数p.k表示用户愿意从出发点p.o或目的地p.d骑行的距离，步行意愿参数p.w和骑行意愿参数p.k均由用户自己设置(不设置为默认参数)。

S6、根据查询请求数据构建混合交通模式网(HTMN)，并根据出租车行程时间预测结果、共享单车行程时间预测结果、租车站点状态预测结果和还车站点状态预测结果，在混合交通模式网中采用行程时间比较算法(TTCA)得到行程时间最少的路线，将该路线及其预测行程时间和交通方式推荐给用户。

步骤S6包括以下分步骤S61～S66：

S61、在以用户的出发点p.o为圆心，步行意愿参数p.w为半径的圆内遍历单车站点，根据租车站点状态预测结果判断该步骤遍历的每个单车站点是否有可用的共享单车供用户使用，若是则设置一条从用户的出发点p.o到租车站点b_a的步行路线，进入步骤S62，否则直接进入步骤S62。

例如，如图3所示，范围内单车站点b₁有可用的共享单车供用户使用，则设置一条从用户的出发点p.o到租车站点b₁的步行路线。

S62、在以用户的出发点p.o为圆心，骑行意愿参数p.k为半径的圆内遍历单车站点，根据还车站点状态预测结果判断该步骤遍历的每个单车站点是否有可用的停车位供用户使用，若是则设置一条从租车站点b_a到还车站点b_b的单车骑行路线，进入步骤S63，否则直接进入步骤S63。

例如，如图3所示，范围内单车站点b₂和b₃均有可用的停车位供用户使用，则分别设置一条从租车站点b₁到还车站点b₂和b₃的单车骑行路线。

S63、在以用户的目的地p.d为圆心，步行意愿参数p.w为半径的圆内遍历单车站点，根据还车站点状态预测结果判断该步骤遍历的每个单车站点是否有可用的停车位供用户使用，若是则设置一条从还车站点b_d到目的地p.d的步行路线，进入步骤S64，否则直接进入步骤S64。

例如，如图3所示，范围内单车站点b₅有可用的停车位供用户使用，则设置一条从还车站点b₅到目的地p.d的步行路线。

S64、在以用户的目的地p.d为圆心，骑行意愿参数p.k为半径的圆内遍历单车站点，根据租车站点状态预测结果判断该步骤遍历的每个单车站点是否有可用的共享单车供用户使用，若是则设置一条从租车站点b_c到还车站点b_d的单车骑行路线，进入步骤S65，否则直接进入步骤S65。

例如，如图3所示，范围内单车站点b₄有可用的共享单车供用户使用，则设置一条从租车站点b₄到还车站点b₅的单车骑行路线。

S65、在用户的出发点p.o、目的地p.d以及所有单车站点两两之间均设置一条乘坐出租车路线，即完成混合交通模式网的构建，如图3所示。

在图3所示的一个有向网络图中，从出发点p.o到目的地p.d的每一条路径都能作为一条可达路线，其中，这里的路线是由有序的位置节点表示的，如p.o→b₁→b₂→b₄→b₅→p.d。单车站点之间的路线可以通过A*算法确定，位置节点之间的出租车路线可以通过T-drive等算法确定。可以看到，如果出发点p.o陷入了交通拥挤，用户可以先骑车或步行离开交通拥挤区域，然后在交通状况良好的地方乘坐出租车；如果目的地p.d陷入了交通拥挤，用户可以在目的地附近下车，然后骑车或步行前往目的地。

S66、根据出租车行程时间预测结果、共享单车行程时间预测结果以及步行路线的时间，采用行程时间比较算法得到用户的出发点p.o到目的地p.d之间行程时间最少的路线，将该路线及其预测行程时间和交通方式推荐给用户。

例如，对于路线p.o→b₁→b₂→p.d，从用户的查询请求数据中能够知道用户的出发时间，根据该时间可以计算得到用户从出发点p.o步行到达单车站点b₁的时间t₁：

其中d表示步行路线起点到终点的曼哈顿距离，v_步为用户的预测步行速度。

然后计算用户到达b₁时，该站点的可用单车数量，如果可用，用户在此取车，骑车前往b₂，根据共享单车行程时间预测结果能够得到用户从b₁到达b₂的时间t₂，同时判断该站点在用户到达时是否有可用停车位，如果没有，该条路径对用户来说是不可行的，同理可以得到用户乘坐出租车从b₂到达目的地p.d的时间t₃。然后将各个时间花费相加，可以得到用户在路径p.o→b₁→b₂→p.d的行程时间t₁+t₂+t₃，以及对应的交通方式——步行+共享单车+出租车。

S7、根据推荐给用户的路线的预测行程时间，结合实时的行程记录，采用基于行程时间经验风险的评估函数计算得到推荐路线的可信度，并将其发送给用户。

得到推荐给用户的路线之后，本发明实施例使用基于行程时间经验风险的评估函数(Empirical Risk of Travel Time，ERTT)评价推荐路线的可信度。假设推荐路线为P：p1→p2→p3→…→pn，预测花费时间为T_P，实际花费时间为δ_P，则可信度因子CON可表示为：

CON＝E(δ_P-T_P)²

其中T_P＝t_p1→p2+t_p2→p3+…+t_pn-1→pn，δ_P＝δ_p1→p2+δ_p2→p3+…+δ_pn-1→pn，则：

CON＝E(t_p1→p2+t_p2→p3+…+t_pn-1→pn-δ_p1→p2-δ_p2→p3-…-δ_pn-1→pn)²

因为不同路段的行程时间是相互独立的，则有：

其中t_pi→pi+1表示从位置节点pi到位置节点pi+1预测花费的时间，δ_pi→pi+1表示从位置节点pi到位置节点pi+1实际花费的时间，E(·)表示期望，Δy_pi→pi+1表示所有用户经过路段pi→pi+1的时间误差均值。

其中N为不同时间槽经过路段pi→pi+1的用户数量，Δy_j,pi→pi+1表示用户j经过路段pi→pi+1时预测花费时间和实际花费时间的误差值，Var(·)表示方差，E²(Δy_pi→pi+1)表示误差均值的平方。很明显，路径的估计行驶时间的可信度可以通过历史数据中对应的误差的方差和均值来衡量。可信度因子CON越小，该时间段路径预测时间的可靠性就越高。

下面通过具体实验例对本发明的效果作进一步描述。

本实验例运行在一个3.6GHZ、i7CPU、8GB RAM的单核服务器上。从NYC taxi、芝加哥出租车网站、Citibike及divvybike官方网站分别下载了2016年4月1日到5月31日的出租车行程记录和共享单车系统数据作为数据集。

首先验证基于随机森林算法(Random Forest，RF)的共享单车行程时间预测模型，如图4所示。其中，以MAE(均方差)作为评价标准，图4展示了MAE随着训练数据大小变化的改变。对比模型分别是ANNs(Artificial Neural Networks)和AdaBoost(AdaptiveBoosting)，实线表示在纽约数据集上(表示为NY)，虚线表示在芝加哥数据集上(表示为CG)。很明显，训练数据在训练集中的占比越大，模型的效果越好，而且选择的RF模型要好于另外两个。

如图5所示，不同方法的平均行程时间随着行程距离的变化。在出租车行程记录上执行本发明的算法，可以看到，本发明比只乘坐出租车和只骑行共享单车的出行方法花费的行程时间要少，说明本发明在出发点或者目的地是交通拥挤状态的时候是有效的。

本领域的普通技术人员将会意识到，这里所述的实施例是为了帮助读者理解本发明的原理，应被理解为本发明的保护范围并不局限于这样的特别陈述和实施例。本领域的普通技术人员可以根据本发明公开的这些技术启示做出各种不脱离本发明实质的其它各种具体变形和组合，这些变形和组合仍然在本发明的保护范围内。