专利名称：一种路径快速规划方法
技术领域：
本发明涉及导航领域，更具体地说，涉及一种路径快速规划方法。
背景技术：
近年来，GPS (Global Positioning System，全球定位系统)的应用越来越普遍，从 GPS获取自己的位置，再由此规划到目的地的路径，极大地方便了人们的日常生活。导航系统需要快速计算出最佳路径而进行导航，但是现有导航系统大多依靠一些计算处理能力较为有限的硬件，加上导航系统本身都将消耗大部分的系统资源，所以要求路径规划的方法必须高效快速。导航路径的选择，目前的方法是将交通网络抽象为一个包含多个节点的拓扑网络，然后通过最短路径(包括路程最短和时间最短两种)算法规划一条从起点到终点的路径。传统的算法，比如Dijkstra算法，以起点为中心，对整个地图的道路进行扩展式搜索， 直到扩展到终点，才对所有可行的道路进行比较、筛选，最终得出最短的路径。这种算法由于需要考虑到所有道路的可能性，加上在扩展的时候没有制定方向，在路网密集的区域或者长距离路径规划的情况下，加载的数据量和运算量将会相当惊人，导致规划时间将很长。 在现实中，最优路径并不一定就是最短路径，最优路径的选择往往还要考虑道路等级、路面情况、交通灯等待时间等因素，如，一般驾驶者都希望尽量在交通秩序较理想的主干道行车而宁愿因此多耗些时间和汽油。因此，现有的单纯以Dijkstra最短路径算法或A 3算法等规则规划出来的路径并不一定是最优的路径规划。

发明内容
本发明目的旨在克服传统的路径规划算法的低效以及便携导航系统在运算处理能力有限的不足，提供一种路径快速规划方法，以满足现有导航系统快速计算、规划最佳路径的需要。本发明的技术方案是一种路径快速规划方法，包括以下步骤Si)将道路网络按道路等级建立空间分层，并对每一层道路网络划分网格区域、依据道路数据建立道路网络的拓扑结构；S2)在低层次道路网络的起点、终点位置分别进行升层探索，搜索进入高层次道路网络的跃点位置；S3)在高层次道路网络上起点和终点的跃点间按最短路径算法规划路径。道路网络空间分层是根据道路等级从高到低进行分层次，低层次道路包含高层次道路，各层次道路相对独立而且连通。每一层道路网络以网格为单元存储和管理数据，下层道路网络在上层道路网络的网格划分基础上进行网格划分。所述道路网络的拓扑结构中，对每个网格单元，赋予道路前续个数、后续个数、所在层次、正向阻力级别、反向阻力级别、后续结构索引、前续结构索引的7个属性。
在步骤Sl中，在构建空间分层的道路网络时采用道路合并的方法上一层的道路网络在下一层的道路网络基础上，将连续的非属性变化点和非高等级道路交叉路口的路段进行合并，将相邻路段的连接点简化省略。在被省略的连接点建立层级之间的路段编号对应表。在步骤S2中，在低层次道路网络的起点、终点位置分别进行升层探索时，按起点和终点的距离的不同搜索不同的高层次道路网络。系统在处理道路网络的数据时，将需要的网格区域的数据加载到系统缓存中，代替磁盘的反复读取。一种路径快速规划方法的升层规则，包括Si)如果起点和终点分别所在的网格之间隔一个网格以上，进行升层规划；S2)在0层或1层内，如果起点和终点分别所在的网格之间隔一个网格，执行S3)， 如果起点和终点分别所在的网格为对角相邻，则执行S4)，如果起点和终点分别所在在网格相邻，则执行S5)；S 3)起点和终点所跨的九个网格范围，内缩四分之一个网格形成一个矩形范围， 如果起点和终点都在该矩形范围内，则加载矩形范围所在的9个网格，在该层规划，否则升层规划；S4)起点终点所跨四个网格内缩四分之一网格形成一个矩形范围，如果起点和终点都落在该矩形范围内，则在该层规划，否则升层规划；S5)以起点和终点的中点所在网格进行扩展0. 75个网格形成一个矩形范围，起点和终点都落在该矩形范围内，则在该层规划，否则升层规划；S6)在2层内，如果起点和终点分别所在的网格为相邻或对角相邻的关系，则将起点和终点所跨的四个网格，内缩四分之一个网格形成一个矩形范围，如果起点和终点在该矩形范围内，则加载这四个网格，在2层规划，否则升到3层规划；S7)在2层内，如果起点和终点在同一个网格内，则以该网格的相邻对称网格为基础的四个网格，内缩四分之一个网格形成一个矩形分为，如果启点和终点在该矩形范围内， 在加载这四个网格，在2层规划，否则升到三层规划；S8)在2层内，如果起点或终点至少有一点位于17、23、24这三个网格中，直接升到
三层规划。本发明能弥补现有导航仪的硬件性能的不足所导致的路径规划速度慢的缺点，能够高效快速规划出适合出行的最优路径，并且节省系统资源。


