路径数据处理、路径规划方法、装置和计算机设备

摘要

本申请涉及一种路径数据处理方法、装置、计算机设备、存储介质和计算机程序产品，以及一种路径规划方法、装置、计算机设备、存储介质和计算机程序产品，可应用于交通领域或者地图领域。方法包括：获取基于原始路网拓扑，原始路网拓扑中包括限制路段串；将原始路网拓扑中过滤目标路段后的剩余拓扑进行映射，得到目标映射拓扑，目标路段为限制路段串中的路段；创建与原始路网拓扑中的目标路段串对应的等效映射路段串，目标路段串为原始路网拓扑中包含目标路段的非限制路段串；将目标映射拓扑以及等效映射路段串所构成的拓扑确定为规划拓扑，规划拓扑用于规划得到规划起点和规划终点之间的目标路径。采用本申请的方法可以提高路径规划效率。

权利要求

1.一种路径数据处理方法，其特征在于，所述方法包括：

获取基于真实路径信息得到的原始路网拓扑，所述原始路网拓扑中包括限制路段串，所述限制路段串用于表征真实路径信息中的限制通行路径；

将所述原始路网拓扑中过滤目标路段后的剩余拓扑进行映射，得到目标映射拓扑，所述目标路段为所述限制路段串中的路段；

创建与所述原始路网拓扑中的目标路段串对应的等效映射路段串，所述目标路段串为所述原始路网拓扑中包含所述目标路段的非限制路段串；

将所述目标映射拓扑以及所述等效映射路段串所构成的拓扑，确定为规划拓扑，所述规划拓扑用于规划得到规划起点和规划终点之间的目标路径。

2.根据权利要求1所述的方法，其特征在于，所述创建与所述原始路网拓扑中的目标路段串对应的等效映射路段串，包括：对于所述原始路网拓中所包括的限制路段所组成的限制路段集合，将其中包括于所述目标路段串的限制路段作为目标限制路段；

创建所述目标限制路段对应的等效映射路段；

基于所述等效映射路段，确定所述目标路段串对应的等效映射路段串。

3.根据权利要求2所述的方法，其特征在于，所述创建所述目标限制路段对应的等效映射路段，包括：若所述目标路段为所述限制路段串中的起始路段，则将所述限制路段串的中间限制节点作为目标限制节点；

创建与所述目标限制节点对应的等效映射节点，基于所述等效映射节点创建所述目标限制路段对应的等效映射路段。

4.根据权利要求3所述的方法，其特征在于，所述基于所述等效映射节点创建所述目标限制路段对应的等效映射路段，包括：若所述目标映射拓扑存在与所述起始路段的源节点对应的映射节点，则在所述源节点对应的映射节点与第一目标等效映射节点之间建立所述起始路段中连接边的等效映射边，以创建所述起始路段对应的第一等效映射路段；

其中，所述第一目标等效映射节点为所述起始路段的目标节点对应的等效映射节点。

5.根据权利要求3所述的方法，其特征在于，所述基于所述等效映射节点创建所述目标限制路段对应的等效映射路段，包括：若所述限制路段串包括至少三个限制路段，则

在各个目标限制节点对应的等效映射节点之间建立所述限制路段串中的中间连接边的等效映射边，以构建所述限制路段串中的中间限制路段对应的第二等效映射路段；

其中，所述限制路段串中的中间连接边为所述中间限制路段中的连接边。

6.根据权利要求3所述的方法，其特征在于，所述基于所述等效映射节点创建所述目标限制路段对应的等效映射路段，包括：对于包含一个非限制节点的目标路段串，将所述目标路段串中连接限制节点和非限制节点的连接边作为目标连接边；

在所述目标连接边所连接的非限制节点对应的映射节点和所述目标连接边所连接的限制节点对应的等效映射节点之间，建立所述目标连接边的等效映射边，将所述等效映射边所在的等效映射路段作为所述目标连接边所在的目标限制路段对应的第三等效映射路段。

7.根据权利要求1所述的方法，其特征在于，所述将所述原始路网拓扑中过滤目标路段后的剩余拓扑进行映射，得到目标映射拓扑，包括：对于所述原始路网拓扑中不包含所述限制路段串的第一子拓扑，遍历所述第一子拓扑中各个第一路段，将遍历到的第一路段进行映射，得到第一映射路段，各个第一映射路段构成第一映射拓扑；

对于所述原始路网拓扑中仅包含所述限制路段串的第二子拓扑，遍历所述第二子拓扑中各个第二路段，若遍历到的第二路段为目标路段，则对遍历到的第二路段进行丢弃，若遍历到的第二路段不是目标路段，则将遍历到的第二路段进行映射，得到第二映射路段，各个第二映射路段构成第二映射拓扑；

将所述第一映射拓扑以及所述第二映射拓扑所构成的拓扑，作为目标映射拓扑。

8.根据权利要求1所述的方法，其特征在于，所述方法还包括：

当接收到路径规划请求时，基于所述路径规划请求确定所述规划起点和所述规划终点；

在所述规划拓扑中，基于所述规划起点和所述规划终点进行搜索，得到所述规划起点和所述规划终点之间的规划路段串；

基于所述规划拓扑与所述原始路网拓扑之间的映射关系，从所述原始路网拓扑中确定所述规划路段串对应的原始路段串，将所述原始路段串所确定的路径作为所述规划起点和所述规划终点之间的目标路径。

9.根据权利要求8所述的方法，其特征在于，所述基于所述规划拓扑与所述原始路网拓扑之间的映射关系，从所述原始路网拓扑中确定所述规划路段串对应的原始路段串，包括：从所述原始路网拓扑中确定与所述规划路段串所包含的节点存在映射关系的目标节点，以及与所述规划路段串所包含的连接边存在映射关系的目标连接边；

基于所述目标节点和所述目标连接边之间的连接关系，得到所述原始路段串。

10.一种路径规划方法，其特征在于，所述方法包括：

获取路径规划请求，根据所述路径规划请求确定规划起点和规划终点；

在规划拓扑中，基于所述规划起点和所述规划终点进行搜索，得到所述规划起点和所述规划终点之间的规划路段串；

其中，所述规划拓扑是目标映射拓扑以及等效映射路段串所构成的拓扑，所述目标映射拓扑是将原始路网拓扑中过滤目标路段后的剩余拓扑进行映射得到的，所述等效映射路段串与所述原始路网拓扑中的目标路段串对应的，所述原始路网拓扑是基于真实路径信息得到的，所述原始路网拓扑中包括限制路段串，所述限制路段串用于表征真实路径信息中的限制通行路径，所述目标路段为所述限制路段串中的路段，所述目标路段串为所述原始路网拓扑中包含所述目标路段的非限制路段串；

基于所述规划拓扑与所述原始路网拓扑之间的映射关系，从所述原始路网拓扑中确定所述规划路段串对应的原始路段串，将所述原始路段串所确定的路径作为所述规划起点和所述规划终点之间的目标路径。

11.根据权利要求10所述的方法，其特征在于，所述基于所述规划拓扑与所述原始路网拓扑之间的映射关系，从所述原始路网拓扑中确定所述规划路段串对应的原始路段串，包括：从所述原始路网拓扑中确定与所述规划路段串所包含的节点存在映射关系的目标节点，以及与所述规划路段串所包含的连接边存在映射关系的目标连接边；

基于所述目标节点和所述目标连接边之间的连接关系，得到所述原始路段串。

12.根据权利要求10所述的方法，其特征在于，所述等效映射路段串的创建步骤包括：对于所述原始路网拓中所包括的限制路段所组成的限制路段集合，将其中包括于所述目标路段串的限制路段作为目标限制路段；

创建所述目标限制路段对应的等效映射路段；

基于所述等效映射路段，确定所述目标路段串对应的等效映射路段串。

13.一种路径数据处理装置，其特征在于，所述装置包括：

原始拓扑获取模块，用于获取基于真实路径信息得到的原始路网拓扑，所述原始路网拓扑中包括限制路段串，所述限制路段串用于表征真实路径信息中的限制通行路径；

原始拓扑映射模块，用于将所述原始路网拓扑中过滤目标路段后的剩余拓扑进行映射，得到目标映射拓扑，所述目标路段为所述限制路段串中的路段；

等效路段创建模块，用于创建与所述原始路网拓扑中的目标路段串对应的等效映射路段串，所述目标路段串为所述原始路网拓扑中包含所述目标路段的非限制路段串；

规划拓扑确定模块，用于将所述目标映射拓扑以及所述等效映射路段串所构成的拓扑，确定为规划拓扑，所述规划拓扑用于规划得到规划起点和规划终点之间的目标路径。

14.根据权利要求13所述的装置，其特征在于，所述等效路段创建模块还用于：对于所述原始路网拓中所包括的限制路段所组成的限制路段集合，将其中包括于所述目标路段串的限制路段作为目标限制路段；

创建所述目标限制路段对应的等效映射路段；

基于所述等效映射路段，确定所述目标路段串对应的等效映射路段串。

15.根据权利要求14所述的装置，其特征在于，所述等效路段创建模块还用于：若所述目标路段为所述限制路段串中的起始路段，则将所述限制路段串的中间限制节点作为目标限制节点；

创建与所述目标限制节点对应的等效映射节点，基于所述等效映射节点创建所述目标限制路段对应的等效映射路段。

16.根据权利要求15所述的装置，其特征在于，所述等效路段创建模块还用于：若所述目标映射拓扑存在与所述起始路段的源节点对应的映射节点，则在所述源节点对应的映射节点与第一目标等效映射节点之间建立所述起始路段中连接边的等效映射边，以创建所述起始路段对应的第一等效映射路段；

其中，所述第一目标等效映射节点为所述起始路段的目标节点对应的等效映射节点。

17.根据权利要求15所述的装置，其特征在于，所述等效路段创建模块还用于：若所述限制路段串包括至少三个限制路段，则

在各个目标限制节点对应的等效映射节点之间建立所述限制路段串中的中间连接边的等效映射边，以构建所述限制路段串中的中间限制路段对应的第二等效映射路段；

其中，所述限制路段串中的中间连接边为所述中间限制路段中的连接边。

18.根据权利要求15所述的装置，其特征在于，所述等效路段创建模块还用于：对于包含一个非限制节点的目标路段串，将所述目标路段串中连接限制节点和非限制节点的连接边作为目标连接边；

在所述目标连接边所连接的非限制节点对应的映射节点和所述目标连接边所连接的限制节点对应的等效映射节点之间，建立所述目标连接边的等效映射边，将所述等效映射边所在的等效映射路段作为所述目标连接边所在的目标限制路段对应的第三等效映射路段。

19.根据权利要求13所述的装置，其特征在于，所述原始拓扑映射模块还用于：对于所述原始路网拓扑中不包含所述限制路段串的第一子拓扑，遍历所述第一子拓扑中各个第一路段，将遍历到的第一路段进行映射，得到第一映射路段，各个第一映射路段构成第一映射拓扑；

