路径规划汇总十篇

序论：好文章的创作是一个不断探索和完善的过程，我们为您推荐十篇路径规划范例，希望它们能助您一臂之力，提升您的阅读品质，带来更深刻的阅读感受。

篇（1）

引言

物流与国民经济及生活的诸多领域密切相关，得到越来越多的重视，甚至被看作是企业“第三利润的源泉”。因此，作为物流领域中的典型问题，旅行商问题(Traveling Salesman Problem，TSP)的研究具有巨大的经济意义。

TSP(Traveling Salesman Problem)问题, 是VRP[2]的特例，也称为巡回旅行商问题,货担郎问题。简称为TSP问题，已证明TSP问题是NP难题。。TSP问题可描述为:给定一组n个城市和它们两两之间的直达距离,寻找一条闭合的旅程,使得每个城市刚好经过一次而且总的旅行路径最短。TSP问题的描述很简单,简言之就是寻找一条最短的遍历n个城市的路径,或者说搜索整数子集X={1,2,…,n}(X中的元素表示对n个城市的编号)的一个排列π(X)={v1, v2,…, vn},使取最小值.式中的d(vi,vi+1)表示城市vi到城市vi+1的距离。它是一个典型的、容易描述但却难以处理的NP完全问题。同时TSP问题也是诸多领域内出现的多种复杂问题的集中概括和简化形式。所以,有效解决TSP问题在计算理论上和实际应用上都有很高的价值。而且TSP问题由于其典型性已经成为各种启发式的搜索、优化算法 (如遗传算法、神经网络优化法、列表寻优法、模拟退火法等)的间接比较标准。

1 遗传算法与蚁群算法

1.1 遗传算法原理

遗传算法(Genetic Algorithms，GA) 是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法,由美国J.Holland教授提出,其主要内容是种群搜索策略和种群中个体之间的信息交换,搜索不依赖于梯度信息.该算法是一种全局搜索算法,尤其适用于传统搜索算法难于解决的复杂和非线性问题.。选择算子、交叉算子和变异算子是遗传算法的3个主要操作算子.遗传算法中包含了如下5个基本要素:①对参数进行编码;②设定初始种群大小;③设计适应度函数;④设计遗传操作;⑤设定控制参数(包括种群大小、最大进化代数、交叉率、变异率等)

1.2 蚁群算法原理

研究表明：蚂蚁在觅食途中会留下一种外激素．蚂蚁利用外激素与其他蚂蚁交流、合作，找到较短路径．经过某地的蚂蚁越多，外激素的强度越大．蚂蚁择路偏向选择外激素强度大的方向．这种跟随外激素强度前进的行为会随着经过蚂蚁的增多而加强，因为通过较短路径往返于食物和巢穴之间的蚂蚁能以更短的时间经过这条路径上的点，所以这些点上的外激素就会因蚂蚁经过的次数增多而增强．这样就会有更多的蚂蚁选择此路径，这条路径上的外激素就会越来越强，选择此路径的蚂蚁也越来越多．直到最后，几乎所有的蚂蚁都选择这条最短的路径．这是一种正反馈现象．

2.算法改进

在传统解决方法中，遗传算法以其快速全局搜索能力在物流领域获得了广泛的应用。但遗传算法在求解到一定程度时，往往作大量的冗余迭代，对于系统中的反馈信息利用不够，效率较低；蚁群算法也以其较强的鲁棒性和智能选择能力被广泛应用于旅行商问题 。蚁群算法是通过信息素的累积和更新而收敛于最优路径,具有分布、并行、全局收敛能力，但由于蚁群算法的全局搜索能力较差，易陷入局部最优，很难得到最优解。

为了克服两种算法各自的缺陷,形成优势互补。为此首先利用遗传算法的随机搜索、快速性、全局收敛性产生有关问题的初始信息素分布。然后,充分利用蚁群的并行性、正反馈机制以及求解效率高等特征。算法流程如图1

图1 遗传混合算法流程

2.1遗传混合算法的具体描述如下：

Step1 给出，放置m个蚂蚁在n个城市上。

Step 2 把所有蚂蚁的初始城市号码放置到tabuk中，列表tabuk纪录了当前蚂蚁k所走过的城市，当所有n个城市都加入到tabuk中时，蚂蚁k便完成了一次循环，此时蚂蚁k所走过的路径便是问题的一个解。

Step 3 蚂蚁K从起点开始，按概率的大小选择下一个城市j,k∈{1，2，…,m},j∈allowedk如果蚂蚁k转移到j ,从allowedk中删除,并将j加入到tabuk直至allowedk= 时重新回到起点。

Step 4 是否走完所有的城市，否，则转入Step 3。

Step 5 计算,记录，更新信息素浓度，所有路径信息更新，如果,清空tabuk则转入Step 2。

Step 6 当时，得到相对较优蚂蚁的序列。初始化种群。

Step 7 计算适应度值。

Step 8 进行遗传交叉与变异操作。

Step 9 输出得到的最短回路及其长度。

2.2 算法过程实现

（1）种群初始化

用蚁群算法进行初始化种群，放m只蚂蚁对所有城市进行遍历，将得到的结果进行优化，做为蚁群算法的初始种群。每只蚂蚁走过的路径的就代表了一条基因（a0、a1、…、am-1、am），对于这条基因表示这只蚂蚁首先从a0出发，次之访问a1、…然后依次访问am-1、am最后再回到a0。

（2）状态转移规则设置

    转移概率，为t时刻蚂蚁由i城到j城的概率。

            （1）

式中，allowedk表示蚂蚁k下一步允许选则的城市，表示信息启发因子，其值越大，该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间的协作性超强；β为期望启发因子，β的大小表明启发式信息受重视的程度，其值越大，蚂蚁选择离它近的城市的可能性也越大，越接近于贪心规则［6］。为启发因子，其表达式为: ，每条路上的信息量为：

（2）其中

其中ρ表示路径上信息的蒸发系数，1-ρ表示信息的保留系数；表示本次循环路径(i,j)上信息的增量。表示第k只蚂蚁在本次循环中留在路径(i,j)上的信息量，如果蚂蚁k没有经过路径(i,j)，则的值为零，表示为：

（3）

其中，Q为常数， 表示第k只蚂蚁在本次循环中所走过的路径的长度。

（3）交叉算子的设计

首先随机地在父体中选择两杂交点,再交换杂交段,其它位置根据保持父体中城市的相对次序来确定。例如,设两父体及杂交点的A1和A2, A1=(2 6 4 7 3 5 8 9 1), A2=(4 5 2 8 1 6 7 9 3)。交换杂交段于是仍有B1=(2 6 4 1 8 7 6 9 1),B2=(4 5 2 7 3 5 8 9 3)。在新的城市序列中有重复的数，将杂交段中对应次序排列,即: 7-8、3-1、5-6，依此对应关系替换杂交段中重复的城市数。将B1中(2 6 4)重复的6换为5，B2(9 3)中重复的3换为1.。杂交后的两个体为B1=(2 5 4 1 8 7 6 9 1),B2=(4 5 2 7 3 5 8 9 1)。本算法采用此方法交杂交。

