路径规划典型算法第1篇

【关键词】神经动态规划 最优路径 子问题 Matlab仿真

为了减轻交通压力，人们越来越关心交通系统的智能化进程。智能交通系统主要的研究方向之一就是动态路径诱导系统，它可根据外出的人们的需求，为驾驶员提供最新的路况信息和最佳路径选择，以此避免交通拥堵现象的发生，从而优化交通状况，最终使交通时时地保持一个合理的动态分配。目前，最优路径选择的方法有很多，但是真正需要解决大型问题时，计算机需要搜索的选择范围太大，传统的动态算法基本上无法处理。1995年，神经动态规划算法被提出，该算法把复杂的问题分成若干子问题，这些子问题被拆分后更容易解决，使计算过程大幅简化，且更容易被计算机处理。采用这种方法，可准确、快速、实时、稳定地选择出最优路径，值得推广。

1 神经动态规划概述与核心思想

在解决多阶段决策问题时，动态规划大致思想为：将非常繁琐的原始问题分解为若干个阶段，这些阶段看似不相关，却是相互联系的子阶段，在找到上一阶段的解决方法以后才能处理下一个阶段，依次求出每个阶段的解，最后得到全局最佳的解。多阶段决策问题具备很强的顺序性，同时每个阶段所使用的解决方法也是随着阶段的变化而变化，所以“动态”意义就得以体现。其中交通网中最佳路径的求解就是典型的多阶段决策问题。

在路径优化中，动态规划是一种非常经典的计算方法，但在处理实际问题的时，我们肯定会遇到缺少一个完整信息或者维数灾等一系列问题，所以，引进神经网络对动态规划具有较大的解决实际问题的意义。神经动态规划如图1所示。

2 基于神经动态规划算法的最优路径实现

（1）将原来的问题分解成很多个小问题，即子阶段，并且找到每个子阶段的最优解决办法。求解多级问题的步骤为：根据每个问题的特点，划分子阶段。在划分子阶段时，必须按照一定的规则，比如根据执行决策的时间、空间的顺序等。本文用x来表示子阶段变量。

（2）求解状态和状态变量。每个子阶段具体的起始位置可以依靠自然状态来指导，其中客观条件阶段性数目的状态是自然状态中的一种，它传达每个子阶段的关键信息，此外，一组或者无后效性的变量同样可以用来表示状态变量。本文用Hx来表示第x级的状态变量。

（3）求解原问题决策变量和集合。从目前阶段到下一个阶段状态选择时，决策者需要做出恰当的决策，决策变量的范围称为集合。本文用Dx表示决策集合，用Ux表示决策变量。

（4）研究状态转移的方程。假设状态转移方程是：Hx+1=Tx（Hx，Ux）。次方程式中Tx不定，根据具体问题才能确定，如果Hx确定，一旦变量Ux确定，那么第x+1阶段状态变量（Hx+1）也将确定。

（5）研究指标函数。因为n和vi的递进性和可分离性，所以很容易找到指标函数n和vi之间的关系，显然，指标函数的求解也相对简单化。

（6）动态规划函数的基本方程。边界条件为；

，第x-m阶的最优动态规划函数是。

3 仿真结果

将上述模型，在Matlab仿真软件上进行模拟仿真，分解原始问题并确定各个子阶段的最佳方案，将这个问题用网格的形式如图2进行表示：A为起始地点，E为目标地点，从起始地点到目标终点有很多路径，假设经过每个节点需要一定的运输成本，在Matlab仿真软件上进行仿真后依据动态规则算法的要求，设定好相应的算法模型以及相应的计算公式，这样便可以找到最优路径。

由图2可以非常清楚的看出，成本最低的路线为：或者或者，成本都是110。仿真结果可以看出神经动态规划算法具有较多优点：得到清晰运算结果；很容易找到全局的最优路径；可以找到一组完善的解，有利进一步的分析。

4 结语

我们在使用神经动态规划算法来探索最优路径的时候，具有很多优势，首先其具有稳定、可靠的步骤，过程并不复杂，但是给予我们的结果十分清晰明确，且适用于现实生活。使用这种动态规划算法解决复杂的问题时，可以非常容易找到解决方案，而且效率很高。当然，该算法也有一定的局限，但只要我们不断地改进完善，日后继续研究神经动态规划算法，相信一定可以攻克更多的局限，能够使其更好地被应用。

参考文献

[1]谬慧芬，邵小兵.动态规划算法的原理及应用[J].中国科技信息，2006（23）：32.

[2]杨琰，廖伟志，李文敬，杨文，李杰.基于Petri网的顾及转向延误的最优路径算法[J].计算机工程与设计，2013（10）.

作者简介

杨超（1994-），男，广东省吴川市人。现在就读于长沙理工大学计算机科学与技术系。

路径规划典型算法第2篇

关键词：多目标路径规划 贪心算法 压缩映像 早熟收敛

中图分类号：TP301 文献标识码：A 文章编号：1672-3791（2014）01（c）-0238-03

