一种基于位置预测的潜在共乘群体识别方法

摘要

本发明提出一种在车主的行驶路径基础上，选择匹配的潜在共乘群体的方法，利用字典树来处理基于矩阵处理的预测模型存在的空间复杂度高的问题，利用逃逸机制合理的处理了零频率问题；本此基础上合理的融入关联规则，增强了位置间的联系，缩小了候选位置集合的数量，提高了算法运行效率，更进一步提高了位置预测的精确度。提出的在车主最优行驶路线的基础上进行乘客选择，既重视了车主的意愿，又满足了乘客的要求。

说明书

技术领域

本发明属于车辆共乘领域，具体涉及一种基于位置预测的潜在共乘群体识别方法。

背景技术

共乘，即车辆合乘匹配。车辆共乘匹配问题，是指车主与搭乘顺风车的乘客双方达成一定的约定，车主愿意让乘客搭乘自己驾驶的车辆行驶，并在双方认为合适的地方让乘客下车，共乘产生的费用由乘客(包括车主)分摊的出行方式。1982年，Daganzo第一次开始提出“共乘”的思想，解决在网络中均衡交通流分配问题，虽然他的假设理论并没有成功，但通过这一次尝试，正式开启了车辆共乘在科学发展中的序幕。

车辆共乘首先要做的的是匹配乘客，选择合适的乘客，一般来说有一下几种类型：

(1)完全匹配共乘：指车主和乘客的起点和终点都相同，这种匹配程度最高。

(2)基本匹配共乘：乘客与车主的起点相同，而乘客的终点包含在车主的行驶路径中，或者乘客的终点与车主相同，而乘客的起点包含在车主的行驶路径中，还有就是乘客的起点和终点都包含在车主的行驶路径中。

(3)不完全匹配共乘：指乘客的起点或终点与车主不同，有一定的偏离。

存在的问题有：

一般的基于矩阵实现的马尔可夫位置预测模型存在空间复杂度高和数据零频率的问题；

传统的位置预测模型都面临着算法运行效率低、耗时长的问题；

车辆共乘问题的求解方法一般都是先选择乘客，再选择车主行驶路线，该方案往往因为过于重视乘客选择，而使车主原来的行驶路线出现很大的偏离，忽略了车主的意愿。

发明内容

针对现有技术存在的不足，本发明提供了一种基于位置预测的潜在共乘群体识别方法。

具体通过如下技术方案予以实现：

一种基于位置预测的潜在共乘群体识别方法，本方法是对行驶路径为Lo->Ld的车主识别潜在共乘群体，其中Lo为起点位置，Ld为终点位置；

包括如下步骤：

步骤一、将所有乘客的所有停留点，以及每个停留点对应的时间窗进行存储；

步骤二、从步骤一的结果中筛选出时间窗为[t₁－Δt,t₁+Δt]，出现在起点区域D_o的乘客，得到初始共乘乘客集合R，R＝R₁，R₂，R₃，…，将R中每个初始共乘乘客时间窗为[t₁-Δt,t₄+Δt]的所有停留点进行存储；其中，[t₁,t₂]为Lo对应的时间窗，[t₃,t₄]为Ld对应的时间窗，t₁和t₂均属于0-24h，t₃和t₄均属于0-24h，Δt大于零且小于t₁与t₂的时间差，车主的最大绕远距离为ΔL，D_o为以Lo为圆心，ΔL为半径的圆；

步骤三、对R中每个初始共乘乘客时间窗为[t₁-Δt,t₄+Δt]的所有停留点建立2阶字典树，并分别将R中每个初始共乘乘客的所有停留点按天进行存储

步骤四、利用关联规则，找出R中每个初始共乘乘客的停留点满足最小支持度为0.1的频繁二项集；

步骤五、从步骤四得到的R₁的频繁二项集中依次找出与L_1α满足最小支持度为0.1的停留点，将其列入候选位置集合L′_1β，并计算L_1α和L′_1β中每个停留点的置信度C，其中L_1α为初始共乘乘客R₁当前所处的停留点，L′_1β为初始共乘乘客R₁停留点中与L_1α构成频繁二项集的停留点集合；

步骤六、若L′_1β中的停留点属于L′_1b，则共乘概率P计算公式如下：

其中，L′_1b为2阶字典树中第一阶为L_1Δ、第二阶为L_1α的第三阶的停留点集合，L_1Δ为R1当前停留点的前一个停留点，N(L_1Δ>1α>1b)为字典树中满足第一阶是L_1Δ第二阶是L_1α且第三阶属于集合L′_1b的停留点的个数，