3.仿真实验

对TSP问题仿真所用的数据库是TSPLIB典型51城市的数据。仿真平台如表1所示。

表1  仿真试验平台

设备名称

型号

CPU

Pentium(R)M 1.66 GH

内存

512M

操作系统

Microsoft Windows XP

仿真软件

MierosoftVisualC++6.0

3.1 遗传算法仿真

基本遗传算法仿真。对51城市路径优化路径优化。参数设置如下:种群:50,最大迭代数:5000,交叉概率:0.8,变异概率:0.2

遗传算法找到最优解的时间是95 s, ,路径长度497。

3.2 蚁群算法仿真

基本蚁群算法对51城市路径优化。其参数设置如下：ρ=1α=1，β=8，τ0=0.001Qu=100., m=51

基本蚁群算法找到最优解的时间是68 s, 路径长度465。

3.3遗传混合算法

遗传混合算法对51城市路径优化。其参数设置如下：种群:51,最大迭代数:5 000,交叉概率:0.8,变异概率:0.001;ρ=1α=1，β=8，τ0=0.001Qu=100，m=51；

遗传混合算法找到最优解的时间是50 s, 路径长度459。

遗传算法、基本蚁群算法、遗传混合算法对TSPLIB典型51城市的数据进行仿真,仿真结

果对比如表2所

算法名称

所用时间（s）

最优结果

遗传算法

95

497

基本蚁群算法

68

465

改进混合算法

50

456

4.结论

本文为了更好地解决物流领域中的旅行商问题，充分发挥遗传算法的全局搜索能力和蚁群算法的正反馈能力和协同能力，采用了遗传算法与蚁群算法混合算法进行求解，并且进行了模拟仿真。仿真结果表明，利用遗传与蚁群混合算法可以找到较好解的能力，大大提高计算效率，结果质量也较好。   

参考文献：

［1］小平,曹立明.遗传算法———理论、应用与软件实现[M].西安交通大学出版社,2002.

［2］[日]玄光男,程润伟.遗传算法与工程设计[M].科学出版社, 2000.

［3］胡小兵，黄席樾。蚁群优化算法及其应用[J]. 计算机仿真 2004，24（5）

篇（2）

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*算法作为主搜索方式，引入优先队列二叉堆作为数据存储结构，最后通过实验验证每项措施的改善效果。

篇（3）

中图分类号：F252.14 文献标识码：A

Abstract： The cigarette distribute route problem is a LS-VRP problem with includes the consideration of distance saving and the work balance between each car. This paper found the module with the object of work balance， car saving and distance saving. Then design the route cut based heuristic algorithm to solve the module and get a good effect in the example problem solving.

Key words： route planning； cigarette distribute； heuristic algorithm； multiple objects

在我国，一般以市级烟草配送中心为中心，直接配送到全市各地的上万个配送点。负责卷烟配送的车辆由烟草配送中心出发，依次到其负责的收货点进行配送，最终配送完成后车辆返回配送中心[1]。现有的卷烟配送车辆型号众多，载货量也有区别。卷烟配送路线的规划是一个LS-VRP（大规模车辆路径）问题，是一个NP问题。对于一般的LS-VRP问题有精确算法、亚启发式算法和启发式算法等。

众所周知，我国卷烟配送工作由来已久，因此各地烟草商业企业在发展中已经形成了自己的配货顺序，并根据配货顺序安排配送车辆。这种配货顺序有其存在的合理性，并且已经在运行之中，进行较大的改动有一定的风险。但是传统的车辆配送任务分配主要采取人工的方式进行，工作量大且优化程度较低。另外，在解决大规模VRP问题的方法中，一种思想先按照TSP问题利用算法生成一个全局的配送路线，之后对这个总的配送路线进行截断，来确定分配给每辆车的配送路线，从而生成卷烟配送VRP问题的配送方案。这种方法优化程度较高，而且可以保证较快的计算速度。因此基于大线路截断成小线路进行配送的方法有一定的实际价值。

而且除了总配送路程最短、费用最小、时间最短等一般VRP问题的约束之外，处于管理上的考虑，卷烟配送过程有其特有的特点，例如要求不同车辆工作时间比较均衡且小于上限、车辆之间的配送量均衡等。因此引入了一些原则进行配送任务划分来保证车辆工作强度的均衡。

本文研究的基于配送任务均衡的线路截断方法，属于一种亚启发式算法，主要实现的功能是在收货点配送排序确定的情况下，把这些收货点的配送任务分配给各配送货车。货车从配送中心出发，按照指定的顺序配送其负责的收货点，之后返回配送中心。在这个过程中要考虑配送路径最短、所用车辆最少、配送工作量均衡的要求。

1 模型建立

收货点配送任务序列为：

S=s，s，…，s，…，s

其中s，s，…，s表示n个收货点的收货量。而其角标表示该收货点配送的次序。s为第一个配送，s为第二个配送，依次类推，s为最后一个。每个收货点只能由一个车辆配送。

每个车辆包含标准载货量和标准服务客户数两个指标，这两个指标由车辆的型号和配送人员的工作时间确定。

配送车辆标准载货量为：

V=v，v，…，v，…，v

配送车辆标准服务客户数为：

C=c，c，…，c，…，c

目标函数为：

MinDis=∑d

MinN

MinPv=∑ρv-

MinPc=∑ρc-

式中Dis表示每个配送车辆的配送距离d之和，即总配送距离。N为使用的车辆总数。ρv、ρc分别表示第j辆车的装载量与标准载货量、服务客户数与标准服务客户数的比值，即装载率和服务率，用来衡量车辆的工作负荷程度。、表示了所有车辆的装载率和服务率。Pv与Pc计算了车辆实际装载率、服务率与平均值的差值之和，其值越大表示车辆的任务分配越不均衡。目标函数反映了实际卷烟配送中的实际要求。

2 模型求解

在实际的配送过程中，首先需要设定每辆车的装载率和服务率的上下限值ρv， ρv、ρc， ρc。即车辆的装载率不得高于其上限值，也不能低于其下限值，服务率亦然。这样可以保证车辆的使用率。如果车辆运力紧张的情况下可以将下限值提高，但会降低在配送距离优化中的调整余地。如果需主要考虑配送里程的节约可以适当扩大区间，从而可以在更宽的范围内进行配送任务的划分。

为了保证任务量的均衡和较短的配送距离，本文设计了基于线路截断的亚启发式算法进行配送任务划分。算法的流程如下：

