1.一种快速车载GPS轨迹精确地图匹配的方法,其特征在于,包括以下步骤:S1、获取任一车辆的GPS经过的若干个GPS轨迹点,并对所述若干个GPS轨迹点进行初始化操作,得到有效GPS轨迹点列表VP={vp(1),vp(2),…,vp(k)};
S2、在所述有效GPS轨迹点列表VP={vp(1),vp(2),…,vp(k)}中,以首点vp(1)至末点vp(k)建立地图匹配工作循环,并根据所述地图匹配工作循环,利用以GPS轨迹点导向的最短路径搜索算法得到首点vp(1)至末点vp(k)的最佳地图匹配路径;
S3、由末点vp(k)回溯所述最佳地图匹配路径,遍历获取沿途各GPS轨迹点的最佳匹配结果,并汇总输出匹配结果统计表;
S4、根据所述匹配结果统计表,判断匹配中途是否存在由地图匹配工作循环引起的中断点,若是,则输出首点vp(1)至中断点vp(s)的匹配结果,并返回步骤S2,否则,完成快速车载GPS轨迹精确地图的匹配。
2.根据权利要求1所述的快速车载GPS轨迹精确地图匹配的方法,其特征在于,所述步骤S1包括以下步骤:
S101、获取任一车辆的GPS经过的若干个GPS轨迹点;
S102、将所述若干个GPS轨迹点分离为分段集合Trip(a)={T1,T2,…,Ta,…,Tn},其中,Ta表示一个分段,且所述Ta分段内包括多个GPS轨迹点,Tn表示总分段数;
S103、从分段Ta内的多个GPS轨迹点{ p(1),p(2),…,p(i),…,p(n)}中任选一个GPS轨迹点p(i)作为当前GPS轨迹点,其中,p(n)表示总的GPS轨迹点;
S104、判断所述当前GPS轨迹点p(i)至p(i+1)的直线速度是否大于300km/h,若是,则剔除当前GPS轨迹点p(i),转入下一个GPS轨迹点p(i+1),并重复步骤S104,否则,进入步骤S105;或
判断所述当前GPS轨迹点p(i)与p(i+1)的间隔时间是否小于等于0,若是,则剔除当前GPS轨迹点p(i),转入下一个GPS轨迹点p(i+1),并重复步骤S104,否则,进入步骤S105;
S105、设当前GPS轨迹点的上一累计行驶距离变量为p(i).lastD;
S106、判断所述p(i).lastD是否小于20米,若是,则计算得到GPS轨迹点p(i‑1)至p(i)的距离,并剔除GPS轨迹点p(i),并进入步骤S107,否则,所述p(i).lastD大于20米,并将当前GPS轨迹点p(i)= vp(l)纳入有效节点列表VP={vp(1),vp(2),…,vp(k)},并进入步骤S107;
S107、判断分段Ta内是否所有的GPS轨迹点均被作为当前GPS轨迹点,若是,则建立有效GPS轨迹点列表VP={vp(1),vp(2),…,vp(k)},并获取所述GPS轨迹点列表VP={vp(1),vp(2),…,vp(k)}中各GPS轨迹点k在地图数据中的待匹配邻近连接线集合NearL(k),并初始化匹配结果变量Match(k)=‑1,最佳匹配权重MatchW(k)=10000,完成有效GPS轨迹点列表VP={vp(1),vp(2),…,vp(k)}的建立,并进入步骤S2,否则,返回步骤S101。
3.根据权利要求1所述的快速车载GPS轨迹精确地图匹配的方法,其特征在于,所述步骤S2包括以下步骤:
S201、在所述有效GPS轨迹点列表VP={vp(1),vp(2),…,vp(k)}中,以首点vp(1)至末点vp(k)建立地图匹配工作循环;
S202、根据所述地图匹配工作循环,设有效GPS列表VP={vp(1),vp(2),…,vp(k)}的起始节点为Startp,终止节点为Endp;
S203、判断所述起始节点Startp是否小于等于终止节点Endp,若是,则进入步骤S204,否则,起始节点Startp大于终止节点Endp,完成GPS轨迹的全部匹配,得到首点vp(1)至末点vp(k)的最佳地图匹配路径,并进入步骤S3;
S204、利用以GPS轨迹点导向的最短路径搜索算法搜索起始节点Startp至终止节点Endp的最短路径,并判断最短路径搜索的迭代过程是否结束,若是,则获取备选路径,并进入步骤S3,否则,重复步骤S204,直至最短路径搜索迭代完成。
4.根据权利要求3所述的快速车载GPS轨迹精确地图匹配的方法,其特征在于,所述步骤S204包括以下步骤:
S2041、对所述起始节点Startp进行匹配变量初始化处理,所述匹配变量包括上一起始节点Lastp等于起始节点Startp、当前最远匹配节点Pnow、已修改路网节点集NList、搜索打开节点集OpenL、对应搜索前进参考变量集OpenValueL、搜索结束路网节点集CloseL以及起点邻近路网连接线集NearL(Startp);
S2042、对所述起点邻近路网连接线集NearL(Startp)中各连接线建立地图匹配工作循环;
S2043、判断各连接线是否满足出发条件,若是,则将各连接线的对应端点纳入所述搜索打开节点集OpenL,并分别更新所述对应搜索前进参考变量集OpenValueL、已修改路网节点集NList以及更新各连接线对应前向搜索端点s的搜索属性集Search(s),且当循环结束时,所述搜索打开节点集OpenL不为空集,进入步骤S2044;否则,对所述起始节点Startp选取邻近匹配值最大的连接线作为该点匹配结果,并更新起始节点Startp等于起始节点Startp+1,并返回步骤S202,其中,所述端点搜索属性集Search(s)包括端点出发截断成本集StartCut(s)、路径物理成本集SPcost(s)、局部截断成本集LOCcost(s)、GPS轨迹点加权成本集PWcost(s)、对应轨迹标号集ValidN(s)、局部轨迹增量集Padd(s)以及途径连接线集SPvia(s);
S2044、对所述搜索打开节点集OpenL中各路网搜索前向搜索端点s建立迭代,并判断所述迭代的结束条件是否为搜索打开节点集OpenL已为空集,若是,则获取备选路径,并进入步骤S3,否则,进入步骤S2045;
S2045、选取所述搜索打开节点集OpenL中首个前向搜索端点s开展搜索,分别获取对应轨迹标号ValidN(s)以及前向搜索端点s的对应搜索前进参考变量OpenValueL值OpenValueL.begin,并判断所述对应轨迹标号ValidN(s)是否大于起始节点Startp‑1,若是,则从搜索打开节点集OpenL以及对应前向搜索端点s的首个对应搜索前进参考变量集OpenValueL中剔除前向搜索端点s及其对应的前进变量HeadDist,并进入步骤S2046,否则,进入步骤S2048;
S2046、若所述对应轨迹标号ValidN(s)小于终止节点Endp,且所述对应轨迹标号ValidN(s)小于当前最远匹配节点Pnow,则计算得到前进判断距离Jdist,并进入步骤S2047;或
若所述对应轨迹标号ValidN(s)小于终止节点Endp,且所述局部轨迹增量Padd(s)=0,则计算得到前进判断距离Jdis,并进入步骤S2047;
S2047、判断前向搜索端点s的对应搜索前进参考变量的值OpenValueL(s)是否大于2*前进判断距离Jdist,且前进判断距离Jdist大于200米,若是,则返回步骤S2045,否则,进入步骤S2048;或
判断所述前向搜索端点s的对应搜索前进参考变量的值OpenValueL(s)是否大于400米且前进判断距离Jdist小于等于200米,若是,则返回步骤S2045,否则,进入步骤S2048;
S2048、对当前搜索前向搜索端点s各前向连接线集合ForwardL建立循环,并提取前向连接线u及下一路网节点n(u),当途径连接线集SPvia(s)不为空集时,若前向搜索端点s途径连接线集SPvia(s)的最后一个元素SPvia(s).last等于前向连接线u时,跳至前向连接线集合ForwardL下一连接线,并继续计算前向连接线u与GPS轨迹点vp(ValidN(s))运动方向夹角MoveAng(u);
S2049、判断所述运动方向夹角MoveAng(u)是否大于等于100度,若是,则跳至前向连接线集合ForwardL中下一前向连接线u,并返回步骤S2048,否则,将前向连接线u按运动方向夹角MoveAng(u)从小到大顺序插入拓展连线集NextL,并在循环结束后进入步骤S20410;
S20410、对拓展连线集NextL中元素建立前向搜索循环,提取前向连接线u及下一路网节点n(u),并初始化局部GPS轨迹点加权变量PWac=0、已匹配GPS轨迹点序号Sernow=对应轨迹标号ValidN(s)、局部增量匹配点数AddN=0以及掉头指示变量TurnIndi=false;
S20411、当已匹配GPS轨迹点序号Sernow小于终止节点Endp时,初始化迭代指示变量Indi=true,并建立前向轨迹匹配增益,判断迭代结束条件是否为迭代指示变量Indi=false,若是,则进入步骤S20412,否则,进入步骤S20415;
S20412、令已匹配GPS轨迹点序号Sernow为已匹配GPS轨迹点序号Sernow+1,在GPS轨迹点vp(Sernow)邻近连线集NearL(Sernow)中搜索前向连接线u,并判断前向连接线u是否不在GPS轨迹点vp(Sernow)邻近连线集NearL(Sernow)中,若是,则进入步骤S20413,否则,前向连接线u在GPS轨迹点vp(Sernow)邻近连线集NearL(Sernow)中,并进入步骤S20414;或令已匹配GPS轨迹点序号Sernow为已匹配GPS轨迹点序号Sernow+1,在GPS轨迹点vp(Sernow)邻近连线集NearL(Sernow)中搜索前向连接线u,并判断已匹配GPS轨迹点序号Sernow等于终止节点Endp时,迭代结束条件是否为迭代指示变量Indi=false,若是,则进入步骤S20413,否则,前向连接线u在GPS轨迹点vp(Sernow)邻近连线集NearL(Sernow)中,并进入步骤S20414;
S20413、判断局部增量匹配点数AddN是否等于0,若是,则进入步骤S20415,否则,则局部增量匹配点数AddN大于0,并进入步骤S20416;
S20414、分别令局部增量匹配点数AddN为局部增量匹配点数AddN+1,以及计算得到局部GPS轨迹点加权变量PWac,且若GPS轨迹点存在掉头,则掉头指示变量TurnIndi=true,迭代指示变量Indi=false;当局部增量匹配点数AddN=0,则进入步骤S20415;并判断局部增量匹配点数AddND是否大于0,若是,则进入步骤S24021,否则,返回步骤S20412;其中,所述局部GPS轨迹点加权变量PWac的表达式如下:PWac=PWac+(Sernow).Weight(u)式中,PWac表示局部GPS轨迹点加权变量,vp(Sernow).Weight(u)表示GPS轨迹点vp;
S20415、当前向搜索端点s大于起始节点Startp时,判断前向连接线u的前向端点n(u)的对应轨迹标号集ValidN(n(u))集合是否为空集,若是,则进入步骤S20416,否则,进入步骤S20417;
S20416、计算得到局部搜索成本Costnow,并在前向连接线u的前向端点n(u)的局部截断成本集LOCcost(n(u))末尾插入元素局部搜索成本Costnow,在前向连接线u的前向端点n(u)的途径连接线集SPvia(n(u))末尾插入前向连接线u,在前向连接线u的前向端点n(u)的局部轨迹增量集Padd(n(u))末尾插入元素0,在前向连接线u的前向端点n(u)的路径物理成本集SPcost(n(u))末尾插入元素,在前向连接线u的前向端点n(u)的GPS轨迹点加权成本集PWcost(n(u))末尾插入元素,在已修改路网节点集NList末尾插入n(u),并进入步骤S20419,其中,所述局部搜索成本Costnow的表达式如下:Costnow=LOCcost(s).last+Length(u)式中,LOCcost(s).last表示前向搜索端点s局部截断成本集的最后一个元素,Length(u)表示前向连接线u的长度;
S20417、判断前向连接线u的前向端点n(u)对应轨迹标号集的最后一个元素ValidN(n(u)).last是否等于前向搜索端点s对应轨迹标号集的最后一个元素ValidN(s).last,若是,则进入步骤S20418,否则,前向连接线u的前向端点n(u)对应轨迹标号集的最后一个元素ValidN(n(u)).last小于前向搜索端点s对应轨迹标号集的最后一个元素ValidN(s).last,并进入步骤S20419;
S20418、根据前向连接线u的前向端点n(u)对应轨迹标号集的最后一个元素ValidN(n(u)).last计算得到匹配路径成本Cost1,以及根据计算得到前向连接线u的前向端点n(u)对应轨迹标号集的最后一个元素ValidN(n(u)).last,若匹配路径成本Cost1小于匹配路径成本Cost2,则计算得到前向连接线u的前向端点n(u)局部截断成本集的最后一个元素LOCcost(n(u)).last,并令前向连接线u的前向端点n(u)途径连接线集的最后一个元素SPvia(n(u)).last等于前向连接线u,令前向连接线u的前向端点n(u)局部轨迹增量集的最后一个元素Padd(n(u)).last=0,以及计算得到前向连接线u的前向端点n(u)路径物理成本集最后一个元素SPcost(n(u)).last以及令前向连接线u的前向端点n(u)GPS轨迹点加权成本集的最后一个元素PWcost(n(u)).last等于前向搜索端点s的GPS轨迹点加权成本集的最后一个元素PWcost(s).last,并进入步骤S20420,其中,所述匹配路径成本Cost的表达式如下:
Cost1=SPcost(s).last+Length(u)+PWcost(s).last式中,SPcost(s).last表示前向搜索端点s路径物理成本集的最后一个元素,Length(u)表示前向连接线u的长度,PWcost(s).last表示前向搜索端点s的GPS轨迹点加权成本集的最后一个元素;
所述匹配路径成本Cost2的表达式如下:
Cost2=SPcost(n(u)).last+PWcost(n(u)).last式中,SPcost(n(u)).last表示前向连接线u的前向端点n(u)路径物理成本集最后一个元素,PWcost(n(u)).last表示前向连接线u的前向端点n(u)GPS轨迹点加权成本集的最后一个元素;
所述前向连接线u的前向端点n(u)局部截断成本集的最后一个元素LOCcost(n(u)).last的表达式如下:
LOCcost(n(u)).last=LOCcost(s).last+Length(u)式中,LOCcost(s).last表示,前向搜索端点s局部截断成本集的最后一个元素,Length(u)表示前向连接线u的长度;
SPcost(n(u)).last=SPcost(s).last+Length(u)式中,SPcost(s).last表示前向搜索端点s路径物理成本集的最后一个元素,Length(u)表示前向连接线u的长度;
S20419、根据前向搜索端点s局部截断成本集的最后一个元素LOCcost(s).last 以及前向连接线u的长度Length(u)计算得到前进变量HeadDist,并分别在前向连接线u的前向端点n(u)的局部截断成本集LOCcost(n(u))末尾插入前进变量HeadDist,在前向连接线u的前向端点n(u)的途径连接线集SPvia(n(u))末尾插入前向连接线u,在前向连接线u的前向端点n(u)的局部轨迹增量集Padd(n(u))末尾插入0,在前向连接线u的前向端点n(u)的对应轨迹标号集ValidN(n(u))末尾插入前向搜索端点s对应轨迹标号集的最后一个元素ValidN(s).last,在前向连接线u的前向端点n(u)的路径物理成本集SPcost(n(u))末尾插入前向搜索端点s路径物理成本集的最后一个元素SPcost(s).last以及前向连接线u的长度Length(u),在前向连接线u的前向端点n(u)的GPS轨迹点加权成本集PWcost(n(u))末尾插入前向连接线u的前向端点n(u)GPS轨迹点加权成本集的最后一个元素PWcost(s).last,并进入步骤S20425;其中,所述前进变量HeadDist的表达式如下:HeadDist=LOCcost(s).last +Length(u)式中,LOCcost(s).last表示前向搜索端点s局部截断成本集的最后一个元素,Length(u)表示前向连接线u的长度;
S20420、根据所述前向搜索端点s对应轨迹标号集的最后一个元素ValidN(s).last计算得到当前匹配GPS轨迹点进度Mnow,并判断前向连接线u的前向端点n(u)的对应轨迹标号集ValidN(n(u))集合是否为空集,若是,则进入步骤S20421,否则,进入步骤S20422;其中,所述当前匹配GPS轨迹点进度Mnow的表达式如下:Mnow=ValidN(s).last+AddN式中,ValidN(s).last表示前向搜索端点s对应轨迹标号集的最后一个元素,AddN表示局部增量匹配点数;
S20421、计算得到局部搜索成本Costnow以及令前向变量HeadDist为GPS轨迹点vp(Mnow)和前向连接线u的前向端点n(u)的欧式距离Euc(vp(Mnow), n(u)),并分别在前向连接线u的前向端点n(u)的局部截断成本集LOCcost(n(u))末尾插入前进变量HeadDist,在前向连接线u的前向端点n(u)的途径连接线集SPvia(n(u))末尾插前向连接线u,在前向连接线u的前向端点n(u)的局部轨迹增量集Padd(n(u))末尾插入局部增量匹配点数AddN,在前向连接线u的前向端点n(u)的对应轨迹标号集ValidN(n(u))末尾插入当前匹配GPS轨迹点进度Mnow,在前向连接线u的前向端点n(u)的路径物理成本集SPcost(n(u))末尾插入前向搜索端点s路径物理成本集的最后一个元素SPcost(s).last+局部搜索成本Costnow,在前向连接线u的前向端点n(u)的GPS轨迹点加权成本集PWcost(n(u))末尾插入前向搜索端点s的GPS轨迹点加权成本集的最后一个元素PWcost(s).last+局部GPS轨迹点加权变量PWac以及在已修改路网节点集NList末尾插入n(u),并进入步骤S0425,其中,所述局部搜索成本Costnow的表达式如下:
Costnow=Length(u)‑StartCut(s).last式中,Length(u)表示前向连接线u的长度,StartCut(s).last表示前向搜索端点s出发截断成本集最后一个元素;
S20422、判断前向连接线u的前向端点n(u)对应轨迹标号集的最后一个元素ValidN(n(u)).last是否等于前向搜索端点s对应轨迹标号集的最后一个元素ValidN(s).last,若是,则进入步骤S20423,否则,前向连接线u的前向端点n(u)对应轨迹标号集的最后一个元素ValidN(n(u)).last小于当前匹配GPS轨迹点进度Mnow,并进入步骤S20424;
S20423、分别计算得到匹配路径成本Cost1以及匹配路径成本Cost2,若匹配路径成本Cost1小于匹配路径成本Cost2,则令前进变量HeadDist等于GPS轨迹点vp(Mnow)和n(u)的欧式距离Euc(vp(Mnow),n(u)),令前向连接线u的前向端点n(u)局部截断成本集的最后一个元素LOCcost(n(u)).last为前进变量HeadDist,令前向连接线u的前向端点n(u)途径连接线集的最后一个元素SPvia(n(u)).last为前向连接线u,令前向连接线u的前向端点n(u)局部轨迹增量集的最后一个元素Padd(n(u)).last为局部增量匹配点数AddN,以及分别计算得到前向连接线u的前向端点n(u)路径物理成本集最后一个元素SPcost(n(u)).last以及前向连接线u的前向端点n(u)GPS轨迹点加权成本集的最后一个元素PWcost(n(u)).las,并进入步骤S20428;其中,所述匹配路径成本的表达式如下:Cost1=SPcost(s).last+Length(u)+PWcost(s).last+PWac‑StartCut(s).last式中,SPcost(s).last表示前向搜索端点s路径物理成本集的最后一个元素,Length(u)表示前向连接线u的长度,PWcost(s).last表示前向搜索端点s的GPS轨迹点加权成本集的最后一个元素,PWac表示局部GPS轨迹点加权变量,StartCut(s).last表示前向搜索端点s出发截断成本集最后一个元素;
所述匹配路径成本Cost2的表达式如下:
Cost2=SPcost(n(u)).last+PWcost(n(u)).last式中,SPcost(n(u)).last表示前向连接线u的前向端点n(u)路径物理成本集最后一个元素,PWcost(n(u)).last表示前向连接线u的前向端点n(u)GPS轨迹点加权成本集的最后一个元素;
所述前向连接线u的前向端点n(u)路径物理成本集最后一个元素SPcost(n(u)).last的表达式如下:
SPcost(n(u)).last=SPcost(s).last+Length(u)+StartCut(s).last式中,SPcost(s).last表示前向搜索端点s路径物理成本集的最后一个元素,Length(u)表示前向连接线u的长度,StartCut(s).last表示前向搜索端点s出发截断成本集最后一个元素;
所述前向连接线u的前向端点n(u)GPS轨迹点加权成本集的最后一个元素PWcost(n(u)).last的表达式如下:
PWcost(n(u)).last=PWcost(s).last+PWac式中,PWcost(s).last表示前向搜索端点s的GPS轨迹点加权成本集的最后一个元素,PWac表示局部GPS轨迹点加权变量;
S20424、执行前进变量HeadDist为GPS轨迹点vp(Mnow)和前向连接线u的前向端点n(u)的欧式距离Euc(vp(Mnow), n(u)),并计算得到局部搜索成本Costnow,以及在前向连接线u的前向端点n(u)的局部截断成本集LOCcost(n(u))末尾插入前进变量HeadDist,在前向连接线u的前向端点n(u)的途径连接线集SPvia(n(u))末尾插入前向连接线u,在前向连接线u的前向端点n(u)的局部轨迹增量集Padd(n(u))末尾插入局部增量匹配点数AddN,在前向连接线u的前向端点n(u)的对应轨迹标号集ValidN(n(u))末尾插入当前匹配GPS轨迹点进度Mnow,在前向连接线u的前向端点n(u)的路径物理成本集SPcost(n(u))末尾插入前向搜索端点s路径物理成本集的最后一个元素SPcost(s).last以及局部搜索成本Costnow,在前向连接线u的前向端点n(u)的GPS轨迹点加权成本集PWcost(n(u))末尾插入前向搜索端点s的GPS轨迹点加权成本集的最后一个元素PWcost(s).last以及局部GPS轨迹点加权变量PWac,并进入步骤S20428;其中,所述局部搜索成本Costnow的表达式如下:Costnow=Length(u)‑StartCut(s).last式中,Length(u)表示前向连接线u的长度,StartCut(s).last表示前向搜索端点s出发截断成本集最后一个元素;
S20425、当前向搜索端点s对应轨迹标号集的最后一个元素ValidN(s).last小于终止节点Endp时,在搜索结束路网节点集CloseL中剔除前向搜索端点s,并计算得到前进变量HeadDist(n(u)),若搜索打开节点集OpenL中有前向连接线u的前向端点n(u),则剔除该元素,并判断前向搜索端点s对应轨迹标号集的最后一个元素ValidN(s).last是否等于当前最远匹配节点Pnow,若是,则进入步骤S20426,否则,前向连接线u的前向端点n(u)对应轨迹标号集的最后一个元素ValidN(s).last小于当前最远匹配节点Pnow,并进入步骤S20427;
其中,前进变量HeadDist(n(u))的表达式如下:HeadDist(n(u))= Euc(vp(ValidN(s).last +1),n(u)+ LOCcost(n(u)).last)式中,Euc(vp(ValidN(s).last+1),n(u)表示GPS轨迹点vp(ValidN(s).last和前向连接线u的前向端点n(u)的欧式距离,LOCcost(n(u)).last)表示前向连接线u的前向端点n(u)局部截断成本集的最后一个元素;
S20426、在搜索打开节点集OpenL起始位置插入前向连接线u的前向端点n(u),在对应搜索前进参考变量集OpenValueL起始位置插入前进变量HeadDist(n(u)),在搜索结束路网节点集CloseL中插入前向连接线u的前向端点n(u),并返回步骤S2044;
S20427、在搜索打开节点集OpenL末尾位置插入n(u),在对应搜索前进参考变量集OpenValueL末尾位置插入前进变量HeadDist(n(u)),当前向搜索端点s对应轨迹标号集的最后一个元素ValidN(s).last等于终止节点Endp时,若前向连接线u在GPS轨迹点vp(Endp)邻近连线集NearL(Endp)中,则在搜索结束路网节点集CloseL中剔除前向搜索端点s,在搜索打开节点集OpenL起始位置插入前向连接线u的前向端点n(u),在对应搜索前进参考变量集OpenValueL起始位置插入0以及在搜索结束路网节点集CloseL插入前向连接线u的前向端点n(u),并返回步骤S2043;
S20428、当前向连接线u的前向端点n(u)对应轨迹标号集的最后一个元素ValidN(n(u)).last小于终止节点Endp时,计算前进变量HeadDist(n(u))等于GPS轨迹点vp(ValidN(s).last和n(u)的欧式距离Euc(vp(ValidN(n(u)).last +1)以及前向连接线u的前向端点n(u))和前向连接线u的前向端点n(u)局部截断成本集的最后一个元素 LOCcost(n(u)).last,若搜索打开节点集OpenL中有前向连接线u的前向端点n(u),则剔除前向连接线u的前向端点n(u),并判断前向连接线u的前向端点n(u)对应轨迹标号集的最后一个元素ValidN(n(u)).last是否大等于当前最远匹配节点Pnow,若是,则进入步骤S20429,否则,进入步骤S20430;其中,所述前进变量HeadDist(n(u))的表达式如下:HeadDist(n(u))=Euc(vp(ValidN(n(u)).last +1)+LOCcost(n(u)).last式中,Euc(vp(ValidN(n(u)).last +1)表示GPS轨迹点vp(ValidN(s).last和n(u)的欧式距离Euc,LOCcost(n(u)).last表示前向连接线u的前向端点n(u))和前向连接线u的前向端点n(u)局部截断成本集的最后一个元素;
S20429、在搜索打开节点集OpenL起始位置插入前向连接线u的前向端点n(u),在对应搜索前进参考变量集OpenValueL起始位置插入前进变量HeadDist(n(u)),并返回步骤S2044;
S20430、判断前向连接线u的前向端点n(u)对应轨迹标号集的最后一个元素ValidN(n(u)).last是否大于当前最远匹配节点Pnow,若是,则进入步骤S20431,否则,前向连接线u的前向端点n(u)对应轨迹标号集的最后一个元素ValidN(n(u)).last小于当前最远匹配节点Pnow,并进入步骤S20432;
S20431、更新当前最远匹配节点Pnow为前向连接线u的前向端点n(u)对应轨迹标号集的最后一个元素ValidN(n(u)).last,并清空搜索结束路网节点集CloseL集合,插入前向连接线u的前向端点n(u),并返回步骤S2044;
S20432、在搜索打开节点集OpenL末尾位置插入前向连接线u的前向端点n(u),在对应搜索前进参考变量集OpenValueL末尾位置插入前进变量HeadDist(n(u)),当前向连接线u的前向端点n(u)对应轨迹标号集的最后一个元素ValidN(n(u)).last等于终止节点Endp时,若前向连接线u在GPS轨迹点vp(Endp)邻近连线集NearL(Endp)中,在搜索打开节点集OpenL起始位置插入n(u),在对应搜索前进参考变量集OpenValueL起始位置插入0,并返回步骤S2043。
5.根据权利要求1所述的快速车载GPS轨迹精确地图匹配的方法,其特征在于,所述步骤S3包括以下步骤:
S301、由末点vp(k)回溯所述最佳地图匹配路径,遍历获取沿途各GPS轨迹点,并根据沿途GPS轨迹点,获取搜索结束路网节点集CloseL各元素,遍历所述搜索结束路网节点集CloseL选择一最优元素作为匹配路径回溯点;
S302、根据所述匹配路径回溯点,以最优匹配尾节点BestEndN为尾节点回溯完成当前轨迹段匹配过程;
S303、根据当前匹配轨迹段回溯结果,输出从GPS轨迹点vp(Lastp)到GPS轨迹点vp(Pnow)中各GPS轨迹点的匹配结果,并分别清空所有已修改路网节点集NList中涉及路网节点各途径连接线集SPvia、路径物理成本集SPcost、局部截断成本集LOCcost、GPS轨迹点加权成本集PWcost、局部轨迹增量集Padd、对应轨迹标号集ValidN以及端点出发截断成本集StartCut;
S304、判断起始节点Startp是否大于终止节点Endp,若是,则当前出行GPS轨迹点全部匹配结束,并汇总输出匹配结果统计表,并进入步骤S4,否则,起始节点Startp小于终止节点Endp,并进入步骤S4。
6.根据权利要求5所述的快速车载GPS轨迹精确地图匹配的方法,其特征在于,所述步骤S301包括以下步骤:
S3011、由末点vp(k)回溯所述最佳匹配路径,遍历获取沿途各GPS轨迹点,并根据沿途GPS轨迹点,获取搜索结束路网节点集CloseL各元素;
S3012、对所述搜索结束路网节点集CloseL中各元素道路节点建立循环,并初始化最小总路径加权成本MinCost等于100000,当节点对应轨迹标号集的最后一个元素ValidN(s).last等于当前最远匹配节点Pnow时,建立最优局部路径终点搜索迭代m=false,以及初始化当前搜索路网节点CrtN为前向搜索端点s,当途径连接线集SPvia(s)不为空集,且前向搜索端点s对应轨迹标号集的最后一个元素ValidN(s).last等于当前最远匹配节点Pnow时,以及途径连接线集SPvia(s)仅存在一个元素,则检查是否陷入回溯端点死循环,若是,则终止迭代进入搜索结束路网节点集CloseL中下一元素,并进入步骤S3013,否则,进入步骤S3015;
S3013、检查当前最远匹配节点Pnow附近是否存在前向搜索端点s途径连接线集的最后一个元素SPvia(s).last,若是,则找到局部最优终点,并进入步骤S3015,否则,进入步骤S3014;
S3014、若前向搜索端点s途径连接线集的元素数量SPvia(s).size大于1,则分别在途径连接线集SPvia(s)、对应轨迹标号集ValidN(s)、局部轨迹增量集Padd(s)、路径物理成本集SPcost(s)以及GPS轨迹点加权成本集PWcost(s)中剔除最后一个元素,并令路径回溯端点CrtEndN等于前向搜索端点s途径连接线集的最后一个元素的尾点SPvia(s).last.tail,并返回步骤S3012;或
若前向搜索端点s为轨迹匹配段落起点,则分别在途径连接线集SPvia(s)、对应轨迹标号集ValidN(s)、局部轨迹增量集Padd(s)、路径物理成本集SPcost(s)以及GPS轨迹点加权成本集PWcost(s)中剔除最后一个元素,并令路径回溯端点CrtEndN等于前向搜索端点s途径连接线集的最后一个元素的尾点SPvia(s).last.tail,并返回步骤S3012;
S3015、根据找到的路径回溯端点CrtEndN及所属连接线路径回溯端点CrtEndN途径连接线集的最后一个元素SPvia(CrtN).last,计算得到路径总成本TotalCost,并判断所述路径总成本TotalCost是否小于最小总路径加权成本MinCost,若是,则更新最小总路径加权成本MinCost等于路径总成本TotalCost以及最佳匹配尾节点BestEndN等于路径回溯端点CrtEndN,进入下一备选尾节点,并返回步骤S3011,否则,遍历完搜索结束路网节点集CloseL,选择一最优元素作为匹配路径回溯点,并进入步骤S302;其中,路径总成本TotalCost的表达式如下:
TotalCost=SPcost(CrtN)+PWcost(CrtN)+Euc(vp(Pnow),CrtN)式中,SPcost(CrtN)表示路径回溯端点CrtEndN的路径物理成本集,PWcost(CrtN)表示路径回溯端点CrtEndN的GPS轨迹点加权成本集,Euc(vp(Pnow),CrtN)表示GPS轨迹点vp(Pnow)和路径回溯端点CrtEndN的欧式距离。
7.根据权利要求5所述的快速车载GPS轨迹精确地图匹配的方法,其特征在于,所述步骤S302包括以下步骤:
S3021、更新起始节点Startp为当前最远匹配节点Pnow+1,并分别初始化当前回溯GPS轨迹点CrtP等于当前最远匹配节点Pnow、当前回溯尾节点CrtEndN等于最佳匹配尾节点BestEndN以及回溯指示变量BackCk等于端点BestEndN途径连接线集的元素数量SPvia(BestEndN).size,建立回溯迭代,并判断回溯迭代的回溯指示变量BackCk是否等于1,若是,则进入步骤S3022,否则,回溯迭代的回溯指示变量BackCk大于1,并进入步骤S3023;
S3022、检查是否已回溯到路网路径起点,若是,则直接终止迭代,并进入步骤S3023,否则,返回步骤S3021;
S3023、建立从当前回溯GPS轨迹点CrtP到上一起始节点Lastp的逆序循环k;
S3024、当匹配结果变量Match(k)等于‑1时,若路径回溯端点CrtEndN途径连接线集的最后一个元素SPvia(CrtEndN).last在邻近连线集NearL(k)中,则更新匹配结果变量Match(k)等于路径回溯端点CrtEndN途径连接线集的最后一个元素SPvia(CrtEndN).last,最优匹配权重MatchW(k)等于节点k匹配连接线的匹配权重vp(k).Weight(Match(k));以及当匹配结果变量Match(k)大于‑1时,若路径回溯端点CrtEndN途径连接线集的最后一个元素SPvia(CrtEndN).last在邻近连线集NearL(k)中,且轨迹点vp(k)对应该连接线的匹配权重vp(k).Weight(SPvia(CrtEndN).last)小于最佳匹配权重MatchW(k),则匹配结果变量Match(k)为路径回溯端点CrtEndN途径连接线集的最后一个元素SPvia(CrtEndN).last,最佳匹配权重MatchW(k)为节点k匹配连接线的匹配权重vp(k).Weight(Match(k)),若路径回溯端点CrtEndN途径连接线集的最后一个元素SPvia(CrtEndN).last不在邻近连线集NearL(k)中,且路径回溯端点CrtEndN对应轨迹标号集的最后一个元素ValidN(CrtEndN).last小于当前回溯GPS轨迹点CrtP时,则当前回溯GPS轨迹点CrtP为当前回溯GPS轨迹点CrtP‑1;
S3025、令k为k‑1,并继续循环,若判断循环是否结束,若是,则进入步骤S3026,否则,返回步骤S3024;
S3026、建立从回溯指示变量BackCk到1的逆序循环t;
S3027、若路径回溯端点CrtEndN对应轨迹标号集的第t个元素ValidN(CrtEndN).at(t)大于当前回溯GPS轨迹点CrtP时,则剔除路径回溯端点CrtEndN的途径连接线集SPvia(CrtEndN)以及路径回溯端点CrtEndN的对应轨迹标号集ValidN(CrtEndN)集合中的最后一个元素,更新回溯指示变量BackCk等于路径回溯端点CrtEndN途径连接线集的元素数量SPvia(CrtEndN).size,并继续循环下一元素t‑1;以及若路径回溯端点CrtEndN对应轨迹标号集的第t个元素ValidN(CrtEndN).at(t)大于等于当前回溯GPS轨迹点CrtP时,则建立从当前回溯GPS轨迹点CrtP到上一起始节点Lastp的逆序循环k,当匹配结果变量Match(k)等于‑1时,且路径回溯端点CrtEndN途径连接线集的第t个元素SPvia(CrtEndN).at(t)在邻近连线集NearL(k)中,则更新匹配结果变量Match(k)等于路径回溯端点CrtEndN途径连接线集的第t个元素SPvia(CrtEndN).at(t),最佳匹配权重MatchW(k)等于节点k匹配连接线的匹配权重vp(k).Weight(Match(k));当匹配结果变量Match(k)大于‑1时,若路径回溯端点CrtEndN途径连接线集的第t个元素SPvia(CrtEndN).at(t)在邻近连线集NearL(k)中,且轨迹点vp(k)对应该连接线的匹配权重vp(k).Weight(SPvia(CrtEndN).at(t))小于最佳匹配权重MatchW(k),则使匹配结果变量Match(k)等于路径回溯端点CrtEndN途径连接线集的第t个元素SPvia(CrtEndN).at(t),最佳匹配权重MatchW(k)等于节点k匹配连接线的匹配权重vp(k).Weight(Match(k)),若路径回溯端点CrtEndN途径连接线集的第t个元素SPvia(CrtEndN).at(t)不在邻近连线集NearL(k)中,且路径回溯端点CrtEndN对应轨迹标号集的第t个元素ValidN(CrtEndN).at(t)小于当前回溯GPS轨迹点CrtP时,则使当前回溯GPS轨迹点CrtP为当前回溯GPS轨迹点CrtP‑1;
S3028、令k为k‑1,继续循环,并判断循环是否结束,若是,则进入步骤S3029,否则,返回步骤S3027;
S3029、建立从回溯指示变量BackCk到1的逆序循环t;
S30210、若路径回溯端点CrtEndN对应轨迹标号集的第t个元素ValidN(CrtEndN).at(t)大于当前回溯GPS轨迹点CrtP时,则剔除路径回溯端点CrtEndN的途径连接线集SPvia(CrtEndN)以及路径回溯端点CrtEndN的对应轨迹标号集ValidN(CrtEndN)集合的最后一个元素,并更新回溯指示变量BackCk等于路径回溯端点CrtEndN途径连接线集的元素数量SPvia(CrtEndN).size,并继续循环下一个元素t‑1;以及若路径回溯端点CrtEndN对应轨迹标号集的第t个元素ValidN(CrtEndN).at(t)小于等于当前回溯GPS轨迹点CrtP时,则建立从当前回溯GPS轨迹点CrtP到上一起始节点Lastp的逆序循环k,当匹配结果变量Match(k)等于‑1时,若路径回溯端点CrtEndN途径连接线集的第t个元素SPvia(CrtEndN).at(t)在邻近连线集NearL(k)中,则使更新匹配结果变量Match(k)等于路径回溯端点CrtEndN途径连接线集的第t个元素SPvia(CrtEndN).at(t),最佳匹配权重MatchW(k)等于节点k匹配连接线的匹配权重vp(k).Weight(Match(k));
若匹配结果变量Match(k)大于‑1时,若路径回溯端点CrtEndN途径连接线集的第t个元素SPvia(CrtEndN).at(t)在邻近连线集NearL(k)中,且若vp(k).Weight(SPvia(CrtEndN).at(t))小于最佳匹配权重MatchW(k),则使匹配结果变量Match(k)等于路径回溯端点CrtEndN途径连接线集的第t个元素SPvia(CrtEndN).at(t),最佳匹配权重MatchW(k)等于节点k匹配连接线的匹配权重vp(k).Weight(Match(k)),若路径回溯端点CrtEndN途径连接线集的第t个元素SPvia(CrtEndN).at(t)不在邻近连线集NearL(k)中,且若路径回溯端点CrtEndN对应轨迹标号集的第t个元素ValidN(CrtEndN).at(t)小于当前回溯GPS轨迹点CrtP时,则使当前回溯GPS轨迹点CrtP等于当前回溯GPS轨迹点CrtP‑1;
S30211、令k为k‑1,并继续循环,判断循环是否结束,若是,则进入步骤S30212,否则,返回步骤S30210;
S30212、更新路径回溯端点CrtEndN等于其途径连接线集的最后一个元素的尾节点SPvia(CrtEndN).last.tail,以及更新回溯指示变量BackCk等于路径回溯端点CrtEndN途径连接线集的元素数量SPvia(CrtEndN).size;
S30213、设置临时点TempN等于SPvia(CrtEndN).last.tail,若SPvia(CrtEndN).size大于1,剔除路径回溯端点CrtEndN的途径连接线集SPvia(CrtEndN)、轨迹标号集ValidN(CrtEndN)的最后一个元素,更新当前回溯尾节点CrtEndN等于临时点TempN,回溯指示变量BackCk等于路径回溯端点CrtEndN的途径连接线集包含元素数目SPvia(CrtEndN).size,结束循环t;
S30214、判断是否迭代结束,若是,则返回步骤S3023,否则,进入步骤S30215;
S30215、继续迭代,并判断回溯指示变量BackCk是否等于1,若是,则返回步骤S3023,否则,进入步骤S30216;
S30216、判断回溯指示变量BackCk是否大于1,若是,则返回步骤S3023,否则,回溯指示变量BackCk是否等于0,迭代结束,从而实现以最优匹配尾节点BestEndN为尾节点回溯完成当前轨迹段的匹配过程,并进入步骤S303。
8.根据权利要求1所述的快速车载GPS轨迹精确地图匹配的方法,其特征在于,所述步骤S4包括以下步骤:
S401、根据所述匹配结果统计表,判断匹配中途是否存在由地图匹配工作循环引起的中断点,若是,则进入步骤S402,否则,完成快速车载GPS轨迹精确地图的匹配;
S402、输出首点vp(1)至中断点vp(s)的匹配结果,并从中断点vp(s)到末点vp(k)执行步骤S2至S3,直至完成全部车载GPS轨迹点的匹配。