路径规划典型算法大全11篇

路径规划典型算法篇（1）

0引言

路径规划是车载导航系统最重要的功能之一[1]。根据图论中最短路径理论，不管是最短路径规划、最短时间规划还是最低消费规划，都可以通过赋予图中的边以相应的权值来满足用户的不同需求。

通常情况下，路径搜索可以分为平面搜索和分层搜索两大类。平面搜索算法中最经典的是20世纪60年代初期由Dijkstra提出的Dijkstra算法，非常适合在带权有向图中解决最短路径问题。但是该算法的时间复杂度为O（n2），效率比较低，因此在实际应用时受到了很大的限制。后来许多学者在存储结构和排序算法上对Dijkstra算法进行了改进[2-3]，通常改进算法的时间复杂度与节点数成正比，如O（mlbn）或O（m+nlbn）[4]。也有学者通过引入启发函数的方式进行改进，启发式搜索以1968年Hart等提出的A*算法为代表，现在仍被广泛应用，但这些改进算法的效率会随节点数的增加而急剧下降。此外，平面搜索算法计算出的“最短”路径并不一定是“最优”路径，最短路径中可能存在大量的窄小拥挤的小巷，而最优路径要尽可能多地包括主干道等快速路段[5]，这就有了分层思想。文献[6]首先提出了层次空间的推理过程，文献[7]又将层次空间推理法则引入到行车最优路径搜索中，但这两篇文献均没有给出具体的路网层次拓扑结构的表达方法[8]。有代表性的分层算法有最近E节点法[9]和最佳E节点法[10]，其中最近E节点法简单但准确率不高，最佳E节点法能够得到最优解，但效率低[11]。

本文试图设计一种实用的分层路径规划算法。首先建立分层路网的拓扑结构，然后从搜索空间、搜索策略和数据结构三个方面进行研究，采用启发式的A*算法作为主搜索方式，引入优先队列二叉堆作为数据存储结构，最后通过实验验证每项措施的改善效果。

路径规划典型算法篇（2）

中图分类号：TP301.6

Dijkstra算法是一种经典的求最短路径的算法。所谓最短路径问题是指：从带权图的某一顶点出发，找出一条通往另一顶点的最短路径。最短路径问题是GIS应用中研究的一个重要内容，在事故抢修、交通指挥、应急管理、GPS导航等应用中都是必要的功能，所以最短路径分析功能一般会作为基本功能集成到GIS平台中，如ARCGIS，SuperMap。多数系统解决最短路径问题采用Dijkstra算法为理论基础，它非常适合在带权有向图中求解单源单目的最短路径问题。

1 经典Dijkstra算法

1.1 算法思想

Dijkstra算法是典型最短路算法，用于计算一个顶点到其他所有顶点的最短路径。其基本思想是，逐步产生最短路径。首先求出从某一顶点出发到其他顶点长度最短的一条路径，然后参照它求出长度次短的路径，依次类推，按路径长度的递增次序，直到计算出该顶点到其他所有顶点的最短路径。

为了实现该算法，设带权图G=（V，E），V为图中顶点的集合，E为边或者弧的集合。设集合S存放已经求出的最短路径的顶点，设集合T为除了S以外的其他顶点，引入辅助数组dist[]，它的每一个分量dist[i]表示当前找到的从出发点到顶点i的最短路径长度。

算法的具体步骤：

（1）初始化：S={V0}；T={V-S}；Dist[j]=Edge[0][j]；j=1，2，…..n-1，n为图中顶点的个数；

（2）求出最短路径长度：dist[k]=min{dist[i]}，i∈V-S；S=S∪{k}；

（3）修改：dist[i]=min{dist[i]，dist[k]+EDedge[k][i]}对于每一个i∈V-S；

（4）判断：若S=V，则算法结束，否则转到（2）；

初始时，S中仅含有初始顶点V0，每次从V-S中取出具有最短特殊路长度的顶点，将其添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。

1.2 算法分析

实现经典的Dijkstra算法需要两个并列的for循环。一个循环用来实现辅助数组的初始化工作，时间复杂度为O（n），第二个for循环是一个二重循环，实现最短路径求解的功能，因为图中所有顶点都要做计算，每个顶点的计算又要对集合S内的顶点进行检测，对集合V-S中的顶点进行修改，所以时间复杂度为O（n2）。算法总的时间复杂度为O（n2），复杂度比较高。

2 Dijkstra算法改进

通过Dijkstra经典算法思想可知，计算从u到v的最短路径时，也计算了u到S中所有顶点的最短路径，但是，S中的某些顶点可能与最终最短路径中的顶点无关，该算法在进行最短路径搜索过程中会涉及到图中所有的顶点，那么图中S的大小直接影响着算法的速度。这直接影响了算法的效率，因为由时间复杂度可看出顶点数量越多所用时间就越长。优化该算法势在必行。

2.1 改进策略

改进的策略用一句话描述就是顶点覆盖，分段进行。通过前面的分析可知，如果能减少算法中集合S中顶点的个数，会减少算法的运行时间。在这借用希尔提出希尔排序的思想，把有向图中的顶点按照某种策略分成若干个小的集合，形成顶点的全覆盖，这样每个集合的数量就比原来少了，但是把他们合起来顶点及关系总数不变，并且要求不同的集合要有一个连接的关键顶点，关键点的确定是计算最短路径的关键。

顶点覆盖划分的方法可根据具体的计算应用决定，比如可以按照区域划分，按关键点划分，按公路、铁路线划分等等。划分的数量不宜太多也不宜太少，应根据实际情况科学分析。划分数量和每个划分中顶点的数量应事宜，划分数量多，重复执行的次数就有可能多；划分的数量少对算法的改进程度不高。确定连接不同集合的关键点和划分策略有关，有时也要进行事先的运算，关键点应该具有这样的性质，是从一个集合区域到另一个集合区域必经的顶点或者就是终点。最短路径的计算结果是每个小集合划分的结果之和得到的。这样改的好处是，既能减少程序运行时涉及的顶点的数量，如果采用邻接矩阵的方式存储带权图，还能节省存储空间。

2.2 算法设计

下面给出改进算法的方法步骤：

（1）根据划分策略，确定顶点所属不同集合Si，i=1，2，3小于等于划分的个数，确定存储表示方法，并建立相应带全图；

（2）把所有关键点放入关键点集合key，并表示关键点所连接的区域信息，并建立拓扑图；

（3）计算关键点集合顶点间的最短路径，并放入专门的数组或数据表中；

（4）计算任意两个顶点间的最短路径，首先判断顶点所属范围，若两个点均属于关键顶点集合，则直接查找步骤四的计算结果数据表，算法执行结束；若属于同一个顶点划分，直接调用Dijkstra算法，转步骤（5），若属于不同的集合，转步骤（6）；

（5）在两顶点所属划分Si范围内，直接调用Dijkstra算法求两点间的最短距离，算法结束；

（6）假定两定点分别属于划分Si和Sj，则两顶的距离等于，u0和v0所属的集合分别为Ti和Tj，那么最短路径的计算有三部分组成，先计算起始结点到与其所在集合Si连接的关键点的最短距离，在计算与Sj相连接的关联点到终点的最短路径，再计算两个关键点之间的最短路径，最后将三部分计算结果相加，即为两定点间的最短路径。

2.3 性能分析

首先该算法是从减少顶点数量的角度对算法进行优化，对经典算法本身的执行没有改动，不论是计算关键结点之间的最短路径，还是计算任意两个顶点之间的最短路径，仍然调用迪杰斯特拉算法，这就保证了算法的可行性。如两个顶点不属于同一区域采用的是分阶段计算最短路径然后相加的方法，减少了计算的复杂性，增强了可理解性和可执行性。

其次关于改进算法的时间复杂度，和顶点集合划分的数量有关。假设带权图中共有n个顶点，有m个顶点集合划分，k为关键顶点的数量。时间复杂度分为以下几种情况：

（1）如果两顶点均属于关键顶点，则只需要到数据表中进行查找，则复杂度取决于关键顶点的数量和查找最短路径所需要的时间。计算关键顶点的复杂度为O（k2），查找路径可以用优化的查找方法；

（2）如果两顶点属于同一个集合划分，复杂度为O（（n/m）2），是没有改进前的算法复杂度的1/m2。

（3）如果两顶点，不属于同一个集合划分，最短路径计算是三部分计算之和，三次调用经典算法，复杂度与第二种情况同，但事件应该略多。

从空间复杂度角度，若采用邻接矩阵的存储表示方法，经典算法需要用n2个存储空间，改进后只需k*（n/m）2，当然增加了存储关键顶点和其最短路径的存储空间，但相比节省的存储空间和优化的时间复杂度，必要的增加还是值得的。

通过对时间和空间复杂度的分析可以看出改进算法可以极大的减少运算量，降低时间复杂度和空间复杂度。

3 改进算法在GIS中的应用

在ArcGIS平台中实现改进算法的应用，在Java环境下利用Arcobject进行二次开发，采用改进的Dijkstra算法思想编写函数，实现最短路径的搜索。

ArcGIS自带的网络分析模块，具有分析矢量数据的功能，只对具有拓扑关系的矢量数据进行分析，所以首先在ARCGIS环境下对地图进行矢量化，然后进行拓扑分析。本文采用的数据是某一地区的地图数据，文件中一共有3572条地理实体记录，共有2826个顶点，通过对地图数据的分析，确定了按照地理区域进行顶点划分的策略，共分成23个区域，共找到72个关键顶点，每个划分的顶点根据地域及关键点的链接，并不十分平均，但是比起总体的数据量，每个集合的规模都小的多。

利用改进算法进行计算时，按照算法思想采用了两个顶点在关键顶点集合、在两个不同顶点划分集合和两个顶点在同一个顶点集合三组不同的数据进行验证。通过和经典的Dijkstra算法运行结果从正确性和运行时间的对比，证明一方面改进的算法进行最短路径搜索的结果和经典算法相同的，另一方面比经典的算法无论从时间上还是从空间上都有一定的提高。如图1所示，两种算法运行时间的对比图。