对于所述原始路网拓扑中仅包含所述限制路段串的第二子拓扑，遍历所述第二子拓扑中各个第二路段，若遍历到的第二路段为目标路段，则对遍历到的第二路段进行丢弃，若遍历到的第二路段不是目标路段，则将遍历到的第二路段进行映射，得到第二映射路段，各个第二映射路段构成第二映射拓扑；

将所述第一映射拓扑以及所述第二映射拓扑所构成的拓扑，作为目标映射拓扑。

20.根据权利要求13所述的装置，其特征在于，所述装置还包括路径规划模块，用于：当接收到路径规划请求时，基于所述路径规划请求确定所述规划起点和所述规划终点；

在所述规划拓扑中，基于所述规划起点和所述规划终点进行搜索，得到所述规划起点和所述规划终点之间的规划路段串；

基于所述规划拓扑与所述原始路网拓扑之间的映射关系，从所述原始路网拓扑中确定所述规划路段串对应的原始路段串，将所述原始路段串所确定的路径作为所述规划起点和所述规划终点之间的目标路径。

21.根据权利要求20所述的装置，其特征在于，所述路径规划模块，还用于：从所述原始路网拓扑中确定与所述规划路段串所包含的节点存在映射关系的目标节点，以及与所述规划路段串所包含的连接边存在映射关系的目标连接边；

基于所述目标节点和所述目标连接边之间的连接关系，得到所述原始路段串。

22.一种路径规划装置，其特征在于，所述装置包括：

规划请求获取模块，用于获取路径规划请求，根据所述路径规划请求确定规划起点和规划终点；

路段串搜索模块，用于在规划拓扑中，基于所述规划起点和所述规划终点进行搜索，得到所述规划起点和所述规划终点之间的规划路段串；其中，所述规划拓扑是目标映射拓扑以及等效映射路段串所构成的拓扑，所述目标映射拓扑是将原始路网拓扑中过滤目标路段后的剩余拓扑进行映射得到的，所述等效映射路段串与所述原始路网拓扑中的目标路段串对应的，所述原始路网拓扑是基于真实路径信息得到的，所述原始路网拓扑中包括限制路段串，所述限制路段串用于表征真实路径信息中的限制通行路径，所述目标路段为所述限制路段串中的路段，所述目标路段串为所述原始路网拓扑中包含所述目标路段的非限制路段串；

目标路径确定模块，用于基于所述规划拓扑与所述原始路网拓扑之间的映射关系，从所述原始路网拓扑中确定所述规划路段串对应的原始路段串，将所述原始路段串所确定的路径作为所述规划起点和所述规划终点之间的目标路径。

23.根据权利要求22所述的装置，其特征在于，所述目标路径确定模块还用于：从所述原始路网拓扑中确定与所述规划路段串所包含的节点存在映射关系的目标节点，以及与所述规划路段串所包含的连接边存在映射关系的目标连接边；

基于所述目标节点和所述目标连接边之间的连接关系，得到所述原始路段串。

24.根据权利要求22所述的装置，其特征在于，上述装置还包括等效路段创建模块，用于：对于所述原始路网拓中所包括的限制路段所组成的限制路段集合，将其中包括于所述目标路段串的限制路段作为目标限制路段；

创建所述目标限制路段对应的等效映射路段；

基于所述等效映射路段，确定所述目标路段串对应的等效映射路段串。

25.一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，其特征在于，所述处理器执行所述计算机程序时实现权利要求1至9或者10至12中任一项所述的方法的步骤。

26.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现权利要求1至9或者10至12中任一项所述的方法的步骤。

说明书

路径数据处理、路径规划方法、装置和计算机设备

技术领域

[0001] 本申请涉及计算机技术领域，特别是涉及一种路径数据处理方法、装置、计算机设备、存储介质和计算机程序产品，以及一种路径规划方法、装置、计算机设备、存储介质和计算机程序产品。

背景技术

[0002] 随着计算机技术的发展，出现了路径规划技术，通过路径规划可以为用户推荐最优路径，用户可以通过最优路径进行导航。为确定用户可以顺利通行，对话得到的最优路径中不能包含限制通行路径，限制通行路径例如是违反交通规则的路径。

[0003] 传统技术中，为避免规划的最优路径中包含限制通行路径，在进行路径规划后，需要进行回溯，验证当前的最优路径是否包含了限制通行路径，导致路径规划的效率低。

发明内容

[0004] 基于此，有必要针对上述技术问题，提供一种能够提高路径规划消息的路径数据处理方法、装置、计算机设备、计算机可读存储介质和计算机程序产品，以及一种路径规划方法、装置、计算机设备、存储介质和计算机程序产品。

[0005] 一方面，本申请提供了一种路径数据处理方法。所述方法包括：获取基于真实路径信息得到的原始路网拓扑，所述原始路网拓扑中包括限制路段串，所述限制路段串用于表征真实路径信息中的限制通行路径；将所述原始路网拓扑中过滤目标路段后的剩余拓扑进行映射，得到目标映射拓扑，所述目标路段为所述限制路段串中的路段；创建与所述原始路网拓扑中的目标路段串对应的等效映射路段串，所述目标路段串为所述原始路网拓扑中包含所述目标路段的非限制路段串；将所述目标映射拓扑以及所述等效映射路段串所构成的拓扑，确定为规划拓扑，所述规划拓扑用于规划得到规划起点和规划终点之间的目标路径。

[0006] 另一方面，本申请还提供了一种路径数据处理装置。所述装置包括：原始拓扑获取模块，用于获取基于真实路径信息得到的原始路网拓扑，所述原始路网拓扑中包括限制路段串，所述限制路段串用于表征真实路径信息中的限制通行路径；原始拓扑映射模块，用于将所述原始路网拓扑中过滤目标路段后的剩余拓扑进行映射，得到目标映射拓扑，所述目标路段为所述限制路段串中的路段；等效路段创建模块，用于创建与所述原始路网拓扑中的目标路段串对应的等效映射路段串，所述目标路段串为所述原始路网拓扑中包含所述目标路段的非限制路段串；规划拓扑确定模块，用于将所述目标映射拓扑以及所述等效映射路段串所构成的拓扑，确定为规划拓扑，所述规划拓扑用于规划得到规划起点和规划终点之间的目标路径。

[0007] 另一方面，本申请还提供了一种计算机设备。所述计算机设备包括存储器和处理器，所述存储器存储有计算机程序，所述处理器执行所述计算机程序时实现上述路径数据处理方法所述的步骤。

[0008] 另一方面，本申请还提供了一种计算机可读存储介质。所述计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现上述路径数据处理方法所述的步骤。

[0009] 另一方面，本申请还提供了一种计算机程序产品。所述计算机程序产品，包括计算机程序，该计算机程序被处理器执行时实现上述路径数据处理方法所述的步骤。

[0010] 上述路径数据处理方法、装置、计算机设备、存储介质和计算机程序产品，通过获取基于真实路径信息得到的原始路网拓扑，原始路网拓扑中包括限制路段串，限制路段串用于表征真实路径信息中的限制通行路径，将原始路网拓扑中过滤目标路段后的剩余拓扑进行映射，得到目标映射拓扑，创建与原始路网拓扑中的目标路段串对应的等效映射路段串，将目标映射拓扑以及等效映射路段串所构成的拓扑，确定为规划拓扑，由于目标路段为限制路段串中的路段，目标路段串为原始路网拓扑中包含目标路段的非限制路段串，得到的规划拓扑中系统性地消除了原始拓扑中的限制路段串，并保留了原始拓扑中所有的非限制路段串，因此，当通过规划拓扑进行路径规划时，可以直接规划得到目标路径，避免了进行回溯验证，提高了路径规划效率。

[0011] 另一方面，本申请提供了一种路径规划方法。所述方法包括：获取路径规划请求，根据所述路径规划请求确定规划起点和规划终点；在规划拓扑中，基于所述规划起点和所述规划终点进行搜索，得到所述规划起点和所述规划终点之间的规划路段串；其中，所述规划拓扑是目标映射拓扑以及等效映射路段串所构成的拓扑，所述目标映射拓扑是将所述原始路网拓扑中过滤目标路段后的剩余拓扑进行映射得到的，所述等效映射路段串与所述原始路网拓扑中的目标路段串对应的，所述原始路网拓扑是基于真实路径信息得到的，所述原始路网拓扑中包括限制路段串，所述限制路段串用于表征真实路径信息中的限制通行路径，所述目标路段为所述限制路段串中的路段，所述目标路段串为所述原始路网拓扑中包含所述目标路段的非限制路段串；基于所述规划拓扑与所述原始拓扑之间的映射关系，从所述原始路网拓扑中确定所述规划路段串对应的原始路段串，将所述原始路段串所确定的路径作为所述规划起点和所述规划终点之间的目标路径。

[0012] 另一方面，本申请提供了一种路径规划装置。所述装置包括：规划请求获取模块，用于获取路径规划请求，根据所述路径规划请求确定规划起点和规划终点；路段串搜索模块，用于在规划拓扑中，基于所述规划起点和所述规划终点进行搜索，得到所述规划起点和所述规划终点之间的规划路段串；其中，所述规划拓扑是目标映射拓扑以及等效映射路段串所构成的拓扑，所述目标映射拓扑是将所述原始路网拓扑中过滤目标路段后的剩余拓扑进行映射得到的，所述等效映射路段串与所述原始路网拓扑中的目标路段串对应的，所述原始路网拓扑是基于真实路径信息得到的，所述原始路网拓扑中包括限制路段串，所述限制路段串用于表征真实路径信息中的限制通行路径，所述目标路段为所述限制路段串中的路段，所述目标路段串为所述原始路网拓扑中包含所述目标路段的非限制路段串；目标路径确定模块，用于基于所述规划拓扑与所述原始拓扑之间的映射关系，从所述原始路网拓扑中确定所述规划路段串对应的原始路段串，将所述原始路段串所确定的路径作为所述规划起点和所述规划终点之间的目标路径。

[0013] 另一方面，本申请还提供了一种计算机设备。所述计算机设备包括存储器和处理器，所述存储器存储有计算机程序，所述处理器执行所述计算机程序时实现上述路径规划方法所述的步骤。

[0014] 另一方面，本申请还提供了一种计算机可读存储介质。所述计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现上述路径规划方法所述的步骤。

[0015] 另一方面，本申请还提供了一种计算机程序产品。所述计算机程序产品，包括计算机程序，该计算机程序被处理器执行时实现上述路径规划方法所述的步骤。

[0016] 上述路径规划方法、装置、计算机设备、存储介质和计算机程序产品，由于规划拓扑是目标映射拓扑以及等效映射路段串所构成的拓扑，目标映射拓扑是将原始路网拓扑中过滤目标路段后的剩余拓扑进行映射得到的，等效映射路段串与原始路网拓扑中的目标路段串对应的，原始路网拓扑是基于真实路径信息得到的，原始路网拓扑中包括限制路段串，限制路段串用于表征真实路径信息中的限制通行路径，目标路段为限制路段串中的路段，目标路段串为原始路网拓扑中包含目标路段的非限制路段串，得到的规划拓扑中系统性地消除了原始拓扑中的限制路段串，并保留了原始拓扑中所有的非限制路段串，因此，当通过规划拓扑进行路径规划时，得到的规划路段串不包含限制路段串，从而通过映射关系可以从原始路网拓扑中确定不包括限制路段串的原始路段串，避免了对路段串进行回溯验证，提高了路径规划效率。