随着需求的增长，市民出行时除路程外还将其他要素纳入考虑，比如驾驶过程中的舒适度体验，行程的安全性，路段的拥挤程度等等。所以把市民出行时的路径规划问题抽象成多目标优化模型更加符合实际[1]。在实际应用中，用户需要在可忍受的时间内获得一组高质量的解。因为用户最满意的不一定是算法定义的最优解，而是最符合现实情境要求的解，所以合理的做法是提供多个选择，让用户根据实际情况进行决策。上述背景对算法提出了两个基本要求，即高效性和解的多样性。在一个城市内进行最优路径搜索时，所涉及到的节点数高达几千多个，而路径规划问题是典型的NP难问题，一些精确算法，如动态规划，分枝定界，其计算量呈指数增长[2]。而经典Dijkstra算法在节点数比较多时，消耗的时间和存储空间都十分巨大，所以应用也十分有限。近几年来，遗传算法在解决复杂的多目标优化问题中有成功应用，将其应用于大规模的多目标路径规划问题开始成为学者们研究的热点。相较于前面提到的几种算法，遗产算法在处理大规模路径规划问题时更具优势，更加容易实现解的多样性[3]。本文在遗传算法的传统框架上进行优化，用贪心算法设计初始种群，将压缩映像引入适应度标定中并且改进了更新策略，从而将算法更好地植入模型中，提高了计算效率。

1 模型建立

本文设定三个目标，，，分别代表最小路径长度，最小事故发生率和最小路径拥挤度，建立多目标路径规划问题的数学模型：

（1）

（2）

（3）

（4）

其中，为全体有效路径；为路径的路段总数。为路径中第个路段的长度；为路段的事故发生率；为路段的拥挤程度，且。求解该模型的目的在于找到一个非劣解集，协调各个目标之间的矛盾，达到目标间的平衡[3]。

2 算法设计

在60年代中期，Holland提出遗传算法，模仿达尔文的生物进化论，将适者生存的概念引入算法设计中，其主要组成部分包括初始种群的产生，个体适应度标定，选择算子，交叉算子和变异算子[4]。本文对传统遗传算法进行了三处改动：（1）用贪心算法设计初始种群；（2）将压缩映像法引入适应度标定中；（3）改进更新策略。

2.1 初始种群的生成

初始种群最常用的是逐次递进法，节点从起始点开始深入，逐层递进，不满足条件时，逐步退回上一个节点，再次逐层深入直至到达终点。还有随机节点生成法，由计算机随机生成一列节点，检验是否构成有效路径。与上述两种方法的盲目式搜索相反，利用贪心算法能够在起点和终点唯一确定一条路径。

算法步骤是这样的：决定起点的下一个节点时，考察其邻节点到终点的距离，两点间的距离由坐标计算可得，选择离终点最近的节点，依此类推直至到达终点。所以建立每个节点的二维坐标信息是算法实现的重要前提，节点的坐标能简化算法设计，提高搜索效率，并且通过现有的科技手段很容易获得，既不占用过大的存储空间，也不增加数据结构的设计的难度。所以路径搜索时引入节点的坐标有很大的价值。

为生成大量初始路径，将贪心算法与随机节点生成法结合，由计算机随机生成个节点，，1，2，…，。是给定常量，表示起点，表示终点。在和间运用贪心算法生成连通道路，最后整合成从起点到终点的通路。需要注意的是，该路径可能存在回路，必须使用紧缩算子消除回路[5]。

2.2 压缩映像在适应度评价中的应用

权重法是将多目标优化转化成单目标最简单和直接的手段，其算法实现相当容易，只需为每个目标赋予权重系数，但存在这样一个缺点：不同性质的目标之间单位不一致，单位小的目标函数值对结果影响微弱，比如本文提到的事故发生率。为改善这一不足，作者引入模糊数学领域中的压缩映像法[6]，将三个目标的度量纳入一个体系中。

以第一个目标为例，假设有一列染色体，，，则第一个目标函数值的压缩值为：

（5）

同理可计算和。经过压缩后，，，都落在中，完成了单位的统一。设给三个目标赋予的权重分别为，，，适应度的计算公式为：

（6）

2.3 更新策略

设为第代父代种群，为经交叉生成的子代种群，种群规模均为。传统的遗传算法通过选择算子从选出一组染色体进入池，交叉生成子代，经变异后直接作为新种群继续进化[7]。这种做法会流失父代中的优秀基因，从而降低收敛效率。结合精英保留策略和NSGA-Ⅱ算法中的更新策略[8～9]，本文采用如下方法：合并父代和子代组成规模为的，剔除中重复的染色体，根据适应度从大到小排列，选取前条染色体进入新种群，若不足，剩余个体从中随机产生。在更新过程中，子代个体并不比父代更具被选入的先天优势，两者根据适应度大小公平竞争，获得继续进化的机会。相较经典的“精英保留”策略，它扩大了父代染色体参与竞争的数量，使更多优良个体被保留，相较NSGA-Ⅱ，它的计算量要小得多。其中删除重复个体的操作维持了种群在进化过程中的多样性，避免算法陷入早熟收敛。

2.4 几个关键算子

选择算子使用普通的赌方式，在文献[10]中有详细介绍。交叉算子采用常用的一点交叉，但如果随机选出的染色体，没有共同节点时，则搜索二者中距离最近的节点，（距离由坐标计算可得），使用前文提到的贪心算法构造连通路径，接着仿照一点交叉法完成染色体交叉，得到两条新的染色体。

设计变异算子时，首先由计算机随机生成两个节点，通过贪心算法构造这两个节点间的连通路径替代原染色体中的路段。

无论是交叉算子还是变异算子，生成的新染色体都有可能产生回路，和初始种群的产生一样，也需要消除路径中的回路。强调一点，在本文的交叉算子和变异算子中，节点的坐标信息发挥了很大的作用，笔者认为在解决多目标路径规划问题时，有必要将节点的坐标进行充分利用。

2.5 算法流程

step1：产生初始种群。

step2：计算个体适应度并判断是否满足终止条件；若满足，输出一组最优解，否则转入step3。