图1 运行时间对比

4 结束语

本文在分析经典Dijkstra算法的基础上，提出了“顶点覆盖，分段计算”的思想，进行算法的改进。通过对原带权图中顶点进行覆盖划分，减少算法中顶点集合数目，缩小问题的规模，并通过分段计算最短路径以达到降低算法时间复杂度和空间复杂度的目的，经在ArcGIS中二次开发，结果正确实现了预期设想。

参考文献：

[1]殷人昆.数据结构（用面向对象方法与C++语言描述）（第二版）[M].北京：清华大学出版社，2007.

[2]王涛春，齐学梅，赵诚.Dijkstra优化算法及其在电子导游中的应用[J].安徽师范大学学报（自然科学版），2010（33）：525-529.

[3]陈红琳.在ArcGis矢量图中搜寻最短路径的实现[J].北京测绘，2009（02）：16-18.

[4]王华.基于Dijkstra算法的物流配送最短路径算法研究[J].计算机与数字工程，2011（39）：48-50.

[5]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，1997.

路径规划典型算法篇（3）

中图分类号：TM715 文献标识码：A

随着我国社会水平和居民生活条件的提高，社会对配电网络规划的合理性、安全性、可靠性和经济性有了更高的要求。配网规划方法是指对电网进行研究分析并且对未来负荷进行预测，在保证电能质量和满足用户电能需求的基础上，寻求一个最优配网规划方案，使配网投资、检修、线路损耗等各种费用的总和达到最小。传统的配网规划方法是电力规划人员自行拟定几套方案然后在从中挑选出比较合理的方案。随着科学技术的发展配网规划方法得到了进一步的优化，主要分为经典配网优化方法和启发式优化方法。

1 配电网规划的特点

配电网络是指电网二次降压变电站直接输出或者是经过再次降压后向电力用户进行供电的网络。配电网络主要由架空线或者是电缆、降压变压器和配电所共同构成。通过配电网络能够安全、合理的将电能输送到用电场所。配电网络规划的核心思想是“随机应变”，配电网络的规划一般具有非线性，多目标、多阶段和离散性等特点，具体而言其特点有以下4个方面。

1.1非线性。配电网络中由于具有异步电动机、同步电动机、变压器等设备的大量使用，使得电网的非线性特征明显。另外伴随着科学技术的发展变频器等非线性设备的使用越来越广泛。因此，配电网络的目标函数是非线性的同时也应当注意到影响目标函数的决策值大多数是离散值。在实际问题的处理过程中，对非线性目标函数的处理是非常的麻烦的，并且占用内存较大。

1.2多目标性，多约束性和多阶段性。占地面积和环境等诸多因素会影响到配电网络规划的效果，因此配网规划是一个涉及了很多约束条件的多目标最优规划问题。在进行配网规划时要从长远的角度进行考虑，努力避免配网规划的短视行为和盲目性需要对电网做整体性的规划。另外，配网规划应该分多个不同的阶段进行实施，并且及时的对每个阶段之间的影响进行评估，及时的对配网规划出做合理的修正。

1.3协调困难。在进行配网规划时经常会遇到，多目标之间存在相互冲突的现象，比如降低施工成本和提高配网可靠性之间的矛盾。因此，在进行配网规划时要提前确定目标的优先级别。

1.4不确定性。现阶段社会发展迅速，对电能的需求呈指数增加另外对电能的需求也会受到经济周期的作用另外还会受到政策等不确定性因素的影响，因此发电量、输电线路电压等级、负荷预测和后期投资等数据很难进行准确的预测。

2 配电网规划优化方法

由上面的分析可知随着配网规模的逐渐加大，做出比较合理的配网规划难度逐渐增加，需要对配网的规划方法进行优化。近几年来，配网规划优化方法取得了很大的进步。配网规划优化方法一般分为配网规划优化法和启发式优化法。具体分类如图1所示。

2.1 配网规划经典数学优化法

配网规划经典数学优化法的种类有很多种，并且该种类的算法是将配电网规划问题转化为相应的数学模型进行准确的求解。经典数学优化法采用严格的数学描述，充分的描述配网运行变量和决策变量之间的关系，从而使得整个规划方案取得最优解。现阶段比较常用的经典数学优化方法有以下几种：0-1规划法，非线性规划法，线性规划法，最短路径法，网络潮流法和混合整数规划法等等。

经典数学优化法能够对电网规划进行准确的描述。但是，这类方法计算量巨大，占用计算内存大并且计算时间很长。该类方法一般适用在中小型配网规划，对于大型的配网规划问题往往会出现“维数灾”的问题，并且大型配网中影响决策的因素有很多种无法准确的进行描述，及时能够得到结果也不一定是最优解。

2.2配网规划启发式优化法

在工程实践过程中，启发式优化法主要是考虑配网规划效果和配网规划效率，并且现代启发式优化方法能够给出一个令人满意的解。

现阶段主要的启发式规划方法包括蚁群优化法、模拟退火法、遗传算法、粒子群优化法和人工神经网络优化法等等。在上述几种优化方法中比较常用的方法是蚁群优化法。这种算法是一种多算法，它具有正反馈、贪婪启发式搜索和分布式计算等特点。配网规划中蚁群优化法是将电力负荷作为所要寻找的食物源。

蚁群优化法具体原理如下所述，在中低压配网中，输电线路的规划以最小的支出费用最为目标函数，主要包括线路损耗和线路投资两部分。

上式中，N代表输电线路经过的变电站个数，lk代表的是第k条输电线路的长度，Pk代表的是第k条线路所传输的有功功率，β代表的是输电线路的折算系数。在对配网进行规划建立目标函数时，往往还要受到诸多条件的约束，比如输电线路的容量不能够过负荷运行，线路的电压损失必须在合理的范围内，输电线路要沿着城市街道进行铺设。

在已知变电站供电范围的情况下，配网规划的数学模型，如下面公式：

其中，上式中ω为等值系数，k为线路编号，N为街道段号，lk代表电流，Imax为线路最大允许电流，s为负荷点编号，S为节点数，Vmax，Vmin 为最高电压和最低电压。

在采用蚁群优化法进行配网规划时，首先使用框架的形式将该地区的地理数据进行描述，并且收集相应的地理信息。地理信息数据对变电站的供电范围，变电站的位置坐标，负荷的坐标、负荷率，街道的节点坐标和街道的段号坐标等内容进行了详细的记录。然后利用计算机语言对相关的地理信息进行编程提取相应的街道段及其节点坐标、负荷坐标及负荷量等特征值，然后对这些特征进行分类编号，最后将电网信息统一录入地理信息知识库。

在对配网进行规划时将负荷作为蚂蚁寻找的“食物源”，蚂蚁在铺线时根据相关的信息转移准则决定所选择的线路。

在人工蚂蚁i选择所前进的路径k时，由具有启发信息的状态转移函数引导选路。其中状态引导函数如下：

其中，代表待选前进路径中访问中负荷最多的街道，为待选路径中最短的街道，代表由转移概率所决定的街道。对于街道的选择，采用顺次选择的方法选取合适的街道。蚁群优化法一般是采用伪随机比率作为选择街道的规则。

当某组蚁群中的人工蚂蚁完成了线路铺设后，街道中的相关信息也应按照以下步骤进行进一步的更新。

（1）当蚂蚁i没有经过街道k时，则街道k的信息不需要进行改变，即：

τ（k，t+1）=τ（k，t）

（2）若当蚂蚁i经过街道k时，则街道k的信息进行适当的改变

τ（k，t+1）=（1-τ0）τ（k，t）+Δτ

在上式中，t代表当前时刻，t+1代表下一时刻，τ0代表街道信息矢量，Δτ代表街道信息变化量。

采用蚁群优化法解决配网规划问题时，每个人工蚂蚁均可以但知道所属节点街道上的负荷数值，进而选择前进的街道段。在采用该种优化算法的时候一般选择变电站作为蚂蚁的巢穴，线路负荷作为蚂蚁食物，人工蚂蚁按照上面的信息转移准则寻找相关的食物，最后能够得到一个可行性的最优解。

总体而言，相比与其他类型的启发式优化法而言，蚁群算法能够很好的完成配电网的结构重组不需要对配网的连通性和辐射性等相关特性进行检验修复。

结语

通过对配电网规划优化方法的研究分析发现，到目前为止，配网规划研究已经获得了长远的发展，并且配网规划优化方法也取得快速发展。但是必须注意到配电网络的规划具有非线性，多目标、多阶段和离散性等特点，目前的规划优化方法依然存在着收敛性和计算速度等问题的制约。经典的配网规划方法计算结果能保证解的最优性，但是计算占用内存过大，耗费时间长，一般只适合于小型系统。配网启发式优化方法弥补了经典优化方法的不足，但是容易陷入局部最优。

参考文献

路径规划典型算法篇（4）

 

一、概述各移动运营商及移动通信相关技术咨询单位在进行规划方案验证时，传统的方法是通过规划仿真软件使用宏蜂窝传播模型及20米精度三维电子地图对规划方案进行仿真验证；然而，宏蜂窝传播模型的应用范围和自身局限性限制了规划方案仿真验证的精度：首先，宏蜂窝传播模型的应用范围一般在500米以上，而CBD区域基站的覆盖半径一般在500米以下。其次，宏蜂窝传播模型只能从宏观上反映方案覆盖效果，无法根据建筑物的高度从微观上反映局部的覆盖情况。因此，需要采用更合适的传播模型配合高精度的三维电子地图对CBD区域的规划方案进行仿真验证，以确保该重点区域无线网络建成后的网络性能。

目前射线跟踪模型作为一种高精度的规划仿真传播模型在大中型城市覆盖重点区域的规划方案仿真验证中得到广泛应用。本文首先对射线跟踪模型的原理进行探讨，然后以WaveCall公司的WaveSight模型为例说明射线跟踪模型的应用方法。其结果有助于应用射线跟踪模型对规划方案进行精确验证，对规划工作有积极的参考和指导作用。