Step1 对每辆车进行模拟装车，以车辆j为例，将待分配任务序列（第一次循环时即为初始S序列）中的收货点从前到后依次装入车辆j中，当车辆j的装载量与服务率之一达到其下限值时，当前最后一个装入的点即为其装载任务的下限点，假设该点为sl，之后继续装载，当车辆j的装载量与服务率之一达到上限值时，最后一个装入的点即为其装载任务的上限点，假设该点为s，则车辆j的可截断区间为s，s。即该车辆的当前配送任务可以是从配送序列的第一个点s开始到s，s中任何一点结束。计算所有车辆的可截断区间。

Step2 找到每个车辆可截断区间内相隔距离最长的一组相邻点s，s，两点之间距离记录为Sav，则车辆的模拟配送任务为s…s，

s是剩余配送任务序列的起始点，即新的s。之后比较所有车辆当前模拟装车的使用效率ρ=ρv+ρc，选择使用效率最高的车型作为当前循环的所选车型，其配送任务为其对应的s…s，将已配送的点以及该车辆从任务序列和备选车型中删除。

Step3 如果最后一个车的使用效率低于平均使用效率的20%，则可以通过调高每辆车的装载率和服务率下限值之后返回Step1，直到将最后一辆车的配送任务分配至其他车辆为止。如果使用效率高于平均使用效率的20%低于85%，则通过调低每辆车的装载率和服务效率下限值返回Step1，可以减少前面车辆的任务量，提升最后一辆车使用效率。如果最后一辆车的使用效率高于平均使用效率的85%则任务分配结束。

若循环20次之后仍无法跳出循环，则输出当前解。

3 仿真实验与数据分析

下面通过Matlab软件编程进行仿真实验。

配送任务序列为某地市实际卷烟配送任务，共712个点。

输入数据：

配送中心与收货点、各收货点之间的距离矩阵，各收货点的收货量，车辆矩阵：

首次循环的装车方案为：

当前总配送里程为1 201km。最后一辆车的使用效率1.96为平均使用效率1.93的1.014%，达到终止条件，配送任务分配完毕。整个算法运行时间为1.87s。

篇（4）

【Abstract】Intelligent transportation has a very wide range of applications in modern industry. Inproving route planning algorithm is one of the important ways to increase the efficiency of intelligent transportation. Based on Intelligent Transportation Project in China Robocup competition，an adaptive route planning algorithm is designed. The proposed algorithm can be applied to the intelligent classification of garbage and the automation of logistics. Compare with the exist algorithms， it can change the route and destination before the start of transportation.

【Key words】Route Planning； Adaptive； Intelligent Transportation

0 引言

智能搬运机器人主要指按设定的路线，或者使用视觉、磁线、激光导航的自动行驶的机器人。智能搬运机器人是一种自动导向车（Automated Guided Vehicle，简称AGV）[1]， 也称自动导向搬运车、自动引导搬运车。随着AGV的性能逐渐提高，智能搬运机器人被广泛用于工业、农业、医学、国防等领域[2]。路径规划是提高智能搬运机器人性能的一个重要方向[3]。

路径规划指的是根据既定的标准，如何规划一条从起始点到终点的最优路径[4]。根据环境信息的知情情况，路线规划又分为局部路径规划和全局路径规划[5-6]。本文讨论的路线规划以中国机器人大赛中的智能搬运项目为蓝本，利用颜色识别技术设计了一个自适应的路径规划算法，它可以应用于工业自动化过程中自动化物流、垃圾智能分类等领域。

1 可适应的路径规划算法

在描述本文提出的可适应的路径规划算法之前，首先介绍机器人大赛智能搬运项目的比赛规则，在1.2节将介绍根据算法设计的机器人。

1.1 路径规划规则

图1所示为中国机器人大赛智能搬运项目中的使用的场地图。图中黑字A、B、C、D、E、F、G为待搬运的色块所在地，其中A、B、C、D、E可随机放置3-5个色块，F和G点每点可随机放置不超过5个色块。O点所在为起点及终点，图中a、b、c、d、e为目标所在地，机器人要识别待搬运色块的颜色，并搬运到相应的颜色目标所在地，机器人的路径除点a、b、c、d、e外只能为图中黑色的线条。根据要求，设计的机器人必须有颜色识别、路径识别存储等功能。色块共用5种颜色：绿色、白色、红色、黑色、蓝色。本文假设图中目标点a、b、c、d、e 的颜色在搬运前是可以随机调整的，但搬运过程中是固定的，这种假设与生活中的情形比较相符。现有比赛中用到的算法都是固定了目标点的颜色、每个夹角的度数和每段路径的长度，应用性低，因此本文提出自适应的路径规划算法。

1.2 智能搬运机器人设计

本文设计的智能搬运机器人包括如下几个模块：（1）路径检测；（2）转向控制；（3）电机驱动；（4）车速检测；（5）电源管理；（6）物体检测（7）物体抓取；（8）路径规划。主控制器是51单片机，它负责接收赛道数据、赛车速度等反馈信息，并对这些信息进行恰当的处理，形成合适的控制量来对舵机与驱动电机进行控制，采用红外传感器控制小车沿着预设的轨道黑线及时调整车身姿态，使之准确、快速地跑完全程，采用四驱差速来进行原地转向与前进，使用稳压芯片7805稳定电压，用颜色传感器准确识别要抓取物块的颜色，超声波传感器定位需抓取物块，测算出距离出来以便接下来准确的搬运至目的地。实现这些功能共包含电机模块，超声波模块，颜色传感器模块，红外模块，伺服电机抓手模块，电源稳压模块。智能车的设计主要体现在电路板和机械结构上面，车的前部携带着超声波探头，与颜色传感器，用于识别物体，在颜色传感器与超声波探头下面是红外模块用来循迹，来到车身是双层的结构，在上层前端固定着有三个伺服电机控制的抓手，上层的中间是红外驱动模块，车的尾部则是放置电池及电源模块，由一根铜柱支撑着51的最小系统外加电机驱动的模块。而车的下层则是装载着四个电机驱动四个轮子。

本文设计的智能搬运机器人在行驶过程中通过不断地向地面发射红外光来进行路径检测，当红外光可遇到白色地面时发生漫发射，反射光被装在小车上的接收管接收；如果遇到黑线则红外光被吸收，则小车上的接收管接收不到信号，再通过比较器来采集高低电平，从而实现信号的检测，最终形成路径。

1.3 自适应的路径规划算法

所谓的自适应指的是没有完全掌握整个搬运路径，包括目标点a、b、c、d、e的颜色、两点间距离，弧线间角度等，这样，机器人在搬运前必须遍历路径并记录下来。a、b、c、d、e的颜色可在搬运前任意更改，在搬运当中目标颜色不变，每次搬运前机器人都需要自己检测目标点的眼神。为方便描述，假设E和F并无任何块。算法令1代表绿色，2代表白色，3代表红色，4代表黑色，5代表蓝色，用数字来记录颜色，这样如果算法涉及加权，例如aA是一段斜坡，则预算aA可能更花费时间。算法首先要判断障碍色块及目标点a、b、c、d、e的颜色。

