一种基于栅格网的无路网路径规划方法

倪冰洁

(江苏省测绘研究所,江苏 南京 210013)

0 引言

各类商用导航软件已经成为民众日常出行的必需品,尤其是其包含的路径规划及导航功能,能够查找各类地址,提供驾车、骑行、步行等各类出行方式的路径规划能力,以及实时导航功能。 然而商用导航软件主要针对城市路网进行路径规划,能够满足城市出行使用,但无法满足在特定地理环境下、特定人员及车辆的出行需求。 部分特种车辆在野外环境,如平原、山区、沼泽等,需要根据所驾驶车辆类型,规划相关行驶路径,从而达到快速到达某特定处所的目的,因而亟需一种路径规划方法,满足此类使用需求。

本文针对特定场景下的路径规划需求,提出了一种基于栅格网的无路网路径规划方法,按照一定的大小对地理图形进行栅格化划分,再针对每一个栅格,对耕地、林地、草地、戈壁、水域等不同地类计算通行时间,最终根据通行要求计算形成起始点、途经点、结束点的最优路径。

1 地理信息系统

地理信息系统的定义是由两个部分组成的。 一方面,地理信息系统是一门科学,是描述、存储、分析和输出空间信息理论和方法的一门新兴交叉学科。另一方面,地理信息系统是一个技术系统,是以地理空间数据库为基础,采用地理模型分析方法,适时提供多种空间和动态的地理信息,为地理研究和地理决策服务的计算机技术系统[1]。

地理信息系统一般具有数据采集与输入、数据编辑与更新、数据存储与管理、空间查询与分析、空间决策与支持等基本功能。 其中数据部分包含了大量的地理数据,它表征地理圈或地理环境固有要素或物质的数量、质量、分布特征、联系和规律等内容。 常见的地理信息系统中所包含的地理数据包含了道路、水系、居民点、农用地、特殊用地、林地、裸地等相关的数据[2]。 本文主要利用地理信息系统所包含的不同地形地类的数据,以及地理信息系统提供的空间检索分析方法,设计路径规划系统。

2 设计原理

现有路径规划功能均基于道路路网进行规划[3],但特殊情况下,所需要通过地域的成熟道路较少,通行时间要求比较高,通行方式不再局限于普通车辆,通行不再局限于在道路上通行,而是各类地形均可通行。 针对这种全地形、多通行工具的出行方式,设计了一种基于栅格网的无路网路径规划方法,主要设计思路如图1 所示。

图1 无路网路径规划设计思路

无路网路径规划设计核心要点包含4 个步骤。

(1)地理环境栅格化:获取目标区域的地理环境数据,并根据需求对地理环境进行栅格划分,形成栅格网。

(2)设计通行模型:根据不同的通行工具,设计

在不同地理环境下的通行速度模型。

(3)计算通行时间栅格:根据地理环境栅格以及通行模型,计算某通行工具通过栅格所需要的时间,形成通行时间栅格图。

(4)计算最优路径:根据通行时间栅格图,从形成起点至终端的最短通行时间,所经过的栅格集合为最优通行路径。

2.1 地理信息栅格化

地理信息栅格化是将地理信息服务所提供的各类地理环境图层进行栅格化划分并对统一栅格内的栅格地形进行处理,主要有栅格划分和栅格归一化两部分处理内容。

栅格划分是从物理上将地理位置进行栅格化分割形成地理栅格图,栅格可以是多种形式的,如正方形、正三角形等,本文以正方形的划分方式进行设计。栅格大小可以根据路径规划的精准度需求进行调整,如10 m×10 m、20 m×20 m 等,如图2 所示,将地理环境图所包含的道路、水网、耕地等各类地理图层按20 m×20 m 大小划分形成地理栅格。

图2 地理环境图栅格划分原理

栅格归一化处理是指在地理栅格划分完以后,对地理栅格地形进行归一化处理,为后续计算通行时间做准备。 以地理栅格内所占权重面积最大的地形为主,各类地形的权重系数各不相同,划分原理如图3所示。

图3 栅格划分原理

2.2 通行模型

路径规划结果与所乘用的交通工具有着直接关系,交通工具所具备的能力与通行速度直接决定了路径规划的结果。 针对实际使用过程中的行驶需求以及常见的交通工具类型,设计通行模型。 通行模型以速度为主要因素,设定不同通行工具在不同地理环境下的通行速度[4],如表1 所示。

表1 各通行工具通行模型(单位:km/h)

2.3 通行时间栅格设计

通行时间是指通行工具在地理栅格中通行所需时间,以地理信息栅格划分为基础形成通行时间栅格,从而为后续计算最短通行时间做基础。 根据正方形的地理信息栅格,计算通行时间可以考虑两种方式,分别为对角线、对边线,如图4 所示。

图4 栅格内通行距离计算设计

对边线方式,是地理信息栅格中通过的最短路径,而对角线方式相对通行距离较长,可充分兼顾实际通行时所产生的额外通行距离。 因而本文计算通行距离时,采取对角线方式。

通行时间计算公式为:

式中:T为通行时间;A为栅格的宽度;S为通行工具的平均通行速度;K为通行因子。 根据栅格地形因素额外增设,如多种因素同时并存,考虑多个因子相乘,常见通行因子参见表2。

表2 常见通行因子

2.4 最优路径计算

按照2.1~2.3 所示方法,可计算每个栅格内的通行时间,逐个计算地图内所有栅格的通行时间,形成地图通行时间栅格图。 在计算栅格与栅格之间如何通行时,考虑以某栅格为中心,周边8 个栅格通行时间最短的栅格为通行路径。 在计算两点之间最优路径时,可转化为计算两点之间的最短通行时间,所经过的栅格集合即为经过分析规划的最优路径[5],详细过程如图5 所示,图中颜色变灰的栅格形成的路径即为计算得出的最优路径。

图5 通行时间栅格图及最短路径

3 结语

本文提供根据特种车辆在特殊场景下行驶所面临的路径规划需求,提出了一个基于无路网的路径规划方法,采取“化整为零、化零为整”的总体思路,将地图划分为多个栅格进行分析计算。 该方法可以弥补当前商用导航无法在特殊地形下规划路径的不足,可以支撑特种车辆在特定需求下路径导航的需求,具有较好的应用意义。 但该方法还存在着一定的提升空间,如相关通行模型的参数、系数因子可进一步校订,所规划的路径需到现场进行进一步验证比对,调整优化参数及方法,从而满足最终的使用需求。