二、射线跟踪模型简介2.1 微蜂窝传播模型介绍 当前传播模型根据应用范围可分为宏蜂窝传播模型和微蜂窝传播模型，宏蜂窝传播模型应用范围为1km至几十km；而微蜂窝传播模型应用范围仅为几百米，一般只适用于基站附近区域。免费论文。由于CBD区域基站的覆盖一般在500米以内，因此应用微蜂窝传播模型对该区域规划方案的效果进行仿真验证更为合适。

微蜂窝传播模型根据模型建立方法，可分为经验模型，确定性模型以及混合模型；

l经验模型

经验模型是在大量测量的基础上产生的，该模型与室外传统宏蜂窝传播模型类似，不考虑理论计算，对基站附近测量大量数据后统计归纳出经验模型。

l确定性模型

确定性模型是依据电波传播理论计算出接收点与发射点之间的传播损耗。射线跟踪模型是一种典型的确定性模型，确定性模型不考虑测量，仅在确定计算公式中的个别参数时需要测量验证。

l混合模型

混合模型结合了经验模型和确定性模型，一方面混合模型以电波传播理论为依据得出电波的传播模型，同时需要对基站附近测量大量数据以统计确定传播模型中的参数值。

2.2 射线跟踪模型介绍 射线跟踪模型是一种确定性模型，其基本原理为标准衍射理论（Uniform Theory ofDiffraction，简称UTD）。根据标准衍射理论，高频率的电磁波远场传播特性可简化为射线（Ray）模型。因此射线跟踪模型实际上是采用光学方法，考虑电波的反射、衍射和散射，结合高精度的三维电子地图（包括建筑物矢量及建筑物高度），对传播损耗进行准确预测。

由于在电波传播过程中影响的因素过多，在实际计算预测中无法把所有的影响因素都考虑进去，因此需要简化传播因素；射线跟踪算法把建筑物的反射简化为光滑平面反射、建筑物边缘散射以及建筑物边缘衍射。

根据考虑路径的种类不同，射线跟踪模型可分为三种：

l2D射线跟踪模型

只考虑水平切面的传播路径，即第一类路径。

l3D射线跟踪模型

只考虑水平切面以及垂直切面的传播路径，即第一类及第三类路径。

l全3D射线跟踪模型

考虑所有传播路径，即考虑所有第一、二、三类路径。

三、射线跟踪模型基本原理射线跟踪模型的基本原理是简化传播因素，采用光学方法定位传播路径并计算各接收点与发射点之间的路径损耗；因此，射线跟踪模型的关键在于如何定位接收点与发射点之间的传播路径并计算路径损耗。免费论文。

3.1 水平切面的传播损耗从发射源在接收点之间可能存在很多传播路径，但是一般只有一到两条强度最强，在传播中起主导作用的主导传播路径。路径损耗计算时只需计算主导传播路径的损耗即可。免费论文。

3.2 垂直切面的传播损耗 相对于水平切面的传播损耗，垂直切面的传播损耗计算要简单一些，计算垂直切面的传播损耗时，需要首先确定发射源与接收点之间的垂直传播路径，然后计算其中各个刀锋衍射损耗，其路径损耗为各刀锋衍射损耗之和。

3.3 射线跟踪模型简要结论 根据射线跟踪模型的理论以及相关资料，可以得到射线跟踪模型的简要结论如下：

1.对近距离的场强预测， 水平切面算法（2D射线跟踪算法）起主导作用。

2.全3D方向算法中全3D路径（即第三类路径）对远距离的场强预测准确性影响很大。

3.在整齐规划的建筑群中，对远距离的场强预测，垂直切面算法可取代全3D方向算法。

四、射线跟踪模型的应用 本节主要以WaveCall公司的WaveSight射线跟踪模型为例，对射线跟踪模型的应用进行说明。

WaveCall公司的WaveSight射线跟踪模型作为AIRCOM公司的规划软件Enterprise的插件，可用于高精度的规划方案仿真验证。该模型基于标准衍射理论及射线跟踪算法，综合考虑电波传播范围内建筑物的轮廓、高度、地形剖面图，对电波的传播特性进行准确预测。

WaveSight模型是一种3D射线跟踪模型，该模型包括两种类型路径：水平切面路径以及垂直切面路径。

对比传统射线跟踪模型，WaveSight 具有优点十分明显：首先，WaveSight射线跟踪模型采用了不同于传统射线跟踪模型的算法，空前地提高了计算效率：该模型完成一个基站的覆盖预测所需时间仅是传统射线跟踪模型所需时间的1/3左右，不仅保证了覆盖预测的精度，同时还保证了覆盖预测的速度。此外，WaveSight 模型使用简单，该模型不需要使用测试数据对其进行调校，仅需要输入两个参数：使用频率及接收端高度。

WaveSight 射线跟踪模型的缺点是：仅适用于市区环境，对电子地图精度要求较高，不仅要求地图精度必须达到5m 以上，而且要求提供建筑物矢量信息以及高度信息。

五、结论及后续工作 本文首先对射线跟踪模型的原理进行探讨，然后给出射线跟踪模型的简要结论，最后以WaveCall公司的WaveSight模型为例说明射线跟踪模型的应用方法。其结果有助于应用射线跟踪模型对规划方案进行精确验证，对规划工作有积极的参考和指导作用。

今后研究工作可以再上述研究基础上进一步展开，对全3D射线跟踪算法进行进一步的探讨，同时也可以对其它射线跟踪模型如WinProp模型等进行研究，

进一步研究射线跟踪传播模型算法，更精确地城市CBD区域进行预测，指导网络的规划及优化工作。

【参考文献】

1．WaveCall公司；《WaveCallPropagationWhitePaper》；2001

路径规划典型算法篇（5）

中图分类号：TP242 文献标识码：A 文章编号：1009-914X（2016）20-0218-01

1 引言

科学技术日新月异，移动机器人的应用范围越来越广。路径规划是移动机器人实现自主导航的关键技术之一[1-5]。按照移动机器人对环境的认知程度，可以将路径规划分为基于先验信息的全局路径规划和基于传感器信息的局部路径规划。A-star算法是全局路径规划的经典算法之一；然而，传统A-star算法在搜索过程中也存在自身的缺陷，如搜索出的路径不易于机器人运动控制、搜索速度慢等。本文针对复杂环境下A-star算法的缺陷进行了启发函数和搜索策略的改进。

2 A-star算法概述

A-star算法作为一种启发式搜索算法的优势就在于从当前搜索节点搜索下一步节点时，由一个启发函数来引导选择代价最小的节点作为下一步搜索节点。这样减少了搜索空间，提高了效率。A-star算法中代价函数如下：

1.1

上式1.1中，表示从起始点经过节点n到达目标点的最低代价的估计值，它由两部分组成：一部分为，是从起始点到当前点的实际代价值；表示从当前点到目标点的估计代价值，称为启发函数。

A-star算法的应用关键在与启发函数和Open、Close列表的设置，好的启发函数可以加快搜索速度，合理的Open、Close列表设置能节省存储空间。Open列表用于存放未被检测过的位置点，Close列表用于存放已被检测完毕的位置点。

3 改进的搜索策略

首先， A-star算法的搜索核心是启发函数，启发函数使其避免了盲目性搜索的繁杂性。传统的A-star算法所使用的启发函数是经典的Manhattan距离或欧几里得距离。

分析A-star算法的搜索过程可知，当启发函数（是最终真实路径的距离）时，此时搜索范围较大，运行效率低下，搜索时间长；当启发函数时，算法的搜索过程将按照最理想的路径点一步步往下搜索，但是现在情况不能满足该种情况的要求；当时，搜索范围较小，运行效率较高，搜索时间较短，但是搜索出的路径不是最短的所以，为了得到较高的运行效率和最优的路径，我们应当选取启发函数的值接近于。因为A-star算法在进行下一步搜索时，只能搜索与其当前位置相临接的位置点，并不是任意、盲目地选取下一点。如图1所示，根据以上分析，本文结合Manhattan距离和欧式距离设置的启发函数如下式。

当时，代价函数改写为

当时，代价函数改写为

上式1.4中，和分别表示机器人当前节点与目标节点之间横坐标和纵坐标的差值，。

其次，在栅格环境中运用传统A-star算法进行路径搜索时，得出的结果会出现经过障碍物顶尖的情况，这在实际情况中是不允许的。分析算法在选取下一点的搜索原理可知，出现该情况的原因是在栅格环境中往左上、左下、右上、右下方向进行搜索时搜索的限制条件没有将与机器人当前位置相邻区域的环境情况考虑在内。本文对搜索过程做如下改进：

①机器人当前位置为，进行下一步的搜索，如果下一步位置为则执行②；如果下一步位置为则执行③；如果下一步位置为则执行④；如果下一步位置为则执行⑤；否则执行⑥；

②判断与机器人的相邻的、是否都为可行区域，若是则执行⑥，否则说明该路径是不安全的，需要重新搜索，执行⑦；

③判断与机器人的相邻的、是否都为可行区域，若是则执行⑥，否则说明该路径是不安全的，需要重新搜索，执行⑦；

④判断与机器人的相邻的、是否都为可行区域，若是则执行⑥，否则说明该路径是不安全的，需要重新搜索，执行⑦；

⑤判断与机器人的相邻的、是否都为可行区域，若是则执行⑥，否则说明该路径是不安全的，需要重新搜索，执行⑦；

⑥计算此点的、、值。

⑦更新搜索节点。

4 实验仿真与结论

基于以上优化方法，本文在MATLAB2014b中进行了仿真，假设移动机器人的运动环境已知，为栅格化环境模型。图2为改进后的A-star算法仿真得出的路径规划结果，黑色为障碍物，白色为可行区域，其他颜色表示比较危险的可行区域。