step3：用选择算子从中选出条染色体进入池。

step4：对池中的染色体通过交叉算子进行随机，产生种群。

step5：合并，组成，用本文设计的更新策略获得条染色体。

step6：对更新后的种群应用变异算子，结果作为新种群，返回第二步。

3 试验结果及分析

3.1 前5条最优解

利用几何画板5.0绘制出33个节点75条边的无向图，节点坐标和路段长度由几何画板获得，事故发生率和拥挤度由计算机随机产生，构造出验证遗传算法效果的算例，如图1所示。

算法在MATLAB7.0环境下编译。种群规模取40，迭代次数取200，交叉率取0.8，变异率取0.08，路程，事故发生率，拥挤程度的权重系数分别为0.4，0.3，0.3，求得从节点1到节点33的在多目标规划下的前5条最优解，结果见表1。从表1中可以看出目标之间的相互制约关系。由于本文选取的算例规模比较小，所以可以用Dijkstra算法获得算例在仅考虑一个目标下的精确的最优值，见表1中最后一行。从表中可以发现没有一条路径能同时取得单目标下最小值，这证明求解多目标优化模型的关键在于协调和平衡几个目标。值得一提的是，为考察本文使用的更新策略的作用，将传统方法即把交叉变异后的种群直接作为进化的新种群的方式和改进后的方法对比，经试验发现，用传统方法得到的最后一代几乎全是路径1，而后者却得到了超过30条互不相同的路径。实验结果表明，该遗传算法在解决解的多样性问题上效果很好，扩大了用户决策的空间。（如表1）

3.2 解的收敛性

图2是迭代200次中种群的路程平均值变化曲线。从图中可以看出，最初种群的路程平均值比较大，经过50代后开始逐渐趋向平稳，在100代时因变异算子产生小的波动，最后稳定在18.7左右。曲线表明算法是快速收敛的。

3.3 解的有效性

我们知道在多目标路径规划问题中，绝大多数情况下无法找到一条路径同时取得三个目标的最优值。现在假定这条路径存在，那么非劣性解越接近它，表明解的质量越好[11]。基于这种思想，定义任意一条有效路径到虚拟的最优路径的距离，记这条虚拟路径的三个目标函数值为，，，任意有效路径函数值为，，。计算两者距离的公式如下：

（7）

公式（7）给出了比较两条路径优劣的指标。那么用产生初始种群的算法随机生成一条有效路径，挑战表中的5条最优解，如果最优路径到虚拟路径的距离小于随机路径到虚拟路径的距离，则称这个最优解是成功的，否则失败。试验200次，5条最优路径的成功率分别为100%，98%，99.5%，99%，91%。为避免算法的偶然性，对算例求解10次，其最优解的成功率均在90%以上，说明这5条最优解的性质都不错，证明遗传算法是有效的。

4 结语

本文采用遗传算法解决大规模的多目标路径规划，并对传统的遗传算法进行改进，使之具备更好的计算性能。在具体试验中，该算法体现了良好的收敛性和解的多样性，同时保证了最优解的有效性。为缓解种群陷入早熟收敛的压力，本文改进了传统的更新策略，但尚不明确它是否会带来意想不到的副作用。遗传算法的研究仍将集中在两方面：一是改进交叉和变异算子，防止种群早熟或陷入局部最优解[12]；二是提高算法的搜索能力，减少求解时间。

参考文献

[1] 潘斌斌.多目标路径规划问题的算法综述[J].重庆工商大学学报：自然科学版，2012，29（5）：78-84.

[2] 郎茂祥.基于遗传算法的物流配送路径优化问题研究[J].中国公路学报，2002，15（7）：77-79.

[3] 梁晓辉，吴威，赵沁平.大规模真实地形数据中的全局路径规划方法―― 基于遗传算法的研究[J].计算机研究与发展，2002，39（3）：301-306.

[4] 阮宏博.基于遗传算法的工程多目标优化研究[D].山东：大连理工大学土木工程系，2007.

[5] 刘旭红，张国英，刘玉树，等.基于多目标遗传算法的路径规划[J].北京理工大学学报，2005，25（7）：613-616.

[6] 宋晓秋.模糊数学原理与方法[M].徐州：中国矿业大学出版社，2004.

[7] 肖晓伟，肖迪，林锦国.多目标优化问题的研究概述[J].计算机应用研究，2011，28（3）：805-808，827.

[8] 刘旭红，刘玉树，张国英，等.多目标优化算法NSGA-II的改进[J].计算机工程与应用，2005（15）：76-78.

[9] 关志华.非支配排序遗传算法（NSGA）算子分析[J].管理工程学报，2004（1）：56-60.

[10] 井祥鹤，魏冬峰，周献中.运输方式选择多目标优化问题的混合遗传算法[J].计算机工程与应用，2008，44（6）：210-212，224.

路径规划典型算法第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代表街道信息矢量，Δτ代表街道信息变化量。

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

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

结语

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

参考文献

[1]电力系统卷编辑委员会编.中国电力百科全书（第二版，电力系统卷）[M].北京：中国电力出版社，2011：52―708.

路径规划典型算法第4篇

【关键词】移动机器人 最优路径规划 栅格法 A*算法

自从有移动机器人这一概念以后，*成为长期以来研究的最热门的内容之一。移动机器人可研究的领域相对较多，其关键技术有传感器信息结合、创建地图、定位导航、路径规划等。其中核心技术之一是路径规划技术，从起始点到终点，快速在环境地图中找到最短或最佳的无碰撞路径，这是路径规划的主要任务。本文是以“探索者-1”移动机器人作为研究平台。它由多个CPU控制，通过扫描式超声波传感器探测周边环境。当机器人接收到超声障碍信息后，可生成栅格环境地图，并基于迷宫八方向搜索的思想找到最佳路径。