图1为道路分层示意2为网格分区示意图；图3为道路合并示意图；图4为系统路径规划流程；图5为双向升层探索示意图；图6为路径计算数据路段结构示意图；图7为判断升层时，起点和终点相隔一个网格的示意5
图8为判断升层时，起点和终点处于一个网格的示意图。
具体实施例方式本方法为一种路径快速规划方法，总体分为地图的预处理和路径规划两个部分， 地图的预处理是为路径规划作准备。地图的预处理包括空间分层、网格分区和道路数据拓扑结构三部分。空间分层是将路网数据根据道路等级进行分层次组织，如图1所示，越高层的道路越高级(如高速、国道)，低层道路包含高层道路，层次越低，道路越详细(如街、巷)。网格分区如图2所示，是将每一层道路用矩形分割成网格，并以网格为单元存储和管理数据，当系统读取时，以网格为单元索引读取所需数据，具有针对性，能够大大减少数据的读取量，快速完成数据读取。道路数据拓扑结构是系统进行路径规划的重要依据。是根据路网的实际情况为每个网格单元赋予道路层次、道路前续后续信息、网格数据索引等信息，以供系统进行路径计算和规划。在构建空间分层的道路网络时采用道路合并的方法，如图3所示，上一层的道路网络在下一层的道路网络基础上，将连续的非属性变化点和非高等级道路交叉路口的路段进行合并，将相邻路段的连接点简化省略如图1所示，系统进行道路规划时，首先设定规划参数，包括起点、终点、经过点、 规划方式等，由系统判断两点的关系，即判断两点是否详细层邻接区域，如果详细层邻接， 则发起低层近距离规划，否则发起针对远距离规划的双向升层探索。进行低层近距离规划时，系统将在最底层地图数据上进行路径探索，由于起点终点位置接近，数据量相对少，系统规划的时间很短。如果起点和终点分别所在的网格之间隔一个网格以上，进行升层规划。在0层或1层内，如果起点和终点分别所在的网格之间隔一个网格，如图7所示 (图中s为起点，e为终点)将起点和终点所跨的九个网格范围(如图7 (a)、图7 (b)、图7 (c) 所示)，内缩四分之一个网格形成一个矩形范围，如果起点和终点都在该矩形范围内，则加载矩形范围所在的9个网格，在该层规划，否则升层规划。如果起点和终点分别所在的网格为对角相邻，则将起点终点所跨四个网格内缩四分之一网格形成一个矩形范围，如果起点和终点都落在该矩形范围内，则在该层规划，否则升层规划；如果起点和终点分别所在在网格相邻，则以起点和终点所在网格进行扩展0. 75个网格形成一个矩形范围，起点和终点都落在该矩形范围内，则在该层规划，否则升层规划。在2层内，如果起点和终点分别所在的网格为相邻或对角相邻的关系，则将起点和终点所跨的四个网格，内缩四分之一个网格形成一个矩形范围，如果起点和终点在该矩形范围内，则加载这四个网格，在2层规划，否则升到3层规划；如果起点和终点在同一个网格内，如图8所示，(s为起点、e为终点、m为中点)则以起点和终点的中点所在网格的相邻对称网格为基础的四个网格，内缩四分之一个网格形成一个矩形分为，如果起点和终点在该矩形范围内，在加载这四个网格，在2层规划，否则升到三层规划；如果起点或终点至少有一点位于预定的特殊网格中，直接升到三层规划。进行双向升层探索时，系统将首先根据起点和终点的坐标读取包含起点和终点的区域的最低层次道路，如图4所示，然后在起点区域中查找高层道路，并将高层道路信息经过处理并入高层数据中。然后也在终点区域中查找高层道路，结合已有的高层道路信息进行路径规划。无论低层近距离规划还是双向升层探索，规划得出的结果最终都需经过进行重构规划路径的过程，抽象路径转换为实体路径，并引导和规划路径显示。在进行道路规划时，系统将所需数据加载到系统缓存中，无需频繁的磁盘读写，以便快速写数据。
权利要求
1.一种路径快速规划方法，其特征在于包括以下步骤51)将道路网络按道路等级建立空间分层，并对每一层道路网络划分网格区域、依据道路数据建立道路网络的拓扑结构；52)在低层次道路网络的起点、终点位置分别进行升层探索，搜索进入高层次道路网络的跃点位置；53)在高层次道路网络上起点和终点的跃点间按最短路径算法规划路径。
2.如权利要求1所述的路径快速规划方法，其特征在于道路网络空间分层是根据道路等级从高到低进行分层次，低层次道路包含高层次道路，各层次道路相对独立而且连通。
3.如权利要求1所述的路径快速规划方法，其特征在于每一层道路网络以网格为单元存储和管理数据，下层道路网络在上层道路网络的网格划分基础上进行网格划分。
4.如权利要求1所述的路径快速规划方法，其特征在于所述的道路网络的拓扑结构中，对每个网格单元，赋予道路前续个数、后续个数、所在层次、正向阻力级别、反向阻力级别、后续结构索引、前续结构索引的7个属性。
5.如权利要求1所述的路径快速规划方法，其特征在于在步骤Sl中，在构建空间分层的道路网络时采用道路合并的方法上一层的道路网络在下一层的道路网络基础上，将连续的非属性变化点和非高等级道路交叉路口的路段进行合并，将相邻路段的连接点简化省略。
6.如权利要求5所述的路径快速规划方法，其特征在于在被省略的连接点建立层级之间的路段编号对应表。
7.如权利要求1所述的路径快速规划方法，其特征在于在步骤S2中，在低层次道路网络的起点、终点位置分别进行升层探索时，按起点和终点的距离的不同搜索不同的高层次道路网络。
8.如权利要求1所述的路径快速规划方法，其特征在于系统在处理道路网络的数据时，将需要的网格区域的数据加载到系统缓存中，代替磁盘的反复读取。
9.一种路径快速规划方法的升层规则，包括51)如果起点和终点分别所在的网格之间隔一个网格以上，进行升层规划；52)在0层或1层内，如果起点和终点分别所在的网格之间隔一个网格，执行S3)，如果起点和终点分别所在的网格为对角相邻，则执行S4)，如果起点和终点分别所在在网格相邻，则执行S5)；53)起点和终点所跨的九个网格范围，内缩四分之一个网格形成一个矩形范围，如果起点和终点都在该矩形范围内，则加载矩形范围所在的9个网格，在该层规划，否则升层规划；54)起点终点所跨四个网格内缩四分之一网格形成一个矩形范围，如果起点和终点都落在该矩形范围内，则在该层规划，否则升层规划；55)以起点和终点的中点所在网格进行扩展0.75个网格形成一个矩形范围，起点和终点都落在该矩形范围内，则在该层规划，否则升层规划；56)在2层内，如果起点和终点分别所在的网格为相邻或对角相邻的关系，则将起点和终点所跨的四个网格，内缩四分之一个网格形成一个矩形范围，如果起点和终点在该矩形范围内，则加载这四个网格，在2层规划，否则升到3层规划；57)在2层内，如果起点和终点在同一个网格内，则以该网格的相邻对称网格为基础的四个网格，内缩四分之一个网格形成一个矩形分为，如果启点和终点在该矩形范围内，在加载这四个网格，在2层规划，否则升到三层规划；58)在2层内，如果起点或终点至少有一点位于17、23、24这三个网格中，直接升到三层规划。
全文摘要
本发明为一种路径快速规划方法，包括以下步骤S1)将道路网络按道路等级建立空间分层，并对每一层道路网络划分网格区域、依据道路数据建立道路网络的拓扑结构；S2)在低层次道路网络的起点、终点位置分别进行升层探索，搜索进入高层次道路网络的跃点位置；S3)在高层次道路网络上起点和终点的跃点间按最短路径算法规划路径。本发明以道路合并、双向升层探索等方法规划导航路径，能满足现有导航系统快速计算、规划最佳路径的需要。
文档编号G01C21/34GK102435200SQ201110260870
公开日2012年5月2日 申请日期2011年9月5日 优先权日2011年9月5日
发明者李庆建 申请人:广东东纳软件科技有限公司