与的传统A-star算法相比较，改进后的A-star算法搜索时间减少了0.04s，搜索的节点数减少了4.9%，路径的关键节点数减少了50%，并且路径没有过障碍物顶尖的现象，改进后的A-star算法会优先选择远离障碍物的安全区域规划路径，最终生成的路径更加符合机器人的运动控制。说明改进后的A-star算法是可行的。

机器人路径规划是一个经典研究领域，在当前复杂的生产、生活背景下，一方面对机器人的实时性提出了更高的要求，另一方面对规划出的路径安全性、与人相容性有了提出了更高的性能指标要求。本文充分考虑了机器人对实时性和安全性的要求，提出了改进的A-star路径规划方法，提高了搜索速度，降低了碰撞发生的可能性，并通过仿真实验验证了新方法的有效性。

参考文献

[1] 蔡自兴，贺汉根。未知环境中移动机器人导航控制理论与方法[M]。北京：科学出版社，2009.

[2] 王殿君。基于改进A*算法的室内移动机器人路径规划[J]。清华大学学报（自然科学版）。2012，Vol.52， No.8.

[3] 马喜峰， 张雷. 基于对称极多项式曲线的移动机器人平滑路径生成[J]. 机器人， 2005， 27（5）： 450-459.

路径规划典型算法篇（6）

我国目前白车身焊接机器人焊接路径规划方面仍处于落后水平，相关路径规划也极为不完善，机器人工作的过程中经常出现作业顺序不合理的状况，导致生产周期增长，影响整个焊接线路的发展。所以如何制定出一条合理的路径规划是当前首要目标，本文立足实际就针对这个问题提出一些有效性策略。

一、路径规划的意义

白车身焊接机器人焊接中制定出一条合理的路径规划可以有效缩短机器人生产时间，进而缩短整个工期，提高整个生产效率，某种程度上降低了生产成本。另一方面，白车身焊接机器人焊接路径规划具有一定的典型性，在自动驾驶、服务机器人、挖掘机器人等路径规划研究方面具有重要的借鉴意义，具有较高的社会价值和经济价值。

二、白车身焊接机器人焊接路径规划

（一）路径规划的基本任务

现代化工业生产的主要目标是为了获得较高的制造质量、取得较高的生产率，而付出较低的生产成本，这是现代企业提高自身竞争力的重要手段，也是路径规划中的主要任务之一，而在路径规划的过程中要想保证焊接质量主要取决于以下两点：

第一，最大程度的使用机器人工位。使用机器人工位能够有效降低工人的劳动强度，减少人为错误几率，提高焊接的准确性，保证焊接的顺利进行，从而保证焊接的稳定性。

第二，要完成所有的焊接点，保证焊接的工艺参数。

要想实现较低的制造成本就是最大化的利用现有资源，提高机器人的工作效率，缩短机器人工位的生产周期，减少机器人的使用数量。路径规划的重要方向就是提高生产率，保证生产环节的顺利进行，缩短生产周期，提高生产率。

（二）路径规划

白车身焊接机器人焊接路径规划主要有两个分支，一是改变工艺参数，使用新的工艺方法和辅助设备。二是要提高分配的合理性、提高焊接顺序的合理性，提高合理性的目标是为了减少机器人工位的生产周期。第二个分支实现的途径主要是通过提高机器人焊接路径的合理性，从而提高单个机器人的生产效率，最终缩短整个生产周期。

（三）遗传算法

遗传算法是进化算法中产生最早、应用最广泛的一种基本算法，在工程技术和经济管理领域都有广泛的应用。遗传算法有群体搜索和遗传算子两个基本特征，所谓的群体搜索打破了领域的限制，使信息可以广泛分布于整个空间。而遗传算子就是使染色体进行随机操作，以降低人机交互的依赖。两个特征保证了遗传算法具有最优的搜索能力、最简明的操作能力以及信息处理的隐秘能力。

白车身焊接路径规划主要问题如下：

第一，白车身中所需要焊接的焊接点众多。

第二，在生产的过程中常常追求没有意义的高精度。

第三，在解答相关问题时需要运用数学方法。

第四，因为方案最终应用于企业，所以数学方法最好要简洁明了，便于学习。

综上，在路径研究时需要运用遗传算法，主要优势在于：

第一，遗传算法的计算步骤比较简单明了，在实际操作时便于学习和使用。在计算时大大减少了计算量，从而节约时间。

第二，能够在很大程度上优化焊接作业顺序，减轻焊接的工作量。

第三，减少定量分析与定性分析的工作量。

第四，能够很好的掌控全局，在全局中找到最优解。

三、路径规划的仿真

（一）仿真系统的各要素

路径仿真系统一般要具有以下几个基本要素：

第一，对仿真问题的描述。模型和仿真运行控制共同组成了一个仿真系统，而一个特定的模型又是由一个参数和一组参数值构成。例如白车身点焊机器人焊接路径的参数模型一般包括家具模型、机器人模型、侧围模型，在这基础之上还加入了具体的参数值，就形成了特定的模型。

第二，行为产生器。模型确定以后就要对模型进行试验，这是一套试验的软件，行为产生器可以生成一组根据时间变化的数据，这类数据是仿真的物资基础。

第三，模型行为及对行为的处理。

模型行为可以大致分为三种：轨迹行为、结构行为以及点行为。

仿真系统中都要获取轨迹行为，这些行为的获取主要是根据时间的推移而产生的。

（二）仿真软件的选择

一个完善的机器人仿真系统可以依据机器人的运动学、动力学、行为轨迹等多项内容进行仿真计算，并可以根据机器人的实际操作内容进行仿真操作过程，并不依赖于真正的机器人。但目前最主要的工作是对机器人的路径规划做一个仿真方案，而不是设计出一个机器人的仿真系统。在进行机器人路径规划时需要一定的条件，在现实生活中可以有多个选择，最好的选择就是使用一些类似CAR这种专业软件，如果条件不允许可以选择VC++或者使用CATIA等软件进行仿真。VC++自主编写的优点在于针对性比较强，在做路径时可以考虑多方面因素，然而缺点是不能建立详细的三维模型，在实际操作时不能全方面的展现白车身焊接工位情况，且工作量较大。CATIA与VC++相比最大的优势就是可以建立详细的三维模型，能够全方位展现工位情况，仿真轨迹最为真实，在仿真过程中还可以检查是否干涉。而缺点也是比较明显的，在仿真的过程中不能将动力学和控制算法考虑在内。

四、小结

白车身主要是以钢结构为主的支架，是汽车中重要组成部分。而车身制造是整个环节中比较复杂又极为重要的一环，影响整个汽车的质量。我国研究白车身焊接机器人焊接路径仍处于落后阶段，为了提高综合竞争力需要加大技术投资，提高我国白车身制造综合竞争。

参考文献：

路径规划典型算法篇（7）

1 引言

在移动机器人导航技术应用过程中，路径规划是一种必不可少的算法，路径规划要求机器人可以自己判定障碍物，以便自主决定路径，能够避开障碍物，自主路径规划可以自动的要求移动机器人能够安全实现智能化移动的标志，通常而言，机器人选择的路径包括很多个，因此，在路径最短、使用时间最短、消耗的能量最少等预定的准则下，能够选择一条最优化的路径，成为许多计算机学者研究的热点和难点。

2 背景知识

神经网络模拟生物进化思维，具有独特的结构神经元反馈机制，其具有分布式信息存储、自适应学习、并行计算和容错能力较强的特点，以其独特的结构和信息处理方法，在自动化控制、组合优化领域得到了广泛的应用，尤其是大规模网络数据分析和态势预测中，神经网络能够建立一个良好的分类学习模型，并且在学习过程中优化每一层的神经元和神经元连接的每一个节点。1993年，Banta等将神经网络应用于移动机器人路径规划过程中，近年来，得到了广泛的研究和发展，morcaso等人构建利用一个能够实现自组织的神经网络实现机器人导航的功能，并且可以通过传感器训练网络，取得更好的发展，确定系统的最佳路径。神经网络拓扑结构模型可以分为：

2.1 前向网络

网络中各个神经元接受前一级的输入，并输出到下一级，网络中没有反馈，可以用一个有向无环路图表示。这种网络实现信号从输入空间到输出空间的变换，它的信息处理能力来自于简单非线性函数的多次复合。网络结构简单，易于实现。反传网络是一种典型的前向网络。

2.2 反馈网络

网络内神经元间有反馈，可以用一个无向的完备图表示。这种神经网络的信息处理是状态的变换，可以用动力学系统理论处理。系统的稳定性与联想记忆功能有密切关系。Hopfield网络、波耳兹曼机均属于这种类型。

3 基于人工神经网络的移动机器人路径规划算法

神经网络解决移动机器人路径规划的思路是：使用神经网络算法能够描述机器人移动环境的各种约束，计算碰撞函数，该算法能够将迭代路径点集作为碰撞能量函数和距离函数的和当做算法需要优化的目标函数，通过求解优化函数，能够确定点集，实现路径最优规划。神经网络算法在移动机器人路径规划过程中的算法如下：

（1）神将网络算法能够初始化神经网络中的所有神经元为零，确定目标点位置的神经元活性值，并且能够神经网络每层的神经元连接将神经元的值传播到出发点；

（2）动态优化神经网络，根据神经网络的目标节点和障碍物的具置信息，在神经网络拓扑结构中的映射中产生神经元的外部输入；

（3）确定目标值附件的神经元活性值，并且使用局部侧的各个神经元之间，连接整个神经网络，并且在各个神经元中进行传播。

（4）利用爬山法搜索当前邻域内活性值最大的神经元，如果邻域内的神经元活性值都不大于当前神经元的活性值，则机器人保持在原处不动；否则下一个位置的神经元为邻域内具有最大活性值的神经元。

（5）如果机器人到达目标点则路径规划过程结束，否则转步骤（2）。

4 基于人工神经网络的移动机器人路径规划技术展望