该算法如下：

如果点E、F也存在色块，算法类似。算法可以加入权值。

2 结论

本文针对中国机器人大赛智能搬运项目的路径规划算法进行改进，提出自适应的智能路径规划算法，同时开发上位机软件和搬运部件接口。经实验证明，该算法有效可靠，有较高的效率。

【参考文献】

[1]陈书光.机器人路径规划算法探讨[J].商，2012（15）.

[2]宁志刚.一种高效的机器人路径规划算法[J].科技致富向导，2011（18）.

[3]周嵘，张志翔，翟晓晖，闵慧芹，孔庆杰.机器人室内路径规划算法的实用性研究[J].机械与电子，2016（8）.

篇（5）

一、前言

随着信息技术在现代企业中的广泛应用和高速发展，企业信息化程度大幅提高，企业的许多革命性的创新成果得益于此。在激烈的市场竞争中，仓储配送和信息技术的有机结合为企业带来了新的机遇，建设智慧仓储网络的理念应运而生。而配送作为衔接各个物流节点的关键流程，使仓储网络形成为一个系统性的整体，保证了物资的正常供应。优化配送车辆路径能提高配送效率，降低配送成本，并提升配送准确性。

物资公司作为公司的专业分公司，负责管理在上海区域所有工程及运维检修物资的供应。工程项目物资的供应分为供应商直送现场和仓库供应现场两种类型。其中，供应商直送现场为一次配送，关键点在于供应计划与供应商的有效衔接与调度协同；而利用公司仓储配送网络，通过中心库向各周转库配送以供应现场物资需求的过程为二次配送。合理二次配送车辆路径规划与实施，能提高后续工程建设、运维检修及应急抢修的需求响应速度，增强物资供应的计划性和准确性，可有效提升物资供应管理水平。

二、车辆路径问题定义

车辆路径问题是指存在几个物资需求方，各有一定数量的物资需求，由一个配送中心提供物资，并安排一个车队配送物资。为此需要规划合理的行车路线以使他们的物资需求得到满足，且能在一定的约束条件下，达到路程最短或耗时最少的目标。

公司有十二个周转库，当周转库内某种物资数量低于安全库存时，由中心库提供物资进行补库。由于工程项目对响应速度要求较高，当需要对多个周转库进行补库时，必须综合周转库的地理位置、物资需求量、车辆的运载量、配送次数等，设计出合理的车辆配送路径。

三、配送路径规划意义

1.避免交叉运输

中心库车辆配送路径规划，将原先零散配送的物资进行整合后，以合理的配送路径集中配送，避免了交叉运输的情况，缩短了总配送距离，降低了运输成本。

2.推进节能环保

车辆配送路径优化在满足各周转库的物资需求的前提下，以缩短配送车辆的总行驶距离为目标，能提高能源利用效率，推动公司更积极地承担节能环保的社会责任。

四、配送路径规划过程

1.组织结构

物资公司仓储配送网络包括了集中的物资调配中心、一个中心库以及十二个周转库。

（1）物资调配中心作为信息汇集、指令的中心，实时获取中心库和周转库内库存物资数量、物资需求数量等信息，并根据这些信息判断是否需要补库。

（2）如果周转库需要补库，物资调配中心发送补库指令给中心库。

（3）中心库综合需补库的周转库数量、地理位置及物资需求量等，规划所需的车辆数、配送路径等信息，将物资配送至周转库。

2.车辆路径问题描述

对于物资仓储配送网络，配送车辆路径问题可以描述为，十二个周转库的位置固定且各有一定的需求量，中心库用多辆载重量固定的汽车进行配送，要求合理安排汽车路线以使总距离最短，并能满足以下条件：

（1）每个周转库的物资需求到能满足；

（2）每个周转库的物资必须由尽可能少的车辆配送，例如在周转库的需求能由一辆汽车满足的情况下，必须只由一辆汽车配送；

（3）每条配送路径上各周转库的需求量总和不能超过汽车载重量。

3.车辆路径规划

将中心库及十二个周转库构成的13个的节点两两连线，共有C132=78种组合，即这13个仓库中任意两个仓库间的路径共计78条。利用Google、百度等电子地图软件，将两个仓库分别作为起点和终点，搜索出这78条路线以及之间的行驶距离。以字母O表示中心库，字母A至L表示十二个周转库。当有多个周转库需要补库时，配送路径确定步骤如下：

（1）确定各个周转库需要的物资数量；

（2）与汽车载重量进行比较，确定需要的汽车数量；

（3）根据各周转库的需求量，运用里程节约法，就近的仓库由同一汽车配送，同时避免交叉运输的情况，形成配送路径；

（4）根据实时路况，对配送路径进行一定调整，避免高峰期路段拥堵导致无法及时配送。

由于从实际情况考虑，为减少最后配送到的几个仓库的等待时间，在12个周转库中按地理位置分为两块区域，在郊环附近的7个仓库为一个配送区域，郊环线以内的4个仓库和崇明区域为一个配送区域。

以郊环线附近7个仓库的配送为例，如下图所示，每汽车载重量为5吨，A至G共7个周转库需中心库O配送物资，直线上的数字为距离，括号内的为对应的周转库的物资需求量。

4.路径信息

配送路径规划完毕后，将行车路线信息给对应的汽车司机。车辆出发后，利用短信在途跟踪获取车辆实时的位置信息，并将实时路况信息传递给司机，减少因交通拥堵造成的配送延误。

五、结语

本文综合各周转库地理位置、需求数量、汽车运载量等方面，运用里程节约法规划出车辆配送路径。车辆配送路径规划将对原先粗放式的配送方式进行优化，积极配合政府及上级公司对节能环保提出的要求，在满足各仓库需求的前提下缩短总配送距离，提高物资配送效率，降低配送成本。物资公司后续将逐步加强自动化和信息化建设，推进仓储网络各类信息的实时共享、获取、分析和处理，运用先进信息技术提高配送准确性和效率效益，确保智慧仓储网络的配送脉络高效稳定，构建一个现代化、智慧化、特色化的仓储配送体系。

参考文献：

篇（6）

一、引言