附图说明

[0017] 图1为一个实施例中路径数据处理方法以及路径规划方法的应用环境图；

[0018] 图2为一个实施例中路径数据处理方法的流程示意图；

[0019] 图3为一个实施例中路段串的示意图；

[0020] 图4为一个实施例中包含一条直达路径的限制通行路径的路径示意图；

[0021] 图5为一个实施例中包含两条直达路径的限制通行路径的路径示意图；

[0022] 图6为一个实施例中包含三条直达路径的限制通行路径的路径示意图；

[0023] 图7为一个实施例中原始路网拓扑得到的剩余拓扑的示意图；

[0024] 图8为一个实施例中由原始路网拓扑得到的规划拓扑的示意图；

[0025] 图9为一个实施例中路径规划方法的流程示意图；

[0026] 图10为一个实施例中路径数据处理装置的结构框图；

[0027] 图11为一个实施例中路径规划装置的结构框图；

[0028] 图12为一个实施例中计算机设备的内部结构图。

具体实施方式

[0029] 为了使本申请的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本申请进行进一步详细说明。应当理解，此处描述的具体实施例仅仅用以解释本申请，并不用于限定本申请。

[0030] 本申请实施例提供的路径数据处理方法以及路径规划方法，可以应用于智能交通系统和智能车路协同系统中，其中：

[0031] 智能交通系统(Intelligent Traffic  System，ITS)又称智能运输系统(Intelligent Transportation System)，是将先进的科学技术(信息技术、计算机技术、数据通信技术、传感器技术、电子控制技术、自动控制理论、运筹学、人工智能等)有效地综合运用于交通运输、服务控制和车辆制造，加强车辆、道路、使用者三者之间的联系，从而形成一种保障安全、提高效率、改善环境、节约能源的综合运输系统。或者；

[0032] 智能车路协同系统(Intelligent Vehicle Infrastructure Cooperative Systems，IVICS)，简称车路协同系统，是智能交通系统(ITS)的一个发展方向。车路协同系统是采用先进的无线通信和新一代互联网等技术，全方位实施车车、车路动态实时信息交互，并在全时空动态交通信息采集与融合的基础上开展车辆主动安全控制和道路协同管理，充分实现人车路的有效协同，保证交通安全，提高通行效率，从而形成的安全、高效和环保的道路交通系统。

[0033] 本申请实施例提供的路径数据处理方法以及路径规划方法，可以应用于如1所示的应用环境中。其中，终端102通过网络与服务器104进行通信。数据存储系统可以存储服务器104需要处理的路径数据。数据存储系统可以集成在服务器104上，也可以放在云上或其他服务器上。其中，终端102可以但不限于是各种台式计算机、笔记本电脑、智能手机、平板电脑、物联网设备和便携式可穿戴设备，物联网设备可为智能音箱、智能电视、智能空调、智能车载设备等。便携式可穿戴设备可为智能手表、智能手环、头戴设备等。服务器104可以用独立的服务器或者是多个服务器组成的服务器集群来实现。

[0034] 本申请实施例提供的路径数据处理方法以及路径规划方法可以由终端或者服务器单独执行，也可以由终端和服务器协同执行。

[0035] 例如，服务器104可以获取基于真实路径信息得到的原始路网拓扑，原始路网拓扑中包括限制路段串，限制路段串用于表征真实路径信息中的限制通行路径，将原始路网拓扑中过滤目标路段后的剩余拓扑进行映射，得到目标映射拓扑，目标路段为限制路段串中的路段，创建与原始路网拓扑中的目标路段串对应的等效映射路段串，目标路段串为原始路网拓扑中包含目标路段的非限制路段串，将目标映射拓扑以及等效映射路段串所构成的拓扑，确定为规划拓扑。

[0036] 终端102可以向服务器104发送携带规划起点和规划终端的路径规划请求，服务器基于路径规划请求确定规划起点和规划终点，在规划拓扑中，基于规划起点和规划终点进行搜索，得到规划起点和规划终点之间的规划路段串，基于规划拓扑与原始拓扑之间的映射关系，从原始路网拓扑中确定规划路段串对应的原始路段串，将原始路段串所确定的路径作为规划起点和规划终点之间的目标路径。

[0037] 在一个实施例中，如图2所示，提供了一种路径数据处理方法，以该方法应用于图1中的服务器为例进行说明，包括以下步骤：

[0038] 步骤202，获取基于真实路径信息得到的原始路网拓扑，原始路网拓扑中包括限制路段串，限制路段串用于表征真实路径信息中的限制通行路径。

[0039] 其中，真实路径信息指的是现实世界中真实的路径信息，通过对现实世界中包含的具体路段、具体地点等数据进行采集得到。原始路网拓扑是基于真实路径信息得到的，反映的是现实世界中真实的路径信息。原始路网拓扑是一种图结构，包括节点、连接边以及连接关系等拓扑结构数据，节点用于表示具体地点，连接边用于表示两个地点之间的直达路径，其中，A地点到B地点的直达路径可以理解为通过该直达路径从A地点到B地点时，不需要经过其他地点。一条连接边，以及该连接边连接的两个节点共同用于表示一个路段。路段串指的是前后连接的路段集合。如果使用N(Node)表示原始路网拓扑的节点，使用L(Link)表示路网拓扑的连接边，那么一条路段串可以表示为N0L0N1L1..NiLi..NnLnNn+1，其中的Li源节点是Ni，目标节点是Ni+1，NiLiNi+1表示一个路段。如图3所示，图3中的路段串可以表示为N0L0N1L1N2L2N3。

[0040] 原始路网拓扑中包括限制路段串。限制路段串用于表征真实路径信息中的限制通行路径。限制通行路径指的是不可通行路径。例如可以是交通管理法律法规规定的不可通行路径，或者可以是根据路况信息确定的不可通行路径，例如交通拥堵路径。限制通行路径可以只包含一条直达路径，举例说明，如图4所示，为一个实施例中包含一条直达路径的限制通行路径的路径示意图，图4中的（a）图中，从A地点到B地点的路径为只包含一条直达路径的限制通行路径；限制通行路径中也可以包括两条直达路径，举例说明，如图5所示，为一个实施例中包含两条直达路径的限制通行路径的路径示意图，图5中的（a）图中从A地点到C地点的路径为包含两条直达路径的限制通行路径；限制通行路径中也可以包括三条或者三条以上直达路径，举例说明，如图6所示，为一个实施例中包含三条直达路径的限制通行路径的路径示意图，图6中的（a）图中从A地点到D地点的路径为包含三条直达路径的限制通行路径。可以理解的是，当存在限制通行路径时，规划得到的路径需要绕开该限制通行路径，例如，绕开图4中的（a）图所示的限制通行路径，规划得到起点到终点的路径可以如图4中的（b）图所示；绕开图5中的（a）图所示的限制通行路径，规划得到起点到终点的路径可以如图5中的（b）图所示；绕开图6中的（a）图所示的限制通行路径，规划得到起点到终点的路径可以如图6中的（b）图所示，其中，图6中的（a）图所示的限制通行路径是为了禁止进入环岛以后右转，规划的路径中提前右转，从而避免环岛拥堵。

[0041] 根据所表征的限制通行路径所包含的直达路径数量，限制路段串可以是包含一个路段的限制路段串，例如可以表示为N0L0N1，也可以是包含两个路段的限制路段串，例如可以表示为N0L0N1L1N2，还可以是包含三个或三个以上路段的限制路段串，例如包含三个路段时可以表示为N0L0N1L1N2L2N3。需要说明的是，本申请实施例的限制路段串主要指的是包括两个或者两个以上路段的限制路段串。

[0042] 原始路网拓扑中可以包括一个或者多个限制路段串。对于包含多个路段的限制路段串，只有当所有的路段都连通时，才为限制路段串，例如，假设N0L0N1L1N2L2N3为包含三个路段的限制路段串，那么只有N0L0N1、N1L1N2、N2L2N3这三条路段同时连通时才为限制路段串，如果只包括其中部分路段不是限制路段串，例如N0L0N1L1N2不是限制路段串。

[0043] 具体地，服务器可以从本地获取原始路网拓扑，或者通过网络从其他计算机设备获取原始路网拓扑，根据该原始路网拓扑，服务器可以生成用于路径规划的规划拓扑。

[0044] 步骤204，将原始路网拓扑中过滤目标路段后的剩余拓扑进行映射，得到目标映射拓扑，目标路段为限制路段串中的路段。

[0045] 其中，原始路网拓扑中过滤目标路段后的剩余拓扑指的是原始路网拓扑中去除目标路段剩下的所有路段所构成的拓扑。可以理解的是，若目标路径的源节点和目标节点还同时是其他目标路段的源节点或者目标节点，则只需要过滤目标路段的连接边即可。目标路段为限制路段串中的路段，可以预先进行设定。目标路段可以是限制路段串中的任意一个路段，并且限制路段串可以包括一个或者多个目标路段。举例说明，假设原始拓扑为图7中的左图，其中N0L0N1L1N2L2N3为限制路段串，若路段N0L0N1为目标路段，则过滤目标路段后的剩余拓扑如图7中的右图所示。由图7可以看出，过滤掉目标路段后，原本的限制路段串被断开了，处于不连通的状态，而由于目标路段中的节点N0同时是路段N0L6N6的节点，因此该节点在剩余拓扑中仍然存在。

[0046] 具体地，服务器将原始路网拓扑中过滤目标路段后的剩余拓扑进行映射，得到目标映射拓扑。目标映射拓扑中的拓扑结构数据与原始路网拓扑中的拓扑结构数据存在一一对应的映射关系。例如，对于原始路网拓扑中的每一个节点，在目标映射拓扑中存在与之对应的映射节点，对于原始路网拓扑中的每一条连接边，在目标映射拓扑中存在与之对应的映射边，对于原始路网拓扑中所有的连接关系，在目标映射拓扑中存在与之对应的连接关系。

[0047] 在一个实施例中，服务器可以遍历原始路网中的每一个路段，对于遍历到的每一个路段，判断该路段是否为目标路段，若是遍历到的路段为目标路段，则不进行映射，若是遍历到的路段不是目标路段，则将遍历到的路段进行映射，得到目标映射路段，所有目标映射路段所构成的拓扑即为目标映射拓扑。目标映射拓扑是通过原始路网拓扑进行映射得到的，因此，目标映射拓扑中的每一条目标映射路段在原始路网拓扑中都存在与之对应的路段。并且由于未对目标路段进行映射，在得到的目标映射拓扑中，与限制路段串存在映射关系的路段串是不连通的，即通过将原始路网拓扑中过滤目标路段后的剩余拓扑进行映射，可以得到不包含限制路段串的拓扑。

