基于地理国情监测数据的路径规划研究

梁子亮 付 超

(江苏省基础地理信息中心，江苏 南京 210013)

1 概述

在测绘生产中，小比例尺地形图调绘、地理国情监测等项目需要作业员进行外业巡查，即利用外业工作底图实地进行核对、检查；相片控制测量、放线测量等项目则需要作业员在尽可能短的时间内完成所有点状要素的测绘工作。近年来，测绘工作参与到越来越多的自然资源调查中，以第三次全国国土调查为例，作业员需要以实地现状认定地类的原则，对作业底图中的图斑实地核实确认图斑地类，并标注信息，调绘图斑边界。在以上项目中，测绘外业路径规划将直接影响到工作的效率。如何进行路径规划，是图论学科中的一个非常重要的研究方向。在实际应用中，路径规划不仅仅要解决寻找两点之间最短距离的问题，还要考虑所遇到的阻抗，以求得到最快、最短甚至是最优的路径，在确定最佳路径时，所有成本属性均可用作阻抗[1]。在本研究中，选择时间作为阻抗，并添加部分约束条件用于适应不同的出行工具及天气因素。在图论中，有较多算法可以实现最短路径的搜索, 最典型、最常用的算法为Dijkstra算法[2]，本文基于地理国情监测数据[3]，利用ArcGIS软件，实现基于Dijkstra算法的外业路径规划。

2 试验区概况

新沂市隶属于徐州市，位于江苏省北部，西边与邳州市相邻，东边与沭阳县及东海县相邻，南边与宿迁市相邻，北边与山东省郯城县相邻。新沂市东西最大跨度为62.9 km，南北最大跨度为41.0 km，面积约1 592 km2。新沂是亚欧大陆桥东起第一座枢纽城市，陇海与新长、胶新铁路，京沪高速与连霍高速、徐连高速公路，G205与S323，S249在新沂市形成了“三纵三横”的交通网络格局[4]。新沂市周边80 km范围内分布着徐州观音机场、连云港白塔埠机场和山东临沂机场，构成了快速便捷的立体交通网络。本研究从地理国情监测资料中提取了新沂市的乡村道路(LVLL)、城市道路(LCTL)及公路(LRDL)，并人为添加了863个测绘要素。

3 Dijkstra算法过程

目前在GIS应用领域[5,6]，路径规划所采用的算法主要是Dijkstra算法，其被用于计算一个要素到其他所有要素的最短的距离，适用于测绘外业的始点确定、作业路径不确定的情况[7]。该算法可以简述为：

设G=(V,E)是一个带权有向图，把图中节点集合V分成两组，第一组为已求出最短路径的节点集合S，第二组为其余未确定最短路径的节点集合U，按最短路径长度的递增顺序把节点加入到S中，并保持从V到S中各节点的最短路径长度不大于从V到U中任何节点的最短路径长度。此外，每个节点对应一个距离，S中节点的距离就是从V到此节点的最短路径长度，U中节点的距离，是从V到此节点只包括S中的节点为中间节点的当前最短路径长度，其计算步骤可以简述为[8]：

1)初始时，S只包含源点，即S={V}，V的距离为0。U包含除V外的其他节点，即:U={其余顶点}，若V与U中节点V有边，则正常有权值，若U不是V的出边邻接点，则权值为∞；

2)从U中选取一个距离V最小的节点K，把K加入S中(即V到K的最短路径长度)；

3)以K为新考虑的中间点，修改U中各节点的距离；若从源点V到节点U的距离(经过节点K)比原来距离(不经过节点K)短，则修改节点U的距离值，修改后的距离值的节点K的距离加上边上的权；

4)重复步骤2)和3)直到所有节点都包含在S中[8]。

4 算法实现

4.1 测绘要素的聚合

类似于地理国情监测、国土调查等项目的测绘要素具有局部点位密度大的特点，为避免路径中出现较多支路影响作业效率，需要对测绘要素进行一定的聚合。本研究提出按照道路格网结合点间距进行聚合的思路，并按照如下步骤执行：

1)提取地理国情监测成果中的乡村道路、城市道路及公路的线状图层，并新建测绘要素点层；2)将三个道路图层融合至一个线状图层；3)将步骤2)生成的线状图层转为面状图层，并为图层中的每个子面赋予唯一的标识码；4)将步骤3)生成的面状图层的子面标识码赋值于落入其中的测绘要素；5)将测绘要素按照步骤4)中标识码属性进行“点转线”操作，生成线图层；6)将步骤5)生成的线图层转点，该点应落于线内部；7)从测绘要素中剔除与步骤5)生成的线图层相交的点；8)将步骤6)与步骤7)的两个点层合并，生成最终的聚合点层。

经过上述的聚合操作，测绘要素由863个降低至573个，聚合前后的点位分布如图1，图2所示。

由图1及图2可见，经过点位聚合，测绘要素的局部密度大为降低，每个道路格网中仅保留了一个测绘要素，便于优化后续的路径分析成果。

4.2 路径规划的实现

地理国情监测数据将乡村道路分为了乡村路、机耕路及农村硬化道路三种不同的类型，其中，乡村路与机耕路一般不为硬化道路，乡村路则较难被汽车通过。为设计更符合实际情况的路径规划，根据乡村道路的三种类型，制定以下出行规则：1)阴雨天气中，汽车及电动自行车可在城市道路、公路及农村硬化道路上通行，尽可能避免在机耕路上通行，禁止在乡村路上通行；2)晴朗天气中，汽车可在城市道路、公路、农村硬化道路及机耕路上通行，禁止在乡村路上通行；3)晴朗天气中，电动自行车可在所有道路上通行。

根据以上规则，将距离出发点最近的测绘要素作为起始点，进行最短路径规划，所得结果局部效果见图3～图5。

由图3～图5可知，本文实现了573个测绘要素在不同天气因素及不同出行方式下的路径规划，其路径长度分别为830.343 km，830.333 km及828.176 km，所得路径不仅简洁，更能满足不同测绘生产任务的需求。

5 结语

本文对新沂市863个测绘要素进行了聚合，最终得到测绘要素573个，并基于天气因素、出行工具及路况因素等约束件，利用Dijkstra算法提出了一种测绘外业路径规划方法。结果表明，与经验判断法相比，本文所得方法能够有效提高工作效率，可为测绘外业路径规划提供参考。