危险天气区域下，导致飞行事故症候的事件比较频繁。在飞机巡航期间，由于受大范围天气系统的影响，雷雨，冰雹，龙卷风、闪电等，如果飞机在航路上遇到大面积雷雨区时，一般就会飞机返航、备降。而通常雷暴是在云层中，有的时候即使不下雨，但是云层中依然会有雷暴。雷暴区域附近产生的下击暴流和风切变，会直接造成起降飞机失控。风切变即是在短距离内风向、风速发生明显突变的状况。强烈的风切变瞬间可以使飞机过早地或者被迫复飞。在一定程度下就可以导致飞机失速和难以操纵的危险，造成飞行事故。机组由于对雷暴的认识不清，签派员在遇到雷雨天气条件下航班的放行时，往往主对天气的了解和掌握也主要集中在机场终端区雷雨天气的研究。航路雷雨天气下的放行成为一个难点，对其发展趋势不明白，没有事先做好充分的绕飞计划，以及绕飞油量没有带够等因素而导致返航备降。在航路上飞机飞行高度都比较的高，而空域范围较广，并且受到的地形限制非常小，解决的办法可以让飞机进行绕飞或改变在云上飞行飞行高度等措施来避开雷暴等危险天气的影响。本文将探讨的就是危险天气区域下的航班改航路径规划。

二、人工势场法路径规划

人工势场模型人工势场法由Khatib 1986年提出的一种虚拟力法，起初只是为了解决机械手臂在移动抓取物体的时候，能够不碰到工作台。他的基本思想是把机器人在周围环境中的运动，设计成一种抽象的人造引力场中的运动，目标点对移动机器人产生“引力”，障碍物对移动机器人产生“斥力”，最后通过求合力来控制移动机器人的运动。后来该方法在移动机器人上应用也有很好的效果，能产生出非常平滑的运行轨迹。人工势场法的基本思想是在环境中建立目标位置引力场和受限区周围斥力场共同作用的人工势场，搜索势函数的下降方向来寻找无碰撞路径。引力和斥力的合力作为移动物体加速力来控制移动物体的运动方向和计算移动物体的位置。该方法结构简单，在实时避障和平滑控制轨迹方面得到了广泛的运用。在采用传统人工势场路径规划模型进行航空器改航路径规划时，在狭窄区域容易发生振荡现象，导致航空器左右来回运动，造成了规划的不稳定。人工鱼群算法人工鱼群算法是一种群智能多点并行搜索优化算法。该算法的主要特点是不需要了解问题的特殊信息，只需要对问题进行优劣的比较，有着较快的收敛速度，具有克服局部极值获得全局极值的能力。王飞等将该算法应用机着落排序问题和地面等待策略问题，取得了较好的应用效果。通过构造单个人工鱼来控制人工势场函数的参数，调用改进人工势场模型进行改航路径规划，生成多条改航路径，利用适应度函数对生成的改航路径进行评估，通过算法的觅食、聚群、追尾等行为的选择，选出适应度好的人工鱼参与下一组鱼群的进一步计算，通过随机行为可以在新的空间进行新一轮的搜索，最终生成最优的改航路径。

如事例1、某航班执行成都—西宁航线，由于西宁机场雷雨天气备降兰州。飞机在兰州落地之后，西宁天气好转，雷暴向东移出本场，往兰州机场方向移动，正好在兰州到西宁的航路上，且范围较广。考虑到兰州到西宁的航线距离较近，不到150公里，且该航路标高较高，地形较复杂，飞机起飞后绕飞困难等因素，通过对天气演变趋势的详细研究，制定详细的绕飞计划和带够足够的绕飞油量后，再次放行飞往西宁。

事例2、某航班执行成都—张家界航线，在飞机进入长沙管制区后，由于航路上有大面积雷暴区，使得飞机绕飞比较困难，而且机载油量有限，备庆。最终由于该天气系统往张家界机场方向发展，时间较长，且考虑到该机场是特殊机场，取消该航班。

事例3飞行受限区域昆明到贵阳航线所经航路点为： 昆明（ KMG） - 过马河（SL）- P72- 贵阳（KWE）； 通过 Mercator投影建立经纬度与X - Y 轴的投影关系，则KMG、SL、P72、和 KWE在该平面直角坐标系中坐标分别为 （ - 124. 8 220，64. 2 764）、（ - 118. 6 788，68. 3 736）、（ - 103. 9 652，71. 6 366） 和（ - 82. 2 684，76. 8 524）。根据天气预报生成飞行受限区域，图 1 中阴影部分为雷暴云团 A、B、C。假设雷暴云团 A向东北方向以 40 km /h的速度匀速漂移，云团的形状、面积和强度保持不变；云团 B绕云团几何中心旋转，云团 C处于扩张阶段。

图 1 飞行受限区域

优化后的改航路径利用人工势场- 人工鱼群算法，得到优化的改航路径。

如图 2、图 3所示。

图 2 优化的改航路径

图 3 路径规划中的航线角度

改航路径的修正通过对转弯角度较大的改航路径点的判断，来确定分段点，从而将初始的改航路径分成 7段进行线性拟合，并计算出拟合后 7段航线的交点，将交点顺次连接，生成拟合的改航路径。

图 4 分段拟合后生成的改航路径

如图 4中实线所示。由于在第 6航段不满足与受限区的最小距离的约束，所以需要进一步修正。具体如下： 将图 4中的航段 1、2、3，截弯取直，合并为如图 5中的第 1航段，原航段 4改为第 2航段，将原航段 5、6合并为第 3航段，原航段 7变为第 4航段，如图 5所示。经验证修正后的改航路径，满足约束条件，这样就得到最终的改航路径。

参考文献

[1] 谢春生，李雄. 危险天气影响航路飞行区域的划设及评估[J]. 中国安全科学学报. 2010（10）

[2] 张静，徐肖豪，王飞. 天气影响的机场容量概率分布[J]. 南京航空航天大学学报. 2011（01）

篇（7）

加载规划求解功能

在Excel2003版本中，通过点击菜单“工具宏加载宏”，加载规划求解加载项，便可加载该宏。在Excel2007版本中，通过点击Office按钮，点击“Excel选项加载项转到Excel加载项”，然后加载规划求解加载项，便可以加载规划求解的宏。在Excel2010版本中，通过点击“文件”选项卡打开“Excel选项”对话框，单击左侧“加载项”标签，在右侧单击“转到”按钮，打开“加载宏”对话框，勾选“规划求解加载项”复选框，单击“确定”按钮，即可在工具栏的“数据”选项卡中出现“分析”选项组，菜单上面就有了“规划求解”按钮。

案例

王老师从学校A到学校I参加会议，途中需要经过一些学校，学校之间的距离和线路已在图1中标明，请帮王老师规划一下，在不影响去学校I最短距离的情况下，顺便探访其他学校，请将路线描述出来。

1.Dijkstra算法描述及C语言函数实现