[0048] 在一个实施例中，若原始路网拓扑中包括多个限制路段串，则对于每一个限制路段串中都需要设定至少一个目标路段，服务器在遍历的过程中，对于所有限制路段串中的目标路段都不进行映射，从而得到的目标映射拓扑中，不包含任何限制路段串。

[0049] 步骤206，创建与原始路网拓扑中的目标路段串对应的等效映射路段串，目标路段串为原始路网拓扑中包含目标路段的非限制路段串。

[0050] 其中，目标路段串为原始路网拓扑中包含目标路段的非限制路段串。原始路网拓扑可以包括一个或者多个目标路段串。每一个路段在原始拓扑中可以作为多个路段串中路段，因此，目标路段除了作为限制路段串中的路段，还可以同时是非限制路段串中的路段。举例说明，参考图7，连接边L0所在的目标路段除了是限制路段串N0L0N1L1N2L2N3中的路段外，还同时是N0L0N1L1N2L3N4和N0L0N1L4N5中的路段。

[0051] 目标路网拓扑中某个目标路段串对应的等效映射路段串为与该目标路段串的映射路段串等效的路段串，即该等效映射路段串可以作为该目标路段串的映射路段串的等效替代。由于目标映射拓扑中是不存在目标路段串对应的映射路段串的，这里的等效可以理解为，该等效映射路段并不是目标路段串在目标映射拓扑中的映射路段串，但是与目标路段串在目标映射拓扑中的映射路段串效果相同，可以表示相同的路径信息。可以理解的是，由于等效映射路段串是目标路段串的映射路段串的等效替代，对于目标路段串与其映射路段串之间的映射关系，在等效映射路段串与该目标路段串之间存在同样的映射关系，并且在等效映射路段串与该映射路段串之间存在同样的映射关系。

[0052] 具体地，由于目标映射拓扑是将原始路网拓扑中过滤目标路段后的剩余拓扑进行映射得到的，目标映射拓扑中不包含目标路段的映射路段，那么原始路网拓扑中的目标路段串，在目标映射拓扑中不存在与之对应的映射路段串，如果直接基于目标映射拓扑进行路径规划，则对于目标路段串所表示的路径搜索不到，会导致路径规划的准确性降低，因此服务器可以额外创建目标路段串的等效映射路段串，等效映射路段串与目标路段串的映射路段串等效，可以用于替代目标路段串的映射路段串，创建的等效映射路段串要保证不会使得限制路段串的映射路段串处于联通状态，并且等效路段串与目标映射拓扑所构成的拓扑中，限制路段串的映射路段串也不会处于联通状态。

[0053] 在一个实施例中，服务器可以基于目标映射拓扑，创建目标路段串对应的等效映射路段串。

[0054] 在一个实施例中，对于每一个目标路段串中包含的各个路段，服务器可以分别创建对应的等效映射路段，将这些等效映射路段所构成的路段串，确定为目标路段串对应的等效映射路段串。可以理解的是，两个不同的目标路段串可能包括一个或者两个相同的路段，对于这些相同的路段，只需要创建一次等效映射路段即可。举个例子，参考图7，目标路段串N0L0N1和目标路段串N0L0N1L1N2包含相同的路段N0L0N1，只需要对路段N0L0N1创建一次等效映射路段。

[0055] 步骤208，将目标映射拓扑以及等效映射路段串所构成的拓扑，确定为规划拓扑，规划拓扑用于规划得到规划起点和规划终点之间的目标路径。

[0056] 具体地，目标映射拓扑以及等效映射路段串可以重新构成一个拓扑，在重新构成的拓扑中，若目标映射拓扑和等效映射路段串包括相同的连接边，则可以合并成一条连接边，若目标映射拓扑和等效映射路段串包括相同的节点，则可以合并为同一个节点，目标映射拓扑以及等效映射路段串所构成的拓扑即为规划拓扑。需要说明的是，这里相同的节点，指的是某个节点既是目标映射拓扑中的节点，也是等效映射路段串中的节点，相同的连接边，指的是某个连接边既是目标映射拓扑中的连接边，也是等效映射路段串中的连接边。映射节点和等效映射节点不是相同的节点，同样的，映射边和等效映射边也不是相同的连接边。

[0057] 由于目标映射拓扑与原始路网拓扑中过滤目标路段后的剩余拓扑之间存在映射关系，并且等效映射路段串与原始路网拓扑中包含目标路段的非限制路段串存在映射关系，那么目标映射拓扑以及等效映射路段串所构成的规划拓扑，与原始路网拓扑必然存在映射关系。在该规划拓扑中，除去限制路段串外，原始路段串中其他所有的路段串都存在对应的映射路段串，即规划拓扑中，系统性地消除了所有的限制路段串。服务器可以基于规划拓扑进行路径规划，确定规划起点和规划终点之间的最优路段串，得到的最优路段串中不会包含限制路段串。

[0058] 在一个实施例中，当接收到路径规划请求时，服务器可以基于路径规划请求确定规划起点和规划终点，在规划拓扑中，基于规划起点和规划终点进行搜索，得到规划起点和规划终点之间的规划路段串，基于规划拓扑与原始路网拓扑之间的映射关系，从原始路网拓扑中确定规划路段串对应的原始路段串，将原始路段串所确定的路径作为规划起点和规划终点之间的目标路径。

[0059] 举例说明，参考图8，为一个实施例中，由原始路网拓扑得到规划拓扑的示意图，图8中的（a）图为原始路网拓扑，图8中的（b）图为规划拓扑，图8中，N0L0N1L1N2L2N3为限制路段串，N0L0N1为目标路段，N0L0N1、N0L0N1L1N2、N0L0N1L1N2L3N4、N0L0N1L4N5均为包括目标路段N0L0N1的非限制路段串，即这些路段串为目标路段串，由图8中的（b）图可以看出，由于映射过程中过滤了目标路段，N0L0N1、N0L0N1L1N2、N0L0N1L1N2L3N4、N0L0N1L4N5这些目标路段串在规划拓扑中都被打断了，因此需要针对这些目标路段串生成对应的等效路段串，即N0L0N1对应的等效映射路段串N0L10N1，N0L0N1L1N2对应的等效映射路段串N0L10N10L11N20，N0L0N1L1N2L3N4对应的等效映射路段串N0L10N10L11N20 L13N4，N0L0N1L4N5对应的等效映射路段串N0L10N10L14N5。可以理解的是，在图8中，除去等效路段串之外的其他路段串所构成的拓扑即为目标映射拓扑。

[0060] 上述路径数据处理方法中，通过获取基于真实路径信息得到的原始路网拓扑，原始路网拓扑中包括限制路段串，限制路段串用于表征真实路径信息中的限制通行路径，将原始路网拓扑中过滤目标路段后的剩余拓扑进行映射，得到目标映射拓扑，创建与原始路网拓扑中的目标路段串对应的等效映射路段串，将目标映射拓扑以及等效映射路段串所构成的拓扑，确定为规划拓扑，由于目标路段为限制路段串中的路段，目标路段串为原始路网拓扑中包含目标路段的非限制路段串，得到的规划拓扑中系统性地消除了原始拓扑中的限制路段串，并保留了原始拓扑中所有的非限制路段串，因此，当通过规划拓扑进行路径规划时，可以直接规划得到目标路径，避免了进行回溯验证，提高了路径规划效率。

[0061] 在一个实施例中，创建与原始路网拓扑中的目标路段串对应的等效映射路段串，包括：对于原始路网拓中所包括的限制路段所组成的限制路段集合，将其中包括于目标路段串的限制路段作为目标限制路段；创建目标限制路段对应的等效映射路段；基于等效映射路段，确定目标路段串对应的等效映射路段串。

[0062] 其中，限制节点指的是限制路段串中所包括的节点，例如图7中限制路段串N0L0N1L1N2L2N3中的节点N0、N1、N2、N3为限制节点。限制路段指的是源节点为限制节点的路段，限制路段的目标节点可以为限制节点，例如图7中的限制路段N0L0N1、N1L1N2、N2L2N3，限制路段的目标节点也可以不是限制节点，例如图7中的限制路段N2L3N4。限制路段集合指的是原始路网拓扑中所有的限制路段所组成的集合。非限制路段指的是源节点不是限制节点的路段，例如图7中的路段N4L5N3。包括于目标路段串的限制路段，即该限制路段同时是限制路段串和目标路段串中的路段，举例说明，参考图7，图7中的限制路段N0L0N1既是限制路段串N0L0N1L1N2L2N3中的路段，也是目标路段串N0L0N1L1N2中的路段。原始路网拓扑中某个原始路段对应的等效映射路段为与该原始路段的映射路段等效的路段，即该等效映射路段可以作为该原始路段的映射路段的等效替代。

[0063] 具体地，服务器将限制路段集合中，包括于目标路段串的限制路段作为目标限制路段，分别创建这些目标限制路段对应的等效映射路段，进而基于创建的等效映射路段，确定各个目标路段串对应的等效映射路段串。

[0064] 在一个实施例中，若某个目标路段串中仅包括目标限制路段，则该目标路段串所包括的目标限制路段对应的等效映射路段所构成的路段串即为该目标路段串的等效映射路段串，举例说明，继续参考图8，图8中的路段串N0L0N1L1N2仅包括目标限制路段N0L0N1、N1L1N2，则对这两个目标限制路段创建了对应的等效映射路段串N0L0N10和N10L11N20后，这两个等效映射路段串所构成的路程串N0L0N10L11N20即为该路段串对应的等效映射路段串。

[0065] 在一个实施例中，若某个目标路段串中不仅包括目标限制路段，还包括非目标限制路段，则服务器可以将该其中的目标限制路段对应的等效映射路段与其中的非目标限制路段共同构成的路段串，确定为目标路段串对应的等效映射路段串。这里的非目标限制路段包括非限制路段以及限制路段集合中除目标限制路段外的其他限制路段。举例说明，继续参考图8，图8中的路段串N0L0N1L1N2L3N4L5N3包括目标限制路段N0L0N1、N1L1N2和N2L3N4，还包括非目标限制路段N4L5N3，则可以将N0L0N1、N1L1N2和N2L3N4的等效映射路段，即N0L10N10、N10L11N20和N20L13N4，和非目标限制路段N4L5N3所构成的路段串N0L10N10L11N20L13N4L5N3确定为路段串N0L0N1L1N2L3N4L5N3的等效映射路段串。

[0066] 上述实施例中，对于原始路网拓中所包括的限制路段所组成的限制路段集合，服务器将其中包括于目标路段串的限制路段作为目标限制路段，创建目标限制路段对应的等效映射路段，进而基于等效映射路段，确定目标路段串对应的等效映射路段串，可以快速得到目标路段串对应的等效映射路段串。

[0067] 需要说明的是，本申请提供的路径数据处理方法以及路径规划方法中，在将原始路网拓扑中过滤目标路段后的剩余拓扑进行映射时，目标路段可以是限制路段串中的任意一个路段，并且过滤的目标路段可以是一个或者多个，以下实施例中，主要以目标路段为限制路段串中的起始路段进行说明。