1 机器人路径规划环境模型建立

在有障碍的环境中，移动机器人根据传感器发出的信息，生成环境地图，才可以实现路径规划以及导航，而栅格地图、拓展地图、几何三维特征地图是移动机器人生成的环境地图的三种表示方法。当移动机器人在获得信息时，会在一定程度上存在较多的不确定性，这是由传感器差异造成的。由于获得的信息不确定导致处理数据方法也不确定。解决这一问题，概率法，灰色理论，模糊理论等起到一定的作用。

1.1 栅格地图的创建

在栅格地图模型中，移动机器人所接收的每个栅格的信息直接与地图中的每个区域相匹配，这样移动机器人就可以根据栅格地图进行定位甚至导航。

“探索者-1”得到环境障碍信息主要途径依托于扫描式超声传感器，但是这种传感器具有盲区、多次反射等缺陷，所以超声信息存在很大的不确定性。因此可采用灰色系统理论来创建完善的栅格地图模型。

1.2 栅格地图创建实验结果

以“探索者-1”移动机器人作为实验对象进行实验，实验环境和实验结果如图1所示。

实验结果：采用栅格法，有一定的辨别真伪能力，能够有准备地描绘所需要的环境地图。

2 A*路径规划算法与传统算法的比较优势

传统算法生成的相邻子节点的作用是相同的，且不分先后顺序。如果不利用优先级的子节点生成策略，会产生许多问题，比如没有考虑机器人的宽度，而生成越过障碍物顶点栅格顶格的路径规划。A*路径规划算法是一种非常经典的启发式搜索算法，它的估计函数计算式为：f（x）=g（x）+h（x），其中f（x）为节点x的估价函数；g（x）为实际代价；h（x）是最佳路径的估价，在函数中作用最大。另外，估价函数决定着A*算法的正确与否。取g（x）在状态空间到x节点的深度，如图2所示。其中h（x）的计算方法为：h（x）=|Xd―Xs|+|Yd―Ys|。式中：（Xd，Yd）表示目标点坐标，（Xs，Ys）表示当前点坐标。

3 改进A*路径规划的算法

机器人定位前，A*算法已规划好最佳的路径，但路径中夹杂了多余的点坐标，当移动机器人到达拐点处时，不能自行地调整姿态。因此，我们对A*算法提出两个方面的改进：

（1）简化坐标点，除去冗余的坐标点，只剩下起点、拐点和终点。

（2）解出拐点处的旋转方向和最小角度，当机器人到达拐点处时，根据角度和方向自行处理自己的位态。用A*规划任意路径，通过实验证明它的正确性，如图3中A所示。

改进A*算法后的路径规划如图3中B所示，路径只包含起点1、拐点3、6、8、9和终点11。

4 仿真分析

为了验证A*算法的可靠性，在不同环境下，可选用编译工具Matlab 7.0对移动机器人进行路径规划仿真。其结果表明：采用改进的A*路径规划算法，使得要计算的路径点减少，且当机器人到达拐点处时，能够自动调节位态，使移动机器人更好地自主定位。

5 结语

基于A*路径规划算法移动机器人，找到的最优路径要满足几何长度的最短与时间最短的条件，只有这样的无碰路径才是最优路径。在栅格环境下，采用A*算法的移动机器人其实并不能完美满足实际应用，为了使其路径更加完美，则需要继续地实验论证，期待未来的移动机器人不但可让路径简单化，而且还能找到其在拐角处旋转的方向和角度，满足定位要求。

参考文献

路径规划典型算法第5篇

关键词：车辆路径问题；启发式算法；多配送中心；带时间窗；集送货一体化

中图分类号：TP181 文献标识码：A 文章编号：1009-3044（2016）26-0079-02

Development and Application of Vehicle Routing Problem

BIAN Chen， ZHAO Jian-dong

（School of Computer Science and Engineering， Anhui University of Science & Technology， Huainan 232001， China）

Abstract： As a hotspot in the field of operational research and combinatorial optimization， vehicle routing problem is closely related to real life.As long as the deepening study of vehicle routing problem， various kinds of new types of heuristic algorithm is applied to solve such problems.The vehicle routing problem with various constraint were investigated， analysis and summary in this paper， and the related domestic and foreign research results were reviewed and refined， on this basis， this paper summarizes the research of vehicle routing problem. Based on the current various standard of classification， this paper discusses and analyzes the classical vehicle routing problem firstly， and summarized the basic methods and modern heuristic algorithm on this basis.

Key words： vehicle routing problem； heuristic algorithm； hybrid；multi-depots； time window； pickup and delivery

1 背景

车辆路径问题（Vehicle Routing Problem，VRP ）是由 Dantzig等人在1959 年提出的一个经典的NP-hard问题[1]。是指对于一系列的装货点及卸货点，规划合理的配送路径，在满足了约束条件之下，载货车辆按照规划的路线依次访问，能够满足一定的需求或达到某些目标。其研究成果已广泛地应用于各个学科之中。VRP已经不止是单纯的理论研究，现实世界中，国内外学者的研究经历了其从最早期无车辆约束的TSP问题发展为对车辆运载能力、车辆行驶里程、客户服务数量进行限制的经典VRP，而后依据客户需求的改变和客户对配送要求的提高，从服务无时限向有时限（也称为时间窗问题）以及从纯送货问题或者纯取货问题向混合取送问题（也称为集货送货一体化）的变化的VRP问题。为了不断满足现实要求，当前针对VRP的大部分研究，集中在对其动态性的讨论上，即从配送过程中信息的确定性向动态接受客户需求（也称为不确定性）的变化。