为了求出最短路径，Dijkstra就提出了以最短路径长度递增，逐次生成最短路径的算法。即如果存在一条从i到j的最短路径（Vi...Vk，Vj），Vk是Vj前面的一个顶点，那么（Vi...Vk）也必定是从i到k的最短路径。例如，对于源顶点V0，首先选择其直接相邻的顶点中长度最短的顶点Vi，那么通过已知可得从V0到Vj顶点的最短距离dist[j]=min{dist[j]，dist[i]+matrix[i][j]}。根据这种思路，假设存在G=，源顶点为V0，U={V0}，dist[i]记录V0到i的最短距离，path[i]记录从V0到i路径上的i前面的一个顶点。那么可从V-U中选择使dist[i]值最小的顶点i，将i加入到U中；更新与i直接相邻顶点的dist值（dist[j]=min{dist[j]，dist[i]+matrix[i][j]}）；直到U=V，停止。

/*Dijkstra算法代码C语言实现：*/

void DijkstraPath（MGraph g，int *dist，int *path，int v0） //v0表示源顶点

{

int i，j，k；

bool *visited=（bool *）malloc（sizeof（bool）*g.n）；

for（i=0；i

{

if（g.matrix[v0][i]>0&&i！=v0）

{

dist[i]=g.matrix[v0][i]；

path[i]=v0； //path记录最短路径上从v0到i的前一个顶点

}

else

{

dist[i]=INT_MAX； //若i不与v0直接相邻，则权值置为无穷大

path[i]=-1；

}

visited[i]=false；

path[v0]=v0；

dist[v0]=0；

}

visited[v0]=true；

for（i=1；i

{

int min=INT_MAX；

int u；

for（j=0；j

{

if（visited[j]==false&&dist[j]

{

min=dist[j]；

u=j；

}

}

visited[u]=true；

for（k=0；k

{

if（visited[k]==false&&g.matrix[u][k]>0&&min+g.matrix[u][k]

{

dist[k]=min+g.matrix[u][k]；

path[k]=u；

}

}

}

}

2.Excel“规划求解”功能实现最短路径

（1）可将学校A到学校I的距离与逻辑关系通过以下表表示。

（2）新建工作簿，将上表各节点的逻辑关系用下Excel工作表表示（如图2）。

“节点关系”这一栏仅用于描述各节点之间的关系，仅以B点来说（+代表此点出发，-代表以此点进），进入方向为A，出发为C、E、F。所以B=-AB+BC+BE+BF，以此类推。真正反映数量关系的是F栏的“数量（逻辑关系）”，同样以B节点为例，F19中公式关系是=-D18+D21+D22+D23，通过D栏各线段是否在最短路径（o表示“不在”，1表示“在”）上，迭代产生。最短路径设置在G31，使用公式“=SUMPRODUCT（C18：C31，D18：D31）”，通过对D栏、F栏进行规划求解来设置相应的约束条件以生成最短距离。

3.规划求解

点击“数据规划求解”，目标单元格G31为最短路径，通过函数SUMPRODUCT（C18：C31，D18：D31）进行求和。因为选取的是最短路径，所以在“最小值”选项打标记。从下页图3可看出规划求解通过调整所指定的可更改的单元格（可变单元格）D18：D31中的值，可以从目标单元格公式中求得所需的结果。约束条件是在D18：D31中只能是0、1的两种，结束条件是节点条件的取值与目标值对应。

由于规划求解过程是一个迭代过程，有的值可能达到1E-9左右，约为0，将“是否为最短路径”和“数量（逻辑关系）”设置成数值格式，并取消“小数位”。

从上例创建模型的过程中，我们看到可以对规划求解模型中的可变单元格数值应用约束条件（约束条件：“规划求解”中设置的限制条件），约束条件可以引用其他影响目标单元格公式的单元格的值。

Excel不仅是一个小型的数据库软件，更是一个操作极为方便的工作数据表，几乎能胜任数据处理的各种要求，功能强大、使用灵活。让我们共同使用好Excel，提高工作效率。

资讯

便携办公利器——华硕PU500商务笔记本

全能轻薄的商务本

华硕PU500作为主流15.6英寸商务本，重量为1.96Kg，厚度只有22mm，拥有深色发丝拉纹设计。屏幕采用防眩光雾面屏。电源适配器体积比传统适配器小20%，加入电源插接报警，当适配器插头未完全插入时系统会自动弹出窗口报警，保护电脑安全。

动力强劲的商务本

华硕PU500采用i5-3317U处理器，配备4GB DDR3 1600MHz内存，Intel? HD Graphics 4000显示芯片。PU500采用“SSD+HDD”的混合硬盘模式（选配），既保持了SSD快速读取的优势，又具有传统机械硬盘的超高性价比。

接口配备齐全包括两个USB2.0接口、一个支持关机充电的USB3.0接口，同时还配备投影展示常用的VGA视频输出接口，HDMI等接口。

最为安全的商务本

篇（8）

中图分类号：TP39文献标识码A文章编号1006-0278（2013）06-172-01

一、引言

随着虚拟现实技术的日益成熟，只有景色、建筑物等一般视景信息的虚拟场景已不能满足人们的视觉需求，迫切需求一个有生命的对象引入到虚拟场景中，增加浏览者的沉浸感。虚拟场景中虚拟人的路径规划是虚拟现实研究中的一项关键技术。目前，研究者们已经把研究的重心放在如何为虚拟人规划出一条行走的最优路径，使虚拟人的路径导航更具有真实感和可信度。

由于虚拟环境中的模型多由三角面网格组成，通过使用基于空间多层次划分的八叉树方法，充分发挥了其空间划分的优势，加快了场景的渲染速度，减少了确定对象的处理时间以及存储空间①。

文章采用八叉树和A*算法相结合的方法，对路径进行规划，并对A*算法做了改进，以适应八叉树的存储结构。

二、密集型区域八叉树划分算法

八叉树是由四叉树推广到三维空间而形成的一种三维栅格数据结构，它作为一种场景组织方法，广泛应用于虚拟现实系统，可显著减少对场景中多边形进行排序的时间。

由于传统八叉树对空间的划分是均匀的，导致了最终生成一个结构不平衡的八叉树，从而增加整个八叉树的存储空间以及各结点的遍历时间。文章采用了对传统八叉树算法进行改进，采用基于密集型区域八叉树划分方法。密集型区域八叉树的网格划分算法是对每一子空间重新建立最小包围盒，这样避免了在建立顶点树时，由于该部分顶点在空间上分布不均匀而导致树的深度的增加，进而减少了存储空间，加快了网格模型数据的读取速度。另外，由于建立了顶点的最小包围盒，在误差较小时，只有空间距离比较近的顶点才会聚合在一起；而相距较远的顶点只有在深层次简化时才会聚合，这些特点在一定程度上保证了简化时网格模型的逼真度。

密集型区域八叉树划分方法的算法描述如下：

步骤1使用OBB包围盒方法建立模型的最小包围盒。

步骤2以包围盒的X轴、Y轴、Z轴方向的中分面作为分割基准，将包围盒平均划分为八个子包围盒。

