基于GIS的输电线路最优路径生成方法

摘要

一种基于GIS的输电线路最优路径生成方法，它包括以下步骤：(1)确定输电线路路径的起点与终点；(2)提取输电线路路径区域范围；(3)对GIS地图进行处理：将GIS地图在同一坐标系中划分为障碍区域图层、地形地貌图层和道路线路图层三个图层；(4)采用最小面积矩形包围盒法处理障碍区域并构造成可视图；(5)最优路径的求取：首选求取可行的避障路径，然后构造成本矩阵，最后采用Dijkstra算法计算最短路径的避障路径，从而获得输电线路的最优路径；(6)统计转角数和交叉跨越次数。本发明不仅具有避开障碍区、优化生成路径的功能，而且还具备路径长度和转角个数统计等功能。

说明书

技术领域

本发明涉及电力系统输电线路设计技术领域，具体地说是一种基于GIS 的输电线路最优路径生成方法。

背景技术

目前，在输电线路设计中，路径优化是由设计人员首先在室内选线，并 到现场进行踏勘后，重新调整路径，形成最终路径。但是，现有的路径优化 方案存在如下缺陷：

1.传统的路径设计是基于已有的地图和沿路路径资料进行的，这就造成 了地理信息相对滞后，需要大量的现场踏勘来辅助，不仅准确率低，还增加 了工作量。

2.传统的路径设计是在纸质图纸上完成的，工作量大，且修改较为复杂。

3.影响线路路径的因素多样，包括地形地貌、用地类型、交叉跨越、施 工条件等，传统的路径设计不能统筹考虑这些因素。

发明内容

针对上述现有技术的不足，本发明提供了一种基于GIS的输电线路最优 路径生成方法，它不仅具有避开障碍区、优化生成路径的功能，而且还具备 路径长度和转角个数统计等功能。

本发明解决其技术问题采取的技术方案是：一种基于GIS的输电线路最 优路径生成方法，其特征是，包括以下步骤：

(1)确定输电线路路径的起点与终点：输电线路路径的起点与终点为两 个变电站，由变电站设计人员提供变电站站址和变电站进出线方向，并在GIS 地图上进行标注；

(2)提取输电线路路径区域范围：测量起点与终点的直线距离，以地图 上南北方向和东西方向形成直角三角形，求出该直角三角形水平边与竖直边 的距离，并将这两个距离分别加2后向上取整数，可得到路径区域范围；

(3)对GIS地图进行处理：将GIS地图至少划分为障碍区域图层、地形 地貌图层和道路线路图层三个图层，每个图层分别含一类GIS信息，所有图 层在同一坐标系中互相叠加；

(4)采用最小面积矩形包围盒法处理障碍区域并构造成可视图：采用最 小面积矩形包围盒包围障碍区域的方法进行处理障碍区域图层中的障碍区域 并用矩形包围盒表示障碍区域；

(5)最优路径的求取：首选求取可行的避障路径，然后构造成本矩阵， 最后采用Dijkstra算法计算最短路径的避障路径，从而获得输电线路的最优 路径；

(6)统计转角数和交叉跨越次数：将输电线路最优路径的的转角数和交 叉跨越次数分别进行加和统计。

上述方法中，所述障碍区域图层的形成过程为：

1)确定判断为障碍区域的因素：所述确定判断为障碍区域的因素包括用 地类型、地方规划、地质和冰区等因素；

2)按GIS信息筛选障碍区域：如果用地类型为军事设施、大型工矿企业 或居民区，或者地方规划为自然保护区或风景名胜区，或者地质为地质灾害 带、不良地质带或采动影响区，以及冰区为重冰区的地区均视为障碍区域；

3)形成障碍区域图层：将上述筛选的障碍区域整合到一个新建图层形成 障碍区域图层。

上述方法中，采用最小面积矩形包围盒法处理障碍区域的过程为首先采用 AABB法求出障碍区轮廓的外接矩形，即最大最小x坐标和最大最小y坐标所 构成的矩形；然后将坐标旋转任意角度θ，使得旋转后包围障碍区的面积为最 小，最小面积的外接矩形即为障碍区轮廓的最小面积矩形包围盒，其中，θ以 π/180为步长递增，且θ∈[0,π/2]。

上述方法中，所述求取可行的避障路径的过程为：