随着现代物流行业的崛起，企业为了降低运输成本，越来越重视对VRP问题的探究，新型的VRP不断地涌现，使得其更有研究价值和现实意义。

2车辆路径问题研究现状及评述

本文根据现有对VRP问题研究的成果，从综合的角度分析车辆路径路径问题，目前国内外针对车辆路径问题的研究主要集中在其扩展问题上。

2.1 多配送中心的车辆路径问题

根据配送中心数目的多少，配送车辆调度问题可以分为单配送中心车辆调度问题和多中心车辆调度问题，在整个物流管理的体系中，配送地一般都存在多个中心，因此对多配送中心车辆调度问题的研究更加具有现实意义。目前国内对于多配送中心车辆调度问题的研究还是处于一个有限的阶段。

在多配中心车辆路径问题中，车辆路径的安排需要满足以下四点条件：

1）每一辆车都从一个配送中心驶出，并在服务了一定数量的客户后返回初始的配送中心；

2）每一个客户每次只能被一辆车服务；

3）车辆不能够在两个配送中心之间进行运输，并且行驶路径不能够出现回路；

4）车辆的运载量不能够超出容量限制，并且每一个配送中心提供的客户服务数量是有限的。

对配送中心的车辆路径问题一般可以如下的描述：在整个物流配送系统中，存在着多个服务中心为多个客户进行服务，需要制定一条配送行车路径使得所有客户的需求被满足的前提之下，配送成本降至最低。多配送中心的VRP是一个NP难度组合优化问题，因此一般求解是很难得到最优解的。当前，国内外学者普遍采用多阶段的办法来解决此类问题，一般先将多配送中心问题转化为单配送中心问题，再利用启发式算法进行求解。崔文[2]通过多阶段的启发式算法，将此类问题通过聚合―求解―优化的步骤逐步求解出最优路径，提出了通过启发式算法在短时间生成最初的有效路径来代替Lin-Kemighan算法中采用的随机路径作为初始路径。

2.2 开放式车辆路径问题

开放式车辆路径问题（OVRP）是现代运输运筹学中的一个新型研究课题，与经典VRP问题相比较，他的一个显著特点是车辆在完成运输服务后可以将其他的配送中心点选为终点。OVRP一般可以简化为忽视了回程约束的带容量约束车辆路径问题（CVRP），其求解目标是构建一个哈密顿通路以满足所有顾客的需求。在现实中，物流公司可能通过雇佣车辆来完成配送任务，那么车辆是否回到出发点并不受到关注，这段路程的费用也将不计。

OVRP是配送运输管理中广泛存在的问题，在现实生活中有很多应用，特别是在具有外包业务特点的配送服务中具有较大的应用价值，例如校园班车问题、牛奶配送、报纸配送等，在这类问题中，由于企业没有自己的车辆，所以将其配送业务外包给其他的车辆或车队，而且企业并不要求车辆在服务完客户后回到车场点。OVRP问题的首要优化目标一般都是最少车辆数，在此基础上优化行驶距离。在过去的十几年里，尽管学者们通过禁忌搜索，确定性退火技术，大规模领域搜索方法，分枝切面法等多种方法为OVRP问题提供了基本的解决办法，但面对大规模的数据处理，OVRP问题仍然存在着一定的求解难度。Sariklis[6]等人通过两阶段启发式算法来进行求解，第一阶段是先生成客户群，然后在每一个客户群中安排路线，进行局部优化，第二阶段将OVRP问题转化为最小生成树问题并求解。Brandao[7]在求解时，通过最近邻居法和最小K度生成树来划分客户群，并最终用禁忌搜索法优化路径。

2.3 时间窗口约束的车辆路径问题

带时间窗车辆路径问题（Vehicle Routing Problem with Time Windows，VRPTW）作为物流管理问题中一个重要的分支，他基于以下假设：1.需要必不可少的通信设备，使得顾客和服务中心之间，服务中心和货运车辆之间的信息能够快速便捷的传递；2.配送的计划中，存在预约服务的客户。服务车辆必须在客户规定的时间窗[[Ai，Bi]]对其进行服务，其中[Ai]是客户[i]的允许最早开始时间，[Bi]是其所允许的最迟开始时间。如果车辆到达客户的时间早于[Ai]，那么车辆只得等待直至到达服务的最早时间点，其系统优化目标是最小化客户的平均等待时间。

近年来，对于求解带时间窗车辆路径问题取得较好效果的是启发式算法。Gold等人最早综述了VRPTW的研究状况。上世纪80-90年代，对VRPTW的研究开展综述的是Solomon等人[10]。随后Braysy等人[11]综述了经典启发式、智能启发式算法并提出了展望。最近，Raúl Ba?os[12]等人提出了一种针对多目标VRPTW问题的混合现代启发式算法，得到优化解决方案。

2.4 带集货送货需求的车辆路径问题

车辆调度领域之内的问题一般可以按如下区分为两大类：一种是纯装货或者纯卸货问题，另一种是带装货卸货一体化的车辆调度问题（VRPSPD），而后者更是包括了先送货后取货的车辆路径问题，同时集货送货的车辆路径问题以及混合集货送货的车辆路径问题。