步骤3如果每个子空间内存在物体的属性不相同或未达到规定的限差，则重新从步骤1开始进行划分。否则，划分结束，并对划分后的每一个结点记录下结点编号、划分标志、结点在顶点树中的深度以及它所含的景物面片表的入口指针。

三、A*算法

A*算法是建立在典型的Dijkstra算法上的，是由Hart，Nilsson，Raphael等人首先提出的。该算法的创新之处在于选择下一个被检查的节点时引入了已知的全局信息，对当前节点距终点的距离做出估计，作为评价该节点处于最优路线上的可能性的量度，这样就可以首先搜索可能性较大的节点，从而提高了搜索过程的效率。

下面是对A*算法的介绍，我们首先来介绍一下启发式搜索中的估计函数。因为在启发式搜索中，对位置的估价是十分重要的。估价函数的表示如下：

其中是节点的估价函数，是已知的，指在状态空间中从初始节点到节点的实际代价；是从结点到目标节点最佳路径的估计代价，它体现了搜索的启发信息，启发信息决定着算法的启发能力。启发信息越多，估价函数就越好，即约束条件越多，则排除的节点就越多，说明这个算法越好。这种做法存在一个平衡的问题，也会使算法的准确性下降。具体的说，代表了搜索的广度优先趋势，当时，可以省略，这样就提高了搜索效率。

A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：

这里，是估价函数，是起点到终点的最短路径值，是到目标的最短路经启发值。由于这个其实是无法预先知道的，所以我们用前面的估价函数做近似。代替，但需要满足（在大多数情况下都满足时，可以不用考虑）。代替，并满足。可以证明应用这样的估价函数是可以找到最短路径的。

四、基于密集型区域八叉树的A*算法改进

由于使用八叉树存储结构存储的环境地图扩展步长不一致，采用传统的A*算法效率较低，因此对A*算法做了改进，以适应八叉树结构的搜索。改进的办法是从叶节点开始搜索并为Open表设置两个优先队列，命名为队列1和队列2（队列1中存放的节点总是高于队列2），在两个队列中分别存放相邻层次的全部节点，层次越高的优先级越高。通过这种分层次的搜索，也大大缩小了搜索的空间并缩短了搜索时间，这样一来大大提高了搜索效率。

五、结束语

篇（9）

一、本文就常见的几种常见的路径规划算法及应用进行简单的探讨如下：

（一）遗传算法概念

遗传算法是根据达尔文的进化论，模拟自然选择的一种智能算法，“适者生存”是它的核心机制。遗传算法是从代表问题可能潜在解集的一个种群开始的。基于随机早期人口，根据的原则，优胜劣汰，适者生存，世代演化产生更好的人口大概。在每一代，根据问题域的个体适应度大小来选择个人，然后选定的个人在自然遗传学，遗传算子组合交叉和变异，产生代表性的解集的人口 。通过这些步骤，后生代种群比前代对于环境具有更好的适应性。人口最优个体解码后可作为近似最优解。

（二）遗传算法的特点

作为一种智能算法，遗传算法具有如下特点：①遗传算法在寻优过程中，只把适应度函数的值作为寻优判据。②遗传算法是由一个问题集合（种群）开始的，而不是从一个个体开始的。故而遗传算法的搜索面积很大，适合全局寻优。③遗传算法根据概率性的变换规则进行个体的优胜劣汰并推动种群的进化。④遗传算法具有隐含的并行性。⑤遗传算法具有自组织、自适应以及内在的学习性，同时遗传算法具有很强的容错能力。⑥遗传算法的基本思想简单。对于复杂的和非线性的问题具有良好的适应性。

（三）遗传算法的应用

遗传算法提供了一个整体框架地址复杂系统问题，它不依赖于俞特定领域的问题，问题的类型、 已是强的鲁棒性，所以广泛应用余许多科学： 功能优化遗传算法的经典应用，是遗传算法的性能评价的常见的例子，许多人建设的各种复杂的表格功能测试： 连续函数和离散函数，凸、 凹函数、 低维功能和高尺寸功能、 单式功能和更多峰值函数。一些非线性、 多模型、 多目标函数优化问题和其他优化方法很难解决，GA 你可以更好的结果。增加问题的规模，搜索空间的组合优化问题，将会迅速增加，有时的当前枚举方法和计算很难找到最佳的解决方案。实践证明，遗传算法、 组合优化问题的粒子非常有效。例如，已成功应用遗传算法解决旅行商问题、 背包问题、 装箱问题、 图形划分问题。此外，遗传算法的生产调度、 自动控制、 机器人技术、 图像处理和机器学习，人工生命，遗传编码，已获得广泛的应用。

二、蚁群算法及其应用

（一）蚁群算法概念

蚁群算法又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法。

（二）蚁群算法的特点

①蚁群算法是一种自组织算法。在早期的算法，单一的人工蚂蚁障碍找到求解算法，久而久之，通过信息作用的激素，人工蚂蚁进化将找到一些解决办法更接近最优的解决方案，它是无序到有序的过程。

②蚁群算法的并行算法是一种基本的。每个蚁群搜索进程独立的对方，只能通过信息素通讯。因此，蚁群算法可以看作是一种分布式的多智能体系统，它在问题空间搜索算法开始是一个独立的解决方案，不仅提高了可靠性，这使得该算法具有强的全局搜索能力。

③蚁群算法是一种积极的反馈的算法。从蚂蚁觅食中不难看到蚂蚁已设法找到最短路径的信息的过程取决于直接上的最短路径的积累，以及信息素的积累是一个积极的反馈过程。这种正反馈的过程进行初步的差距有不断扩大，并导致系统的最优解的方向发展。

④蚁群算法具有较强的鲁棒性。比较与其他算法、 蚁群算法、 初始对齐要求不高，外务大臣蚁群算法用于路由和搜索过程的初步结果不需要手动调整。第二，设立简单、 便于应用的蚁群算法求解组合优化问题的蚁群算法参数的殖民地，数目。

（三）蚁群算法应用

蚁群算法应用包括：二次分配问题、车间任务调度问题、车辆路线问题、机构同构判定问题、学习模糊规则问题、旅行社新旅游线路与旅行产品的制作等领域。

三、神经网络算法

（一）神经网络的概念

人工神经网络也被称为神经网络连接模式，它是一种动物模型，神经网络的行为特征，分布式并行处理算法的数学模型。网络依赖于复杂的系统，通过调整内部之间的联系，大量节点，以实现节能的目的，信息处理。

特征的神经网络模型的人工神经网络的主要网络连接拓扑，神经元的特点，学习规则。目前，近40种神经网络模型，其中有一个BP网络，传感器网络，自组织映射，神经，波尔兹曼机，自适应共振理论。系统的稳定性与联想记忆功能密切相关。

神经网络的应用

篇（10）