1)基本定义

定义1：设v_i＝(x_i,y_i)(i＝1,2,…,m)，v₁＝v_m+1是障碍区域图层R₁²上的定点，如 果对任意i,j(i≠j),i,j＝1,2,…,m，线段v_iv_i+1与v_jv_j+1或是相邻且相交于一端点或不 相交；

定义2：障碍区域图层R₁²障碍物集合O是简单多边形的集合，每个障碍 物对应的各简单多边形顶点数m_i可以不同，且i≠j时， 其中i,j＝1,2,…,K；

定义3：s,j∈R₁²，分别成为起始点与目标点，点集V＝{s,g}∪V₀，其中V₀表 示全体障碍物定点，V＝{v_i|i＝1,2,…,n}，其中v₁＝s，v_n＝g，v₂～v_n-1对应全体障 碍物定点V₀的一个序列；设O₁＝{s}，O_k＝{g}；

定义4：在障碍区域图层R₁²上，定义G₁是由V构成的有权图，边的权值 定义为V集两顶点间的扩展Euclid距离，表示为d(v_i,v_j)，简记为d_ij，其中 v_i,v_j∈V；

定义5：设G₁＝(V,E)，V＝{v_i|i＝1,2,…,n}，E为与任何障碍物均不相交边c的 全体且i≠j，G₁成为可视图；

2)判断邻接关系

<1>设v_j∈V且v_i,v_j∈O_k，k＝1,2,…,K，计算(v_i,v_j)(j＝i,i+1,…,m_k,m_k+1)的权 值d(v_i,v_j)的可按公式(2)计算，即：

$d(v_i,v_j)=\left(\begin{array}{cc}\sqrt{{(x_i-x_j)}^2+{(y_i-y_j)}^2}& j=\{i+1,m_k+1\}\\ 0& j=i\\ \infty & \mathrm{else}\end{array}\right)---\left(2\right);$

<2>设V_i∈O_k，V_j∈V-O_k，k＝1,2,…,K，j＝i,i+1,…,n，计算边权值d(v_i,v_j)首 先要判断V_i和V_j两点所构成的线段V_iV_j与V_a和V_a+1所构成的线段V_aV_a+1是否相交， 根据相交结果来计算d(v_i,v_j)的值。这里V_a,V_a+1∈O_l，l＝1,2,…,K，a＝1,2,…,n；

<3>判断线段V_iV_j与V_aV_a+1有无交点，即关于参数λ和μ的矢量方程(3)：

(1-λ)V_i+λV_j＝(1-μ)V_a+μV_a+1  (3)

是否有λ，μ∈[0,1]的解，如果λ，μ∈[0,1]表明不相交，可以作为路径，如果 λ，表明相交，不可作为路径。

上述方法中，所述构造成本矩阵的过程为：

1)基本定义

定义6：定义cost[n][n]为包含三个图层信息的成本矩阵；

定义7：将点v_i、v_j移到在表示地形区域的地形地貌图层R₂²上，定义G₂是由V构成的有权图，d′(v_i,v_j)为修正后的权值；

定义8：将点v_i、v_j移到在表示道路线路的道路线路图层R₃²上，定义c 为表示线段V_iV_j与道路线路图层R₃²上线段交叉跨越次数；

2)修正路径长度

统计在各种地形中线段V_iV_j所跨越的距离l_n，修正权值d(v_i,v_j)为d′(v_i,v_j)

$d^{\prime }(v_i,v_j)=\underset{n=1}{\overset{6}{\Sigma }}{f}_n{l}_n---\left(4\right)$

式4中，f_n为修正系数，n为地形编号；

3)修正转角

t_i表示为线段V_iV_j与V_i-1V_i(k≠i,k≠j)之间是否存在转角，当 d(v_i-1,v_i)+d(v_i,v_j)＝d(v_k-1,v_j)则t_i＝0，否则t_i＝1；

4)修正交叉跨越

V_iV_j线段在道路线路图层R₃²可能会与一条或多条道路或线路产生交叉跨 越，用c_i来表示发生交叉跨越的次数；

5)构造出线段V_iV_j的成本矩阵

线段V_iV_j的成本矩阵cost[i][j]如公式(5)所示：

cost[i][j]＝d′(v_i,v_j)+f_cc_i+f_tt_i      (5)