VRPSPD的提出最早可以追溯到1989年，由Min提出的在解决了车辆数量一定并且车辆运载能力有限的情况下，一个中心配送点和22个地方图书馆之间的书籍配送问题。VRPSPD问题可描述为：某一个仓库为其用户群体进行货运服务，任意用户可能同时需要送货和集货服务，并且某一客户的送取货的需求之和不能大于车辆总运载能力Q。

VRPSDP的难点在于服务车辆的装载量难以控制易发生溢出。当每一个客户的送货需求是已知的时候，依据车辆的剩余装载能力来定义插入准则，。

2.5 动态车辆路径问题

依据物流信息在配送之前是否完全可知，VRP按新的分类方式分为静态VRP和动态VRP。动态车辆路径问题的首次完全提出要归功于Wilson和Colvin[13]，当时他们研究的单一车辆问题描述了客户旅程的需求，从始发地到目的地的旅程是动态变化，并通过启发式算法来提升计算效率。车辆路径问题中动态信息最常见的来源就是客户需求的在线到达。具体来说，需求可以是针对货物的调整也可以是是服务需求的变化。

一般认为动态车辆路径问题和静态车辆路径问题的区别在于信息的确定性与未知性，而前者在配送服务过程中，会出现不同类型的动态信息。

动态车辆路径问题一般具有的特征如下：

1）安排配送路径和车辆执行计划的过程中新客户信息能够实时的传达。

2）任何新传达的信息都允许是不精确的。

3）新信息需要被快速的响应。

4）与静态VRP问题相比求解的目标函数更为繁杂。

任何动态车辆路径问题仍是基于静态车辆路径问题提出的，目前针对动态车辆路径问题的求解办法，仍然需要借鉴处理静态车辆路径问题的各类算法，其中大部分算法为元启发算法。

动态车辆路径问题首先要明确需要响应哪些动态信息，并以客户需求变化为依据，选择需要优化的目标函数，例如将配送车辆的总行程作为目标函数进行优化，然后再设置额外的约束条件，例如设定单车最大行程为约束条件。借助各类启发式算法如蚁群优化算法等进行优化，在整个配送过程中，不再是单一直接地插入顾客需求，通过最大熵法分布估计算法计算出具有发展潜力的客户群体和区域。在=当需求发生冲突时衡量各个客户需求的利益，通过惩罚措施来降低费用。

3 结束语

车辆路径问题因其不可预估的经济效益和其在现代物流中的所占据的重要地位已经引起了国内外学者的高度关注，并依据实际需求不断引入新的约束。在理论与应用上，各类精确算法、启发式算法被广泛地应用于解决车辆路径问题，并已经取得了长足的进步。然而，同样被关注的是，从现有的各类研究成果看来，虽然新型约束条件下的VRP模型更加完善也更符合现代物流实际需求，但实际求解算法却很难在精度和效率上做到两全，简化算法测率需要得到更多的重视，特别是，各类启发式算法在求解时的弊端也愈加明显，需要取长补短发挥其他算法的优势。

参考文献：

[1] Dantzing G，Ramser J. The truck dispatching problem[J]. Management Science， 1959， 10（6）： 80-91.

[2]崔西.大规模多配送中心车辆路径问题研究[D]. 济南： 山东大学， 2009.

[3]Sariklis D， Powell S.A heuristic method for the open vehicle routing problem[J].Journal of the Operational ResearchSociety，2000，51： 564-573.

[4] Branda～o J.A tabu search algorithm for the open vehicle routing problem[J].European Journal of Operational Research， 2004，157：552-564.

[5] Desrochers M， Lenstra J K， Savelsbergh M W，et al. Vehicle Routing With Time Windows： Optimization and Approximation[M]. Amsterdam， The Netherlands： Elsevier Science Publishers， 1988.

[6] Braysy， Gendreau. Vehicle Routing Problem With Time Windows，Part I：Route Construction and Local Search Algorithms[J]. Transportation Science， 2005（39）： 104-118.

路径规划典型算法第6篇

关键词：白车身；机器人焊接；路径规划

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

一、路径规划的意义

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

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

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

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

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

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

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

（二）路径规划

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

（三）遗传算法

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

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

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

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

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

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

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

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

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

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

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

三、路径规划的仿真

（一）仿真系统的各要素

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

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

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

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

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

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

（二）仿真软件的选择

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

四、小结

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

参考文献：

[1]王立东.基于Christofides算法的白车身焊接机器人路径优化[J].河西学院学报，2011，27（2）：96-100.

路径规划典型算法第7篇

关键词：电力规划；规划全过程；城市发展规划配套；EPGIS深化应用；规划数据全采集

引言

由于城市建设提速、道路改造频繁，电力部门所做的城市电网规划不适应、跟不上发展的节奏，各类工商业区、旧城区改造后新增的成百上千倍的供电量不能做到有效预测，以致在电网规划中不能及时体现，电网中短期规划调整由于数据衔接不畅满足不了城市快速发展的要求。某些时期政府规划特别是道路建设有很大的随意性，给电网规划带来困难。

尤其是近三年来，太原城市道路改造工作的快速推进，着实解决了制约都市建设的主要因素。太原空间布局“一城独大”，城市中心区聚集了太多的行政、产业、人口及服务，不仅造成了交通的拥堵，也造成了空间结构的失衡。产业、基础设施和人口从市中心区疏解到城市周边，会迅速带动县域经济的崛起，实现全市城乡的均衡发展。可以预见，随着道路基础设施不断完善，对电力资源的要求逐步提升，提升电力规划工作的合理、科学性，为城市建设提速是电力企业的重要责任。