[0068] 在一个实施例中，创建目标限制路段对应的等效映射路段，包括：若目标路段为限制路段串中的起始路段，则将限制路段串的中间限制节点作为目标限制节点；创建与目标限制节点对应的等效映射节点，基于等效映射节点创建目标限制路段对应的等效映射路段。

[0069] 其中，限制节点中包括头限制节点、尾限制节点以及中间限制节点，头限制节点为限制路段串中起始路段的源节点，尾限制节点为限制路段串中的末尾路段的目标节点，限制路段串的限制节点中除去头限制节点、尾限制节点外，其他都是中间限制节点。原始路网拓扑中某个限制节点对应的等效映射节点为与该限制节点的映射节点等效的节点，即该等效映射节点可以作为该限制节点的映射节点的等效替代。

[0070] 具体地，若目标路段为限制路段串中的起始路段，则服务器可以将限制路段串中的各个中间限制节点作为目标限制节点，创建各个目标限制节点对应的等效映射节点，基于各个等效映射节点创建目标限制路段对应的等效映射路段。

[0071] 在一个实施例中，考虑到目标映射拓扑中已经存在目标限制节点的映射节点，服务器在创建与目标限制节点对应的等效映射节点时，可以对目标限制节点的映射节点进行复制，以创建得到目标限制节点对应的等效映射节点。举例说明，继续参考图8，其中，限制路段串N0L0N1L1N2L2N3的中间限制节点为节点N1和节点N2，节点N10、节点N20分别为节点N1和节点N2的等效映射节点，可以通过对目标映射拓扑中映射得到的节点N1和节点N2进行复制得到。

[0072] 在一个实施例中，服务器还可以创建起始路段的源节点对应的等效映射节点，如此，对于仅包含限制节点的目标路段串，服务器可以在各个等效映射节点间建立目标路段串中的连接边对应的等效映射边，从而可以创建得到该目标路段串中各个路段对应的等效映射路段，这些等效映射路段前后连接形成该目标路段串的等效映射路段串。

[0073] 上述实施例中，通过将限制路段串的中间限制节点作为目标限制节点，创建与目标限制节点对应的等效映射节点，基于等效映射节点创建目标限制路段对应的等效映射路段，由于等效映射路段是基于等效映射节点构建的，可以确保得到的等效映射路段不会使得目标映射拓扑中的限制路段串重新处于连通状态。

[0074] 在一个实施例中，考虑到路径规划的效率，规划拓扑中包含的节点和连接边越多时，服务器在进行路径搜索时，所需花费的时间越长，因此希望得到的规划拓扑在系统消除限制路段串的前提下，拓扑结构越简单越好，基于此，本申请进一步提供以下实施例，旨在进一步简化得到的规划拓扑的拓扑结构。

[0075] 在一个实施例中，基于等效映射节点创建目标限制路段对应的等效映射路段，包括：若目标映射拓扑存在与起始路段的源节点对应的映射节点，则在源节点对应的映射节点与第一目标等效映射节点之间建立起始路段中连接边的等效映射边，以创建起始路段对应的第一等效映射路段；其中，第一目标等效映射节点为起始路段的目标节点对应的等效映射节点。

[0076] 其中，第一目标等效映射节点为起始路段的目标节点对应的等效映射节点。起始路段的目标节点为限制路段串的中间限制节点，其对应的等效映射节点为已经创建好的节点。限制路段串中的中间连接边指的是限制路段串中的中间路段所包括的连接边，例如，图8中限制路段串N0L0N1L1N2L2N3的中间连接边为L1。限制路段串中某个连接边对应的等效映射边为与该连接边的映射边等效的连接边，即该等效映射边可以作为该连接边的映射边的等效替代。

[0077] 具体地，由于限制路段串中的起始路段的源节点可能还同时是其他路段的源节点或者目标节点，在这种情况下，目标映射拓扑中就会存在与起始路段的源节点对应的映射节点，那么在构建限制路段串中的起始路段的等效映射路段时，可以在源节点对应的映射节点与第一目标等效映射节点之间建立起始路段中连接边的等效映射边，从而该等效映射边与源节点对应的映射节点、第一目标等效映射节点共同构成了限制路段串中的起始路段的等效映射路段，为了与后续实施例中等效映射路段进行区分，此处将起始路段的等效映射路段称为第一等效映射路段。

[0078] 举例说明，参考图8，其中，起始路段N0L0N1的源节点为N0，目标节点为N1，目标节点N1对应的等效映射节点为节点N10，则服务器可以在节点N0和节点N10之间建立起始路段中连接边L0的等效映射边L10，最终得到起始路段N0L0N1的等效映射路段N0L10N10。

[0079] 可以理解，通过在起始路段的源节点对应的映射节点与第一目标等效映射节点之间建立起始路段中连接边的等效映射边，得到起始路段的等效映射路段，那么以该等效映射路段可以和与起始路段连接的其他路段进行连接，进而可以在以起始路段为尾路段的所有路段串中替代起始路段，得到这些路段串的等效映射路段串。举例说明，继续参考图8，其中，路段串N6L6N0L0N1中的尾路段为限制路段串N0L0N1L1N2L2N3中的起始路段，那么路段串N6L6N0L10N10可以作为路段串N6L6N0L0N1的等效映射路段串。

[0080] 上述实施例中，若目标映射拓扑存在与起始路段的源节点对应的映射节点，则服务器在创建起始路段对应的第一等效映射路段，可以直接利用源节点对应的映射节点进行创建，避免了对起始路段的源节点创建等效映射节点造成规划拓扑结构冗余，从而可以提高路径规划效率。

[0081] 在一个实施例中，基于等效映射节点创建目标限制路段对应的等效映射路段，包括：对于包含一个非限制节点的目标路段串，将目标路段串中连接限制节点和非限制节点的连接边作为目标连接边；在目标连接边所连接的非限制节点对应的映射节点和目标连接边所连接的限制节点对应的等效映射节点之间，建立目标连接边的等效映射边，将等效映射边所在的等效映射路段作为目标连接边所在的目标限制路段对应的第三等效映射路段。

[0082] 其中，非限制节点指的是原始路网拓扑中除限制节点之外的节点。连接限制节点和非限制节点的连接边，即该连接边的源节点为限制节点，而目标节点为非限制节点。举例说明，参考图8，目标路段串N0L0N1L1N2L3N4中连接限制节点和非限制节点的连接边为L3。

[0083] 具体地，对于包含一个非限制节点的目标路段串，由于其中必然是包含限制节点的，因此必然存在一条连接限制节点和非限制节点的连接边，服务器可以将该连接边作为目标连接边。而由于非限制节点是原始拓扑中过滤目标路段后的剩余拓扑中的节点，在目标映射拓扑中必然存在与之对应的映射节点，因此，服务器可以在目标连接边所连接的非限制节点对应的映射节点和目标连接边所连接的限制节点对应的等效映射节点之间，建立目标连接边的等效映射边，将等效映射边所在的等效映射路段作为目标连接边所在的目标限制路段，目标连接边所在的目标限制路段即目标连接边与该目标连接边所连接的非限制节点对应的映射节点、该目标连接边所连接的限制节点对应的等效映射节点共同构成的路段，该路段即为第三等效映射路段。

[0084] 举例说明，参考图8，目标路段串N0L0N1L1N2L3N4中的目标连接边为L3，在L3所连接的限制节点N2的等效映射节点N20和L3所连接的非限制节点N4的映射节点N4之间建立L3的等效映射边L13，则N20L13N4即为N2L3N4的等效映射路段。

[0085] 可以理解的，通过在目标连接边所连接的非限制节点对应的映射节点和目标连接边所连接的限制节点对应的等效映射节点之间，建立目标连接边的等效映射边，得到的第三等效映射路段与其他的映射路段之间建立了连接，那么对于包括多个非限制节点的目标路段串，该包含一个非限制节点的目标路段串为其子路段串，可以和其他映射路段串共同构成其对应的等效映射路段串。举例说明，参考图8，假设以图8中的节点N4为源节点，还存在其他的以其他非限制节点为目标节点的附加路段，那么这些附加路段和路段串N0L0N1L1N2L3N4共同构成包含多个非限制节点的目标路段串，则路段串N0L10N10L11N20L13N4和这些附加路段共同构成这些包含多个非限制节点的目标路段串对应的等效映射路段串。

[0086] 同理，如果在该包含一个非限制节点的目标路段串之外，还存在以该目标路段串中的非限制节点为源节点，以限制路段串中的限制节点为目标节点的附加路段，那么以该附加路段所重新构成的目标路段串对应的等效路段串，可以由已经构建的等效路段串和该附加路段共同构成。继续参考图8，N4L5N3和N0L0N1L1N2L3N4共同构成新的目标路段串，则N0L10N10L11N20L13N4和N4L5N3共同构成该新的目标路段串对应的等效映射路段串。

[0087] 可见，本申请中，通过对包含一个非限制节点的目标路段串创建等效路段串，就可以实现同时创建得到其他包含该目标路段串的非限制路段的等效映射路段串，不仅提高规划拓扑的生成效率，而且可以大大简化规划拓扑的拓扑结构。

[0088] 上述实施例中，在目标连接边所连接的非限制节点对应的映射节点和目标连接边所连接的限制节点对应的等效映射节点之间，建立目标连接边的等效映射边，将等效映射边所在的等效映射路段作为目标连接边所在的目标限制路段对应的第三等效映射路段，避免了对目标路段串中的非限制节点创建等效映射节点造成规划拓扑结构冗余，从而可以提高路径规划效率。

[0089] 在一个实施例中，基于等效映射节点创建目标限制路段对应的等效映射路段，包括：若限制路段串包括至少三个限制路段，则在各个目标限制节点对应的等效映射节点之间建立限制路段串中的中间连接边的等效映射边，以构建限制路段串中的中间限制路段对应的第二等效映射路段。

[0090] 其中，限制路段串中的中间连接边为中间限制路段中的连接边。举例说明，参考图8，限制路段串N0L0N1L1N2L2N3的中间限制路段为N1L1N2，该中间限制路段所包含的中间连接边为L1。

[0091] 具体地，限制路段串可以包括三个或者三个以上的限制路段，这些限制路段中的中间限制路段与起始路段可以构成目标路段串，对于这种目标路段串，服务器可以在各个目标限制节点对应的等效映射节点之间建立限制路段串中的中间连接边的等效映射边，将等效映射边与等效映射边连接的两个等效映射节点共同构成限制路段串中的中间限制路段对应的等效映射路段，此处称为第二等效映射路段。

[0092] 举例说明，参考图8，限制路段串N0L0N1L1N2L2N3中的目标限制节点为节点N1和节点N2，节点N1和节点N2的等效映射节点为节点N10和节点N20，在节点N10和节点N20之间建立中间连接边L1的等效映射边L11，则可以得到中间限制路段N1L1N2对应的第二等效映射路段N10L11N20。