未来时间内，人工神经在机器人路径规划过程中的应用主要发展方向包括以下几个方面：

4.1 与信息论相融合，确定神经网络的最优化化目标解

在神经网络应用过程中，由于经验值较为难以确定，因此在神经网络的应用过程中，将神经网络看做是一个贝叶斯网络，根据贝叶斯网络含有的信息熵，确定神经网络的目标函数的最优解，以便更好的判断机器人移动的最佳路径。

4.2 与遗传算法想结合，确定全局最优解

将神经网络和遗传算法结合起来，其可以将机器人的移动环境设置为一个二维的环境，障碍物的数目、位置和形状是任意的，路径规划可以由二维工作空间一系列的基本点构成，神经网络决定机器人的运动控制规则，利用相关的神经元的传感器作用获未知环境的情况，将障碍信息和目标点之间的距离作为神经网络的输入信息，使用遗传算法完成神经网络的权值训练，神经网络的输出作为移动机器人的运动作用力，实现一个可以在未知环境中进行的机器人运动路径规划。

4.3 与蚁群算法相结合，降低搜索空间，提高路径规划准确性

为了提高神经网络的搜索准确性和提高效率，可以将蚁群算法与神经网络相互结合，蚁群算法的路径规划方法首先采用栅格法对机器人工作环境进行建模，然后将机器人出发点作为蚁巢位置，路径规划最终目标点作为蚁群食物源，通过蚂蚁间相互协作找到一条避开障碍物的最优机器人移动路径。

5 结语

随着移动机器人技术的发展，路径规划作为最重要的一个组成部分，其得到了许多的应用和发展，其在导航过程中，也引入了许多先进的算法，比如神经网络，更加优化了移动的路径。未来时间内，随着神经网络技术的改进，可以引入遗传算法、信息论、蚁群算法等，将这些算法优势结合，将会是路径规划更加准确和精确。

参考文献

[1]朱大奇,颜明重,滕蓉. 移动机器人路径规划技术综述[J].控制与决策,2010,25(7): 961-967.

[2]刘毅.移动机器人路径规划中的仿真研究[J].计算机仿真,2011,28(6): 227-230.

[3]熊开封,张华.基于改进型 FNN 的移动机器人未知环境路径规划[J].制造业自动化,2013,35(22): 1-4.

[4]柳长安,鄢小虎,刘春阳.基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报,2011,39(5).

路径规划典型算法篇（8）

【摘　要】本文通过对比求解最短路径问题的Dijkstra算法和Floyd算法的设计思想、求解过程和应用实例，讨论了两种算法的特点及适用领域。

关键词 最短路径问题；Dijkstra算法；Floyd算法

作者简介：高岚（1979—），女，吉林长春人，硕士，吉林工程技术师范学院信息工程学院，讲师，主要从事软件工程教学研究。

0　引言

最短路径问题是网络分析中最基本的组合优化问题之一，在公交路线网络规划中应用广泛。因此，实际公交线网优化设计中，路径选择算法成为一个重要研究课题，它直接关系到交通网络效率、传输延迟和吞吐量等主要技术性能指标。

早在20世纪初，最短路径这一重要问题就已得到人们的高度重视，当时有许多科学家研究这一问题的求解方法，但直到1959年荷兰计算机科学家Dijkstra（迪加斯特拉）才给出这一问题求解的基本思想，成为一代经典。当时的Dijkstra提出的这一算法主要解决的是从固定的一点到其他各点的最短路径问题。但实际生活中要求解的可能是任意两点间的最短距离，可采用Floyd（弗洛伊德）算法。本文通过将两种算法进行一些对比讨论，得出关于两种算法效率和适用问题的一些结论。

1　最短路径问题

最短路径问题是图论中的基本问题。在赋权图中，找出两点间总权和最小的路径就是最短路径问题。最短路径算法包括指定顶点对之间的最短路径算法和所有顶点间的最短路径算法，前者对于运输的合理化具有重要理论意义，而后者的意义在于选择合理的中转中心，使得总费用最少。在图论中最典型的两种求最短路径算法分别是Dijkstra算法和Floyd算法。

2　Dijkstra算法

2.1　算法基本思想

每次新扩展一个距离最短的点，更新与其相邻点间距离。当所有边的权都为正时，由于不会存在一个距离更短的没有扩展过的点，所以这个点的距离不会再被改变，因而保证了算法的正确性。根据这个原理，采用Dijkstra算法求解最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能破坏已经更新的点距离不会改变的性质。

2.2　Dijkstra算法思想在物流配送中的应用

采用图论中的最短路径算法Dijkstra算法来建立物流配送路径选择模型，主要思想是从代表两个顶点的距离开始，每次插入一个顶点比较任意两点之间的已知最短路径和插入顶点作为中间顶点时两点间的最短路径，得到的最终的权矩阵就反映了所有顶点间的最短距离信息。最短距离者作为费用最小者，即最佳的物流配送选址位置。

3　Floyd算法

3.1　算法基本思想

通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。

从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。

3.2　Floyd算法在选址问题中的应用

某城市考虑建立区域内二次供水中转站。在选址问题中，点表示可供选址，其间连线表示运输费用，其需求点之间运费如图1所示。在选址中，要求该中转站到其他站点的距离最短，即运输费用最少，通过运用求解最短路径的Floyd算法可求出该网点布局的最佳中转站。

由计算可知，a到其他点的费用和为C(a)=33，同理C(b)=27，C(c)=18，C(d)=21，C(e)=33，比较可知c到其他各点的费用最小。因此本例从经济性考虑，选c点为中转站最优。

4　讨论

典型的最短路径求解算法Dijkstra算法和Floyd算法各有所长。Dijkstra算法可为任一源节点找出与其它所有节点的最短路径，是目前公认的较好的最短路径算法，但由于它遍历计算的节点很多，所以效率低。Floyd算法是一种用于寻找给定的加权图中顶点间最短路径的算法，是一种动态规划算法，可以算出任意两个节点之间的最短距离，代码编写简单，但是Floyd算法计算最短路径时时间复杂比较高，不适合计算大量数据。

综上，求解单源点无负权边最短路径可采用Dijkstra算法，而求所有点最短路径应用Floyd算法。对于稀疏图，采用n次Dijkstra算法比较出色，对于稠密图，适用Floyd算法。

5　结束语

本文通过对比两种求解最短路径算法的设计思想、求解过程、应用实例，讨论了算法的特点及适用领域。了解算法求解问题的差异，针对不同类型问题采取对应的求解算法，将大大提升解决问题的效率，对实际生产生活起到重要作用。

参考文献

［1］辛建亭,胡萍.图论在通讯网中的应用[J].2009,3.

［2］凡金伟,吕康.基于Dijkstra算法在物流配送中的应用[J].电脑编程技巧与维护,2009(4):39-45.

［3］邓春燕.两种最短路径算法的比较[J].电脑知识与技术,2008(12):511-512.

［4］徐凤生.求最短路径的新算法[J].计算机工程与科学,2006,2.

［5］殷剑宏,吴开亚.图论及其算法[M].合肥:中国科学技术大学出版社,2005.

［6］陈玉华.浅谈图论在现实生活中的应用[J].云南省教育学院学报,2004.

路径规划典型算法篇（9）

中图分类号：V279+.2 文献标识码：A 文章编号：1009-914X（2013）06-0155-02

1、无人机任务规划系统

无人机任务规划系统（Unmanned Aerial Vehicle Mission PlanningSystem）是根据地理信息系统（Geographic Information System）和卫星侦察系统（Satellite Reconnaissance System）提供的数字地图数据、敌方防空系统部署情况并结合无人机自身性能参数，利用航迹规划算法为无人作战飞机规划出一条或多条安全系数大、突防概率高、飞行线路或飞行时间短的飞行路线。该系统的输入为一系列地形、威胁等约束条件，输出为从初始点到目标点的一系列的参考航迹点，uAV依次飞过航迹点序列并最大限度地发挥UAV的作用遂行装订在航迹上的侦察、发射等任务，完成从起点到终点的飞行。航迹规划是任务规划的主体和核心组成部分。

2、算法在无人机任务规划中的作用

在防空技术日益先进、防空体系日趋完备的现代数字化战争环境中，任务规划是提高UAV遂行任务性能的有效手段。无人机任务规划是在综合考虑时间、油耗、威胁以及飞行区域等约束的前提下，根据UAV性能载荷及作战任务的不同对无人机进行合理的分配和规划出一条最优或者是满意的飞行航迹，以支持无人机顺利飞行并安全返回，实现耗时、耗油、承受威胁代价最小和UAV种类及数量等资源的实时、动态合理调配，是使任务目标与约束条件相匹配的函数优化问题。

算法是任务规划的核心，是飞行航迹寻优的数学实现途径。算法优劣直接决定任务规划的速度和质量。无人机任务规划算法研究的不断深入推动了无人机任务规划技术朝着实时化、精准化、智能化的方向不断发展进步。

3、无人机任务规划算法的分类

为使任务规划效能最优，学者们先后提出了基于概略图的规划方法、通视图法、Voronoi法、轮廓线法、子目标网络法、随机路标图法、最速下降法、法、最优控制法、模拟退火法、动态规划法、电势理论法、启发式算法、遗传算法、蚁群算法、基于合同的方法等一系列算法，又相应的提出了如改进A*搜索法、改进遗传算法等改进算法。根据智能化、自动化程度或适用范围可将规划算法划分为不同的类别。

3.1 按照智能化、自动化程度划分

按照算法的智能化、自动化程度，可将无人机任务规划算法划分为经典任务规划算法和现代任务规划算法。经典任务规划算法主要有最优控制法、导数相关法（牛顿法、梯度法等）、基于概略图的规划方法、通视图法、Voronoi法、轮廓线法、子目标网络法、随机路标图法、最速下降法、法、最优控制法、数学规划法、动态规划法等。现代任务规划算法突出了现代计算机技术、数学与计算科学、数字地图等科技的应用，主要有启发式寻优搜索法、人工神经网络法、遗传算法、模拟退火法、专家系统法、蚁群算法、电势理论法、启发式A*搜索法、D*优化算法等。