1 项目主要内容

针对上述情况，亟需建立一套以先进的规划理论、规划方法为指导，通过多项数据来源和接口，构建模型，建立电力电网规划辅助及决策风险分析的研究与应用的信息化系统。具有使用方便、结果直观，图形信息全的优点，结合城市规划发展，形成对电网规划工作的全过程管控与技术支撑，整个系统能够诠释理论与专家经验的结合，科学性与实用性的统一，从而完成结构合理、界面友好、扩展性强的电网规划辅助平台构建。结合城市建设发展规划为电网规划设计人员提供全面的源头资料，提高城市电网的规划设计水平。从规划的各个时期、层面做好分析工作，使经济效益的观点寓于城网规划之中，使供电企业的效益有机的增长。

2 项目设计思路

项目将按照电网空间信息服务平台，电网规划资源信息库，电网数字化辅助规划三个部分研究实施。

电网空间信息服务平台：通过国网EPGIS平台提供的相关空间分析服务对电网现状（供电能力、负荷分析预测等）分析提供技术支持。

电网规划资源信息库：主要为电网规划提供相关数据功能，包括接入地理信息数据、卫星影像数据、国网GIS平台数据、营销数据等，为电网规划提供主要的数据支撑。

电网数字化辅助规划：主要对供电区域的空间分析计算，提供需求预测、负荷与电源分析、电气计算、项目统计、数据分析、经济评价、指标评估、风险评估、成果辅助管理等。

3 项目研究路线

项目通过对地市供电公司及下属技术支撑单位的电网规划工作范围、特点及需求的详细分析形成了对规划工作启动阶段、编制阶段和审查实施阶段的全过程信息化、规范化辅助，具体包括：

规划前期：通过上级规划方案分析形成对本单位规划范围及内容的初步理解，并根据需求整合现有各类非电力规划资源，如市政发展规划、产业推动计划等，依托EPGIS数据接入实现包括电网规划、电源规划、能源资源、地理地质、电网架构、电量负荷、典型设备电气参数等各类重要数据。并针对规划区域针对性分析现状。为规划工作的开展提供准确、全面的数据和科学、有效的前期分析工具。

规划中期：依据前期调研收集的各种规划数据及当前的现状分析，提供为负荷与电源分析、需求预测及潮流计算等辅助计算工具，使规划人员从繁琐的人工计算中解脱出来，最终形成线路布线和优化、变电站选址定位等功能辅助规划方案的形成。

规划后期：实现规划方案初稿产生后的方案评估、经济评价、方案评审及数字化方案资料移交，针对规划成果提供多样化展示，并形成规划方案资源库，便于检索查询为方案规划工作提供典型经验。

4 项目主要特点

4.1 实现EPGIS平台接入

国网GIS平台服务的请求报文采用SOAP方式，涉及到空间图形数据时采用GML标准格式进行封装，采用标准的XML接入规范实现。

根据国网GIS平台的开放接口实现基础地理数据的接入、图形服务的接入、业务功能的接入。

基础地理数据接入：包括基础地理信息数据（铁路、河流、公路、省界、市界、县界、收费站、乡间小路等）、卫图影像、输电线路、杆塔、变电站及站内设备矢量数据。

图形服务接入：包括图形浏览服务、矢量图形服务、专题图服务、空间分析服务、查询定位服务、电网拓扑分析服务、切片地图服务。

业务功能接入：电力线路走廊分析、最短路径分析、供电能力分析、供电半径分析。

4.2 负荷预测

负荷预测是电网规划中的基础性工作，它为电网规划提供了必不可少的基础数据，其精度的高低直接影响着整个规划工作的优劣。负荷预测涉及的范围广泛，影响负荷的因素很多且具有不确定性，预测的方法和模型众多且各有其优缺点和适用场合，预测的思路也千差万别，所以准确的负荷预测难度很大。

在各途径结果相互校核的基础上，通过专家干预，最终确定目标年各项预测结果。按年度分区，分电压等级收集和积累最大负荷数据，根据电网地理分布、变电站主变、线路及大用户的典型日、最大负荷计算分区最大负荷和区块间的同时率，绘制全市负荷分布图，并实现任意划定区域内的负荷统计等功能。分析各分区的负荷密度、增长率、电网密度和负荷的匹配情况。

4.3 潮流计算

潮流计算是电力系统非常重要的分析计算，用以研究系统规划和运行中提出的各种问题。对规划中的电力系统，通过潮流计算可以检验所提出的电力系统规划方案能否满足各种运行方式的要求；对运行中的电力系统，通过潮流计算可以预知各种负荷变化和网络结构的改变会不会危及系统的安全，系统中所有母线的电压是否在允许的范围以内，系统中各种元件（线路、变压器等）是否会出现过负荷，以及可能出现过负荷时应事先采取哪些预防措施等。潮流计算方法很多：高斯-塞德尔法、牛顿-拉夫逊法、P-Q分解法、直流潮流法，以及由高斯-塞德尔法、牛顿-拉夫逊法演变的各种潮流计算方法。目前主要的潮流计算方法研究方向为牛顿法及P-Q分解法在算法模型上的优化。

路径规划典型算法第8篇

【关键词】智能交通系统 蚁群算法 信息素 最优路径 组合优化

交通运输的现代化使人们享受便利的同时，也面临道路拥堵、事故频发等问}。近年来，智能交通系统越来越受到人们的重视，它涉及到交通领域诸多方面，如最优路径选择、车辆路径规划、动态车辆调度、交通流量控制等。其中一个重要的应用是一类典型的以数学理论为基础的组合优化问题，而蚁群算法具有内在的搜索机制及正反馈性，适合求解一系列的组合优化问题。