[0093] 上述实施例中，若限制路段串包括至少三个限制路段，则服务器可以在各个目标限制节点对应的等效映射节点之间建立限制路段串中的中间连接边的等效映射边，从而可以快速创建与包含中间限制路段的目标路段串对应的等效路段串。

[0094] 在一个实施例中，将原始路网拓扑中过滤目标路段后的剩余拓扑进行映射，得到目标映射拓扑，包括：对于原始路网拓扑中不包含限制路段串的第一子拓扑，遍历第一子拓扑中各个第一路段，将遍历到的第一路段进行映射，得到第一映射路段，各个第一映射路段构成第一映射拓扑；对于原始路网拓扑中仅包含限制路段串的第二子拓扑，遍历第二子拓扑中各个第二路段，若遍历到的第二路段为目标路段，则对遍历到的第二路段进行丢弃，若遍历到的第二路段不是目标路段，则将遍历到的第二路段进行映射，得到第二映射路段，各个第二映射路段构成第二映射拓扑；将第一映射拓扑以及第二映射拓扑所构成的拓扑，作为目标映射拓扑。

[0095] 具体地，服务器可以将原始路网拓扑分为两部分，一部分为不包含限制路段串的第一子拓扑，另一部分为仅包含限制路段串的第二子拓扑，对于第一子拓扑，服务器可以遍历第一拓扑中的各个节点和各个连接边，将遍历到的各个节点和各个连接边进行映射，得到各个映射节点和各个映射边，各个映射节点和各个映射边按照原始路网拓扑中的连接关系进行连接得到各个第一映射路段，各个第一映射路段共同构成第一映射拓扑；对于第二子拓扑，遍历第二子拓扑中各个节点和各个连接边，若遍历到的节点为目标路段中的节点，则对遍历到的节点进行丢弃，若遍历到的节点不是目标路段中的节点，则对遍历到的节点进行映射，得到各个映射节点，若遍历到的连接边为目标路段中的连接边，则对遍历到的连接边进行丢弃，若遍历到的连接边不是目标路段中的连接边，则对遍历到的连接边进行映射，得到各个映射边，各个映射节点和各个映射边按照原始路网拓扑中的连接关系进行连接得到各个第二映射路段，各个第二映射路段共同构成第二映射拓扑；最后将第一映射拓扑以及第二映射拓扑所构成的拓扑，作为目标映射拓扑。

[0096] 在一个具体的实施例中，在对节点和连接边进行映射时，服务器可以直接对节点进行复制，得到节点对应的映射节点，服务器可以直接对连接边进行复制，得到映射边。

[0097] 上述实施例中，通过将原始路网拓扑分成两部分进行遍历，对于不包含限制路段串的第一子拓扑可以直接进行映射，避免了对节点和连接边进行不必要的判断，提高映射效率。

[0098] 在一个实施例中，上述方法还包括：当接收到路径规划请求时，基于路径规划请求确定规划起点和规划终点；在规划拓扑中，基于规划起点和规划终点进行搜索，得到规划起点和规划终点之间的规划路段串；基于规划拓扑与原始路网拓扑之间的映射关系，从原始路网拓扑中确定规划路段串对应的原始路段串，将原始路段串所确定的路径作为规划起点和规划终点之间的目标路径。

[0099] 其中，规划请求可以是终端发送至服务器的请求对规划起点和规划终点之间的路径进行规划的请求。规划起点和规划终端携带在规划请求中。规划起点可以是用户输入的具体地点，或者是终端通过定位得到的具体地点。规划终端可以是用户的输入的具体地点。规划拓扑是由目标映射拓扑和等效映射路段串所构成的，其中，目标映射拓扑和原始路网拓扑中过滤目标路段后的剩余拓扑之间存在映射关系，而等效映射路段串和目标路段串之间存在映射关系，因此得到的规划拓扑和原始路网拓扑之间存在映射关系。

[0100] 具体地，当服务器接收到终端发送的路径规划请求时，可以对该规划请求进行解析，获取其中携带的起点和终端，得到规划起点和规划终端，进而在规划拓扑中基于规划起点和规划终点进行搜索，得到规划起点和规划终点之间的最优路径对应的路段串，得到规划路段串。服务器进一步可以基于规划拓扑与原始路网拓扑之间的映射关系，从原始路网拓扑中确定与规划路段串存在映射关系对应的原始路段串，将该原始路段串所确定的路径作为规划起点和规划终点之间的目标路径。

[0101] 在一个实施例中，由于规划拓扑中系统性地消除了限制路段串，服务器可以复用现在的路径搜索算法，例如AStar算法、CRP(Customizable Route Planning)算法等等，通过这些路径搜索算法从规划拓扑中搜索规划起点和规划终点之间的最优路径对应的路段串。

[0102] 进一步，服务器可以向终端返回目标路径，由于目标路径是以路段串的形式体现的，服务器可以将原始路段串返回至终端，终端根据原始路段串可以确定规划起点和规划终点之间的目标路径。

[0103] 上述实施例中，由于规划拓扑中不存在限制路段串，服务器可以直接从规划拓扑中搜索得到规划起点和规划终点之间的规划路段串，避免了进行回溯验证，得到的规划路段串中不会包括限制路段串，提高了路径规划效率。

[0104] 在一个实施例中，基于规划拓扑与原始拓扑之间的映射关系，从原始路网拓扑中确定规划路段串对应的原始路段串，包括：从原始路网拓扑中确定与规划路段串所包含的节点存在映射关系的目标节点，以及与规划路段串所包含的连接边存在映射关系的目标连接边；基于目标节点和目标连接边之间的连接关系，得到原始路段串。

[0105] 其中，由于拓扑中包括的拓扑结构数据包括节点和连接边，因此，规划拓扑和原始路网拓扑之间存在映射关系可以是规划拓扑中的节点和原始路网拓扑中的节点存在映射关系，规划拓扑中的连接边和原始路网拓扑中的连接边存在映射关系。举例说明，继续参考图8，图8中的（b）图和（a）图中，序号相同的节点之间存在映射关系，序号相同的连接边之间存在映射关系，对于（b）图新增的节点，映射关系如下：节点N10和节点N1之间存在映射关系，节点N20和节点N2之间存在映射关系，连接边L10和连接边L0之间存在映射关系，连接边L14和连接边L4之间存在映射关系，连接边L11和连接边L1之间存在映射关系，连接边L13和连接边L3之间存在映射关系。

[0106] 具体地，服务器在搜索得到规划路段串后，根据规划拓扑中包含的节点和连接边，从原始路网拓扑中确定与规划路段串所包含的节点存在映射关系的目标节点，以及与规划路段串所包含的连接边存在映射关系的目标连接边，在原始拓扑中，各个节点和各个连接边之间的连接关系是已经确定的，那么服务器进一步可以基于目标节点和目标连接边之间的连接关系，得到原始路段串。

[0107] 举例说明，继续参考图8，假设规划起点为N0、规划终点为N5，从规划拓扑中搜索得到的规划路段串为N0L10N10L14N5，则根据映射关系，得到目标节点为节点N0、节点N1、节点N5，得到目标连接边为L0和L4，根据这些节点和连接边在原始路网拓扑中的连接关系，得到的原始路段串为N0L0N1L4N5。再比如，假设规划起点为N0、规划终点为N4，从规划拓扑中搜索得到的规划路段串为N0L10N10L11N20L13N4，则根据映射关系，得到目标节点为节点N0、节点N1、节点N2和节点N4，得到目标连接边为L0、L1和L3，根据这些节点和连接边在原始路网拓扑中的连接关系，得到的原始路段串为N0L0N1L1N2L3N4。

[0108] 上述实施例中，通过从原始路网拓扑中确定与规划路段串所包含的节点存在映射关系的目标节点，以及与规划路段串所包含的连接边存在映射关系的目标连接边，基于目标节点和目标连接边之间的连接关系，得到原始路段串，可以将规划拓扑中得到规划路段串快速还原得到原始路段串，提高了路径规划效率。

[0109] 在一个实施例中，如图9所示，提供了一种路径规划方法，以该方法应用于图1中的服务器为例进行说明，包括以下步骤：

[0110] 步骤902，获取路径规划请求，根据路径规划请求确定规划起点和规划终点。

[0111] 步骤904，在规划拓扑中，基于规划起点和规划终点进行搜索，得到规划起点和规划终点之间的规划路段串。

[0112] 其中，规划拓扑是目标映射拓扑以及等效映射路段串所构成的拓扑，目标映射拓扑是将原始路网拓扑中过滤目标路段后的剩余拓扑进行映射得到的，等效映射路段串与原始路网拓扑中的目标路段串对应的，原始路网拓扑是基于真实路径信息得到的，原始路网拓扑中包括限制路段串，限制路段串用于表征真实路径信息中的限制通行路径，目标路段为限制路段串中的路段，目标路段串为原始路网拓扑中包含目标路段的非限制路段串。

[0113] 真实路径信息指的是现实世界中真实的路径信息，通过对现实世界中包含的具体路段、具体地点等数据进行采集得到。原始路网拓扑是基于真实路径信息得到的，反映的是现实世界中真实的路径信息。原始路网拓扑是一种图结构，包括节点、连接边以及连接关系等拓扑结构数据，节点用于表示具体地点，连接边用于表示两个地点之间的直达路径，其中，A地点到B地点的直达路径可以理解为通过该直达路径从A地点到B地点时，不需要经过其他地点。一条连接边，以及该连接边连接的两个节点共同用于表示一个路段。路段串指的是前后连接的路段集合。

[0114] 限制路段串可以是包含一个路段的限制路段串，例如可以表示为N0L0N1，也可以是包含两个路段的限制路段串，例如可以表示为N0L0N1L1N2，还可以是包含三个或三个以上路段的限制路段串，例如包含三个路段时可以表示为N0L0N1L1N2L2N3。需要说明的是，本申请实施例的限制路段串主要指的是包括两个或者两个以上路段的限制路段串。

[0115] 原始路网拓扑中过滤目标路段后的剩余拓扑指的是原始路网拓扑中去除目标路段剩下的所有路段所构成的拓扑。可以理解的是，若目标路径的源节点和目标节点还同时是其他目标路段的源节点或者目标节点，则只需要过滤目标路段的连接边即可。目标路段为限制路段串中的路段，可以预先进行设定。限制路段串中的目标路段可以是一个或者多个。

[0116] 目标路段串为原始路网拓扑中包含目标路段的非限制路段串。原始路网拓扑可以包括一个或者多个目标路段串。每一个路段在原始拓扑中可以作为多个路段串中路段，因此，目标路段除了作为限制路段串中的路段，还可以同时是非限制路段串中的路段。目标路网拓扑中某个目标路段串对应的等效映射路段串为与该目标路段串的映射路段串等效的路段串，即该等效映射路段串可以作为该目标路段串的映射路段串的等效替代。由于等效映射路段串是目标路段串的映射路段串的等效替代，对于目标路段串与其映射路段串之间的映射关系，在等效映射路段串与该目标路段串之间存在同样的映射关系，并且在等效映射路段串与该映射路段串之间存在同样的映射关系。