∑N(L_1ΔL_1αL′_1b)为字典树中满足第一阶是L_1Δ、第二阶是L_1α、且第三阶属于集合L′_1b的所有停留点的个数总和，|∑L_1ΔL_1α|为L′_1b中停留点的种类个数；

对于L′_1β中不属于L′_1b的停留点，则共乘概率P计算公式如下：

∑N(L_1αL′_1α）为字典树中第一阶是L_1α、第二阶属于集合L′_1α的所有停留点的个数总和，N(L_1αL′_1β)为字典树中第一阶为L_1α、第二阶属于集合L′_1β的停留点的个数，|∑L_1α|为L′_1α中停留点的种类个数；

步骤七、计算L′_1β中的所有停留点的预测位置概率Pz，Pz＝0.6*P+0.4*C，取Pz的最大值对应的停留点作为初始共乘乘客R₁的预测终点位置；

步骤八、重复步骤五至步骤七，分别计算R中其余初始共乘乘客的预测终点位置；

步骤九、筛选R中预测终点位置属于终点区域D_d的初始共乘乘客作为潜在共乘群体，终点区域D_d为以Ld为圆心，ΔL为半径的圆。

与现有技术相比，本发明具有以下技术效果：

(1)本发明采用部分匹配预测方法——PPM算法。PPM预测算法利用字典树来处理基于矩阵处理的预测模型存在的空间复杂度高的问题，利用逃逸机制合理的处理了零频率问题。

(2)本发明在PPM算法的基础上合理的融入关联规则，增强了位置间的联系，缩小了候选位置集合的数量，提高了算法运行效率，更进一步提高了位置预测的精确度；同时解决了位置概率分布均匀时仅仅使用PPM算法无法准确做预测的问题。

(3)本发明提出在车主最优行驶路线的基础上进行乘客选择，既重视了车主的意愿，又满足了乘客的要求。

(4)本发明提出的潜在共乘群体识别方法，是基于乘客的历史轨迹，根据历史轨迹预测候选乘客和车主在同一时间段的起点和终点位置是否一样，如果一样或者接近，则这个候选乘客就可以作为潜在共乘对象。不同于实时共乘匹配，本文更注重于对共乘的预先性规划，以便让车主和潜在共乘者对自己的出行提前做安排。

(5)本发明提出的基于位置预测的潜在共乘群体识别方法也可以用于共乘需求预测，即根据乘客历史的轨迹来预测未来是否有共乘需求，如果有，则可以对共乘进行预先性规划。

附图说明

图1为本发明R₁第一天的历史停留点存储形成的2阶字典树。

下面结合附图和具体实施方式对本发明的方案作进一步详细地解释和说明。

具体实施方式

本发明研究的共乘对象是一定数量的潜在乘客，例如，他们每天来往于公寓与上班地点之间，这类共乘具有需求相对稳定的特点，可以进行预先性规划。所以本发明针对这类活动轨迹有规律且相对稳定的乘客，提出了基于位置预测的潜在共乘群体识别方法。当车主提出他某天某个时间段要从A去C时，系统会自动的为该车主推荐最优的潜在共乘群体，让车主可以提前知道和他共乘的乘客的信息，共乘乘客也可以了解车主的信息，达成共识后，就可以实现共乘，从而减轻了乘客的出行费用，一定程度上减少了汽车尾气的排放，节约了能源、降低了空气污染和噪音污染，实现了低碳环保出行。

本发明的停留点即活动地点，两个停留点之间的距离即为一次出行行为，所有乘客及车主每一天都有很多个停留点，例如从家到公司，每个停留点都有对应的时间窗，本发明先将所有乘客的一段时间的所有停留点，以及每个停留点的时间窗进行存储，最终选取在特定时间窗与车主的行驶路径起点相同或相近(最终均从起点位置集合出发)、并且乘客的预测终点位置概率最大且出现在终点区域的乘客作为潜在共乘群体。

本发明中，L_1α、L′_1β、L′_1b、L_1Δ等表达式中的下标1代表初始共乘乘客为R₁，其中的Δ、α、β、b等代表的是R₁不同的停留点，若是初始共乘乘客为R₂，则相应变为L_2α、L'_2b、L_2Δ等。

本发明的Δt为一个时间段，最终从[t₁－Δt,t₁+Δt]时间段中选取满足要求的初始共乘乘客，当Δt的取值不同时，确定的初始共乘乘客集合会发生变化，考虑到共乘时间的较为精确性，本发明的Δt取值在10-20min，以下的实施例以Δt取值为10min为例说明。

实施例1

一种基于位置预测的潜在共乘群体识别方法，车主的行驶路径为Lo->Ld，其中Lo为起点位置，Ld为终点位置，Lo对应的时间窗为[t₁,t₂]，Ld对应的时间窗为[t₃,t₄]，t₁、t₂、t₃、t₄均属于0-24h，车主可接受的最大绕远距离为ΔL，起点区域D_o为以Lo为圆心，ΔL为半径的圆，该圆内的点都认为属于车主的起点位置，终点区域D_d为以Ld为圆心，ΔL为半径的圆，该圆内的点都认为属于车主的终点位置。

在车主的行驶路径基础上，选择匹配的潜在共乘群体，具体方法如下：

步骤一、将所有乘客的历史轨迹中的所有停留点，以及每个停留点对应的时间窗进行存储；

步骤二、从步骤一的结果中筛选出时间窗为[t₁－10,t₁+10]，出现在D_o区域的乘客，即出发时间前后差最多10min，得到初始共乘乘客R1，R2，R3，…；

步骤三、对R1，R2，R3，…分别建立时间窗为[t₁-10,t₄+10]的所有停留点的2阶字典树，并分别将R1，R2，R3，…每个乘客历史轨迹中的所有停留点按天进行存储，

假设车主发布一条信息，明天早上8:00-9:00要从L1前往L4，人们一般都不愿意绕路，所以这里拟定的路线自定义为最优行驶路径，首先遍历所有乘客的历史轨迹，找出在[7:50-8:10]时间段的出现在L1区域的乘客，列为初始候选乘客；然后为这些初始候选乘客建立[7:50-9:10]这个时间段的所有停留点的2阶字典树，每个乘客历史轨迹中的所有停留点按天进行存储；

以R₁为例，形成如下所示的活动轨迹：

Day1:L₁₁…L₁₂…L₁₃…L₁₁…L₁₄…L₁₁…L₁₅…L₁₁…L₁₂…L₁₃…L₁₁

Day2:L₁₂…L₁₃…L₁₁…L₁₃…L₁₄…L₁₅…L₁₆…L₁₉…L₁₁…L₁₇

Day3:L₁₃…L₁₆…L₁₇…L₁₈…L₁₂…L₁₁…L₁₃…L₁₅

Day4:L₁₁…L₁₃…L₁₅…L₁₆…L₁₇…L₁₆…L₁₇…L₁₈…L₁₂…L₁₁

Day5:L₁₂…L₁₁…L₁₇…L₁₆…L₁₃…L₁₇…L₁₈…L₁₉…L₁₁₀…L₁₈…L₁₂…L₁₁

Day6:L₁₄…L₁₅…L₁₆…L₁₁…L₁₃…L₁₄…L₁₇…L₁₈…L₁₂…L₁₄

Day7:L₁₂…L₁₄…L₁₆…L₁₇…L₁₆…L₁₂…L₁₃…L₁₁

……

R₁每个停留点位置为L_1i，i＝1,2,3……为不同的停留点编号，停留点即活动地点，本申请认为两个停留点之间的距离即为一次出行行为，例如L₁₂…L₁₆代表R₁从停留点L₁₂行驶到了停留点L₁₆，且认为用户都是乘车出行。Day2这一行代表该用户R₁在Day2这一天的活动轨迹。

定义字典树的阶数为2，图1为R₁第一天的历史停留点存储形成的2阶字典树，左框为停留点位置，右框为该停留点在该条路径上出现的次数。

步骤四、利用关联规则，找出R1，R2，R3，…中停留点满足最小支持度为0.1的频繁二项集；

步骤五、依次找出L_1α和R1的每个停留点满足最小支持度为0.1的停留点位置，将其列入候选位置集合L′_1β，并计算L_1α和候选位置集合L′_1β中每个停留点的置信度C，

其中，L_1α为初始共乘乘客R1当前所处的停留点位置，L′_1β为初始共乘乘客R1停留点中与L_1α构成频繁二项集的停留点位置集合；

步骤六、若L′_1β中的某个停留点位置属于位置集合L′_1b，则共乘概率P计算公式如下：

其中，L′_1b为2阶字典树中第一阶为L_1Δ、第二阶为L_1α的第三阶的位置集合，L_1Δ为乘客1当前停留点位置的前一个停留点位置，N(L_1Δ>1α>1b)为字典树中满足第一阶是L_1Δ第二阶是L_1α且第三阶属于集合L′_1b的某个停留点的个数，∑N(L_1ΔL_1αL′_1b)为字典树中满足第一阶是L_1Δ、第二阶是L_1α、且第三阶属于集合L′_1b的所有停留点的个数总和，|∑L_1ΔL_1α|为L′_1b中停留点的种类个数；

若L′_1β中的某个停留点位置不属于位置集合L′_1b但属于位置集合L′_1β，则共乘概率P计算公式如下：

∑N(L_1αL′_1α)为字典树中第一阶是L_1α、第二阶属于集合L′_1α的所有停留点的个数总和，N(L_1αL′_1β)为字典树中第一阶为L_1α、第二阶属于集合L′_1β的停留点的个数，|∑L_1α|为L′_1α中停留点的种类个数；

步骤七、计算L′_1β中的所有停留点的预测位置概率Pz，Pz＝0.6*P+0.4*C取Pz的最大值对应的停留点作为初始共乘乘客R1的预测终点位置；

步骤八、重复步骤五至步骤七，分别计算R2、R3、……的预测终点位置；

步骤九、筛选R1，R2，R3，…中预测终点位置属于D_d的乘客作为潜在共乘群体。

实施例2

本实施例提供一种基于位置预测的潜在共乘群体识别方法，假设用户1的历史轨迹为：

L₁₁、L₁₂、L₁₃

L₁₁、L₁₄

L₁₁、L₁₅、L₁₁

L₁₂、L₁₃、L₁₁

预测这条轨迹之后用户即将去的地方，先将这条轨迹输入到2阶字典树中，形成图1。从这条拟定的轨迹可以看出，最后一个停留位置L₁₁为用户当前所在位置，即为本申请中的L_1α；最后一个停留位置L₁₁的前一个位置为L₁₃，即为本申请中的L_1Δ。计算在当前位置L₁₁之后用户1会去的位置，

首先计算与L₁₁满足大于最小支持度0.1的位置:

L₁₁与L₁₂的支持度为：2/4＝0.5

L₁₁与L₁₃的支持度为：2/4＝0.5

L₁₁与L₁₄的支持度为：1/4＝0.25

L₁₁与L₁₅的支持度为：1/4＝0.25

在本实施例中，L₁₂、L₁₃、L₁₄、L₁₅与L₁₁支持度都大于0.1，所以L₁₂、L₁₃、L₁₄、L₁₅都列为候选位置集合。

其次计算各候选位置与L₁₁的置信度：

L₁₁与L₁₂的置信度：2/4＝0.5

L₁₁与L₁₃的置信度：2/4＝0.5

L₁₁与L₁₄的置信度：1/4＝0.25

L₁₁与L₁₅的置信度：1/4＝0.25

依次计算每个候选位置作为下一个预测位置的概率。

假设用户将去位置L₁₄，则计算公式如下：

从字典树中可以得出N(L_1Δ>1α>1b)，也就是N(L₁₃L₁₁L₁₄)的个数为1；|∑L_1ΔL_1α|，也就是|∑L₁₃L₁₁|，字典树中L₁₃L₁₁之后只有位置L₁₄一种，所以值为1；∑N(L_1ΔL_1αL′_1b)，在字典树中，L₁₃L₁₁之后只有位置L₁₄，且个数为1，所以值为1。

因为L₁₁与L₁₄的置信度为0.25，所以L₁₄作为预测位置的最终概率为

Pz＝0.5*0.6+0.25*0.4＝0.4

假设用户将去位置L₁₅，则计算公式如下：

从字典树中可以得出|∑L_1ΔL_1α|，也就是|∑L₁₃L₁₁|，字典树中L₁₃L₁₁之后只有位置L₁₄一种，所以值为1；∑N(L_1ΔL_1αL′_1b)，在字典树中，L₁₃L₁₁之后只有位置L₁₄，且个数为1，所以值为1；N(L_1αL′_1β)，也就是N(L₁₁L₁₅)，在字典树中找出第一阶是L₁₁第二阶是L₁₅的个数，值为1；|∑L_1α|，在字典树中找出第一阶是L₁₁，第二阶的位置种类个数，L₁₁之后有L₁₂、L₁₄、L₁₅三种位置，即为3；∑N(L_1αL′_1α)，在字典树中找出满足第一阶是L₁₁的所有轨迹的个数，在这里有L₁₁L₁₂、L₁₁L₁₄、L₁₁L₁₅，个数分别为2、1、1，所以总共有4个，值为4。

因为L₁₁与L₁₅的置信度为0.25，所以L₁₅作为预测位置的最终概率为:

Pz＝0.071*0.6+0.25*0.4＝0.1426

可以看出，这个用户将去L₁₄的概率较大，则这个用户的预测终点位置为L₁₄。以上述方法依次计算其余每个初始候选乘客的预测位置的最终概率，找出概率最大值对应的停留点作为对应用户的预测终点位置，最后再找出预测终点位置属于Dd的乘客作为潜在共乘群体。