其中f_c为交叉跨越修正系数，f_t为转角修正系数。

上述方法中，所述采用Dijkstra算法计算最短路径的避障路径的过程 为：

1)将路径的起点与终点分别标记为s和g；

2)将路径起点s存入S集合，并标记为T顶点，S集合表示每次运算后 求得的一条最短路径；

3)更新S集合中与起点s连通节点的状态记录；

4)识别与s连通且综合权重最小的临时节点，将其设置为T节点，直至 T节点为终点g为止，否则继续更新更新S集合中与起点s连通节点的状态记 录；

5)根据各节点连通关系与状态记录表中的信息，从终点g开始记录其前 序节点，直至记录到起点s；

6)根据上一步的记录结果，可形成起点s到终点g的最优路径。

本发明的有益效果是：本发明基于GIS地图信息将不适合架设输电线路 的地区视为障碍区域，并在同一坐标系中形成障碍区图层、地形地貌图层、 道路线路图层三个图层，以最小面积矩形包围盒法对障碍区域进行处理，并 结合可视图法完成避障路线规划，生成输电线路的最优路径，它不仅具有避 开障碍区、优化生成路径的功能，而且还具备路径长度和转角个数统计等功 能。

附图说明

图1为本发明的方法流程图；

图2为本发明所述路径区域选择的示意图；

图3为本发明所述旋转角度为θ时的矩形包围盒的示意图；

图4为本发明所述路径区域障碍区图层的可视图；

图5为本发明所述判断两条线段是否相交的示意图；

图6为本发明采用Dijkstra算法计算最短路径的方法流程图。

具体实施方式

为能清楚说明本方案的技术特点，下面通过具体实施方式，并 结合其附图，对本发明进行详细阐述。下文的公开提供了许多不同 的实施例或例子用来实现本发明的不同结构。为了简化本发明的公 开，下文中对特定例子的部件和设置进行描述。此外，本发明可以 在不同例子中重复参考数字和/或字母。这种重复是为了简化和清楚 的目的，其本身不指示所讨论各种实施例和/或设置之间的关系。应 当注意，在附图中所图示的部件不一定按比例绘制。本发明省略了 对公知组件和处理技术及工艺的描述以避免不必要地限制本发明。

如图1所示，本发明的一种基于GIS的输电线路最优路径生成 方法，它包括以下步骤：

(1)确定输电线路路径的起点与终点：输电线路路径的起点与 终点为两个变电站，由变电站设计人员提供变电站站址和变电站进 出线方向，并在GIS地图上进行标注；

(2)提取输电线路路径区域范围：测量起点与终点的直线距离， 以地图上南北方向和东西方向形成直角三角形，求出该直角三角形 水平边与竖直边的距离，并将这两个距离分别加2后向上取整数， 可得到路径区域范围；

(3)对GIS地图进行处理：将GIS地图至少划分为障碍区域图 层、地形地貌图层和道路线路图层三个图层，每个图层分别含一类 GIS信息，所有图层在同一坐标系中互相叠加；

(4)采用最小面积矩形包围盒法处理障碍区域并构造成可视 图：采用最小面积矩形包围盒包围障碍区域的方法进行处理障碍区 域图层中的障碍区域并用矩形包围盒表示障碍区域；

(5)求取可行的避障路径；

(6)构造成本矩阵；

(7)采用Dijkstra算法计算最短路径的避障路径，从而获得 输电线路的最优路径；

(8)统计转角数和交叉跨越次数：将输电线路最优路径的的转 角数和交叉跨越次数分别进行加和统计。

下面对本发明作进一步详细说明说明。

1、确定路径起点和终点与路径区域范围选择

(1)确定路径起点与终点

线路路径的起点与终点为两个变电站。由变电站设计人员提供变电站站 址(变电站中心点位置)和变电站进出线方向，由计算机在GIS地图上进行 标注，并可根据工程需要接受路径必经点位置(人工输入)。

(2)路径区域范围选择

测量起点与终点的直线距离(单位km，下同)，以地图上南北方向和东西 方向做直角三角形。求出次三角形水平边与竖直边的距离。将这两个距离分 别加2，并向上取整数，可得到路径区域范围。如图2所示。得到的路径范围 坐标沿用GIS地图默认坐标。