3.2 按照算法适用范围划分

算法从不同角度构建函数模型和描述、演绎、校验任务规划实施流程，因而不同的规划算法通常有不同的适用范围。按照适用范围将规划算法划分为航迹规划类算法和任务分配规划类算法，而航迹规划类算法又可以分为全局航迹规划类、局部航迹规划类和实时航迹规划类算法。

1）适用UAv航迹规划的算法

VORONOI法～DIJKSTRA搜索算法等几何法比较适用于uAV全局初始航迹的搜索规划，而遗传算法较适用于UAV全局航迹搜索寻优规划，启发式算法、动态规划法、人工势场法等算法较适用于UAV局部航迹规划及实时航迹规划。

2）适用UAv任务分配的算法

整数规划法、蚁群算法、基于合同网的方法及遗传算法等算法适用于多UAV协同任务分配规划。

4、几种常用的任务规划算法的比较研究

人工神经网络算法、蚁群算法、遗传算法是无人机任务规划的常用算法，这些算法各有自身优点和不足，适宜解决问题的范围也各有不同。对算法进行比较研究有利于掌握各种方法的精髓和根据实际情况予以应用。

4.1 人工神经网络法

人工神经网络算法的实质是模拟生物神经网络进行信息处理而对各信息单元构成的拓扑结构的优化。该方法具有高度的并行结构、并行实现能力、高速寻优能力，能够有效发挥计算机的高速运算优势，在无人机任务规划等复杂问题处理方面得到了广泛的应用。经学者长期研究，先后建立了感知器神经网络模型、径向基函数（RBF）神经网络模型、反向传播（BP）神经网络模型、自组织神经网络模型以及Hopfield神经网络模型。其中，Hopfield神经网络模型属于反馈型神经网络模型，适用于处理无人机航迹规划等非线性问题。

Hopfield神经网络法结合能量函数随状态变化单调递减的规律，将能量函数引入人工神经网络，通过寻优能量函数在稳定平衡下的输出等效分析无人机参考飞行航迹，该方法有效地发挥了人工神经网络的收敛性和能量函数趋于稳定状态的特点，同时发挥了Hopfield神经网络法的反馈控制机制，生成的参考航迹具有较好的避障能力和鲁棒性。该算法的实施步骤简述如下：

1）结合规划问题背景对规划空间进行离散化处理并构建与无人机任务规化问题相对应的Hopfield神经网络模型。

2）结合数字地形、障碍物、防空火力及侦测雷达信息及无人机自身约束条件构造能量函数，能量函数需充分体现出不同飞行情况下的网络连接权的变化。连接权随着飞行代价（距离障碍物远近、是否及以何种程度进入雷达侦测区、是否及以何种程度进入雷达侦测区、是否及以何种程度符合飞行半径、燃油限制等UAV自身约束条件等）而变化。

3）对建立的神经网络模型进行模拟，在规划空间则会建立起单峰梯度数值势场并结合势场梯度函数值以及无人机飞行约束条件在规划空间内搜索最优航迹。

4.2 蚁群算法

蚁群算法（Ant Colony Optimization，AC0）是一种用来在图中寻找优化路径的机率型模拟进化算法。它由Marco Dorigo提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。该算法通过个体之间的信息交流与相互协作可实现参考航迹搜索。其基本原理是：蚂蚁通过释放信息素可以影响其他蚂蚁的路径，蚂蚁在初始阶段选择不同路径概率相同，但是由于路径越短在单位时间内通过的蚂蚁数量越多，释放的信息素也就越多，从而随着信息素强度的增大，蚂蚁选择该短路径的概率也就越高，随着时间的推移，这条路径就渐渐发展成为蚂蚁从出发点到目的点的首选路径。正如鲁迅先生所说：“世界上本没有路，走的人多了，也便成了路”，同样，我们可以形象地比喻：其实规划空间中本没有路，走的蚂蚁多了，这条路也就成了它们首选的路。

蚂蚁寻找食物的问题，可归结为在一定搜索空间寻求从出发点到目的点的最优路径问题，与无人机航迹规划――寻求无人机从出发点到目的点的最优参考航迹的问题具有直接模型关联关系。因此，无人机航迹规划问题可以参照蚁群寻食模型予以研究。通过以下步骤可实现基于蚁群算法的无人机航迹规划：

（1）结合威胁、障碍物分布情况构造初始参考路径，在路径起始点设置人工蚂蚁；

（2根据由两点间的可见度以及两点间的信息素值的强度决定的蚂蚁状态转换规则选择下一节点，以此循环持续搜索直至所有蚂蚁到达终点，搜索终结；

（3）搜索得到多条可行航迹并分别计算每条可行航迹的代价（考虑航程代价、飞行威胁代价、自身约束满足情况等），选择代价最小的作为优选参考航迹。

（4）将未经过的各点的航迹点予以人为蒸发，整理规划空间而输出最优参考航迹。

蚁群算法在无人机任务规划研究领域已得到有效应用。国防科技大学的苏菲等通过蚁群算法对多无人机任务分配问题进行了深入研究并提出了基于蚁群分工的优化求解策略；Abbattista F等提出了将遗传算法和蚁群算法有机融合、优势互补的规划策略；Li S H提出了将人工神经网络方法和蚁群算法巧妙融合的灵活规划方法并通过仿真验证了其优越性。

4.3 人工势场法

人工势场法是由Khatib提出的一种虚拟力法，该算法的基本思想是将无人机在周围环境中的运动设计成一种抽象的人造引力场中的运动。将目标点和障碍物赋予两类不同的力的属性，定义目标点对无人机的作用力为“引力”，障碍物对无人机的作用力为“斥力”，通过求无人机在规划环境中受到的合力来控制无人机的运动，使无人机朝着目标点趋近并保证在此过程中不触及威胁和障碍物。

人工势场法在数学描述上简洁、美观，生成参考航迹具有平滑性好、快速性好、安全性好的特点，但对障碍物的规则性有较高要求，否则算法的计算量将很大，有时甚至是无法计算的。目前，人工势场法较多应用于航迹的平滑处理、偶遇障碍物特情的实时航迹规化及障碍物规则分布的局部航迹规划。结合算法特点，人工势场法与遗传算法、蚁群算法的有机融合也成为有效的研究方法。西北工业大学的屈耀红等通过分析不同强度威胁源构成的飞行环境，将人工势场法与遗传算法相结合，实现了无人机全局航迹规划及仿真；北京科技大学的李擎等针对传统人工势场法在航迹规划中的一类目标点不可达问题提出了一种基于遗传算法参数优化的改进人工势场法实现了威胁回避并规划出长度短且光滑的参考航迹。

4.4 遗传算法

遗传算法由美国密歇根大学的Holland等人提出，起源于仿照生物系统自然进化的计算机人工智能模拟研究。算法的基本原理是在构建评价函数、给出描述问题的基本参数后，将需要优化的问题的参数进行编码，经过模拟自然选择操作而选定初始群体后，进行交叉和变异的遗传运算，经过多次重复迭代直至得到比较理想的优化结果，整个算法实施的过程实质上是模拟自然界中基因重组与进化的过程，是模拟自然界优胜劣汰的竞争机制的寻优过程，是基于概率选择的群体进化计算过程。

遗传算法是一种搜索优化算法，它先创建基于问题的染色体个体并通过模拟自然选择操作形成种群，再通过适应度函数（目标函数或评价函数）计算染色体个体的适应性，对优者进行复制，通过交叉和突变操作改良后代品质。其中，交叉操作（单点交叉或多点交叉）是指相互交换2个单个染色体的一部分，而突变操作是指改变染色体上某个随机基因座上的基因值。将染色体（个体）的评价值等效为概率这一标量，再通过排序选择方法或者赌概率选择机制将适应性较弱的染色体淘汰。适应性较强的染色体逐渐主导了种群，最终使种群整体适应性得以提升，再从得到优化的新一代群体中比较选出其中最优个体作为理想解输出，得到的理想解答不一定是实际的最优解，但一定是近似最优解，一般可以满足优化搜索的需要，而且经遗传算法优化搜索可以同时得到一个相对最优解和多个较优解，可以满足系统多输入――多输出的要求，是遗传算法并行计算优质品质的直接体现。通过遗传算法进行问题解的优化搜索的主要方面可归纳为：

1）对拟优化问题进行基因编码，即在搜索开始之前结合问题属性对无人机位置及航迹可行性进行编码；

2）生成初始种群，即在规划空间内随机产生若干（群体大小数）个个体（染色体或串接数据），每个个体等效为一条规划航迹，每个个体由若干基因组成，等效为条规划航迹由若干航迹点组成。

3）构建评价染色体性能的适应度函数（评价函数或者目标函数）、有利于种群进化的三种遗传算子――“选择算子”、“交叉算子”、“变异算子”，从而构建有利于种群进化的数学模态；

4）参照自然界进化模式对问题模型进行合理“选择”、“交叉”、“变异”等遗传操作。

5）按照遗传算子对群体进行多代迭代计算后，在达到进化指标或及进化代数要求后输出一个或多个最优个体，将最优个体解码得到最优参考航迹。

遗传算法对所求解问题的具体细节要求不高，不要求建立描述问题的具体解析规则，具有较好的适用性、鲁棒性，该方法不要求规划空间满足连续性、导数存在和单峰等条件，其内在的种群进化策略能够很好地发挥计算机并行计算的优势，具有智能性、自适应搜索、基于概率选择的渐进式寻优、并行计算等优点，是一种具有很强的通用性、鲁棒性、全局最优性，可用于求解一系列其他方法难以解决的复杂问题。作为一种全局优化算法和搜索算法，一般可以很快地收敛到最优解附近，如果要求更精确地解，可将遗传算法与其他方法结合起来，提高解的质量。