[0117] 规划请求可以是终端发送至服务器的请求对规划起点和规划终点之间的路径进行规划的请求。规划起点和规划终端携带在规划请求中。规划起点可以是用户输入的具体地点，或者是终端通过定位得到的具体地点。规划终端可以是用户的输入的具体地点。

[0118] 具体地，当服务器接收到终端发送的路径规划请求时，可以对该规划请求进行解析，获取其中携带的起点和终端，得到规划起点和规划终端，进而在规划拓扑中基于规划起点和规划终点进行搜索，得到规划起点和规划终点之间的最优路径对应的路段串，得到规划路段串。

[0119] 步骤906，基于规划拓扑与原始拓扑之间的映射关系，从原始路网拓扑中确定规划路段串对应的原始路段串，将原始路段串所确定的路径作为规划起点和规划终点之间的目标路径。

[0120] 具体地，由于目标映射拓扑与原始路网拓扑中过滤目标路段后的剩余拓扑之间存在映射关系，并且等效映射路段串与原始路网拓扑中包含目标路段的非限制路段串存在映射关系，那么目标映射拓扑以及等效映射路段串所构成的规划拓扑，与原始路网拓扑必然存在映射关系。因此，服务器可以基于规划拓扑与原始路网拓扑之间的映射关系，从原始路网拓扑中确定与规划路段串存在映射关系对应的原始路段串，将该原始路段串所确定的路径作为规划起点和规划终点之间的目标路径。

[0121] 在一个实施例中，由于规划拓扑中系统性地消除了限制路段串，服务器可以复用现在的路径搜索算法，例如AStar算法、CRP(Customizable Route Planning)算法等等，通过这些路径搜索算法从规划拓扑中搜索规划起点和规划终点之间的最优路径对应的路段串。

[0122] 进一步，服务器可以向终端返回目标路径，由于目标路径是以路段串的形式体现的，服务器可以将原始路段串返回至终端，终端根据原始路段串可以确定规划起点和规划终点之间的目标路径。

[0123] 上述实施例中，由于规划拓扑是目标映射拓扑以及等效映射路段串所构成的拓扑，目标映射拓扑是将原始路网拓扑中过滤目标路段后的剩余拓扑进行映射得到的，等效映射路段串与原始路网拓扑中的目标路段串对应的，原始路网拓扑是基于真实路径信息得到的，原始路网拓扑中包括限制路段串，限制路段串用于表征真实路径信息中的限制通行路径，目标路段为限制路段串中的路段，目标路段串为原始路网拓扑中包含目标路段的非限制路段串，得到的规划拓扑中系统性地消除了原始拓扑中的限制路段串，并保留了原始拓扑中所有的非限制路段串，因此，当通过规划拓扑进行路径规划时，得到的规划路段串不包含限制路段串，从而通过映射关系可以从原始路网拓扑中确定不包括限制路段串的原始路段串，避免了对路段串进行回溯验证，提高了路径规划效率。

[0124] 在一个实施例中，基于规划拓扑与原始拓扑之间的映射关系，从原始路网拓扑中确定规划路段串对应的原始路段串，包括：从原始路网拓扑中确定与规划路段串所包含的节点存在映射关系的目标节点，以及与规划路段串所包含的连接边存在映射关系的目标连接边；基于目标节点和目标连接边之间的连接关系，得到原始路段串。

[0125] 在一个实施例中，规划拓扑可以通过以下方式生成：获取基于真实路径信息得到的原始路网拓扑，原始路网拓扑中包括限制路段串，限制路段串用于表征真实路径信息中的限制通行路径；将原始路网拓扑中过滤目标路段后的剩余拓扑进行映射，得到目标映射拓扑，目标路段为限制路段串中的路段；创建与原始路网拓扑中的目标路段串对应的等效映射路段串，目标路段串为原始路网拓扑中包含目标路段的非限制路段串；将目标映射拓扑以及等效映射路段串所构成的拓扑，确定为规划拓扑。

[0126] 在一个实施例中，等效映射路段串的创建步骤包括：对于原始路网拓中所包括的限制路段所组成的限制路段集合，将其中包括于目标路段串的限制路段作为目标限制路段；创建目标限制路段对应的等效映射路段；基于等效映射路段，确定目标路段串对应的等效映射路段串。

[0127] 在一个具体的实施例中，本申请实施例提供的路径数据处理方法以及路径规划方法可以应用于导航场景中，在该导航场景中，当用户通过终端主动请求进行路径规划时，可以利用本申请的方案，根据生成的规划拓扑，生成用户指定的规划起点和规划终点之间的目标路径，然后，将目标路径所对应的路段串数据输出给用户，以使终端可以根据得到的路段串数据进行导航。

[0128] 在该应用场景中，服务器预先通过以下步骤生成规划拓扑，并将规划拓扑，以及规划拓扑与原始路网拓扑之间的映射关系进行保存：

[0129] 1、获取真实路径信息得到的原始路网拓扑 ，原始路网拓扑中包括限制路段串，限制路段串用于表征真实路径信息中的限制通行路径。

[0130] 2、对于原始路网拓扑中不包含限制路段串的第一子拓扑，遍历第一子拓扑中各个第一路段，将遍历到的第一路段进行映射，得到第一映射路段，各个第一映射路段构成第一映射拓扑。

[0131] 3、对于原始路网拓扑中仅包含限制路段串的第二子拓扑，遍历第二子拓扑中各个第二路段，若遍历到的第二路段为目标路段，则对遍历到的第二路段进行丢弃，若遍历到的第二路段不是目标路段，则将遍历到的第二路段进行映射，得到第二映射路段，各个第二映射路段构成第二映射拓扑。

[0132] 4、将第一映射拓扑以及第二映射拓扑所构成的拓扑，作为目标映射拓扑。

[0133] 5、假设将限制路段串定义为：N0L0N1L1…NiLi…NnLnNn+1，尾节点Nn有C（C>=1）个出边，Ln是其中的一个。这里，尾节点的出边指的是以尾节点为源节点的连接边。服务器执行以下步骤创建目标路段串对应的等效映射路段串，其中，目标路段串为原始路网拓扑中包含目标路段的非限制路段串。

[0134] 5.1、对于原始路网拓扑中节点序列N1…Ni…N（n 即限制路段串中的中间限制节点），在目标映射拓扑中创建一一对应的等效映射节点，得到节点序列M1…Mi…Mn。等效映射节点和限制路段串中的中间限制节点存在一一对应的映射关系。

[0135] 其中，若某个中间限制节点还存在其他目标节点为非限制节点的出边，则在该中间限制节点和该非限制节点之间建立该出边的等效映射边，建立的等效映射边与该出边存在一一对应的映射关系。

[0136] 5.2、L0是原始路网拓扑中限制路段串的起始路段中的连接边，N0是源节点，N1是目标节点，在目标映射拓扑中，保持源节点N0不变，在源节点N0和等效映射节点M1之间建立起始路段中的连接边L0的等效映射边L10。

[0137] 5.3、在节点序列M1…Mi…Mn，每两个连续节点之间建立限制路段串中的中间连接边的等效映射边，分别得到各个中间连接边L1…Li…Ln‑1的各个等效映射边K1…Ki…Kn‑1，中间连接边和等效映射边之间存在一一对应的映射关系。

[0138] 5.4、Ln的源节点Nn有C个出边，节点Nn对应规划拓扑中的等效映射节点Mn，除了尾边Ln的目标节点（即限制路段串中的最后一个节点），在等效映射节点Mn和其他出边的目标节点建立除Ln外其他各个出边的等效映射边，共有C‑1个等效映射边，等效映射边和原始拓扑中各个出边（节点Nn的出边）存在一一对应的映射关系。

[0139] 当服务器接收到用户的终端发送的路径规划请求时，基于路径规划请求确定规划起点和规划终点，在规划拓扑中，基于规划起点和规划终点进行搜索，得到规划起点和规划终点之间的规划路段串，从原始路网拓扑中确定与规划路段串所包含的节点存在映射关系的目标节点，以及与规划路段串所包含的连接边存在映射关系的目标连接边，基于目标节点和目标连接边之间的连接关系，得到原始路段串，将原始路段串所确定的路径作为规划起点和规划终点之间的目标路径，从而服务器可以向用户的终端返回原始路段串。

[0140] 由于得到的规划拓扑中消除了限制路段串，最终得到的原始路段串不会包含限制路段串，用户可以直接基于该原始路段串确定的目标路径进行导航。

[0141] 在一个具体的实施例中，本申请实施例提供的路径数据处理方法以及路径规划方法可以应用于导航场景中，在该导航场景中，用户的终端可以保存用户经常请求导航时选择的规划起点和规划终点，以及基于该规划起点和规划终点得到目标路径，当用户处于规划起点或者规划终点的范围内，终端可以主动向用户进行行程规划的导航推荐，从而可以根据用户的导航需求定制化的向用户进行行程推荐，提升用户的导航体验感。其中，基于该规划起点和规划终点得到的目标路径可通过上文实施例提供的方法得到，此处不再进行赘述。

[0142] 应该理解的是，虽然如上所述的各实施例所涉及的流程图中的各个步骤按照箭头的指示依次显示，但是这些步骤并不是必然按照箭头指示的顺序依次执行。除非本文中有明确的说明，这些步骤的执行并没有严格的顺序限制，这些步骤可以以其它的顺序执行。而且，如上所述的各实施例所涉及的流程图中的至少一部分步骤可以包括多个步骤或者多个阶段，这些步骤或者阶段并不必然是在同一时刻执行完成，而是可以在不同的时刻执行，这些步骤或者阶段的执行顺序也不必然是依次进行，而是可以与其它步骤或者其它步骤中的步骤或者阶段的至少一部分轮流或者交替地执行。

[0143] 基于同样的发明构思，本申请实施例还提供了一种用于实现上述所涉及的路径数据处理方法的路径数据处理装置，以及一种用于实现上述所涉及的路径规划方法的路径规划装置。该装置所提供的解决问题的实现方案与上述方法中所记载的实现方案相似，故下面所提供的一个或多个路径数据处理装置、路径规划装置实施例中的具体限定可以参见上文中对于路径数据处理方法、路径规划方法的限定，在此不再赘述。

[0144] 在一个实施例中，如图10所示，提供了一种路径数据处理装置1000，包括：

[0145] 原始拓扑获取模块1002，用于获取基于真实路径信息得到的原始路网拓扑，原始路网拓扑中包括限制路段串，限制路段串用于表征真实路径信息中的限制通行路径；

[0146] 原始拓扑映射模块1004，用于将原始路网拓扑中过滤目标路段后的剩余拓扑进行映射，得到目标映射拓扑，目标路段为限制路段串中的路段；

[0147] 等效路段创建模块1006，用于创建与原始路网拓扑中的目标路段串对应的等效映射路段串，目标路段串为原始路网拓扑中包含目标路段的非限制路段串；