2、GIS地图的处理

GIS地图包含该有该区域内所有地形地貌、用地类型、交叉跨越、施工条 件等信息，每一个图层上都包含一类信息。根据本专利应用情况，将GIS地 图整合为障碍区图层、地形地貌图层、道路线路图层这三个图层。三个图层 同原点，同坐标，互相叠加。

(1)障碍区图层(第一图层)

不适宜架设输电线路的地区可被视为障碍区进行规避。采取以下步骤形成 障碍区图层。

(1.1)确定判断为障碍区域的因素(可根据路径设计的具体要求修改)

路径选择时应该考虑到地形地貌、地质、冰区、交通、施工、运行、及地 方规划等因素。根据路径选择的原则，以下地区都可被视为障碍区：

a)用地类型：军事设施、大型工矿企业、居民区；

b)地方规划：自然保护区、风景名胜区等；

c)地质：地质灾害带、不良地质带、采动影响区；

d)冰区：重冰区。

(1.2)按GIS信息筛选判断障碍区

以“用地类型”这层为例。对路径区域范围内的GIS用地类型图层中每个 像素(对应到实际中的长度为米/像素，视GIS地图分辨率而定)中用地类型 进行判断，如果为军事设施、大型工矿企业或居民区，则将此点坐标标记为 障碍区。

“用地类型”图层扫描标记完后，对“地方规划”“地质”“冰区”等图层 逐个进行扫描标记。

如果某一点在之前图层扫描中已标记为障碍区，则可以跳过以后图层中的 扫描。

(1.3)形成障碍区图层

新建一图层，将ii步骤中标记为“障碍区”的点整合起来作为障碍区域， 其余点作为非障碍区，形成障碍区图层(第一图层)。

(2)地形地貌图层(第二图层)

根据国家电网发布的《国家电网公司输变电工程通用造价》可知，在不同 地形地貌(平地、丘陵、河网和沼泽、高山等)上架设输电线路的造价不同。 本专利在规划最优线路路径时要降低架设路径时的造价，就要需要考虑地形 地貌问题。因此提取地形地貌图层作为第二张图层。

(3)道路线路图层(第三图层)

在输电线路路径规划中还要尽量避免规划的路径与、电力线路、通讯线路 等产生的交叉跨越。因此将GIS地图中道路和线路图层合并作为第三图层。

3、路径区域范围内的障碍区的最小矩形包围盒求取

(1)最小面积矩形包围盒法处理障碍区域。

由于障碍区图层中的障碍区域并不是规则的几何多边形，为了后面寻找最 优路径的便利，需要以最小面积的规则几何多边形包围障碍区域。在此专利 中，采用最小面积矩形包围盒包围障碍区域。

如图3所示，采用AABB法求出障碍区轮廓的外接矩形，即最大最小x坐 标和最大最小y坐标所构成的矩形；然后将坐标旋转任意角度θ(以π/180为 步长递增，且θ∈[0,π/2])，使得旋转后包围障碍区的面积为最小。封闭的障碍 区包围盒轮廓线任一点在x-y坐标系下的坐标为(x,y)，在旋转任意角度θ后， 该点在u-v坐标系下的坐标设为(u,v)。坐标变换如式(1)：

u＝xcosθ+ysinθ

v＝ycosθ-xsinθ             (1)

S＝(u_max-u_min)(v_max-v_min)

求出在新的u-v坐标下AABB法求得的外接矩形面积S，这些外接中最小 面积的外接矩形即为障碍区轮廓的最小面积矩形包围盒。存储此矩形包围盒 四顶点在x-y坐标轴下的坐标。

(2)将障碍区图层构造成可视图

将每个障碍区域都按(1)中所述步骤求取最小面积矩形包围盒，然后用 O_i表示障碍区域的矩形包围盒，在可视图上称为障碍物。图4表示某路径区 域障碍区图层的可视图，s、g分别成为起始点和目标点，O₁和O₂表示两个障 碍物，虚线为从起始点s到目标点g的可行路径。

4、最优路径的求取

本专利主要基于障碍区图层所构造的可视图，利用Dijkstra算法，考 虑路径所经过的地理信息、转角和交叉跨越情况的权重，规划出从起始点 到目标点的最优路径。

(1)可行避障路径的求取

(1.1)基本定义