清华大学的郑锐等通过采取保优选择策略和改进编码方式并改进交叉算子，对基本遗传算法作了改进，实现了全局选优且避免局部最优、快速收敛、高精度寻优的航迹规划；空军工程大学的鲁艺等针对实际作战环境的任务规划需要，提出了能够满足uAV机动要求的基于改进遗传算法的UAV高效航迹规化算法；西北工业大学的王景针对遗传算法易陷入局部最优的缺点和减小航迹随机搜索计算量，创新性地提出了限定搜索区域的分层遗传算法，提高了航迹寻优效率并有效地缩短了规划航迹长度；北京航空航天大学的文泾等通过将链接图法、最短路径法、遗传算法相结合，实现了高质量的任务规划并仿真验证。遗传算法渐已发展成为无人机航迹规划领域的主流研究方法。

路径规划典型算法篇（10）

一、设计阶段工程造价控制存在问题分析

1.设计深度不够使工程造价得不到有效控制

近几年来,电力工程的建设项目多、进度要求快, 各级电力勘察设计单位承担的设计任务也大幅增加。一些设计单位在遇到设计任务重、时间紧的时候,往往无法做到深入细致的调查研究,工作敷衍了事,未按国家标准进行设计,对具体设计方案缺乏比较,以及设计水平不高,审查制度不严等,最终造成项目设计深度不够、套用图纸不适等导致设计变更增多, 使工程造价得不到有效控制。

2.工程设计和投资控制联系不够紧密

在实际工作中, 由于送电工程专业技术性强的特点, 一般都是勘测设计人员根据设计委托进行现场调查、勘测和方案比较, 分阶段提供条件给造价人员编制估算或概预算。但是长期以来,技术人员由于缺乏经济观念,往往无法提供编制概预算所需的全部条件;而从事概预算编制的人员不熟悉工程设计和施工的工艺,无法吃透相关定额、标准的内涵,不能主动收集或向技术人员索取所需的全部条件,导致编制的概预算存在缺项、漏项或重复计算、高估冒算的情况,难以真实反映施工现场费用,有效地控制造价。

3.缺乏信息反馈和项目后评价程序

项目完成后由于缺乏造价成本信息反馈和缺少项目的后评价程序使设计单位缺少机会了解实际发生的工程成本, 无法进行事后分析, 在以后工作当中又有可能将问题带入下一个项目中, 不能进一步提高造价控制工作的质量。

二、设计阶段工程造价控制的措施

1.健全设计单位经济责任制,严格控制工程成本,提高竞争意识

设计单位和主管部门对于设计节约和浪费应制定明确的奖罚标准:对因设计原因而造成的工程浪费、工期延误及超出投资限额的损失,要追究设计人员责任;对科学合理、经济的方案予与奖励。促使设计人员增强主观能动性,提高自身素质和相互间竞争的能力, 增强为业主控制投资成本, 提高竞争意识。

2.推行限额设计,全面推广工程典型造价运用工作,加强技术和经济的有机结合

所谓限额设计,就是按照批准的可行性研究报告和投资估算,在保证质量、功能要求的前提下,控制初步设计;按照批准的初步设计编制概算,控制施工图设计和预算;同时,各专业要按分配的投资额来控制设计。限额设计必须贯穿于勘察设计的全过程。

推行限额设计有利于强化设计人员对工程全过程的造价意识, 有利于经济管理人员及时进行造价计算, 为设计人员提供信息, 使勘测设计小组内部形成有机整体, 克服设计深度不够及勘测设计相互脱节的现象, 改变设计过程不算账、设计完成见分晓的现象, 使投资达到动态控制的目的。同时, 推行限额设计还可以促使设计和造价人员进行项目全寿命费用的分析, 使他们不仅要考虑项目一次性的投资, 还要考虑施工阶段和运行后的经济费用。比如: 在输电线路工程项目设计过程中对于线路选线定位以及在雷区的防雷、冰区的避冰、抗冰、防冰、融冰等对运行成本影响较大设计方案的优化时, 就有利于设计人员进行全面分析、仔细考虑、认真权衡, 最大限度降低工程成本, 在投资限额内控制好工程造价。

送电线路工程典型造价是国家电网公司加强工程造价管理,降低工程造价,提高投资效益的重要手段。在送电线路典型设计的基础上,按照各模块的使用条件,通过对大量实际工程的统计、分析,合理确定典型工程断面,再结合各地区各电压等级线路的特点,科学设定设计所需的边界条件,形成典型方案。然后,典型造价在典型方案的基础上编制完成。典型造价成果体现了科学性,先进性,合理性和适用性。在实际工程设计中,必须按照典型造价进行严格把关,若工程主要条件与典型方案有差异而产生造价费用偏差,应对各项技术经济指标进行严格认真的分析比较,直至该设计方案的造价指标在合理范围内。推广典型造价,有利于科学建立工程造价标准,合理评价工程技术经济指标水平,有效控制工程投资,努力降低电网工程建设成本。

3.优化设计方案,有效控制工程造价

设计是工程建设的灵魂, 设计成果的好坏对造价影响很大,因此必须尽可能地优化设计成果。根据国家发展和改革委员会2007年的《电网工程建设预算编制与计算标准》的规定,架空送电线路工程静态投资主要由四个方面构成:即本体工程费、辅助设施工程费、编制年价差和其他费用。本体工程费一般占65%～75%左右,辅助设施工程费一般占0.3%左右,编制年价差正常情况一般占5%～10%左右;其他费用一般占15%～30%左右。从投资构成上看,编制年价差虽然也占一定的投资比例,但它的高低主要受人工、材料、机械要素的市场价格波动影响,对投资主体来说为不可控因素,故对架空送电线路工程造价控制的重点应该是对本体工程费用控制和其他费用控制。

本体工程由六项单位工程构成:工地运输、土石方工程、基础工程、杆塔工程、架线工程、附件工程。按静态投资对各个因素的敏感程度来排序,较高的是杆塔指标、人力运距、基础混凝土。因此,在设计阶段对本体工程的控制重点应主要控制这三个技术指标。

其他费用从构成上主要包括:建设场地征用及清理费,项目建设管理费、项目建设技术服务费、整套启动试运费、生产准备费、辅助施工费、基本预备费等。除建设场地征用及清理费用外,其它各项费用一般有较明确的开支项目和费用标准,概预算编制也有规定的费率计取标准,管理和控制较容易,工程实践中这些项目很少出现超支问题。因此,对其他费用的控制重点是在建设场地征用及清理费的控制。

(1)优化线路路径

对送电线路来说, 路径优化是设计工作的第一步, 也是控制工程造价的重要措施。路径的选择影响本体工程的多个单位工程,是影响整个工程造价的主要因素。设计人员在设计前,要十分重视沿线气象条件、地形、地质、水文、污秽等级、现有可利用交通条件、重要交叉跨越、重大障碍物拆迁等资料的收集工作。不能片面追求路径最短化,而必须在满足所属地区规划部门要求及避让通信、军事等设施前提下,考虑安全运行、方便施工、降低造价、经济运行、障碍物处理及大跨越情况基础上,对线路路径的多方案进行综合比选,选择技术经济最优的方案,例如:拆除建筑物和居民住房, 砍伐经济林木或防护林,跨越采石厂等都会增加拆迁补偿费用,影响到其他费用中的建设场地征用及清理费的控制;不良地质会增加基础建设投入;而不良地形更会增加工程的总体造价。

(2)合理选择导线、地线

导线截面的选择应综合考虑线路的输送目的地负荷容量及负荷增长情况、导线制造、架线施工、运行维护等多方面因素,进行技术、经济的综合比较。发挥地线在防雷保护、通信等方面的综合作用,合理配置OPGW、良导体及普通地线,使选择的导线、地线既要满足技术上的要求,又要保证工程投资的经济合理。

(3)合理规划塔型

影响线路投资最敏感的因素就是塔材量, 不同的杆塔型式在造价、占地、施工、运输和运行安全等方面均不相同。减少每公里塔材的耗钢量是降低造价的最有效途径。如每公里减少1 吨的塔材, 那么每公里可减少材料费及施工费用等各项投资约1 万元。虽然每公里塔材的耗钢量不可能无限制地减少, 但从以往工程统计分析看, 不同的线路在标准相差不多的条件下, 每公里塔材耗钢量可相差几吨。因此,在设计阶段,必须根据工程地形地貌条件, 精心规划工程需要的各种塔型,在满足使用条件下选用耗钢量较少的杆型;同时,降低线路曲折系数, 增加直线杆塔使用比例, 以降低杆塔耗钢指标,从而控制工程造价。还可以结合近、远景规划,使用双回路或多回路铁塔,这样目前工程的造价虽然会高了点,但为以后的工程建设项目预留下线路走廊,避免或减少了下个工程的工地运输、土石方工程、基础工程、杆塔工程的施工工程量及建设场地清理费,从总体上讲还是会大大降低工程造价。

(4)优化杆塔基础形式

杆塔基础作为输电线路结构的重要组成部分,它的造价、工期和劳动消耗量在整个线路工程中占很大比重。其施工工期约占整个工期一半时间,运输量约占整个工程的60%,费用约占整个工程的20%～35%,基础选型、设计及施工的优劣直接影响着线路工程的建设。在基础设计方面, 根据每基杆塔的基础作用力和地形地质条件,优先采用掏挖、嵌固、岩石基础等原状土基础, 并积极采用技术先进的基础型式和杆塔全方位高低腿、不等高基础等, 可大大减少工程中土石方量和混凝土量, 同时也减少了对自然环境和地面植被的破坏, 有效地减少建设场地清理费,节约工程的投资。

4.加强设计变更的管理

