1.一种基于历史数据的汽车行驶轨迹及里程预测方法,其特征在于,主要包括以下步骤:
步骤一:利用GPS设备获取汽车的历史行驶轨迹数据,并对该数据做相应预处理,形成历史行驶轨迹数据库,具体过程如下:(1)利用GPS设备以采样间隔τ采集汽车每次行驶过程中行驶轨迹上的GPS数据点;将汽车每一次行驶过程中采集的GPS数据点都按照时间先后顺序排列则得到若干条行驶轨迹,将这些行驶轨迹记为原始历史行驶轨迹,并以CSV的文件格式保存为原始历史行驶轨迹数据;原始历史行驶轨迹数据包含每个GPS数据点的位置信息;用Pi表示某一条原始历史行驶轨迹中第i个GPS数据点,i=1,2,…,n,n是该原始历史行驶轨迹中GPS数据点的总数,所述位置GPS数据点的位置信息包括:汽车在i点处的经度xi、汽车在i点处的纬度yi、汽车到达i点处的时刻ti、汽车在i点的速度vi;用(xi,yi)表示汽车在Pi数据点位置处的位置坐标;
(2)由于GPS设备受到干扰时可能产生个别异常GPS数据点,因此需剔除异常GPS数据点,方法如下:按时间先后顺序依次取一条原始历史行驶轨迹上每两个相邻的GPS数据点Pi和GPS数据点Pi+1,两个GPS数据点对应的位置信息分别为:xi、yi、ti、vi和xi+1、yi+1、ti+1、vi+1;根据式(1)计算两个GPS数据点的距离ΔDi;根据式(2)和式(3)计算汽车在Pi数据点的位置时,在时间差ti+1-ti内可能行驶的实际最大距离ΔDi-max;若ΔDi≤ΔDi-max,则判断GPS数据点Pi+1不是异常点,则继续比较下两个相邻的GPS数据点,即GPS数据点Pi+1和GPS数据点Pi+2,以此类推;
Vi-max=max{vi,vi+1} 式(2)
ΔDi-max=Vi-max×(ti+1-ti) 式(3)
其中,ti+1-ti=τ;
若ΔDi>ΔDi-max,则判断GPS数据点Pi+1是异常点,并剔除该GPS数据点Pi+1后,则GPS数据点Pi+2即成为GPS数据点Pi相邻的数据点,则式(1)按照式(2)按照Vi-max=max{vi,vi+2}、式按照ΔDi-max=Vi-max×(ti+2-ti)计算,以此类推,其中ti+2-ti=2τ;
将剔除了异常GPS数据点的原始历史行驶轨迹记为历史行驶轨迹,并保存为历史行驶轨迹数据;
(3)计算历史行驶轨迹的里程:用Tj表示第j条历史行驶轨迹,j=1,2,3,…,m,m为历史行驶轨迹的总条数;则用式(4)计算得到该历史行驶轨迹Tj的总里程Sj;
用PIj表示历史行驶轨迹Tj中的第Ij个GPS数据点,则Nj表示历史行驶轨迹Tj中GPS数据点的总数,Ij=1,2,3,…,Nj;(xIj+1,j,yIj+1,j)表示历史行驶轨迹Tj中的第Ij+1个GPS数据点处的位置坐标,(xIj,j,yIj,j)表示历史行驶轨迹Tj中的第Ij个GPS数据点处的位置坐标;
根据式(4)计算得到每条历史行驶轨迹的总里程,并记录在历史行驶轨迹数据中;建立用T={T1,T2,T3,…,Tj,…,Tm}表示的包含m条历史行驶轨迹的历史行驶轨迹数据库;
步骤二:基于路径聚类算法对历史行驶轨迹数据库中的每条历史行驶轨迹进行起点聚类和关键点的挖掘,形成聚类结果;
(1)起点聚类:在一条历史行驶轨迹中的第一个GPS数据点即为起点,用起点集O={O1,O2,…,Om}表示历史行驶轨迹数据库中每条历史轨迹的起点;起点集O中每条历史行驶轨迹的起点对应的位置坐标集为{(x1,1,y1,1),(x1,2,y1,2),…,(x1,m,y1,m)};将历史行驶轨迹数据库T中的历史行驶轨迹两两进行起点对比;用(x1,j,y1,j)表示第j条历史行驶轨迹Tj的起点的位置坐标,用(x1,k,y1,k)表示第k条历史行驶轨迹Tk的起点的位置坐标,k=1,2,3,…,m,且k≠j;
Ⅰ.若进行起点对比的两条历史行驶轨迹Tj和Tk都未聚类,则根据式(5)计算该两条历史行驶轨迹起点的距离ΔTj_k:选择合适的聚类阈值ΔT′,取ΔT′=1~10m;若ΔTj_k≤ΔT′,则表明历史行驶轨迹Tj和Tk起点匹配成功,将这两条历史行驶轨迹归为同一类;若ΔTj_k>ΔT′,则说明历史行驶轨迹Tj和Tk起点匹配不成功,则将历史行驶轨迹Tj和Tk分别归为不同类;
Ⅱ.若进行起点对比的两条历史行驶轨迹Tj和Tk中,历史行驶轨迹Tk已经聚类,则根据式(6)计算历史行驶轨迹Tj的起点与已经聚类的历史行驶轨迹Tk所在类中所有历史行驶轨迹起点的算术平均值的距离:用(x1,ave-X,y1,ave-X)表示已经聚类的历史行驶轨迹Tk所在类中所有历史行驶轨迹的起点位置坐标的算术平均值;X是用以区分不同聚类的类别字符;
若ΔTj_ave-X≤ΔT′,则表明历史行驶轨迹Tj和历史行驶轨迹Tk所在类的起点匹配成功,将历史行驶轨迹Tj也归为历史行驶轨迹Tk所在类;若ΔTj_ave-X>ΔT′,则说明历史行驶轨迹Tj和历史行驶轨迹Tk所在类的起点匹配不成功,则将历史行驶轨迹Tj归为历史行驶轨迹Tk所在类以外的另一类;
将历史行驶轨迹数据库T中的每条历史行驶轨迹都完成聚类,即将每条历史行驶轨迹都被归为某类;
(2)对聚为同一类的历史行驶轨迹进行关键点挖掘:依次将同一类的每条历史行驶轨迹两两对比进行关键点挖掘;若历史行驶轨迹Ta和历史行驶轨迹Tb为任意两条同一类历史行驶轨迹,关键点挖掘的计算为式(7)和式(10);ΔTkey为进行关键点挖掘的计算的两条历史行驶轨迹Ta和Tb上的两个GPS数据点之间的距离,即为历史行驶轨迹Ta上的第u个GPS数据点与历史行驶轨迹Tb上的第q个GPS数据点之间的距离;
其中,u=1,2,…,Na;q=1,2,…,Nb;Na为历史行驶轨迹Ta的GPS数据点的总数,Nb为历史行驶轨迹Tb的GPS数据点的总数;
用Sa,u表示历史行驶轨迹Ta中从起点开始行驶至第u个GPS数据点位置时的里程,用式(8)计算得到;用Sb,q表示历史行驶轨迹Tb中从起点开始行驶至第q个GPS数据点位置时的里程,用式(9)计算得到;
由式(10)可计算得到进行关键点挖掘的计算的两条历史行驶轨迹Ta和Tb上的两个GPS数据点位置处的里程差ΔSkey;
ΔSkey=Sa,u-Sb,q 式(10)
关键点选取条件为:条件一:ΔTkey>ΔTk′ey;条件二:|ΔSkey|≤ΔSk′ey;其中ΔTk′ey为根据道路车道宽度设置的距离阈值,ΔTk′ey=δ×D,δ为系数,取δ=0.7~1.4,D为车道宽度;ΔSk′ey为设置的里程差阈值,ΔSk′ey=3~5m;
则对历史行驶轨迹Ta和Tb进行关键点挖掘的过程如下:从历史行驶轨迹Ta的第一个GPS数据点起的GPS数据点均分别与历史行驶轨迹Tb的第一个GPS数据点起的GPS数据点依次进行关键点挖掘的计算;当历史行驶轨迹Ta的第u个GPS数据点与历史行驶轨迹Tb的第q个GPS数据点进行关键点挖掘的计算时:Ⅰ.若计算结果不满足关键点选取条件的条件一,则历史行驶轨迹Ta的第u个GPS数据点继续与历史行驶轨迹Tb的下一个GPS数据点进行关键点挖掘的计算;
Ⅱ.若计算结果满足关键点选取条件的条件一,再判断是否满足关键点选取条件的条件二:①若计算结果不满足关键点选取条件的条件二:(a)此时若里程差ΔSkey≥0,则历史行驶轨迹Ta的第u个GPS数据点继续与历史行驶轨迹Tb的下一个GPS数据点进行关键点挖掘的计算;(b)若里程差ΔSkey<0,则历史行驶轨迹Ta的下一个GPS数据点继续与历史行驶轨迹Tb的第一个GPS数据点起的GPS数据点依次进行关键点挖掘的计算;②若计算结果满足关键点选取条件的条件二,则历史行驶轨迹Ta的该GPS数据点和历史行驶轨迹Tb的该GPS数据点分别选取为历史行驶轨迹Ta和历史行驶轨迹Tb上的关键点,历史行驶轨迹Ta的该GPS数据点和历史行驶轨迹Tb的该GPS数据点之后的GPS数据点不再进行关键点挖掘的计算;
基于关键点挖掘的计算再将历史行驶轨迹Ta与同类的其他所有历史行驶轨迹进行关键点挖掘,可以得到历史行驶轨迹Ta的所有关键点;通过上述过程将同类的每一条历史行驶轨迹与其他所有历史行驶轨迹进行关键点挖掘,可得到该类每条历史轨迹上的所有关键点;将起点聚类结果和关键点挖掘结果更新至历史行驶轨迹数据库;
步骤三:基于关键点建立预测模型,以实现汽车行驶轨迹预测和行驶里程预测;具体过程如下:
(1)汽车行驶轨迹预测:基于历史行驶轨迹数据库及关键点建立预测模型;在起点位置匹配的前提下,将候选预测轨迹中的历史行驶轨迹用以构建预测模型;
候选预测轨迹定义为汽车本次出行中经起点识别或关键点识别后的所有可能行驶的历史行驶轨迹;
若候选预测轨迹共有r个关键点,某个关键点可用kg表示,g=1,2,3,…,r,P(kg,h)为关键点概率矩阵M中的元素,表示汽车本次行驶到达关键点kg,下一个到达的关键点为关键点kh的转移概率,h=1,2,3,…,r;
则可建立关键点概率矩阵M:
且
其中, 为候选预测轨迹中经过关键点kg的轨迹数目, 为候选预测轨迹中在关
键点kg处下一个经过的关键点是关键点kh的轨迹数目;
最终关键点为一条历史行驶轨迹中的最后一个关键点,历史行驶轨迹中的最终关键点所在路段即为该历史行驶轨迹的终点所在路段;
根据贝叶斯定理,若汽车本次出行的行驶轨迹为候选预测轨迹Tc,可得关键点kg为最终关键点的后验概率P(d=kg|Tc)为:其中,P(d=kg)表示kg为行驶轨迹的最终关键点的先验概率,m=1,2,3,…,r;
即: 其中,N为候选预测轨迹的总数目,N(d=kg)为行驶
轨迹中最终关键点是kg的历史行驶轨迹数目;
P(Tc|d=kg)表示当关键点kg为行驶轨迹的最终关键点,且汽车本次出行的行驶轨迹为候选预测轨迹Tc的条件概率,表达式为:式中若候选预测轨迹Tc为所经过的关键点为k1,k2,…,kf,f=1,2,…,r,则
表示将候选预测轨迹Tc上的所有关键点的转移概率值相乘;
式中 表示从当前所在关键点kl到关键点kg且途中经过z个关键点的z步转移概
率, 表示从候选预测轨迹Tc的起点到关键点kg且途中经过v个关键点的v步转移概率;z=1,2,3,…,r;v=1,2,3,…,r即:
若关键点kg实际上不是历史行驶轨迹的最终关键点,则根据上述过程计算得到的P(d=kg|Tc)将等于0;
将后验概率作为本次出行预测输出的概率,即本次出行预测关键点kg为最终关键点的概率Q(kg):Q(kg)=P(d=kg|Tc);
将候选预测轨迹中每个关键点为最终关键点的概率按式(11)计算得到概率集Q={Q(k1),Q(k2),…,Q(kg),…,Q(kr)},概率集Q中的非零概率为汽车本次出行的行驶轨迹为候选预测轨迹中的每条历史行驶轨迹的概率,即为每条候选预测轨迹的概率;
选择概率集Q中概率最大的关键点为预测的最终关键点,即:Qdes=max{Q(k1),Q
(k2),…,Q(kg),…,Q(kr)};则预测该关键点即为汽车本次行驶的最终关键点,根据最终关键点的含义从而得到该最终关键点所在历史行驶轨迹的终点所在路段,并得出目的地,将该条历史行驶轨迹作为汽车本次出行预测的行驶轨迹;
(2)行驶里程预测:根据预测出的汽车本次出行的行驶轨迹,由历史行驶轨迹数据库获取该条行驶轨迹的里程作为本次预测的最大可能行驶里程Sdes;并根据概率集Q中的非零概率可得汽车本次出行的行驶轨迹为候选预测轨迹中的每条历史行驶轨迹的概率,即为每条候选预测轨迹的概率,由历史行驶轨迹数据库可获取每条候选预测轨迹的里程,将每条候选预测轨迹的概率乘以对应的候选预测轨迹的里程,并进行求和得到本次出行的综合行驶里程Save:将最大可能行驶里程Sdes和综合行驶里程Save都作为本次出行预测的结果;
步骤四:汽车本次出行开始时,通过GPS设备获取当前起点的位置信息,并根据历史行驶轨迹数据库预测汽车本次出行行驶轨迹及里程;具体过程为:(1)汽车本次出行起点在线识别:汽车本次出行开始时,通过GPS设备获取汽车本次出行起点的位置信息,汽车本次出行起点的位置坐标用(xc,yc)表示,与已经聚类的某类中所有历史行驶轨迹的起点位置坐标的算术平均值(x1,ave-X,y1,ave-X)按式(14)进行起点距离计算:选择阈值ΔTc′,取ΔTc′=1~10m;若ΔTc≤ΔTc′,即表示汽车本次出行起点位置与该类历史行驶轨迹的起点位置相匹配,该类的所有历史行驶轨迹即选为候选预测轨迹;若ΔTc>ΔTc′,表明汽车本次出行起点位置与该类历史行驶轨迹的起点位置不匹配,则按照式(14)与聚类结果的其他类历史行驶轨迹的起点位置坐标的平均值进行起点距离计算;若没有符合ΔTc≤ΔTc′的一类历史行驶轨迹,则本次出行不进行预测,但记录本次出行轨迹,并将汽车本次出行起点位置产生新的起点类别,出行结束时记录为历史行驶轨迹;
(2)行驶轨迹及里程预测:根据步骤三中基于关键点建立的预测模型,结合选出的候选预测轨迹,得到汽车本次出行起点位置时预测的行驶轨迹;同时进行汽车本次出行的行驶里程预测,得到汽车本次出行预测的行驶里程和综合行驶里程;
步骤五:汽车行驶过程中,基于关键点对当前行驶轨迹进行识别,每经过一个关键点时动态更新候选预测轨迹;具体过程如下:将汽车本次出行行驶轨迹所经过的GPS数据点依次与候选预测轨迹的关键点进行计算;汽车本次出行行驶轨迹所经过的GPS数据点的位置点坐标用(xl,yl)表示,汽车本次出行行驶轨迹所要识别的关键点的位置点坐标用(xkey,ykey)表示,按式(15)和式(16)计算当前位置GPS数据点与关键点的距离ΔTl,以及汽车本次出行从起点行驶至当前位置GPS数据点的里程Sl和该历史行驶轨迹中从起点到该关键点的里程Skey之差ΔSl:ΔSl=Sl-Skey 式(15)
可根据道路宽度选择合适的阈值ΔTl′,ΔT′=δ×D,δ为系数,取δ=0.7~1.4,D为车道宽度,ΔSl为里程差阈值,ΔSl=3~5m;当且仅当ΔTl≤ΔTl′且|ΔSl|≤ΔSl′时,判断当前位置点与该关键点重合,则剔除不包含该关键点的其余历史行驶轨迹,该关键点所在的历史行驶轨迹更新为候选预测轨迹;同时根据所述步骤三建立的预测模型,得到新的行驶轨迹预测结果及里程预测结果;
汽车本次行驶过程中,每经过一个关键点都动态更新候选预测轨迹,并得到新的行驶轨迹预测结果及里程预测结果;
步骤六:不断重复步骤四,直至汽车本次出行经过行驶轨迹上的所有关键点并到达终点,完成汽车本次出行的行驶轨迹预测及里程预测;并将汽车本次出行的行驶轨迹记录为历史行驶轨迹,更新至历史行驶轨迹数据库。
2.根据权利要求1所述的一种基于历史数据的汽车行驶轨迹及里程预测方法,其特征在于,所述关键点指的是可以代表行驶轨迹位置及决定行驶走向的特征点,其特征在于,关键点是通过所述权利要求1中步骤二的关键点挖掘的方法选取的,关键点位置出现在当前方出现多条分叉路径时,每条分叉路径上距离路口中心点最近,且又恰好能与其他分叉路径有所区分的特征点处,用于判断汽车出行行驶过程中当行驶至路口出现多条路径时,当前行驶轨迹所选择的路径,也表明汽车当前行驶位置所在路段。
3.根据权利要求1所述的一种基于历史数据的汽车行驶轨迹及里程预测方法,其特征在于,所述的采样间隔τ的取值范围为0.5~2,单位为秒。