1 蚁群算法描述

蚁群算法源于20世纪90年代初意大利学者M.Dorigo首次提出的蚂蚁系统。它是基于种群的启发式放生进化系统，是通过对蚁群觅食过程中其行为的研究而得出的一种算法。主要思路是蚂蚁借助自己路径寻优的能力可以找到巢穴与食物之间最短的途径。在寻找过程中主要依靠的是每个蚂蚁在行进过程中留下的挥发性分泌物――信息素，依靠信息素，蚁群的蚂蚁之间可以相互合作，相互配合，因此形成的正反馈可以使每只蚂蚁找到所有路径中最短的路径。

蚂蚁a从节点j移动至k的转移概率可以从式（1）中获取：

（1）

（2）

（3）

2 蚁群算法的应用优势

蚁群算法，又名蚂蚁算法，蚂蚁可以利用信息素的浓度大小从而寻找到觅食的最优路径。该算法的优点可以总结为：

2.1 并行分布式计算

每个蚂蚁都是独立的个体，在觅食过程中属于多起点同时启动，互不影响，从根本上分析该过程属于分布式的多Agent系统，整体蚁群最终任务的顺利完成不会由于某些个体的缺陷而受到影响。该算法具有真实可用性，并且可用于解决对单目标的优化或者对多目标的优化等重要问题。此外，蚂蚁算法还可进行并行计算。

2.2 鲁棒性

蚁群算法的最终结果与蚂蚁最初选择的路径无太大关系，在利用人工仿真蚂蚁进行问题求解过程中，不需要对其进行人工的修整。把问题简单化，可以和其他算法相互结合求解最优问题。

2.3 自组织性

蚁群算法组织指令的来源为系统内部，它不受外界环境的干扰，因此该算法具有自组织性。

2.4 正反馈性

蚂蚁对于最优路径的选择主要依靠路径上信息素浓度的多少，信息素的堆积是正反馈的过程，路径上信息素的含量越多则该路径被选择的几率就会越大，正反馈的作用是使整体能够更快的寻找到最优途径，正反馈在蚁群算法中处于重要地位。

2.5 易于实现

它是一种启发示算法，其计算复杂性为，整个算法的空间复杂度是：。

3 蚁群算法在智能交通领域的应用空间

蚁群算法在解决组合优化问题方面有着明显的优势，从而在智能交通领域也有着广泛的应用空间。

3.1 车辆路径导航

根据行车人员的需要，根据对实时路况信息的统计，系统可以智能的为其推荐最优路径，节省时间，节省资源。

3.2 动态车辆调度

当客户需要调度中心为其进行车辆服务时，调度中心要考虑到客户的情况，要考虑到效率的问题，要考虑到行车路线、行驶时间等问题。蚁群算法便可迅速得到合理的解决方案，使客户和调度中心均可受益。

3.3 车辆路径规划

面对多个客户不同的要求时，配送中心要根据实际情况进行车辆的配送，通过蚁群算法系统获取整体的最优路线，根据路线规划，及时进行车辆出发以满足客户要求，同时充分利用了道路资源和车辆资源。

3.4 公共交通智能化调度

利用先进的技术手段、大型数据库技术等动态地获取实时交通信息，实现对车辆的实时监控和调度，最终建立集运营指挥调度、综合业务通信及信息服务等为一体的智能化管理系统。

3.5 交通流量控制

通过蚁群算法简化复杂的道路交通网络，尽量使交通流量在各个道路上分布均匀，避免因流量过大而造成车辆的阻塞。及时了解交通流量情况，缓解了交通拥挤，降低了交通事故的发生率。

参考文献

[1]M.Dorigo，V.Maniezzo，A.Colom.Ant System：Optimization by a colony of cooperating agents.IEEE trans on SMC，1996，26（01）：28-41

[2]Eric BONABEAUB， Marco DORIGO，Guy THERAULAZ.AWARM intelligence： from natural to artificial systems[M].New York：Oxford University Press，1999

[3]杨海.蚁群算法及其在智能交通中的应用[D].济南：山东师范大学，2008：14-18

作者简介

白晓（1979-），女。工学硕士学位。现供职于厦门软件职业技术学院软件工程系。主要研究方向为软件工程、智能算法。

王娅（1983-），女。工学硕士学位。现供职于厦门软件职业技术学院软件工程系。主要研究方向为网络工程，软件设计。

路径规划典型算法第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高效航迹规化算法；西北工业大学的王景针对遗传算法易陷入局部最优的缺点和减小航迹随机搜索计算量，创新性地提出了限定搜索区域的分层遗传算法，提高了航迹寻优效率并有效地缩短了规划航迹长度；北京航空航天大学的文泾等通过将链接图法、最短路径法、遗传算法相结合，实现了高质量的任务规划并仿真验证。遗传算法渐已发展成为无人机航迹规划领域的主流研究方法。

通过上述研究情况可以看出，人工神经网络法、蚁群算法、人工势场法、遗传算法各有其比较适用范围，其中人工神经网络法适于约束具体化的局部寻优计算，蚁群算法具有并行性好、能与特定分工模型匹配的优势，人工势场法具有建模简单、快速性好、平滑性好、安全性好的特点适用于动态实时规划，遗传算法基于内在的概率选择机制、并行计算机制、按目标函数择优机制，适用于大规模规划区域的全局规划和用于任务分配问题的寻优，是当前任务规划领域的主流研究方法。