[0148] 规划拓扑确定模块1008，用于将目标映射拓扑以及等效映射路段串所构成的拓扑，确定为规划拓扑，规划拓扑用于规划得到规划起点和规划终点之间的目标路径。

[0149] 上述路径数据处理装置，通过获取基于真实路径信息得到的原始路网拓扑，原始路网拓扑中包括限制路段串，限制路段串用于表征真实路径信息中的限制通行路径，将原始路网拓扑中过滤目标路段后的剩余拓扑进行映射，得到目标映射拓扑，创建与原始路网拓扑中的目标路段串对应的等效映射路段串，将目标映射拓扑以及等效映射路段串所构成的拓扑，确定为规划拓扑，由于目标路段为限制路段串中的路段，目标路段串为原始路网拓扑中包含目标路段的非限制路段串，得到的规划拓扑中系统性地消除了原始拓扑中的限制路段串，并保留了原始拓扑中所有的非限制路段串，因此，当通过规划拓扑进行路径规划时，可以直接规划得到目标路径，避免了进行回溯验证，提高了路径规划效率。

[0150] 在一个实施例中，等效路段创建模块，还用于对于原始路网拓中所包括的限制路段所组成的限制路段集合，将其中包括于目标路段串的限制路段作为目标限制路段；创建目标限制路段对应的等效映射路段；基于等效映射路段，确定目标路段串对应的等效映射路段串。

[0151] 在一个实施例中，等效路段创建模块，还用于若目标路段为限制路段串中的起始路段，则将限制路段串的中间限制节点作为目标限制节点；创建与目标限制节点对应的等效映射节点，基于等效映射节点创建目标限制路段对应的等效映射路段。

[0152] 在一个实施例中，等效路段创建模块，还用于若目标映射拓扑存在与起始路段的源节点对应的映射节点，则在源节点对应的映射节点与第一目标等效映射节点之间建立起始路段中连接边的等效映射边，以创建起始路段对应的第一等效映射路段；其中，第一目标等效映射节点为起始路段的目标节点对应的等效映射节点。

[0153] 在一个实施例中，等效路段创建模块，还用于若限制路段串包括至少三个限制路段，则在各个目标限制节点对应的等效映射节点之间建立限制路段串中的中间连接边的等效映射边，以构建限制路段串中的中间限制路段对应的第二等效映射路段；其中，限制路段串中的中间连接边为中间限制路段中的连接边。

[0154] 在一个实施例中，等效路段创建模块，还用于对于包含一个非限制节点的目标路段串，将目标路段串中连接限制节点和非限制节点的连接边作为目标连接边；在目标连接边所连接的非限制节点对应的映射节点和目标连接边所连接的限制节点对应的等效映射节点之间，建立目标连接边的等效映射边，将等效映射边所在的等效映射路段作为目标连接边所在的目标限制路段对应的第三等效映射路段。

[0155] 在一个实施例中，原始拓扑映射模块，用于对于原始路网拓扑中不包含限制路段串的第一子拓扑，遍历第一子拓扑中各个第一路段，将遍历到的第一路段进行映射，得到第一映射路段，各个第一映射路段构成第一映射拓扑；对于原始路网拓扑中仅包含限制路段串的第二子拓扑，遍历第二子拓扑中各个第二路段，若遍历到的第二路段为目标路段，则对遍历到的第二路段进行丢弃，若遍历到的第二路段不是目标路段，则将遍历到的第二路段进行映射，得到第二映射路段，各个第二映射路段构成第二映射拓扑；将第一映射拓扑以及第二映射拓扑所构成的拓扑，作为目标映射拓扑。

[0156] 在一个实施例中，上述装置还包括：路径规划模块，用于当接收到路径规划请求时，基于路径规划请求确定规划起点和规划终点；在规划拓扑中，基于规划起点和规划终点进行搜索，得到规划起点和规划终点之间的规划路段串；基于规划拓扑与原始路网拓扑之间的映射关系，从原始路网拓扑中确定规划路段串对应的原始路段串，将原始路段串所确定的路径作为规划起点和规划终点之间的目标路径。

[0157] 在一个实施例中，路径规划模块，还用于从原始路网拓扑中确定与规划路段串所包含的节点存在映射关系的目标节点，以及与规划路段串所包含的连接边存在映射关系的目标连接边；基于目标节点和目标连接边之间的连接关系，得到原始路段串。

[0158] 在一个实施例中，如图11所示，提供了一种路径规划装置1100，该装置包括：

[0159] 规划请求获取模块1102，用于获取路径规划请求，根据路径规划请求确定规划起点和规划终点；

[0160] 路段串搜索模块1104，用于在规划拓扑中，基于规划起点和规划终点进行搜索，得到规划起点和规划终点之间的规划路段串；其中，规划拓扑是目标映射拓扑以及等效映射路段串所构成的拓扑，目标映射拓扑是将原始路网拓扑中过滤目标路段后的剩余拓扑进行映射得到的，等效映射路段串与原始路网拓扑中的目标路段串对应的，原始路网拓扑是基于真实路径信息得到的，原始路网拓扑中包括限制路段串，限制路段串用于表征真实路径信息中的限制通行路径，目标路段为限制路段串中的路段，目标路段串为原始路网拓扑中包含目标路段的非限制路段串；

[0161] 目标路径确定模块1106，用于基于规划拓扑与原始拓扑之间的映射关系，从原始路网拓扑中确定规划路段串对应的原始路段串，将原始路段串所确定的路径作为规划起点和规划终点之间的目标路径。

[0162] 上述路径规划装置，由于规划拓扑是目标映射拓扑以及等效映射路段串所构成的拓扑，目标映射拓扑是将原始路网拓扑中过滤目标路段后的剩余拓扑进行映射得到的，等效映射路段串与原始路网拓扑中的目标路段串对应的，原始路网拓扑是基于真实路径信息得到的，原始路网拓扑中包括限制路段串，限制路段串用于表征真实路径信息中的限制通行路径，目标路段为限制路段串中的路段，目标路段串为原始路网拓扑中包含目标路段的非限制路段串，得到的规划拓扑中系统性地消除了原始拓扑中的限制路段串，并保留了原始拓扑中所有的非限制路段串，因此，当通过规划拓扑进行路径规划时，得到的规划路段串不包含限制路段串，从而通过映射关系可以从原始路网拓扑中确定不包括限制路段串的原始路段串，避免了对路段串进行回溯验证，提高了路径规划效率。

[0163] 在一个实施例中，目标路径确定模块1106，还用于从原始路网拓扑中确定与规划路段串所包含的节点存在映射关系的目标节点，以及与规划路段串所包含的连接边存在映射关系的目标连接边；基于目标节点和目标连接边之间的连接关系，得到原始路段串。

[0164] 在一个实施例中，上述装置还包括：等效路段创建模块，用于对于原始路网拓中所包括的限制路段所组成的限制路段集合，将其中包括于目标路段串的限制路段作为目标限制路段；创建目标限制路段对应的等效映射路段；基于等效映射路段，确定目标路段串对应的等效映射路段串。

[0165] 上述路径数据处理装置以及路径规划装置中的各个模块可全部或部分通过软件、硬件及其组合来实现。上述各模块可以硬件形式内嵌于或独立于计算机设备中的处理器中，也可以以软件形式存储于计算机设备中的存储器中，以便于处理器调用执行以上各个模块对应的操作。

[0166] 在一个实施例中，提供了一种计算机设备，该计算机设备可以是服务器，其内部结构图可以如图12所示。该计算机设备包括处理器、存储器、输入/输出接口(Input/Output，简称I/O）和通信接口。其中，处理器、存储器和输入/输出接口通过系统总线连接，通信接口通过输入/输出接口连接到系统总线。其中，该计算机设备的处理器用于提供计算和控制能力。该计算机设备的存储器包括非易失性存储介质和内存储器。该非易失性存储介质存储有操作系统、计算机程序和数据库。该内存储器为非易失性存储介质中的操作系统和计算机程序的运行提供环境。该计算机设备的数据库用于存储路径数据、拓扑结构数据等。该计算机设备的输入/输出接口用于处理器与外部设备之间交换信息。该计算机设备的通信接口用于与外部的终端通过网络连接通信。该计算机程序被处理器执行时以实现一种路径数据处理方法或者路径规划方法。

[0167] 本领域技术人员可以理解，图12中示出的结构，仅仅是与本申请方案相关的部分结构的框图，并不构成对本申请方案所应用于其上的计算机设备的限定，具体的计算机设备可以包括比图中所示更多或更少的部件，或者组合某些部件，或者具有不同的部件布置。

[0168] 在一个实施例中，提供了一种计算机设备，包括存储器和处理器，存储器中存储有计算机程序，该处理器执行计算机程序时实现上述路径数据处理方法或者路径规划方法所述的步骤。

[0169] 在一个实施例中，提供了一种计算机可读存储介质，其上存储有计算机程序，计算机程序被处理器执行时实现上述路径数据处理方法或者路径规划方法所述的步骤。

[0170] 在一个实施例中，提供了一种计算机程序产品，包括计算机程序，该计算机程序被处理器执行时实现上述路径数据处理方法或者路径规划方法所述的步骤。

[0171] 需要说明的是，本申请所涉及的用户信息（包括但不限于用户设备信息、用户个人信息等）和数据（包括但不限于用于分析的数据、存储的数据、展示的数据等），均为经用户授权或者经过各方充分授权的信息和数据，且相关数据的收集、使用和处理需要遵守相关国家和地区的相关法律法规和标准。

[0172] 本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的计算机程序可存储于一非易失性计算机可读取存储介质中，该计算机程序在执行时，可包括如上述各方法的实施例的流程。其中，本申请所提供的各实施例中所使用的对存储器、数据库或其它介质的任何引用，均可包括非易失性和易失性存储器中的至少一种。非易失性存储器可包括只读存储器（Read‑Only Memory，ROM）、磁带、软盘、闪存、光存储器、高密度嵌入式非易失性存储器、阻变存储器（ReRAM）、磁变存储器（Magnetoresistive Random Access Memory，MRAM）、铁电存储器（Ferroelectric Random Access Memory，FRAM）、相变存储器（Phase Change Memory，PCM）、石墨烯存储器等。易失性存储器可包括随机存取存储器（Random Access Memory，RAM）或外部高速缓冲存储器等。作为说明而非局限，RAM可以是多种形式，比如静态随机存取存储器（Static Random Access Memory，SRAM）或动态随机存取存储器（Dynamic Random Access Memory，DRAM）等。本申请所提供的各实施例中所涉及的数据库可包括关系型数据库和非关系型数据库中至少一种。非关系型数据库可包括基于区块链的分布式数据库等，不限于此。本申请所提供的各实施例中所涉及的处理器可为通用处理器、中央处理器、图形处理器、数字信号处理器、可编程逻辑器、基于量子计算的数据处理逻辑器等，不限于此。

[0173] 以上实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。

[0174] 以上所述实施例仅表达了本申请的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对本申请专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本申请构思的前提下，还可以做出若干变形和改进，这些都属于本申请的保护范围。因此，本申请的保护范围应以所附权利要求为准。