定义1：设v_i＝(x_i,y_i)(i＝1,2,…,m)，v₁＝v_m+1是图层R₁²(障碍区域图层)上的 定点，如果对任意i,j(i≠j),i,j＝1,2,…,m，线段v_iv_i+1与v_jv_j+1或是相邻且相交于一 端点或不相交。

定义2：图层R₁²障碍物集合O是简单多边形的集合。每个障碍物 对应的各简单多边形顶点数m_i可以不同，且i≠j时， 其中i,j＝1,2,…,K。

定义3：s,j∈R₁²，分别成为起始点与目标点。点集V＝{s,g}∪V₀，其中V₀表 示全体障碍物定点。为了叙述方便，设V＝{v_i|i＝1,2,…,n}，其中v₁＝s，v_n＝g， 而v₂～v_n-1对应全体障碍物定点V₀的一个序列(逆时针排列)；设O₁＝{s}，O_k＝{g}。

定义4：在有障碍区域的图层R₁²上，定义G₁是由V构成的有权图。边的 权(成本)值定义为V集两顶点间的扩展Euclid距离，表示为d(v_i,v_j)(简记 为d_ij)，其中v_i,v_j∈V。

定义5：设G₁＝(V,E)，V如定义3，E为与任何障碍物均不相交边c的全 体且i≠j。G₁成为可视图，因为途中相邻的顶点能相互看到。

(1.2)邻接关系的判断

在搜寻路径时，需要解决两类邻接关系，即同一障碍物多边形顶点间的 临界关系和不同障碍物多边形定点间的邻接关系。这两类邻接关系可以通过 判断V中顶点连线即边(v_i,v_j)与障碍物多边形O_i,i＝1,2,…,K是否相交的方法来 解决。

<1>设v_j∈V且v_i,v_j∈O_k，k＝1,2,…,K，计算(v_i,v_j)(j＝i,i+1,…,m_k,m_k+1)的权 值d(v_i,v_j)的可按公式(2)计算，即：

$d(v_i,v_j)=\left(\begin{array}{cc}\sqrt{{(x_i-x_j)}^2+{(y_i-y_j)}^2}& j=\{i+1,m_k+1\}\\ 0& j=i\\ \infty & \mathrm{else}\end{array}\right)---\left(2\right)$

<2>设V_i∈O_k，V_j∈V-O_k，k＝1,2,…,K，j＝i,i+1,…,n，计算边权值d(v_i,v_j)首 先要判断V_i和V_j两点所构成的线段V_iV_j与V_a和V_a+1所构成的线段V_aV_a+1是否相交， 根据相交结果来计算d(v_i,v_j)的值。这里V_a,V_a+1∈O_l，l＝1,2,…,K，a＝1,2,…,n。

<2>判断线段V_iV_j与V_aV_a+1有无交点，即关于参数λ和μ的矢量方程(3)，如 图5所示：

(1-λ)V_i+λV_j＝(1-μ)V_a+μV_a+1     (3)

是否有λ，μ∈[0,1]的解。如果λ，μ∈[0,1]表明不相交，可以作为路径，如果 λ，表明相交，不可作为路径。

(2)成本矩阵的构造

(2.1)基本定义

定义6定义cost[n][n]为包含三个图层信息的成本矩阵。

定义7将点v_i、v_j移到在表示地形区域的图层R₂²(地形地貌图层)上， 定义G₂是由V构成的有权图，d′(v_i,v_j)为修正后的权值。

定义8将点v_i、v_j移到在表示道路线路的图层R₃²(道路线路图层)上， 定义c为表示线段V_iV_j与图层R₃²上线段(表示道路和线路)交叉跨越次数。

(2.2)路径长度的修正

如前文所述，在不同地形区域上架设输电线路的造价也不同，本着降低 造价的原则，应以地形对造价的影响程度对路径的单位长度进行修正。

V_iV_j线段在图层R₂²可能在一种地形区域中，也可能跨越了两种或多种地 形区域，根据所经过的地形不同，修正系数也有所不同。由国家电网发布的 《国家电网公司输变电工程通用造价》内各地形下的典型方案造价而得到路 径规划在不同地形下的修正系数(修正系数可从表1中查得)。

表1路径规划在不同地形下的修正系数

