一种道路通行限制的车辆路径规划方法

摘要

本发明提供了一种道路通行限制的车辆路径规划方法，步骤包括起终点输入、路网匹配确定起点集和终点集、确定路网拓展范围和最终拓展层级、满足升层条件进行升层、顶层双向拓展、回溯路径、生成最优路径。本发明实现了一条可用于引导以及显示的完整路径。合理的确定了拓展的范围，降低了数据的读取量，进而降低了内存消耗，减少了文件的读写次数，能够满足性能低下的WINCE设备的用户的需求。通过对禁止约束数据和限制约束数据的不同处理，能够规避禁止通行的道路，又能考虑限制通行道路的代价，规划出满足用户需求的路线。

说明书

技术领域

本发明涉及领域，具体涉及一种道路通行限制的车辆路径规划方法。

背景技术

为了实现这种考虑道路通行限制的路径规划方法，市面上出现了一种方法，该方法根据地图数据以及规避路段信息生成导航路径。其中，地图数据中包含通行限制数据，通过用户输入的车辆参数，在规划时与道路数据对应的通行限制数据值做比较，进而规避不能通行的道路，通过迭代，实现一条可以通行的路径。

现有技术存在以下几个缺点：1.地图基础数据更新周期较长，而限制数据更新周期短，这样会造成在使用这种技术的过程中，面临实际道路通行条件与地图中限制数据不符的情况。2.在实际行车过程中，存在一些道路，可通行但是包含一定代价的情况，而上述方法没有考虑这种情况。3.现有技术在规划时，处理限制通行道路采用的迭代的方法，极大的降低了路径规划的效率，在处理能力比较差的PND或车载设备上，很难达到用户的要求。

发明内容

要解决的技术问题：本发明的目的是提供一种道路通行限制的车辆路径规划方法，以提高针对车辆导航应用的路径规划生成路线的实用性。

技术方案：为了解决上述的技术问题，本发明公开了一种道路通行限制的车辆路径规划方法，包括下述步骤：

步骤101：获取用户输入的起点和终点；

步骤102：根据101的信息以及路网框选匹配，获得寻路的起点集和终点集；

步骤103：根据起点和终点的位置，得到起点和终点对应的各层路网中的所在的块，以及邻接块，用来确定路网各层的拓展范围以及拓展的最高层级；

步骤104：在起点和终点同层拓展时，通过同层拓展机制，实现节点的拓展，地图数据按块读入，升层后即可释放，交通限行数据同样按块读入，升层后释放；

步骤105：在同层拓展中，节点采用A*拓展机制进行拓展，首先从拓展队列中获取代价最小的节点进行拓展，拓展节点的下一个节点会存在4种情况，节点不在拓展范围内，则停止当前节点拓展；节点已经被拓展过，则停止当前拓展，节点未被拓展，则根据读入的交通限行数据，判断此节点是否存在限制数据，如果存在，根据当前车的自身参数，判断车是否可通行，如果是，放入到拓展队列中继续拓展，如果否，则停止当前拓展；节点为高级节点，则根据升层条件，如果遇到可升层的节点，对该节点进行升层；

步骤106：升层的节点通过加入到拓展队列，继承前一个节点的所有属性，存放到高一级拓展序列中；在高一级路网中，重复步骤105；

步骤107：当起点和终点的所有可拓展节点升到最高层时，升层拓展结束，此时节点集包含起点在最高层路网的节点集和终点在最高层路网的节点集，然后在最高层进行双向拓展，起点节点集向终点方向拓展，终点节点集向起点方向拓展，节点拓展机制采用A*拓展机制；

步骤108：当满足停止拓展机制时，停止拓展，此时拓展工作完成；停止拓展机制为当前正拓展的节点的实际代价大于最优触碰点的总代价，最优触碰点为起点集和终点集相向拓展时触碰点中总代价最小的节点；

步骤109：从最高层的最优触碰点开始通过查找父节点的方式进行路径的回溯，直到父节点为起点/终点，此时就生成一条可通行的完整的路径。

优选的，所述的步骤102中，起点集包含匹配到的路口的所有出口和出入口，终点集包含匹配到的路口的所有入口和出入口。

优选的，所述的步骤102中路网框选匹配是通过地图路网框选，得到以起点/终点为中心，边长为r的正方形框内的所有路段和路口，然后根据就近原则得到起点/终点匹配的路段或路口，再通过转换，将匹配后的路段或路口转成入口、出口和出入口的形式，就生成了寻路的起点集和终点集。