近年来电力系统变革迅速，随着环境保护意识的增强，电网空间规划需要解决新的挑战，这些新挑战主要包含如下几点：决策分散性使得电网规划协调难度增加；光伏、风电等分布式能源的接入使得电网规划出现了越来越多的不确定性；电网的规划、电网建设模型以及求解受到环境等方面的变换影响很大。

1 传统算法及原理

（1）运用遗传计算方法II、经络和round模拟技术，考虑风电接入等效应。（2）采取基于混合整数的多种线性规划方法对目前市场下长期多目标的电网规划问题进行解决。（3）从新定义碳的排放以及预测的模型，根据动态碳排放量建立电网规划的模型。（4）制定环境友好型的电网规划，建立双重指标体系与相关评估模型，从而对局势进行协调与求解。（5）建立恶意攻击或撞击的模拟模型，电网的扩展方式以风险大小为依据。同时，考虑各方面的成本因素，将电网规划、线路路径优化等方法与原有方法进行相互比较，可以获得一种新型电网规划方法。

以上方式仍然存在弊端：拘束条件“维数灾”，方法的提出仅仅可以解决小范围内电网在空间规划的问题；忽略了电网损坏造成的损失；变电站位置的选择没有考虑在内。根据存在的弊端，本文建立了新的模型。传统的分析方法是分析上层规划及排列形式，但是下层要解决的关键在于线路路径的优化方面。此模型提出的遗传算法以及运用的动态规划法在相互结合的情况下，可以有多种优化方法。遗传算法具有比较广的适应性以及比较强的鲁棒性，可以和其它算法相互结合，从而为电网规划问题提供合适的算法。采用动态规划法对路径优化问题进行求解，可以充分利用其速度快和精确度高的计算特点。当两种方法结合，可以将其最大计算优势发挥出来，从而实现空间电网规划求解质量与效率的有效提高。

2 空间电网规划采用的“位置图像栅格化表示”

通过应用文献，能够把带有环境的信息地图进行划分为NR×NC 的栅格图表，其中根据排列组合知Ci，j 含义为第i 行的第j 列的数字。假定其中有一栅格，在N个栅格当中，可以采取神经网络方法或者模式识别法来对栅格线路路径的相关耗资成本进行计算，同时可以根据实际情况进行更正完善。

路径通过一个栅格，能够通过往邻近栅格方向移动，移动栅格数量为8，标注栅格用来表示八个栅格的移动方向，两个栅格间距为

。它们分别代表水平间距以及高差。

研究地图格栅化模型，根据其相似性可以将其引用到电网建设上来，进而通过格栅的排列组合运算来计算电站综合成本，计算出新建变电站的综合成本。格栅化模型可以作为核算成本的一个重要模型。

3 新模型理论基础“空间的电网规划方式”

3.1 空间电网上层问题分析

首要问题是为新模型制定目标结果函数，由于空间电网规划属于上层问题，也就是传统电网规划问题，为的是确立即将进行建设的候选线路以及变电站位置。因此首先需要满足电网对电荷载的承载，其次考虑运营和投资建设成本最优化。上层问题解决目标函数，根据逻辑运算关系可以得到：

其中：e年均电价格；Tmax 损耗的最大荷载的时长以小时为单位；t 为年度index；NT 投资年回收限制； 为年收益率；Ploss 为有功网损；Nw 为新建变电站数目；w 为新建变电站索引；（iw，jw）表示变电站建设在Ciw， jw上；F2 为线路投资成本，由下层问题得到。

3.2 满足条件

（1）功率平衡原理公式

其中：n 、m 是节点index；Pn 和Qn 分别是节点n 的有功W和无功W注入；Gnm 和Bnm 分别是节点的导纳阵中的电导以及电纳；Wnm 是节点角度差。

（2）潮流等式（线路）

式中：l 为支路index；Pl、Ql 和Sl 分别为支路l 上的有功W、无功W和视在W；UlF和UlT分别为支路l 首末节点电压；Rl 和Xl 分别为支路l 的电阻和电抗；Gl 和Bl 分别为支路l 的对地电导和电纳；lFlT为支路l 首末节点之间的相角差。

（3）节点电压约束

式中：NB 为候选线路数目，候选线路的索引范围为1lNB；NS 为已有支路数目，已有支路索引范围为NB

3.3 空间电网规划下层问题分析

确定最终计算下次函数式为首要问题。对下层问题进行解决，就是要对线路路径优化进行解决，最终是为了得到最小化每条线路耗费的成本，如下方程式所列。

l {（i， j，d）如果线路l在Ci， j上选择方向d}

其中：

l 为线路l 选中栅格及其上方向的集合；Di，j，d为线路在栅格Ci，j 方向d 上的长度。

3.4 限定条件

（1）路径参数公式

其中：Rl，0 和Xl，0 分别代表线路l 单位长度线路的电阻以及电抗值；Gl，0 和Bl，0 分别代表线路l 中单位长度对地电导和电纳值；sl 为线路l 的长度。

（2）栅格上投建线路条数约束

式中：zl，i，j 表示线路l 是不是经过Ci，j，1 表示是经过，0表示不是经过；Zi，j 为Ci，j 可以投建的线路条数的最多数。上下层的问题是通过限制（4）、（5）、（10）和（11）条件进行结合的，它代表的意思即上层问题判别候选路径能否运营。

凭借限定条件可以确立电站的位置，也就是说通过它可以判定线段的端点；候选线路与相关线路端点的投建主要由上层决定，而下层的解决对象即基于前者而滞留的线路路径优化，以进行最合适路径的选取以及建设成的电气相关参数的大小调整。

3.5 新模型计算方法

引入混合优化算法，用遗传算法确定选址，同时结合动态算法来运算，以达到优化路径的目的。所以，需要不断运用动态算法，栅格多时候会导致计算变慢。如果端点不变，路径也不会变，从而最优化路径就不变。因此，通过增加记忆体，使得算法在经常计算的路径里保持纪录路径。通过纪录路径要素，来完成记忆提的作用。优化路径有利于进一步节约计算所需要的时间，效率可以得到提高，采用记忆机制来完成计算的路径优化和快速计算。分析采用这种方式跟实际情况的差别，可知因电网的规划采用的离线变量分析方法，所以不要求及时算出结果，虽然计算耗费了时间，但是这种算法比较符合实际情况。

4 结论

通过比较老式算法与新算法的差别，本文归纳出的空间电网合理规划方法可以获取比较精确而且更加合理的规划结果，通过计算比较，有以下几条结论：

（1）栅格之间高度的差值对会影响到规划电网，所以只有将二维电网转化成三维电网才更合理、更贴近实际。

（2）线路的优化、网架优化以及变电站位置的选取可以在很大程度上影响电网的投资及成本，三方面的完善有利于获取更优的规划结果。

（3）记忆的引入和新方法的提出可以解决比较大规模空间的电网规划问题，使得规划方式更合理、更优化。