在项目建设过程中, 不可避免会发生设计变更。设计变更有业主的功能性变更与设计的技术变更,设计变更管理主要是针对设计的技术变更管理。技术变更又分施工图设计变更与施工中的设计变更,施工中的变更主要是材料设备采购变更和现场施工变更;施工图设计变更会产生基础或结构局部变更,从而影响工程的造价;再者,设计变更管理还涉及到变更所处的时间段的问题,对非发生不可的变更, 设计人员应主动深入了解情况,争取把设计变更控制在最小范围:在设计阶段发生变更,只修改设计图,损失就少;在采购阶段发生变更,不仅要修改图纸,还得要采购新的材料和设备;若是在施工阶段发生变更,不但是设计图和材料设备的变更,而且会造成返工、拆除、重做,势必产生重大变更损失,造成浪费。总之,要严格控制设计变更,变更前要算好账,论证其合理性、必要性再变更,严格履行变更程序,加强设计变更管理,使变更控制在限额内,达到有效地控制工程造价。

5.形成跟踪制度

路径规划典型算法篇（11）

中图分类号:TV122+.5 文献标识码:A 文章编号:1674-0432(2010)-06-0192-3

0 引言

在我国社会主义建设中,为了在小流域上修建农田灌溉排水措施、公路和铁路的桥涵建筑、城市和工矿地区的防洪工程,都必须进行设计洪水计算。因此,小流域设计洪水计算在工农业生产中有着重要的意义。小流域设计洪水的计算方法有很多,可以由流量资料推求设计洪水,也可以由暴雨资料推求设计洪水,但在小流域中很少设有水文观测站,往往缺乏实测的流量资料或暴雨洪水系列资料,因此常采用经验公式法、推理公式法、地区综合法、综合经验单位线法以及水文模型法等方法计算小流域的设计洪水。本文采用经验公式法和地区综合法计算白塔堡河的设计洪水,地区综合法就是采用相邻地区的实测及调查资料来确定各小流域的洪峰流量模数及其它统计参数,计算各小流域设计洪峰流量。

1 流域概况

白塔堡河位于浑河的左侧,是浑河的I级支流,该河发源于东陵区李相镇老塘峪村,流经李相、深井子、南塔、浑南新区、白塔、浑河民族开发区等六个乡镇(街区),于曹仲屯汇入浑河。流域面积182km2,河流总长48.45km,其中河流上游段为低山丘陵区,长29.4km,河道比降1.1‰。老塘峪至浑南新区教场桥之间为低山丘陵区,其下为平原区。该河中上游河道曲折,属宽浅式河床,中下游比较顺直,属窄深式河床。白塔堡河属季节性河流,平时无水或水量很小,汛期发生洪水时洪峰流量很大,极易造成洪水灾害。

2 计算步骤

白塔堡河没有水文观测站,其上游段的地貌特征与满堂河相似,满堂河上建有东陵水文站,本次水文计算采用东陵站21年降雨资料和《辽宁省中小河流(无资料地区)设计暴雨洪水计算方法》的理论分析方法,计算白塔堡河的设计洪水。

2.1 计算步骤

2.2.1 推求设计暴雨 根据实测暴雨资料,采用统计分析和典型放大法求得。

2.2.2 拟定产流方案 推求设计净雨,根据根据暴雨洪水资料,利用径流形成的基本原理,通过相关图法求得。

2.2.3 利用流域汇流方案 利用汇流的概念,用成因分析的方法求得。

2.3.4 推求设计洪水过程线 由求得的设计暴雨,利用产流方案推求设计净雨过程,再利用流域汇流方案由过程求得设计洪水过程设计净雨。

3 设计暴雨

3.1 典型过程及放大计算

利用东陵区的21年降雨量表,找出每年的最大1日、3日、7日降雨量并排序输入水文分析软件,其中21年最大七日降雨量见表1。并计算得出20年一遇的设计点暴雨,成果见表2。

通常寻找降雨量不均匀,并且又突然的强降雨作为典型年。根据表1,选择1996年作为典型年。

表1 21年最大七日降雨量

日期 1

(mm) 2

(mm) 3

(mm) 4

(mm) 5

(mm) 6

(mm) 7

(mm) 七天雨量

(mm)

1988 83.4 12.6 5.9 20.5 6.1 1.3 0 129.8

1989 16.6 2.7 11.5 11.1 8.9 47.2 0 98

1990 0 30.7 0.7 0 0 59.9 6.9 98.2

1991 16.7 13.3 1.4 0 26.4 35.2 8.5 101.5

1992 40.4 0.3 2.6 11.5 0 12 36.2 103

1993 10.7 8.2 62.3 48.4 54.3 6.2 42.4 232.5

1994 33 0 0 118.8 0 0 5 156.8

1995 17.8 67.5 38.1 0 73.7 41.5 6.9 245.5

1996 22.2 32.6 16 0.3 8.3 5.3 145.1 229.8

1997 2.8 0 0 0 135.5 5.8 0 144.1

1998 31.3 125.1 16.8 1.2 0.2 9.7 32.2 216.5

1999 0 0 0 76.2 9.8 0 0 86

2000 12 0 0 0 0 43 2.5 57.6

2001 92.8 14.4 9.5 11.8 0.5 47.8 0 176.8

2002 19.6 60.7 69.7 27.9 21.9 18.4 0 218.2

2003 2 2 1 0.5 152 0 0 157.5

2004 21.5 61 1.5 0 71.5 0 0 155.5

2005 17.5 24 5 0 32 94.5 0 172.5

2006 12.5 0.5 47 7 13.5 0 17 97.5

2007 114 6 0 0 0 0.5 0 120.5

2008 17 0 0.5 0 0 24.5 14.5 118.5

根据《辽宁省中小河流(无资料地区)设计暴雨洪水计算方法》中辽宁东部地区暴雨时-面-深关系曲线查得放大系数为0.99。则可得白塔堡河设计点暴雨量分别为

P1=142.6mm;P3=168.4mm;P7=238.9mm

根据已求出的设计暴雨量和选出的典型暴雨量计算放大倍比如下:

最大一天降雨量倍比

(1)

最大三天与最大一天雨量差额放大倍比

(2)

最大七天与最大三天雨量差额放大倍比

(3)

表2 p=5%设计暴雨

天数(天) 1 3 7

设计暴雨(mm) 144.09 170.2 241.41

3.2 设计暴雨时程分配

根据放大倍比,将1996年典型过程时段放大,便得出二十年一遇的设计暴雨时程分配,见表3

表3 设计暴雨时程分配

暴雨时空分布

天 1 2 3 4 5 6 7

典型年暴雨(mm) 22.2 32.6 16 0.3 8.3 5.3 145.1

Ki 0.98 0.98 0.98 0.98 1.9 1.9 0.99

P(mm) 21.96 32.28 15.88 0.294 15.77 10.07 142.69

3.3 设计洪水

3.3.1 降雨径流计算 根据《辽宁省中小河流(无资料地区)设计暴雨洪水计算方法》中关于降雨径流的计算方法列出表4

表4 可能最大地面净雨时程分配计算

日次(天) 1 2 3 4 5 6 7

P(mm) 21.96 32.28 15.88 0.294 15.77 10.07 142.69

P-E(mm) 17.96 28.274 11.84 0 11.77 6.07 138.6333

RS(mm) 2 4.2 1.5 0 1.5 0.3 56

RS扣除(mm) 1.766 3.966 1.266 0 1.266 0.066 55.76

表4中P为设计暴雨时空分配,RS根据《辽宁省中小河流(无资料地区)设计暴雨洪水计算方法》附图辽宁省水文分区I23区降雨径流相关图查得,RS扣除为地面径流

3.3.2 可能最大洪水推求

(1)综合经验单位线的qm,tn值的确定

根据公式M=J0.25f0.5F=J0.25()0.5F=30.36

且D=0.24g=0.965

qm=DMg=6.47m3/s (4)

根据A=3b=0.556

(5)

tn=AGb=12天(6)

(2)瞬时单位线两参数n、k值的确定

以qm=6.47m3/s,tn=12天,he=10mm

(7)

根据《辽宁省中小河流(无资料地区)设计暴雨洪水计算方法》附图查f(p)―P工作曲线P=1.4 计算出

n=P+1=2.4(8)

(9)

(3)求S(T)曲线并转化为Δt=24小时时段单位线计算表5

表5 用S(T)曲线转化时段单位线计算

t 0 1 2 3 4 5 6 7

t/K 0 0.116686 0.233372 0.350058 0.466744 0.583431 0.700117 0.816803

s(t) 0 0.002 0.009 0.0215 0.036 0.051 0.069 0.083

s(t-Δt) 0 0 0.002 0.009 0.0215 0.036 0.051 0.069

u(Δt,t) 0 0.002 0.007 0.0125 0.0145 0.015 0.018 0.014

q(Δt,t) 0 0.45 1.575 2.8125 3.2625 3.375 4.05 3.15

注:

(4)可能最大设计洪水过程推求最终列出设计洪水过程见图1。

图1 白塔堡河20年一遇设计洪水过程线

由图可知东陵最大洪峰流量为Q=258m3/s。

(5)白塔堡河最大设计洪水推求

根据《辽宁省中小河流(无资料地区)设计暴雨洪水计算方法》中公式由东陵站设计洪水推求白塔堡河设计洪水

Q白塔堡=Q山区+Q平原(10)

(11)

Q白塔堡平原=0.666(F白塔堡)0.824 (12)

根据公式(10)、(11)和(12)计算得白塔堡河设计洪峰流量为Q白塔堡=376.1m3/s。

4 结语

小流域很少设有水文观测站,往往缺少实测的流量资料或暴雨洪水资料。但各省都已编制完成水文手册,绘制出了暴雨等值线图,可以通过各省的水文手册来计算设计洪水。在小流域设计洪水计算方法上,地区综合法能根据相邻流域实测资料计算所规划的小流域设计洪峰流量,计算结果能够较合理的反应小流域设计洪水流量,满足小流域治理规划的要求。

参考文献

[1]叶守泽.水文水利计算[M].北京:中国水利水电出版社,2006.