优选的，所述的步骤103中各层路网是按照道路功能等级，将整个地图路网划分为多层，每一层根据街区分割成大小不一的多个块；邻接块是指与当前块邻接的周边的块。

优选的，所述的步骤104中交通限行数据包括限高、限重和禁行。

优选的，所述的步骤105中升层条件为当前节点有上级节点，且对应的上级节点在拓展范围内。

有益效果：本发明的考虑道路通行限制的车辆路径规划方法通过以上步骤，实现了一条可用于引导以及显示的完整路径。利用步骤103，合理的确定了拓展的范围，降低了数据的读取量，进而降低了内存消耗，减少了文件的读写次数，能够满足性能低下的WINCE设备的用户的需求。利用步骤104，地图数据按块读入和交通约束数据按块读入的方法，使得读入的数据的利用率大大提升，避免了不必要数据的读入，以及避免了一次性申请大内存的难题。利用步骤104，通过对禁止约束数据和限制约束数据的不同处理，能够规避禁止通行的道路，又能考虑限制通行道路的代价，规划出满足用户需求的路线。

附图说明

图1为一种考虑道路通行限制的车辆路径规划方法的步骤示意图；

图2为同层拓展机制示意图。

具体实施方式

实施例1

一种道路通行限制的车辆路径规划方法，包括下述步骤：

步骤101：获取用户输入的起点和终点；

步骤102：根据101的信息以及路网框选匹配，获得寻路的起点集和终点集；

步骤103：根据起点和终点的位置，得到起点和终点对应的各层路网中的所在的块，以及邻接块，用来确定路网各层的拓展范围以及拓展的最高层级；

步骤104：在起点和终点同层拓展时，通过同层拓展机制，实现节点的拓展，地图数据按块读入，升层后即可释放，交通限行数据同样按块读入，升层后释放；

步骤105：在同层拓展中，节点采用A*拓展机制进行拓展，首先从拓展队列中获取代价最小的节点进行拓展，拓展节点的下一个节点会存在4种情况，节点不在拓展范围内，则停止当前节点拓展；节点已经被拓展过，则停止当前拓展，节点未被拓展，则根据读入的交通限行数据，判断此节点是否存在限制数据，如果存在，根据当前车的自身参数，判断车是否可通行，如果是，放入到拓展队列中继续拓展，如果否，则停止当前拓展；节点为高级节点，则根据升层条件，如果遇到可升层的节点，对该节点进行升层；

步骤106：升层的节点通过加入到拓展队列，继承前一个节点的所有属性，存放到高一级拓展序列中；在高一级路网中，重复步骤105；

步骤107：当起点和终点的所有可拓展节点升到最高层时，升层拓展结束，此时节点集包含起点在最高层路网的节点集和终点在最高层路网的节点集，然后在最高层进行双向拓展，起点节点集向终点方向拓展，终点节点集向起点方向拓展，节点拓展机制采用A*拓展机制；

步骤108：当满足停止拓展机制时，停止拓展，此时拓展工作完成；停止拓展机制为当前正拓展的节点的实际代价大于最优触碰点的总代价，最优触碰点为起点集和终点集相向拓展时触碰点中总代价最小的节点；

步骤109：从最高层的最优触碰点开始通过查找父节点的方式进行路径的回溯，直到父节点为起点/终点，此时就生成一条可通行的完整的路径。

所述的步骤102中，起点集包含匹配到的路口的所有出口和出入口，终点集包含匹配到的路口的所有入口和出入口。

所述的步骤102中路网框选匹配是通过地图路网框选，得到以起点/终点为中心，边长为r的正方形框内的所有路段和路口，然后根据就近原则得到起点/终点匹配的路段或路口，再通过转换，将匹配后的路段或路口转成入口、出口和出入口的形式，就生成了寻路的起点集和终点集。

所述的步骤103中各层路网是按照道路功能等级，将整个地图路网划分为多层，每一层根据街区分割成大小不一的多个块；邻接块是指与当前块邻接的周边的块。

所述的步骤104中交通限行数据包括限高、限重和禁行。

所述的步骤105中升层条件为当前节点有上级节点，且对应的上级节点在拓展范围内。

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。