地形地貌 平地 丘陵 河网沼泽 山地 高山 地形编号n 1 2 3 4 6 修正系数f_n1 1.06 1.40 1.21 1.43

统计在各种地形中线段V_iV_j所跨越的距离l_n，修正权值d(v_i，v_j)为d′(v_i，v_j)

$d^{\prime }(v_i,v_j)=\underset{n=1}{\overset{6}{\Sigma }}{f}_n{l}_n---\left(4\right)$

(2.3)转角的修正

在路径规划中，线路转角会增加成本，减少转角也是优化路径的一个原 则，所以在成本矩阵中以转角修正系数加以体现。t_i表示为线段V_iV_j与V_i-1V_i(k≠i，k≠j)之间是否存在转角。判断方法为：当d(V_i-1，v_i)+d(v_i，v_j)＝d(V_k-1，v_j)则 t_i＝0，否则t_i＝1。

(2.4)交叉跨越的修正

路径规划中，应尽量避免输电线路与其他电力线路以及已架设好的通讯 线路产生交叉跨越。因此将交叉跨越的次数也考虑到最优路径的选择当中。 V_iV_j线段在图层R₃²可能会与一条或多条道路或线路产生交叉跨越，用c_i来表 示发生交叉跨越的次数。

(2.5)成本矩阵的构造

考虑到路径的长度，并根据地形区域图层R₂²对路径长度的修正，以及考 虑到线路转角和交叉跨越的因素，可以构造出线段V_iV_j的成本矩阵cost[i][j]， 如公式(5)所示：

coSt[i][j]＝d′(v_i，v_j)+f_cc_i+f_tt_i       (5) 其中f_c为交叉跨越修正系数，f_t为转角修正系数。(交叉跨越修正系数和转角 修正系数均可根据实际情况给出。)

(4)Dijkstra算法计算避障路径

对于带权有向图G，用S集合来表示每次运算后求得的一条最短路径， 初始化时S集合只含一个起始点，用W集合来存储加入S集合后剩余的顶点 集合。以起点为中心查找它所连接的下一个顶点中的路径最短的加入S集合 中，若查找的连接的顶点所连接的路径比S集合中已存在的此路径长度短的 话，则替换掉原先的路径，总之要保存从起始点到当前点的最短路径，直到 找到终点。

Dijkstra算法的核心思想是以起始点为中心向外层层扩展，从与起始 点相连通的未标记点中选择一个权值最小的路径并对其他顶点的权值进行 比较。这是一个循环比较的过程。在此问题上可以使用路径长度、所在地形、 转角和交叉跨越情况的加权为权值。

如图6所示，采用Dijkstra算法计算最短路径的避障路径的过程包括以 下步骤：

1)将路径的起点与终点分别标记为s和g；

2)将路径起点s存入S集合，并标记为T顶点，S集合表示每次运算后 求得的一条最短路径；

3)更新S集合中与起点s连通节点的状态记录；

4)识别与s连通且综合权重最小的临时节点，将其设置为T节点，直至 T节点为终点g为止，否则继续更新更新S集合中与起点s连通节点的状态记 录；

5)根据各节点连通关系与状态记录表中的信息，从终点g开始记录其前 序节点，直至记录到起点s；

6)根据上一步的记录结果，可形成起点s到终点g的最优路径。

5、转角和交叉跨越次数统计

在确定最优路径后，路径所经过的点存在S集合中。将路径的转角数和 交叉跨越次数按照式6和式7进行加和可得

$t=\underset{i\in S}{\Sigma }{t}_i---\left(6\right)$

$c=\underset{i\in S}{\Sigma }{c}_i---\left(7\right)$

其中，t表示路径的转角数，c表示路径的交叉跨越次数。

本发明具有以下特点：

1、路径自动设计：采用本技术方案，可实现输电线路路径基于GIS的自 动设计，即在确定路径起点与终点后，可自动完成路径生成，供设计人员参 考；

2、支持人工修正：可以人工加入必经点，同时也支持设计人员录入现场 踏勘资料，并依此对路径人工或自动修正；

3、支持沿线统计：路径生成后，可根据GIS地理信息，完成路线长度、 转角个数、与已有线路交叉情况的统计。

以上所述只是本发明的优选实施方式，对于本技术领域的普通 技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改 进和润饰，这些改进和润饰也被视为本发明的保护范围。