路径规划典型算法精选(九篇)
前言：一篇好文章的诞生，需要你不断地搜集资料、整理思路，本站小编为你收集了丰富的路径规划典型算法主题范文，仅供参考，欢迎阅读并收藏。
第1篇：路径规划典型算法范文
（吉林工程技术师范学院信息工程学院，吉林 长春 130052）
【摘 要】本文通过对比求解最短路径问题的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.
［7］王燕,蒋笑梅.配送中心全程规划[M].北京:机械工业出版社,2004.
第2篇：路径规划典型算法范文
单个机器人的路径规划是找出从起始点至终点的一条最短无碰路径。多个机器人的路径规划侧重考虑整个系统的最优路径，如系统的总耗时间最少路径或是系统总路径最短等。从目前国内外的研究来看，在规划多机器人路径时，更多考虑的是多机器人之间的协调和合作式的路径规划。
目前国内外多机器人路径规划研究方法分为传统方法、智能优化方法和其他方法三大类。其中传统方法主要有基于图论的方法（如可视图法、自由空间法、栅格法、Voronoi图法以及人工势场方法等）；智能优化方法主要有遗传算法、蚁群算法、免疫算法、神经网络、强化学习等；其他方法主要有动态规划、最优控制算法、模糊控制等。它们中的大部分都是从单个机器人路径规划方法扩展而来的。
1）传统方法多机器人路径规划传统方法的特点主要体现在基于图论的基础上。方法一般都是先将环境构建成一个图，然后再从图中寻找最优的路径。其优点是比较简单，比较容易实现；缺点是得到的路径有可能不是最优路径，而是次优路径。薄喜柱等人[4]提出的一种新路径规划方法的基本思想就是基于栅格类的环境表示和障碍地图的。而人工势场方法的基本思想是将移动机器人在环境中的运动视为一种虚拟人工受力场中的运动。障碍物对移动机器人产生斥力，目标点产生引力，引力和斥力周围由一定的算法产生相应的势，机器人在势场中受到抽象力作用,抽象力使得机器人绕过障碍物。其优点是适合未知环境下的规划，不会出现维数爆炸问题；但是人工势场法也容易陷入局部最小，并且存在丢失解的部分有用信息的可能。顾国昌等人[5]提出了引用总体势减小的动态调度技术的多机器人路径规划，较好地解决了这个问题。
2）智能优化方法多机器人路径规划的智能优化方（算）法是随着近年来智能计算发展而产生的一些新方法。其相对于传统方法更加智能化，且日益成为国内外研究的重点。
遗传算法是近年来计算智能研究的热点，作为一种基于群体进化的概率优化方法，适用于处理传统搜索算法难以解决的复杂和非线性问题，如多机器的路径规划问题。在路径规划中，其基本思想是先用链接图法把环境地图构建成一个路径节点链接网，将路径个体表达为路径中一系列中途节点，并转换为二进制串；然后进行遗传操作（如选择、交叉、复制、变异），经过N次进化，输出当前的最优个体即机器人的最优路径。遗传算法的缺点是运算速度不快，进化众多的规划要占据很大的存储空间和运算时间；优点是有效避免了局部极小值问题，且计算量较小。
孙树栋等人[6，7]在这方面较早地展开了研究，提出的基于集中协调思想的一种混合遗传算法来规划多机器人路径方法较好地解决了避障问题。但不足的是该方法必须建立环境地图，在环境未知情况下的规划没有得到很好的解决；且规划只能保证找到一个比较满意的解，在求解全局最优解时仍有局限。
文献[8]中提出的一种基于定长十进编码方法有效降低了遗传算法的编码难度，克服了已有的变长编码机制及定长二进制编码机制需特殊遗传操作算子和特殊解码的缺陷,使得算法更加简单有效。
智能计算的另一种常见的方法——蚁群算法属于随机搜索的仿生算法。其基本思想是模拟蚂蚁群体的觅食运动过程来实现寻优，通过蚂蚁群体中各个体之间的相互作用，分布、并行地解决组合优化问题。该算法同样比较适合解决多机器人的路径规划问题。
朱庆保[9]提出了在全局未知环境下多机器人运动蚂蚁导航算法。该方法将全局目标点映射到机器人视野域边界附近作为局部导航子目标，再由两组蚂蚁相互协作完成机器人视野域内局部最优路径的搜索，然后在此基础上进行与其他机器人的碰撞预测与避碰规划。因此，机器人的前进路径不断被动态修改，从而在每条局部优化路径引导下，使机器人沿一条全局优化的路径到达目标点。但其不足是在动态不确定的环境中路径规划时间开销剧增，而且机器人缺乏必要的学习，以至于整个机器人系统路径难以是最优路径。
强化学习[10，11](又称再激励学习)是一种重要的机器学习方法。它是一种智能体从环境状态到行为映射的学习，使得行为从环境中获得积累奖赏值最大。其原理如图1所示。
强化学习算法一般包含了两个步骤：a）从当前学习循环的值函数确定新的行为策略；b）在新的行为策略指导下，通过所获得的瞬时奖惩值对该策略进行评估。学习循环过程如下所示，直到值函数和策略收敛:
v0π1v1π2…v*π*v*
目前比较常见的强化学习方法有：MonteCarlo方法、动态规划方法、TD（时间差分）方法。其中TD算法包含Sarsa算法、Q学习算法以及Dyna-Q算法等。其Q值函数迭代公式分别为
TD（0）策略：V(si)V(si)+α[γi+1+γV(si+1)-V(si)]
Sarsa算法：Q(st,at)Q(st,at)+α[γt+1+γQ(st+1,at.+1)-Q(st,at)]Qs′学习算法：Qπ(s,a)=∑Pαss′[Rass′+γVπ(s′)]
近年来，基于强化学习的路径规划日益成为国内外学者研究的热点。M.J.Mataric[12]首次把强化学习引入到多机器人环境中。而基于强化学习的多机器人路径规划的优点主要体现在：无须建立精确的环境模型，简化了智能体的编程；无须构建环境地图；强化学习可以把路径规划、避碰、避障、协作等问题统一解决。
张芳等人[13]提出了基于再激励协调避障路径规划方法，把再励函数设计为基于行为分解的无模型非均匀结构，新的再励函数结构使得学习速度得以提高且有较好的鲁棒性。同时，证明了在路径规划中，机器人的趋向目标和避障行为密切相关，对反映各基本行为的再励函数取加权和来表示总的再励函数要优于取直接和的表示方式，也反映了再励函数设计得合理与否及其确切程度将影响再励学习的收敛速度。王醒策等人[14]在动态编队的强化学习算法方面展开了研究。宋一然[15]则提出了分段再励函数的强化学习方法进行路径规划。其缺点是学习次数较多、效率不高，当机器人数目增加时，它有可能面临维数灾难的困难。所以，基于强化学习的路径规划在多机器人环境下的学习将变得比较困难，需要对传统的强化学习加以优化，如基于人工神经网络的强化学习[16]等。
3)其他方法除了以上国内外几种比较常见且研究较多的方法外，还有唐振民等人[17]提出的基于动态规划思想的多机器人路径规划，把运筹学中的动态规划思想与Dijkstra算法引入到多机器人的路径规划中，用动态规划的基本思想来解决图论中的费用流问题和路径规划中的层级动态联盟问题。其选择距离邻近法作为联盟参考依据。一个机器人的邻居是指在地理位置上分布在这个机器人周围的其他机器人；与该机器人最近邻的机器人为第一层邻居,第一层邻居的邻居为该机器人的第二层邻居,依此类推。那么层级越高（即越近)的邻居,它满足协作要求的可能性越大。动态规划算法实质上是一种以空间换时间的技术，它在实现的过程中，必须存储产生过程中的各种状态，其空间复杂度要大于其他算法，故动态规划方法比较适合多机器人的全局路径规划。
孙茂相等人[18]提出了最优控制与智能决策相结合的多移动机器人路径规划方法。其首先构造一个以各机器人最优运动状态数据库为核心的实时专家系统,在离线状态下完成;然后各机器人在此专家系统的支持下,以最优规划策略为基础,采用速度迁移算法,自主决定其控制。该方法拥有较好的稳定性与复杂度。焦立男等人[19]提出的基于局部传感和通信的多机器人运动规划框架较好地解决了多机器人路径规划在局部在线规划的系统框架问题。沈捷等人[20]提出了保持队形的多移动机器人路径规划。以基于行为的导航算法为基础,把机器人队列的运动过程划分为正常运动、避障和恢复队形三个阶段。在避障阶段,引入虚拟机器人使队形保持部分完整;当队形被严重打乱时,规划机器人的局部目标位姿使队列快速恢复队形。其算法重点为避障机器人进入避障状态,暂时脱离队列,并以虚拟机器人代替避障机器人。
2多机器人避碰和避障
避障和避碰是多机器人路径规划研究中需要考虑的重点问题之一。避障和避碰主要讨论的内容有防止碰撞；冲突消解、避免拥塞；如何避免死锁。在路径规划中常见的多机器人避障方法[21]有主从控制法、动态优先法（建立在机器人之间的通信协商上）、交通规则法、速率调整法，以及障碍物膨胀法、基于人工势场的方法等。
目前国内外对于多机器人避障展开的研究还不是很多，比较典型的有徐潼等人[22]以Th.Fraichard的思想为基础，扩充并完善了路径/速度分解方案来协调多机器人,设立集中管理agent进行整体规划，为每个机器人规划路径；并根据优先级规则对运动特征进行分布式规划以避免机器人间的冲突。周明等人[23]提出分布式智能避撞规划系统，将原来比较复杂的大系统转换为相对简单的子系统问题,由各智能机器人依据任务要求和环境变化,独立调整自身运动状态,完成任务的分布式智能决策体系结构。任炏等人[24]提出了基于过程奖赏和优先扫除的强化学习多机器人系统的冲突消解方法。该算法能够显著减少冲突,避免死锁,提高了系统整体性能。欧锦军等人[25]提出了通过调整机器人的运动速度实现多机器人避碰，将避碰问题转换为高维线性空间的优化问题,并进一步将其转换为线性方程的求解。该方法的缺点是系统的复杂度较高、计算量太大。
人工势场方法的特点是计算简洁、实时性强、便于数学描述，且适合于多自由度机器人环境，但容易产生抖动和陷入局部极小。为了克服其缺点，景兴建等人[26]提出了人工协调场的方法，在传统排斥力场中增加一个协调力,并将吸引力、排斥力和协调力与局部环境下机器人的运动状态和运动要求结合起来，有效地保证机器人的安全性，提高机器人在复杂动态环境下行为决策的准确性和鲁棒性。
3多机器人协作和协调机制
多机器人间的运动协调[27~31]是多机器人路径规划的关键，也是多机器人与单机器人路径规划相区别的根本所在。多机器人系统在复杂动态实时环境下，由于受到时间、资源及任务要求的约束，需要在有限时间、资源的情况下进行资源分配、任务调配、冲突解决等协调合作问题，而机器人间的协调与协作，能够大大地提高整个系统的效率和鲁棒性，成为系统完成控制或解决任务的关键。
目前已有的协调方式分为集中式、分布式和混合式三种。在集中式协调中，集中规划器详细地规划出每个机器人的动作，通常的做法是将多个机器人看做一个多自由度的机器人进行规划；而分布式协调规划中，机器人之间进行合作，将一个任务分成多个子任务，根据各自的特点完成不同的子任务，从而共同完成总任务；混合式协调是集中式和分布式混合在一起的形式。
摘要：在查阅大量文献的基础上对多机器人路径规划的主要研究内容和研究现状进行了分析和总结，讨论了多机器人路径规划方法的评判标准，并阐述了研究遇到的瓶颈问题，展望了多机器人路径规划方法的发展趋势。
关键词：多机器人；路径规划；强化学习；评判准则
Abstract:Thispaperanalyzedandconcludedthemainmethodandcurrentresearchofthepathplanningresearchformultirobot.Thendiscussedthecriterionofpathplanningresearchformultirobotbasedlargeofliterature.Meanwhile,itexpoundedthebottleneckofthepathplanningresearchformultirobot，forecastedthefuturedevelopmentofmultirobotpathplanning.
Keywords:multirobot；pathplanning;reinforcementlearning;evaluatingcriteria
近年来，分布式人工智能(DAI)成为人工智能研究的一个重要分支。DAI研究大致可以分为DPS（distributedproblemsolving）和MAS（multiagentsystem）两个方面。一些从事机器人学的研究人员受多智能体系统研究的启发，将智能体概念应用于多机器人系统的研究中，将单个机器人视做一个能独立执行特定任务的智能体，并把这种多机器人系统称为多智能体机器人系统（MARS）。因此，本文中多机器人系统等同于多智能体机器人系统。目前，多机器人系统已经成为学术界研究的热点,而路径规划研究又是其核心部分。
机器人路径规划问题可以建模为一个带约束的优化问题，其包括地理环境信息建模、路径规划、定位和避障等任务，它是移动机器人导航与控制的基础。单个移动机器人路径规划研究一直是机器人研究的重点，且已经有许多成果[1~3]，例如在静态环境中常见的有连接图法、可视图法、切线图法、Voronoi图法、自由空间法、栅格法、拓扑法、链接图法、DempsterShafer证据理论建图等；动态环境中常见的有粒子群算法、免疫算法、遗传算法、神经网络、蚁群算法、模拟退火算法、人工势场法等。然而，多机器人路径规划研究比单个机器人路径规划要复杂得多，必须考虑多机器人系统中机器人之间的避碰机制、机器人之间的相互协作机制、通信机制等问题。
1多机器人路径规划方法
单个机器人的路径规划是找出从起始点至终点的一条最短无碰路径。多个机器人的路径规划侧重考虑整个系统的最优路径，如系统的总耗时间最少路径或是系统总路径最短等。从目前国内外的研究来看，在规划多机器人路径时，更多考虑的是多机器人之间的协调和合作式的路径规划。
目前国内外多机器人路径规划研究方法分为传统方法、智能优化方法和其他方法三大类。其中传统方法主要有基于图论的方法（如可视图法、自由空间法、栅格法、Voronoi图法以及人工势场方法等）；智能优化方法主要有遗传算法、蚁群算法、免疫算法、神经网络、强化学习等；其他方法主要有动态规划、最优控制算法、模糊控制等。它们中的大部分都是从单个机器人路径规划方法扩展而来的。
1）传统方法多机器人路径规划传统方法的特点主要体现在基于图论的基础上。方法一般都是先将环境构建成一个图，然后再从图中寻找最优的路径。其优点是比较简单，比较容易实现；缺点是得到的路径有可能不是最优路径，而是次优路径。薄喜柱等人[4]提出的一种新路径规划方法的基本思想就是基于栅格类的环境表示和障碍地图的。而人工势场方法的基本思想是将移动机器人在环境中的运动视为一种虚拟人工受力场中的运动。障碍物对移动机器人产生斥力，目标点产生引力，引力和斥力周围由一定的算法产生相应的势，机器人在势场中受到抽象力作用,抽象力使得机器人绕过障碍物。其优点是适合未知环境下的规划，不会出现维数爆炸问题；但是人工势场法也容易陷入局部最小，并且存在丢失解的部分有用信息的可能。顾国昌等人[5]提出了引用总体势减小的动态调度技术的多机器人路径规划，较好地解决了这个问题。
2）智能优化方法多机器人路径规划的智能优化方（算）法是随着近年来智能计算发展而产生的一些新方法。其相对于传统方法更加智能化，且日益成为国内外研究的重点。
遗传算法是近年来计算智能研究的热点，作为一种基于群体进化的概率优化方法，适用于处理传统搜索算法难以解决的复杂和非线性问题，如多机器的路径规划问题。在路径规划中，其基本思想是先用链接图法把环境地图构建成一个路径节点链接网，将路径个体表达为路径中一系列中途节点，并转换为二进制串；然后进行遗传操作（如选择、交叉、复制、变异），经过N次进化，输出当前的最优个体即机器人的最优路径。遗传算法的缺点是运算速度不快，进化众多的规划要占据很大的存储空间和运算时间；优点是有效避免了局部极小值问题，且计算量较小。
孙树栋等人[6，7]在这方面较早地展开了研究，提出的基于集中协调思想的一种混合遗传算法来规划多机器人路径方法较好地解决了避障问题。但不足的是该方法必须建立环境地图，在环境未知情况下的规划没有得到很好的解决；且规划只能保证找到一个比较满意的解，在求解全局最优解时仍有局限。
文献[8]中提出的一种基于定长十进编码方法有效降低了遗传算法的编码难度，克服了已有的变长编码机制及定长二进制编码机制需特殊遗传操作算子和特殊解码的缺陷,使得算法更加简单有效。
智能计算的另一种常见的方法——蚁群算法属于随机搜索的仿生算法。其基本思想是模拟蚂蚁群体的觅食运动过程来实现寻优，通过蚂蚁群体中各个体之间的相互作用，分布、并行地解决组合优化问题。该算法同样比较适合解决多机器人的路径规划问题。
朱庆保[9]提出了在全局未知环境下多机器人运动蚂蚁导航算法。该方法将全局目标点映射到机器人视野域边界附近作为局部导航子目标，再由两组蚂蚁相互协作完成机器人视野域内局部最优路径的搜索，然后在此基础上进行与其他机器人的碰撞预测与避碰规划。因此，机器人的前进路径不断被动态修改，从而在每条局部优化路径引导下，使机器人沿一条全局优化的路径到达目标点。但其不足是在动态不确定的环境中路径规划时间开销剧增，而且机器人缺乏必要的学习，以至于整个机器人系统路径难以是最优路径。
强化学习[10，11](又称再激励学习)是一种重要的机器学习方法。它是一种智能体从环境状态到行为映射的学习，使得行为从环境中获得积累奖赏值最大。其原理如图1所示。
强化学习算法一般包含了两个步骤：a）从当前学习循环的值函数确定新的行为策略；b）在新的行为策略指导下，通过所获得的瞬时奖惩值对该策略进行评估。学习循环过程如下所示，直到值函数和策略收敛:
v0π1v1π2…v*π*v*
目前比较常见的强化学习方法有：MonteCarlo方法、动态规划方法、TD（时间差分）方法。其中TD算法包含Sarsa算法、Q学习算法以及Dyna-Q算法等。其Q值函数迭代公式分别为
TD（0）策略：V(si)V(si)+α[γi+1+γV(si+1)-V(si)]
Sarsa算法：Q(st,at)Q(st,at)+α[γt+1+γQ(st+1,at.+1)-Q(st,at)]Qs′学习算法：Qπ(s,a)=∑Pαss′[Rass′+γVπ(s′)]
近年来，基于强化学习的路径规划日益成为国内外学者研究的热点。M.J.Mataric[12]首次把强化学习引入到多机器人环境中。而基于强化学习的多机器人路径规划的优点主要体现在：无须建立精确的环境模型，简化了智能体的编程；无须构建环境地图；强化学习可以把路径规划、避碰、避障、协作等问题统一解决。
张芳等人[13]提出了基于再激励协调避障路径规划方法，把再励函数设计为基于行为分解的无模型非均匀结构，新的再励函数结构使得学习速度得以提高且有较好的鲁棒性。同时，证明了在路径规划中，机器人的趋向目标和避障行为密切相关，对反映各基本行为的再励函数取加权和来表示总的再励函数要优于取直接和的表示方式，也反映了再励函数设计得合理与否及其确切程度将影响再励学习的收敛速度。王醒策等人[14]在动态编队的强化学习算法方面展开了研究。宋一然[15]则提出了分段再励函数的强化学习方法进行路径规划。其缺点是学习次数较多、效率不高，当机器人数目增加时，它有可能面临维数灾难的困难。所以，基于强化学习的路径规划在多机器人环境下的学习将变得比较困难，需要对传统的强化学习加以优化，如基于人工神经网络的强化学习[16]等。
3)其他方法除了以上国内外几种比较常见且研究较多的方法外，还有唐振民等人[17]提出的基于动态规划思想的多机器人路径规划，把运筹学中的动态规划思想与Dijkstra算法引入到多机器人的路径规划中，用动态规划的基本思想来解决图论中的费用流问题和路径规划中的层级动态联盟问题。其选择距离邻近法作为联盟参考依据。一个机器人的邻居是指在地理位置上分布在这个机器人周围的其他机器人；与该机器人最近邻的机器人为第一层邻居,第一层邻居的邻居为该机器人的第二层邻居,依此类推。那么层级越高（即越近)的邻居,它满足协作要求的可能性越大。动态规划算法实质上是一种以空间换时间的技术，它在实现的过程中，必须存储产生过程中的各种状态，其空间复杂度要大于其他算法，故动态规划方法比较适合多机器人的全局路径规划。
孙茂相等人[18]提出了最优控制与智能决策相结合的多移动机器人路径规划方法。其首先构造一个以各机器人最优运动状态数据库为核心的实时专家系统,在离线状态下完成;然后各机器人在此专家系统的支持下,以最优规划策略为基础,采用速度迁移算法,自主决定其控制。该方法拥有较好的稳定性与复杂度。焦立男等人[19]提出的基于局部传感和通信的多机器人运动规划框架较好地解决了多机器人路径规划在局部在线规划的系统框架问题。沈捷等人[20]提出了保持队形的多移动机器人路径规划。以基于行为的导航算法为基础,把机器人队列的运动过程划分为正常运动、避障和恢复队形三个阶段。在避障阶段,引入虚拟机器人使队形保持部分完整;当队形被严重打乱时,规划机器人的局部目标位姿使队列快速恢复队形。其算法重点为避障机器人进入避障状态,暂时脱离队列,并以虚拟机器人代替避障机器人。
2多机器人避碰和避障
避障和避碰是多机器人路径规划研究中需要考虑的重点问题之一。避障和避碰主要讨论的内容有防止碰撞；冲突消解、避免拥塞；如何避免死锁。在路径规划中常见的多机器人避障方法[21]有主从控制法、动态优先法（建立在机器人之间的通信协商上）、交通规则法、速率调整法，以及障碍物膨胀法、基于人工势场的方法等。
目前国内外对于多机器人避障展开的研究还不是很多，比较典型的有徐潼等人[22]以Th.Fraichard的思想为基础，扩充并完善了路径/速度分解方案来协调多机器人,设立集中管理agent进行整体规划，为每个机器人规划路径；并根据优先级规则对运动特征进行分布式规划以避免机器人间的冲突。周明等人[23]提出分布式智能避撞规划系统，将原来比较复杂的大系统转换为相对简单的子系统问题,由各智能机器人依据任务要求和环境变化,独立调整自身运动状态,完成任务的分布式智能决策体系结构。任炏等人[24]提出了基于过程奖赏和优先扫除的强化学习多机器人系统的冲突消解方法。该算法能够显著减少冲突,避免死锁,提高了系统整体性能。欧锦军等人[25]提出了通过调整机器人的运动速度实现多机器人避碰，将避碰问题转换为高维线性空间的优化问题,并进一步将其转换为线性方程的求解。该方法的缺点是系统的复杂度较高、计算量太大。
人工势场方法的特点是计算简洁、实时性强、便于数学描述，且适合于多自由度机器人环境，但容易产生抖动和陷入局部极小。为了克服其缺点，景兴建等人[26]提出了人工协调场的方法，在传统排斥力场中增加一个协调力,并将吸引力、排斥力和协调力与局部环境下机器人的运动状态和运动要求结合起来，有效地保证机器人的安全性，提高机器人在复杂动态环境下行为决策的准确性和鲁棒性。
3多机器人协作和协调机制
多机器人间的运动协调[27~31]是多机器人路径规划的关键，也是多机器人与单机器人路径规划相区别的根本所在。多机器人系统在复杂动态实时环境下，由于受到时间、资源及任务要求的约束，需要在有限时间、资源的情况下进行资源分配、任务调配、冲突解决等协调合作问题，而机器人间的协调与协作，能够大大地提高整个系统的效率和鲁棒性，成为系统完成控制或解决任务的关键。
目前已有的协调方式分为集中式、分布式和混合式三种。在集中式协调中，集中规划器详细地规划出每个机器人的动作，通常的做法是将多个机器人看做一个多自由度的机器人进行规划；而分布式协调规划中，机器人之间进行合作，将一个任务分成多个子任务，根据各自的特点完成不同的子任务，从而共同完成总任务；混合式协调是集中式和分布式混合在一起的形式。
多机器人间典型的协调方法[32]有合同网协议[33]、黑板模型、结果共享的协同方法、市场机制。近年来强化学习在多机器人协作方面也得到很好的应用，陈雪江[32]在基于强化学习的多机器人协作方面展开了研究，提出了多智能体协作的两层强化学习方法来求解在多智能体完全协作、有通信情况下的协作问题。其主要通过在单个智能体中构筑两层强化学习单元来实现：第一层强化学习单元负责学习智能体的联合任务协作策略；第二层强化学习单元负责学习在本智能体看来是最有效的行动策略。陈伟等人[34]提出基于多目标决策理论的多机器人协调方法；通过对环境的拓扑建模,从基于行为的机器人学角度出发,对任务进行分解并设计目标行为,以多目标行为决策理论作为决策支持,从而达到多机器人运动协调的目的。
4多机器人路径规划方(算)法的判优准则
通常评价机器人路径规划方(算)法的标准文献[35]有正确性、时间/空间复杂度、并行性、可靠性、扩展性、鲁棒性和学习。而多机器人的路径规划除了以上一些衡量标准之外，还需要考虑整个系统的最优化以及机器人间的协调性。
1)正确性是分析算法的最基本的原则之一。一般来说算法的正确性是指:在给定有效的输入数据后，算法经过有穷时间的计算能给出正确的答案。但在多机器人路径规划算法中，正确性主要指:路径规划算法要生成多个机器人协调运动的无碰安全路径;这条路径是优化的。
2)安全性一般指多机器人所生成的各路径中节点与障碍物有一定的距离。但在实际的应用背景下，有人认为安全性可以从两个方面来理解：a）狭义地讲，它就是机器人在行走过程中所做的功。在一定的条件下，它与路径长度准则是一致的。b）广义地讲，它是各种优化条件加权综合而得到的结果。
3)复杂度一个算法的复杂性高低体现在该算法所需要的计算机资源的多少上面。所需要的资源越多，该算法的复杂性越高；反之，所需要的资源越少，该算法的复杂性就越低。算法的复杂性包括时间复杂度和空间复杂度。
在多机器人的路径规划算法中，算法的复杂度分析显得尤为重要。一般地，单机器人路径规划算法的时空复杂度已经颇高，它们的数量级至少是O(n2)；多机器人的路径规划算法不仅是m-O(n2)(即m个机器人路径规划简单地叠加)，它们之间还存在着对运动空间竞争的冲突，面对不断变化的冲突的协调需要花费大量的时间和空间。通常多机器人的路径规划算法与机器人的个数呈指数关系O(km×n2)（k为常数）。这对多机器人路径规划算法的时间/空间复杂度控制是一个很严峻的考验。
4)并行性算法的并行性从算法设计、编写程序、编译和运行等多个不同的层次来体现。路径规划过程需要大量的计算，当处理的环境比较复杂，机器人工作的环境过于紧凑，尤其是机器人数量很多时，算法的时间/空间复杂度势必会成为算法效率的关键。因此，在算法设计和运行上的并行性是通常考虑的方法。对多个机器人的路径规划尽量采用分布式多进程的规划机制，以实现每个机器人路径规划的并行性。
5)可靠性把多个机器人及其工作环境看成是一个系统，多机器人处于它们各自的起始点时，称该系统处于初始状态；当它们处于各自的目标点时，称该系统处于目标状态。多机器人的路径规划就是在该系统的这两个状态间建立一串合理的状态变迁。这一状态变迁过程可能会历经许多状态，如果在状态变迁过程中，路径规划算法控制不好各状态间的转移关系，就会导致系统紊乱，出现机器人间的碰撞、找不到路径等恶性后果，使任务失败。所以这就对算法的可靠性和完备性提出了挑战。为了很好地克服这一困难，需要对系统的各种可能状态建模，分析它们相互间的关系，建立有限状态自动机模型或Petri网模型，并以此为指导，按照软件工程的思想，构造恰当的算法输入来对算法的可靠性进行检验。
6)可扩展性在多机器人的路径规划算法中，可扩展性主要是指一种路径规划算法在逻辑上，或者说在实现上能否容易地从2D空间扩展到3D空间，从低自由度扩展到高自由度，从较少的机器人数到更多的机器人数。可扩展性在各种路径规划算法之间没有一种量的比较标准，只能从实际的具体情况出发、从对环境描述的适宜程度出发、从算法解决这一问题的复杂度出发、从算法本身的自适应出发等来考虑。
7)鲁棒性和学习鲁棒性对于多机器人系统非常重要。因为许多应用，如路径规划要求连续的作业、系统中的单个机器人出现故障或被破坏，要求机器人利用剩余的资源仍然能够完成任务。学习是在线适应特定的任务。虽然通用的系统非常有用，但将它用于特定应用上时，通常需要调整一些参数。具有在线调整相关参数的能力是非常吸引人的，这在将体系结构转移到其他应用时可以节省许多工作。尤其是多机器人系统中机器人的自身学习和相互间的学习能够大大提高整个系统的效率和系统的稳定性。
8）最优化对动态环境有优化反应。由于有些应用领域涉及的是动态的环境条件，具有根据条件优化系统的反应能力成为能否成功的关键。
5结束语
综上所述，国内外研究者在多机器人路径规划取得了一些成果，但是在协作、学习、通信机制等方面仍面临很大的困难和不足。如何进一步提高机器人间的协调性，增强机器人自身以及相互间的学习以提高多机器人系统的效率和鲁棒性都有待深入研究。近年来无线通信技术得到长足发展,但在目前的技术条件下，在多机器人系统中实现所有机器人之间的点对点实时通信还有较大困难，这也是大多数多机器人系统仍然采用集中通信方式的主要原因。因此，如何降低多机器人系统对通信速度的依赖程度也是一个非常重要的问题。
总之,多机器人路径规划设计和实现是一项极其复杂的系统工程,展望其能在结合计算智能方法，如差分进化、遗传算法、粒子群算法、免疫算法、模糊逻辑算法、BP网络、人工势场的改进、模拟退火和环境建模方法等方面取得新的突破。
参考文献：
［1］WEISSG.Multiagentsystems:amodernapproachtodistributedmodernapproachtoartificialintelligence[M].Cambridge,Massachusetts：MITPress，1999：121-161.
[2]蔡自兴，徐光祐.人工智能及其应用:研究生用书[M].3版.北京：清华大学出版社，2004：124-198.
[3]谭民,王硕,曹志强.多机器人系统[M].北京：清华大学出版社，2005：6-81.
[4]薄喜柱,洪炳熔.动态环境下多移动机器人路径规划的一种新方法[J].机器人，2001,23（5）：407-410.
[5]顾国昌,李亚波.基于总体势减小的动态调度技术解决多机器人的路径规划[J].机器人，2001,23（2）：171-174.
[6]孙树栋,林茂.基于遗传算法的多移动机器人协调路径规划[J].自动化学报，2000,26（5）：672-676.
[7]周明,孙树栋,彭炎午.基于遗传算法的多机器人系统集中协调式路径规划[J].航空学报，2000,21（2）：146-149.
[8]CAIZixing,PENGZhihong.Cooperativecoevolutionaryadaptivegeneticalgorithminpathplanningofcooperativemultimobilerobotsystems[J].JournalofIntelligentandRoboticSystems:TheoryandApplications,2002,33(1):61-71.
[9]朱庆保.全局未知环境下多机器人运动蚂蚁导航算法[J].软件学报，2006,17（9）：1890-1898.
[10]SANDHOLMTW，CRITESRH.Multiagentreinforcementlearningintheiteratedprisoner’sdilemma[J].BioSystems，1996，37(1):147-166.
[11]高阳，陈世福，陆鑫.强化学习研究综述[J].自动化学报，2004,30（1）：
86-100.
[12]MATARICMJ.Interactionandintelligentbehavior[D].Massachusetls:DepartmentofElectricalEngineeringandComputerScience,MIT,1994.
[13]张芳,颜国正,林良明.基于再励学习的多移动机器人协调避障路径规划方法[J].计算机工程与应用，2003，39（3）：80-83.
[14]王醒策,张汝波,顾国昌.多机器人动态编队的强化学习算法研究[J].计算机研究与发展，2003,40（10）：1444-1450.
[15]宋一然.基于强化学习的多机器人路径规划方法[J].莆田学院学报，2006,13（2）：38-41.
[16]韩学东,洪炳熔.基于人工神经网络的多机器人协作学习研究[J].计算机工程与设计，2002,23（6）：1-3.
[17]唐振民,赵春霞,杨静宇，等.基于动态规划思想的多机器人路径规划[J].南京理工大学学报，2003,27（5）：610-615.
[18]孙茂相,周明,王艳红,等.多移动机器人实时最优运动规划[J].控制与决策，1998,
13（2）：125-130.
[19]焦立男,唐振民.基于局部传感和通讯的多机器人运动规划框架[J].计算机工程与应用，2007,43(17)：89-93.
[20]沈捷,费树岷，郑波.多移动机器人保持队形路径规划[J].东南大学学报，2005,35(3):391-395.
[21]MANSORMA，MORRISAS.Pathplanninginunknownenvironmentwithobstaclesusingvirtualwindow[J].JournalofIntelligentandRoboticSystems，1999，24(3):235-251.
[22]徐潼，唐振民.多机器人系统中的动态避碰规划[J].计算机工程，2003,29(17):
79-81,104.
[23]周明,孙茂相,尹朝万，等.多移动机器人分布式智能避撞规划系统[J].机器人，1999,21（2）：139-143.
[24]任炏,陈宗海.基于强化学习算法的多机器人系统的冲突消解的方法[J].控制与决策，2006,21(4):430-434,439.
[25]欧锦军,朱枫.一种多移动机器人避碰规划方法[J].机器人，2000,22(6):474-481.
[26]景兴建,王越超,谈大龙.基于人工协调场的多移动机器人实时协调避碰规划[J].控制理论与应用，2004,21(5):757-764.
[27]PANAITL,LUKES.Cooperativemultiagentlearning:thestateoftheart[J].AutonomousAgentsandMultiAgentSystems,2005,11(3):387-434.
[28]TZAFESTASCS,PROKOPIOUPA,TZAFESTASSG.Pathplanningandcontrolofacooperativethreerobotsystemmanipulatinglargeobjects[J].JournalofIntelligentandRoboticSystems，1998,22(2):99-116.
[29]薛宏涛,叶媛媛,沈林成，等.多智能体系统体系结构及协调机制研究综述[J].机器人，2001,23（1）：85-90.
[30]周风余,李贻斌,宋锐，等.基于混合式多智能体系统的协作多机器人系统研究[J].山东大学学报:工学版，2005,35(1):82-87.
[31]夏冰,张佐,张毅,等.基于多智能体系统的动态路径选择算法研究[J].公路交通科技，2003,20（1）：93-96.
[32]陈雪江.基于强化学习的多机器人协作机制研究[D].杭州：浙江工业大学，2004.
[33]SMITHR.Thecontractnetprotocol:highlevelcommunicationandcontrolinadistributedproblemsolver[J].IEEETransonComputer,1980，C-29(12):1104-1113.
[34]陈伟,张铭钧,孟宪松.基于多目标决策理论的多机器人协调方法[J].哈尔滨工程大学学报，2003,24（3）：308-312.
[35]李亚波.多机器人的路径规划与协调[D].哈尔滨：哈尔滨工程大学，2000.
摘要：在查阅大量文献的基础上对多机器人路径规划的主要研究内容和研究现状进行了分析和总结，讨论了多机器人路径规划方法的评判标准，并阐述了研究遇到的瓶颈问题，展望了多机器人路径规划方法的发展趋势。
第3篇：路径规划典型算法范文
【关键词】 图论；贪心算法；应用
在求解一些问题中，贪心算法作为一种优解的有效算法，能够快速地、有效地解决很多实际存在的问题，被广泛运用在图论领域中.虽然贪心算法也有不足之处，如应用范畴比较狭窄，但对于图论有些问题，贪心算法既可以正确求解，也有着很高的应用价值.
一、概述贪心算法
贪心算法是一种分级处理方法，在决策中，贪心算法总会对当前情况进行最好的选择.与动态规划算法不同的是，贪心算法并不考虑问题的整体最优，而只是考虑某种意义上的局部最优.因此，贪心算法并未结合所有问题求得整体最优解，但对于一些问题来讲，它可以求得整体最优解.在一些状况下，虽然贪心算法并未得到整体最优解，但是能够得到与最优解的近似，所以，贪心算法有着很高的应用价值.
二、贪心算法的求解步骤
1.基本要素.对于一个切实存在的问题，怎样才能知道是否能够用贪心算法求解并得到最优解，在具体应用过程中，人们研究和总结出两个重要性质：一是，贪心选择的性质；二是，最优子结构的性质.很多使用贪心方法求解问题中都会具有这两个性质.
2.步骤的求解.贪心算法的求解先要明确出一个贪心准则，每步都按照此准则进行方案优化.排序各个问题，排一次输一个量.假若这个输入与已构成的量最优解加在一起后很难出现可行解，这样就不能将输入值与这部分解相融合.
三、使用贪心算法对单源点最短路径求解的可行性
在图论中存在一个很典型的问题：单源点最短路径这一问题.对问题的描述如下：对于有向带权图G=（V，E），其每条边上的权重都是非负实数.选定在V中某个顶点，称为源点.此问题求解的是从源点到图G中其各个顶点的最短路径长度.在这里所讲的长度就是指通过各个边的权值总和.Dijkstra正是运用贪心算法求解这个问题，用所有路径长度之和作为最小贪心准则，所以，每个单独路径都要有最小长度.实现此算法步骤是：将顶点集合分为两个子集，即：S，V-S.在子集S中将所有最短路径顶点都已求得.在初始时，集合S中有源点，然后，将其做贪心来扩充此集合.选取在G中顶点V，从源点到V点并通过S中顶点的路径称之为源点到顶点V的特殊路径，设置数组Dirt记录各个顶点对应的最短特殊路径长度.
四、应用贪心算法求解最小生成树的可行性
（一）Kruskal算法的应用
对于最小生成树图论的讨论是非常有价值和有意义的，具体描述包括如下几点：已知无项连通带权图 G=（V，E）.E中每条边（u，v）的权值设为c[u][v].求图G的生成树G′，使G′上各边权值的总和是所有生成树中各边权值中总和最小.此问题被称为最小生成树问题.求解最小生成树问题有很 多种方法，其中Kruskal、Prim等算法应用最为广泛.
Kruskal算法与Prim算法相比，在生成最小生成树中，前者比后者更加简洁明了.一是将无向连通带权图 G的n个顶点视为n个 独立的分支，但这几个分支间是互相连通的.并根据权值给各个边从小至大展_排序.将第一条边与连通分支进行相连，之后按照权值递增顺序检查剩下的各个边，若加入此边就构成回路，就抛弃此边，然后，考察余下每条边；反之，加入此边并不会构成回路，就将此边加入.
（二）Prim算法的应用
Prim算法思想是：一是在图中选取一个顶点u，将u置于顶点集合子集S里.若S是顶点集合V的真子集，就应该将顶点加入子集S中，但要满足iI ^ S，jI ^ V-S条件，并且C[i][j]是权值最小的一个边.根据同样的步骤进行贪心选择，直至子集S=V结束.在这时，已被选取的边就构成了在图G中的一颗小生成树.
在对比上文两种方法后才发现，这两种方法虽然都是使用贪心算法解决问题，但由于贪心准则不同的影响，最小生成树选边与求解步骤也是不同的，所以，在实际应用贪心算法中，需要因地制宜地应用，盲目、一味地应用贪心算法，很容易引发其他方面的问题，但相对而言，贪心算法还是值得大范围地应用的.
第4篇：路径规划典型算法范文
关键词：配送区域划分;配送路径优化;算法
中图分类号：F252.14 文献标识码：A
Abstract： The demand of logistics industry and the competitive landscape have changed. The development way of logistics enterprise is from quantity expansion to connotation construction. More and more enterprise study to enhance the competitiveness from three aspects： system， management， and technology. It can make direct economic sense to optimize logistics system. It will be the focus of enterprise development and promotion. It has prevalent meaning of guidance. In this paper， from the angle of enterprise application， I try to use the cluster analysis method determine the distribution region， then use the improved ant colony algorithm to optimize vehicle routing so that we can reduce the cost， and improve the benefits.
Key words： distribution regional division; distribution vehicle routing optimization; algorithm
0 引 言
流通领域中，许多物流配送企业借助外部经济的发展，实现了规模扩张与快速发展，但对如何控制成本，提高运营效率的迫切性并不强。现在随着经营环境的变化，物流需求量更大，客户、网络更复杂，对服务的要求更多样化。但面临的竞争更加激烈，不管是从事跨区域配送还是城市配送，首先需要考虑顾客服务水平，赢得客户的认可，然后考虑配送运营的成本问题，因而如何创新物流服务，提高运营效率和控制日常运营成本成为每个配送企业需要时刻思考的问题。
传统的基于经验的方法，在企业规模有限，客户数量不是非常多，配送网络相对简单的情况下，只要员工和管理者技能过关，执行力好，都应该能够较好地完成配送任务，获得企业的发展。但是随着销售区域扩大，客户数量的不断增加，客户需求持续增长，配送业务量大增，配送周期缩短，配送线路更复杂，并且需求的随机性、变动性加大，光凭经验和手工安排，已无法做到配送计划的优化，必须借助于统计分析、利用数学模型和智能算法，才能获得较好的配送计划，节省时间，提高效率。本文就是针对这些问题，从企业应用的角度，提出先合理划分配送区域，再优化配送路线的方法，从而达到降低成本，提高竞争力的目标。
1 论文总体思路综述
排单和车辆调度是整个配送计划和作业实施的核心，是配送任务和客户服务按时完成的有力保证。
传统的订单排单和车辆调度、路线安排都是由公司里业务能手来完成，送货区域大了，客户多了，这项工作的效率和完成工作的成本控制都会不理想，现在常用的智能优化方法，把它作为一个典型的VSP问题，建立数学模型，利用智能化的算法，求解可行的配送路径规划，作为理论研究，这样的做法是有意义的。但是有两个问题：（1）这个模型数据的收集整理工作量特别大，计算过程也较长，因而成本不会低。（2）模型本身一定要适合实际的作业过程，这就需要有一个不断测试和优化的过程，并且还要适应每天的动态变化，否则反而会影响到日常的作业过程。许多研究理论完备、精深，但是在适应产业化运营时，工程上的可实现性还有待提高和完善。因而影响了这些很有价值的研究在企业实际中的运用。
本文的研究并不针对配送路径规划做理论上的深究，而是立足实际应用，在可接受的范围内，利用较简易实用的智能优化方法，在较短的时间内，以较低的成本获得相对优化的配送路径规划方案。不求最佳，但求有效。为今后电子排单和送货线路优化软件的开发和应用作必要的铺垫。
具体设想：第一步，利用聚类分析法对配送区域进行合理分区，先把复杂问题简单化。第二步，每个分区内就是个典型的TSP问题，有很成熟的解决办法。在平衡好各分区工作时间安排后，就能很快获得较理想的配送方案。
重点是第一步，分区时一定要考虑到客户位置、需求量、车辆载重、作业时间均衡限制等因素，需要花费好多功夫。
2 配送区域动态优化及其方法
2.1 配送区域的初始划分方法。配送区域优化方法对最终优化的结果有很大的影响，因而合理的划分方法的选择十分重要，目前常用的划分方法有扫描法和聚类算法，在配送客户有限、区域较小时运用扫描法就可以了，但是当客户数量很多，区域较大，又要考虑约束条件时，聚类算法就是我们必然的选择了，聚类算法中K-means比较成熟，操作简单，原理是：把大量d维（二维）数据对象n个聚集成k个聚类k
在运用聚类分析法时有几个问题要注意：第一，k的选择，以一天送货总量/单车载重量，也可以放宽一些，到：一天送货总量/单车载重量+1。第二，k个聚类内的密度，分区密度大，效率高，成本低。第三，每个分区内工作时间大体相当，这样便于运行的稳定，进行成本控制和人员、车辆的考核。第四，每个聚类间不重合。做到这样分区效果会比较好。
传统的K-means聚类法，k个聚类区内，初始点是随机产生的，运行时间长，收敛效果差。基于均衡化考虑，在配送对象分布不均匀时，用密度法效果较好，初始中心点以密度来定义，运用两点间欧氏距离方法，求解所有对象间的相互距离，并求平均数，用meanD表示，确定领域半径R=■，n是对象数目，coefR是半径调节系数，0
coefR=0.13时，效果最好。如果使用平均欧氏距离还不理想，可增加距离长度，甚至用最大距离选择法，收敛速度比较快。
在配送对象分布较均匀时，可考虑用网格法，效果较好，整个配送区域划分用k=Q/q，k为初始点个数，假设k=mn，将地图划分成m行n列，以每格中心点为初始点，通过网格内的反复聚类运算，达到收敛，获得网格稳定的聚类中心。
2.2 分区内配送工作量的均衡。这样就完成了配送区域的初步划分，但是没有考虑各个分区内工作量的均衡问题，如果工作量不均衡，对于客户服务水平的保证，成本的控制，作业的安排，人员、车辆的考核都存在问题。
在实际的物流企业配送作业过程中，一般一辆车一天也就送货10多家或20来家，多余的时间要用于收款，与公司财务部门交账，核算出车相关费用，所以不考虑同一车同一天出车多次的情况，多次出车待以后深入探讨。那么就意味着每个分区就是一辆车一条线路，把问题大大简化了，需要说明的是：这种方法对于配送规模不是特别大的单个城市配送是适用的，也具有广泛性。
各分区内的每日配送工作量是以配送作业耗用时间来衡量的，耗用时间有两部分构成：（1）车辆行驶时间;（2）客户服务时间。由于配送分区有限，每个分区内的客户数量不是很多，可以采用实地测时的方式，把每条线路的配送时间统计出来，这是一种手工办法，但比较符合实际，各线路时间分别为T■，T■，T■，T■，…，T■，从中选出最大值T■，最小值T■，用经验法确定允许的差值，然后来调整超过差值的分区内的客户，从而使得各区作业时间基本均衡。
如果客户数量众多，分区也较复杂，就需要借助统计学方法，通过对样本线路车辆行驶时间以及服务时间，拟合出分区作业时间函数，然后，计算出所有线路作业时间，即使分区重新调整，线路重新组合，仍可以很快计算出线路作业时间。本文不在这个方面进行深入探讨。
2.3 重新组合客户，确定最终区域划分。观察各线路作业时间超过允许差值的部分，由大到小来调整，将离聚类中心最远的数据点弹出，使本区T值下降，直至在差值以内，将弹出点加入到临近的不足均衡作业时间的分区内，如果临近分区作业时间超过允许差值，这个点就不能弹出，只能弹出另外的次远数据点，以此类推，任何一个数据点只能弹出一次，直到所有数据点和分区调整完毕。
这样最终确定的分区，既能做到区域划分紧密，效率、成本更低，又能做到各区作业时间均衡，便于工作指派，车辆、人员核算。
以上是本文的第一部分工作，也是最有意义的工作，确定好合理的区域划分，不仅是配送作业合理化的重要步骤，也是业务人员访销工作和客户服务的重要依据。
3 基于改进蚁群算法的分区线路优化方法
分区内线路安排，就是一辆送货车由DC出发，依次经过分区内每一个客户点，完成送货后返回DC，求出近似最优的行车顺序，这是个典型的旅行商问题（Traveling Salesman Problem，TSP），TSP是NP完全问题，解法很多，有精确算法，也有启发式算法，目前许多智能算法就属于启发式算法，可以解决较复杂的线路优化问题，对于一般线路优化也能做得更准确，这里介绍蚁群算法解决实际问题。原因是蚁群算法与其他启发式算法相比，在求解性能上，具有较强的鲁棒性和搜索较好解的能力，是一种分布式的并行算法，一种正反馈算法，易于与其它方法结合。克服基本算法缺点，改善算法性能。
3.1 蚁群算法简介。蚁群算法（Ant Colony Algorithm， ACA）是由意大利学者M.Dorigo等人于20世纪90年代初提出的一种新的模拟进化算法，其真实地模拟了自然界蚂蚁群体的觅食行为。M.Dorigo等人将其用于解决旅行商问题TSP，并取得了较好的实验结果。
蚁群算法用于解决优化问题的基本思路是：用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素数量较多，随时间推移，较短路径上积累的信息素浓度逐步增高，选择该路线的蚂蚁数量也越来越多，最终整个蚂蚁会在正反馈的作用下集中到最佳线路上，这个路线就是最有解。
3.2 用蚁群算法解决分区线路优化问题。以下用数学语言描述蚁群算法的整个过程：设蚂蚁数量为m，分区内客户数量为n，m≤n，客户点i与客户点j之间距离用d■i，j=1，2，3，…，n表示，t时刻i与j连接路径上的信息素浓度为τ■t。初始时刻各路径上的信息素浓度相同。
位于客户点i的第k只蚂蚁选择客户点j的概率为：
P■i，j=■ （1）
其中：
τi，j表示边i，j上的信息素浓度;
ηi，j是启发信息，d是客户点i和j之间的距离;α和β反映了信息素与启发信息的相对重要性;
tabu■表示蚂蚁k已经访问过的城市列表。
当所有蚂蚁完成周游后，按以下公式进行信息素更新。
τ■t+n=ρ・τ■t+Δτ■
Δτ■=■Δτ■■
其中：ρ为小于1的常数，表示信息的持久性。
Δτ■■=■ （3）
其中：Q为常数;l■表示第k只蚂蚁在本次迭代中走过的路径，L■为路径长度。
蚁群算法解决TSP问题具体步骤：（1）基本参数设置：包括蚂蚁数m，信息素重要程度因子0≤α≤5，启发函数重要因子1≤β≤5，信息素消逝参数0.1≤ρ≤0.99，信息素释放总量10≤Q≤10 000，最大迭代次数iter_max，迭代次数初值iter=1。用试验方法确定α、β、ρ、Q值，以获得较优的组合，有助于改进基本蚁群算法，提高整体优化效果，并缩短运算时间。（2）初始解的求解：利用最近邻算法，以缩短算法运算时间，并以此算法产生初始解的路径长度作为产生初始信息素的基础。（3）构建解空间：将各个蚂蚁随机地置于不同出发点，对每个蚂蚁，按公式（1）计算其下一个待访问的网点，直到所有蚂蚁访问完区域内所有网点。（4）更新信息素：计算各个蚂蚁经过的路径长度L■k=1，2，…，m，记录当前迭代次数中的最优解。同时，根据（2）式和（3）式对各个网点连接路径上的信息素浓度进行更新。（5）判断是否终止：若iter
蚁群算法如结合其他启发式算法，建立混合算法，能够解决许多现实问题，达到较好运算效果，结合具体问题，可以深入研究。
4 本文的局限与进一步研究的方向
本文的研究更多地从实际运用和操作的便利角度出发，因而力求方法简便，运算效率较高，然而实际问题远比设想复杂，物流系统的优化应该是整体性的优化。本文只是做了配送区域的合理划分，在此基础上，对区域内配送路径进行优化，只是送货过程的优化，完整的过程还包括客户服务水平，合理的库存水平，以及配送中心选址，服务地点（卸货点）的设置等，只有这些因素都考虑到了，才能真正实现配送系统的优化。另外，还有静态分析和动态分析的区别，大区域划分保持相对静态，区域间根据每日具体的业务需求做必要的动态调整，这部分可借助人工安排，也可参考软件，保持一定的灵活性。整个配送系统的研究千头万绪，在进一步的研究中，首先需要把销售系统的优化结合进来，客户前端的需求和库存决定着后面的订单以及配送，业务员对零售网点的访销，一方面对接客户服务，体现公司的客户服务水平，另一方面，对接订单的处理以及最终的配送工作，业务人员访销作业的系统性安排，以及客户、配送中心信息的一体化都有赖于业务访销与配送作业的综合优化。
因而，配送区域合理划分、送货线路优化以至于整个物流系统，销售系统、供应系统的不断优化，对于物流企业、社会物流以及整个经济运行系统是非常有意义的，对于众多转型中，缺乏专业知识和技术的中小物流企业，有着普遍意义，值得重视。
参考文献：
[1] 陈子侠，等. 杭烟物流与送货路线优化[J]. 物流技术，2003（8）：38-40.
[2] 王勇，池吉. 物流配送路线及配送时间的优化分析[J]. 重庆交通大学学报，2008（4）：647-650.
第5篇：路径规划典型算法范文
[关键词]成品油配送；路径优化；时间窗；数学模型
[DOI]1013939/jcnkizgsc201718184
1引言
库存和运输是物流系统最重要的功能要素，是物流获得“时间价值”和“空间价值”的两大主要环节，它们的耗费约占物流总成本的2/3。[1]库存路径问题主要是研究一个供应商向多个顾客提供配送服务时，在满足顾客的需求量、配送时间窗以及库存容量限制等约束条件的情况下，使总成本达到最小。BirgerRaa[2-3]等人于2007年在研究库存路径问题（Inventory Routing Problem）时，假设顾客的需求率是恒定的，在不引起缺货的情况下，以平均配送和库存成本最小化为目标得出周期性补货策略，并运用粒子群算法对该模型进行了求解。2008年又在模型中加入了车辆使用成本，同时运用插入遗传算法对模型分步进行求解。Kunpeng Li[4]等人在解决成品油配送问题时，考虑车辆容载量、加油站齑嫒萘俊⒊盗臼量等因素的情况下以最大路径遍历时间的最小化为目标函数建立数学模型，并设计了禁忌搜索算法。赵达[5]等人在2006年以零售商系统下随机需求的IRP为研究对象，提出了一种基于马尔科夫决策过程与修正的C-W节约算法的启发式分解算法。我们在2016年以工作量均衡为目标，研究了带硬时间窗约束的成品油二次配送路径优化问题，建立了整数规划模型并设计了求解模型的算法。[6]
成品油配送问题是一种典型的库存路径问题，由于各个加油站的成品油均储存在容量有限的油罐中，为加油站配送成品油的车辆也是特定的油罐车，为了满足加油站的日常销售，油库需要每天向加油站配送成品油，才能保证销售过程中不出现断货。在研究成品油库存路径问题时，如果加油站的销售速率为常数，则可以根据加油站当前的存储量确定出一段时间内的需求量，进一步根据配送车辆的容量以及油罐的容量限制，确定出配送时间窗。这种条件下成品油配送库存路径问题就简化成了带容量和时间窗限制的车辆路径问题。本文主要研究简化以后的成品油配送车辆路径优化问题，建立该问题的数学模型并设计求解模型的蚁群算法。
2问题描述
成品油的配送路径优化问题可以描述为：有一个油库，同时向多个加油站提供某一种型号的成品油；已知加油站在某一时间段内对成品油的需求量；每个加油站有对应的硬时间窗，成品油配送车辆不能早于也不能晚于加油站时间窗进行供油；配送车辆在每个加油站卸油均需要消耗一定的时间；为加油站配送成品油的油罐车为单舱车，且油罐车的数量充足；每辆油罐车的容载量、固定使用成本、单位距离行驶成本均不相同；每辆车可以同时向多个加油站供油，每个加油站只能接受一辆油罐车为其供油；每辆油罐车的平均行驶速度相同，均为50km/h。系统的目标就是在已知各个加油站的需求量以及相互之间的距离的情况下，求使得系统总运行成本最小的配送方案。
在成品油配送过程中，假设配送车辆从油库出发为若干个加油站配送成品油，完成配送任务后返回油库。同一辆配送车服务的若干个加油站的总需求量不能超过车辆的容载量。由于每个加油站只能接受一辆油罐车为其供油，因此为加油站供油的油罐车在该加油站的卸油量与加油站的需求量相等。油罐车在到达加油站时开始卸油，开始卸油的时刻应处于该加油站的时间窗内。每辆车在卸油时会耗费一定的时间，卸油耗费的时间与卸油量成正比，且当车辆在一个加油站完成卸油时会立即驶往下一个加油站。
由于油库的车辆数量充足以及每辆车的容量、固定成本及可变成本不同，因此，需要从可用车辆中选择一部分为加油站送油，并进一步确定出每一辆油罐车服务的加油站集合及配送路径，使得总配送成本最低。每辆选中的油罐车的配送路径可以用油库及加油站的序号按照配送顺序依次表示。如0-1-5-3-0表示一辆配送车辆从油库0点出发，依次为加油站1、5、3配送成品油，配送结束后返回油库。
5结论
成品油配送路径优化问题是成品油二次配送过程中的关键的问题。当制订成品油配送计划时，在保证加油站不断油的情况下，降低配送成本是最主要的考虑因素之一。本文研究了各个加油站的需求量确定的情况下，在满足各个加油站需求量及服务时间窗限制的前提下，使系统的运行成本最低的成品油配送路径优化问题。建立了以系统总运行成本最低为目标的整数规划模型，最后通过算例对模型进行了验证。
本文只考虑了确定需求下单一品种成品油的配送问题，未考虑车辆的分舱及满载约束限制。在实际的成品油配送中，各个加油站的需求量往往是一个随机变量，并且不同品种的成品油需求量服从的随机变量分布不同，油罐车的容量和隔舱数也不同，而且要求满载运输。另外，在本文为了简化问题，假设一个加油站只能被一辆车服务，实际中一个加油站可以被多辆车服务。在后续的研究中，我们将逐渐加入这些约束条件，建立更加符合实际情况的成品油配送路径优化模型，为解决实际问题提供理论依据。
参考文献：
[1]Herer Y，Levy RThe Metered Inventory Routing Problem，an Integrative Heuristic Algorithm[J].International Journal of Production Economics，1997，51（1）：69-81
[2]BirgerRaa，El-HoussaineAghezzafA Practical Solution Approach for the Cyclic Inventory Routing Problem[J].European Journal of Operational Research，2007，1922：429-441
[3]BirgerRaaNew Models and Algorithms forthe Cyclic Inventory Routing Problem[J].4OR，2008，61∶97-100
[4]Kunpeng Li，Bin Chen，AppaIyer Sivakumar，Yong WuAn InventoryCrouting Problem with the Objective of Travel Time Minimization[J].European Journal of Operational Research，2014：936-945
第6篇：路径规划典型算法范文
关键词：最短路径；神经网络；多层前向反馈网络（MLFN）；激活函数
中图分类号：TP18 文献标识码：A
1 引言（Introduction）
现代通信网络广泛使用TCP/IP网络体系结构，在TCP/IP网络体系结构中，网际层是很重要的网络层次，网际层的主要功能就是为数据包（网际层的数据信息单元）寻找路径并转发数据包，这个过程称为路由选择，路由选择是网际层最重要的功能，特别是在包交换网络中。路由选择技术对网络性能有很大的影响，最理想的路由算法就是为源节点与目标节点寻找最短路径并高速转发数据，并且能够避免数据包的丢失。不过要寻找两个节点之间的最短路径是众所周知的难题，目前广泛研究的最短路径算法都具有许多约束条件[1]。
在包交换网络中，两个主机之间的数据包通信一般通过如下方式：发送主机将数据组织成数据块，一般称为包，包中封装有目标主机的网络地址（一般称为IP地址），网络中的路由设备根据包中携带的目标地址为数据包寻找路径并转发，最终到达目标主机。一个路由策略的主要目标就是尽量减少IP数据包的传输延迟，尽最大可能传输数据包。影响数据包平均传输延迟时间的主要因素有网络的可靠性以及网络带宽容量和网络路由等因素的影响，其中路由对网络性能影响非常重大。因此一个理想的路由算法[2]应该尽量在规定的时间内找到最优路径来满足网络的服务质量（QoS）。
目前的最短路径搜索算法主要有：
（1）Bellman-Ford的动态规划算法，这种算法主要用于求含负权值的单源点最短路径算法。
（2）与Bellman算法类似的Dijkstra标记算法（也称迪杰斯特拉算法），其按路径长度递增依次产生最短路径。
当前在大多数的包交换网络中，最短路径计算都应用于网际层路由算法中，特别是网络连接的链路具有权值，权值反映的是每条传输链路的传输代价，包括传输容量、网络拥塞、传输状态（如包队列头分组延迟以及网络故障等）。最短路径问题可以归结为在源节点和目标节点之间寻找成本最小路径问题，换句话说，最短路径路由问题其实是在许多设计和规划中都需要的经典组合优化问题，神经网络技术[3]就可以解决这个复杂的问题。
2 多层前向反馈网络（MultiLayer forward feedback
network）
多层次网络，顾名思义由多个功能层次组成的网络，这种结构的网络，除了数据输出层和数据输入层意外，还包括隐藏层（或者隐藏单元），每个层次各司其职。多层前向反馈网络是神经网络中一种典型的分层结构，输入层神经元信息从输入层进入隐藏层神经元网络后逐层向前传递直至输出层，神经元与神经元之间的连接的权值称为链接权值。现代网络一般都是分层次的结构网络，其中最著名的有ISO七层体系结构与Internet实际使用的TCP/IP体系结构，网络的体系结构都是分层次的，都是多层次的网络结构。通信网络中的网络节点对应神经网络的神经元，节点与节点之间有链接链路，每条链路具有相应的链路权重，对应神经元节点与输出节点之间的链接链路也具有链接权重值，两者之间关系如图1所示。
图1 多层前向反馈网图
Fig.1 Multilayer forward feedback
3 反向传输网络（Back propagation network）
反向传输是训练多层人工神经网络的一种系统方法，它需要具有很好的数学基础，并具有广泛的应用潜力。
与生物神经元类似，人工神经元接收代表其他神经元输出的大量数据，每个输入都乘以链路链接权值，类似于生物神经中的突触强度，汇总后的输入加权值通过激活函数处理最后确定神经元的输出图，如图2所示。
图2 反向传输多层训练网图
Fig.2 Back propagation training network
其中的净值输入：
考虑到线值，相应的神经元输入由下面的公式给出：
=
相应的输出（激活值）使用非线性变换函数f给出。
4 激活函数（Activation function）
最后的数据输出是通过称为激活函数的非线性过滤函数产生的（有时称为变换函数），常见的选择是S函数或逻辑函数。如图3所示，其中α是斜率参数，当函数的改变在两个渐进值之间变化时，用于调整函数突发。
图3 逻辑函数
Fig.3 Logistic function
多个激活函数称为阶跃函数，或Heaviside函数，如图4所示。
图4 Heaviside函数
Fig.4 Heaviside function
5 学习速率（Learning rate）
大多数网络结构在学习过程中都要对权值w和v进行调整。学习速率系数的选择决定了权重调整的大小，从而影响每次迭代的收敛速度，差的系数选择可能导致收敛失败。如果学习速率系数过大，搜索路径将发生振荡，导致后面的收敛速度更慢。而如果系数过小，后面的过程将以很小的步骤进行，也会导致收敛速度减慢。
6 问题陈述（Statements）
考虑一个加权有向图G=（V；E），V是有n个顶点的集合，E是一组有序的m条边。固定成本Cij与图G中顶点i到顶点j的边相关联。在运输系统或机器人系统中，物理成本可能就是两个顶点间的距离，从一个顶点到另一个顶点也需要时间和精力。在一个通信系统中，成本可以由传输时间，节点到节点间链路容量来确定。一般来说，成本系数矩阵【Cij】不一定是对称的，比如，从顶点i到顶点j的成本不一定与从顶点j到顶点i的成本一样。此外，一些顶点间的边可能也不存在，也就是m可能小于n2（也就是m
学习算法如下：
如果输出是正确的，那就不用做权重调整了。
Wij（k+1）=Wijk
如果输出是1，但是结果本来应该为0，那么在活动输入链路中将降低权重值。
Wij（k+1）=Wijk-α.xi，其中α是学习速率（因子）。
如果输出是0，但是结果本来应该为1，那么在活动输入链路中将增加权重值。
Wij（k+1）=Wijk+α.xi
Wij（k+1）是调整后的权重值，而Wijk是调整前的权重值。
Rosenblatts算法如下：
（1）用（n+1）个输入神经元X0，X1，X2，…，Xn创建感知器，其中X=1是偏置输入，O是输出神经元。
（2）初始化随机权重W=（W0，W1…Wn）。
（3）遍历训练输入模式X集合，使用权值为每个输入模式j计算输入加权后的总和。
（4）使用阶梯函数计算输出Y。
Y=f（netj）=1 netj>0
=0 其他
（5）对每个输入模式j，用目标输出Yj与计算得到的Yj进行比较，是否对所有的输入模式都正确分类并都存在且输出了权重值。
如果计算的输出Yj是1，而结果本来为0，用下面给出的公式修改权值。
Wi=Wi-α.xi
如果计算的输出Yj是0，而结果本来应该为1，就使用如下公式修改权值。
Wi=Wi+α.xi其中，α是学习因子。
（7）回到第（3）步。
7 结论（Conclusion）
神经网络被证明是优化分组交换多层网络的一种简单方法，Rosenblatts算法的初步完成为优化神经网络完成最短路径奠定了基础，经过几次迭代网络可以得到优化后的路由。
参考文献（References）
[1] 孙俊逸，雷建锋.基于神经网络下的最短路径问题求解[J].中 国科技论文在线，1-7.
[2] 李望超.神经网络中的最短路径问题[J].电子科学学刊，1996， S1期.
[3] 朱大铭，马绍汉.神经网络求解图最短路径问题的一种新方法 [J].软件学报，1996，A00：191-198.
第7篇：路径规划典型算法范文
关键词：蚁群算法；TSP；改进
中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)22-724-02
Research on Ant Colony Algorithm for TSP
ZHU Jie
(Scool of Software,Tongji University,Shanghai 201804,China)
Abstract:Ant colony algorithm was a novel simulated ecosystem evolutionary algorithm. After introducing the essence of the ant colony algorithm.this paper its application in the complicated combinatorial opitimization problem such as TSP.Then suggested a improved ant colony algorithm to solve TSP problems more effiently.
Key words:ant colony algorithm;TSP; improved
1 引言
现实生产生活中有很多组合优化问题，这类问题随着规模的扩大，问题空间呈现组合爆炸的特征，大多数这类问题在多项式时间内无法求解，对这类问题的处理目前多用启发式算法来求解。
旅行商(TSP)问题就是典型的组合优化问题, 直观地说，TSP问题就是指一位商人从自己的家乡出发。希望能找到一条最短的路径，途经给定的城市集合中的所有城市，最后返回家乡。并且每个城市都被访问一次且仅一次。上世纪50年代中期创立仿生学以来，人们不断地从生物进化的机理中得到启发，提出了许多用于解决复杂组合优化问题的新方法，比如神经网络、遗传算法、模拟退火算法、进化规划算法等，并成功应用于解决实际问题。但由于TSP属于Np-难问题，在最差情况下精确性算法需要指数级的时间来寻找最优解。时间代价太大了。近似算法就是寻求在相对较低的计算成本下．找到好的或接近最优解的解答，但是算法不一定保证能够找到最优解。由意大利学者M.Dorigo,V.Maniezzo, A.Colomi于1992年首先提出的蚁群系统(AntColonySystem, ACS)是一种新生的仿生进化算法，适用于求解复杂组合优化问题，在解决TSP问题方面取得了较为理想的效果。
2 蚂群算法概述
蚁群算法是一种元启发式算法，蚁群算法是一种受自然启发的基于群体智能的算法。算法模型源于真实蚂蚁群体搜寻食物的过程：智能蚂蚁(算法中的人工蚂蚁)模拟真实蚂蚁从巢穴到食物所在地之间搜索最短路径，在问题的解空间中搜索。蚂蚁在觅食过程中通过释放一种称为信息素的物质相互传递信息。信息素痕迹参数是对这种行为的模拟。一般来说，信息素痕迹参数可以赋予点或边(TSP中信息素值赋给点)。蚂蚁们倾向于朝着信息素浓度高的方向前进，因此由大量蚂蚁组成的蚁群的行为便表现出一种信息的正反馈现象，某一路径上走过的蚂蚁越多，则信息素浓度越高，后来者选择该路径的概率就越大。
3 基于蚁群算法的TSP求解
给定一个有n个城市的TSP问题，人工蚂蚁的数量为m，每个人工蚂蚁的行为符合下列规律：（1）根据路径上的信息素浓度，以相应的概率来选取下一步路径；（2）不再选取自己本次循环已经走过的路径为下一步路径，用一个数据结构来控制这一点；（3）当完成了一次循环后，根据整个路径长度来释放相应浓度的信息素，并更新走过的路径上的信息素浓度。
3.1 蚁群算法的基本模型：
■ (1)
■表示蚂蚁下一步允许选择的城市。α表示外激素的相对重要性（α≥0 ），β表示启发信息的相对重要性(β≥0 )。
随着时间的推移，可能会出现两种情况：1)先前留下的外激素逐渐消失；2)残留的外激素过多，从而淹没了启发信息。为了避免这两种情况，在每一只蚂蚁从起点到达终点后，必须对残留的外激素进行更新。用参数ρ(0≤ρ≤1)来表示外激素物质的保留率，则1-ρ就表示外激素的挥发率，经过m个时间单位后，蚂蚁完成一次循环，各路径上的信息量要根据以下式子作调整:
■
■
■表示在本次循环中留在路径ij上的信息量，■表示蚂蚁k在路段ij上留下的残留外激素浓度。
■式中为dij为表示相邻两个城市间的距离。
3.2 蚁群算法的实现步骤如下
步骤1：初始化相关参数，如蚂蚁的数目。
步骤2：将蚂蚁随机或均匀分布到各个城市。
步骤3：每只蚂蚁通过访问各个城市而形成一个解，并在访问的过程中，将已访问到的城市保留在i中。在城市i中每只蚂蚁要从没有访问的城市中选择访问下一个城市j时须根据概率公式(1)进行选择，如此循环，直到所有的蚂蚁访问完所有的城市。
步骤4：计算每只蚂蚁行走的总路径长度Lk，并保存最优解。
3.3 算法设计思想
蚁群算法实现的关键是信息素的释放和更新。以及蚂蚁个体依据信息素进行路径选择的策略，在分析蚁群算法在后期容易陷入局部最优解的原因后，不难发现这是由正反馈现象所引起的。在每次循环结束时，对信息素进行全局更新，从而增强了目前最优路径对蚂蚁的”吸引力”。在TSP问题中应用蚁群算法进行求解最短路径，在城市数量不多时，得出的结果是令人满意的。在前期，这“吸引力”对算法起到了很好的加速作用。然而，它也会导致算法过早停滞。若单纯地调低信息素的权重。会削弱正反馈的机制的作用，很难使信息素集中分布。蚂蚁也就失去了选路的参照，退化为简单的以路径为参照的搜索。本算法改进的地方是对局部信息素和全局信息素进行了区分。采用不同的更新策略，根据发现解的情况动态地调整选择概率．在加速收敛发现最优和防止停滞之间找到平衡。在每次循环结束时，进行全局更新的信息素与蚂蚁自己释放的局部信息素不同。每次循环结束时，只有最优蚂蚁(找到目前最优路径的的蚂蚁)才更新全局信息素，全局信息素用表示。而局部信息素是每只蚂蚁在每移动一步后，都进行局部信息素的更新，蚂蚁k从城市i移动到城市j的概率公式变为：
■
τij(t)表示t时刻在城市i和城市j连线上的局部更新的信息素浓度，λij(t)表示t时刻在城市i和城市j连线上的全局更新的信息素浓度。α表示局部信息素τij的重要性，δ表示全局信息素λij的重要性， ρ是τ和λ的权重。
■
权重p是可变的，在[0,1]间取值。用于控制两种信息素的比重。当发现更优的解时，减少p的值以增加全局信息索的权重，从而有利于更快的发现其附近的解；若迭代多次而没有发现新解，则增加P的值削弱全局信息素的权重，从而扩大搜索的范围。
局部信息素的更新:■
Δτ为常数，信息素初始值。
全局信息素的更新：■
■，Cbs表示最优蚂蚁所走过的路径长度。
4 结论
自蚁群算法提出来后，已经吸引了众多研究者对该算法进行研究，并成功地将其运用在解决组合优化问题上，如TSP，QAP(quadratic assignment problem)，JSP(job―shop scheduling problem)等。对于许多组合优化问题，能够用一个图来阐述将要解决的问题；能定义一种正反馈过程如问题中的残留信息；问题结构本身能够提供解题用的启发式信息；能够建立约束机制：这些使用蚁群算法就能够得到解决。由于蚁群算法具有信息正反馈和并行计算的特点，其求解能力要在一定程度上好于其它一些启发式算法。但是蚁群算法也有一些不足之处，容易陷入局部最优从而出现过早停滞是该算法的主要缺点。
最后,本文提出了一种改进的蚁群优化算法，大胆引入了全局和局部信息素概念，采用了不同的更新策略和动态的路径选择概率．使得在搜索的中后期能更有效地发现全局最优解。在前期加强全局信息素的作用，从而加速收敛；在中后期，逐渐削弱全局信息素在路径选择中的作用，达到扩大搜索区域的目的。
参考文献：
[1] 陈宏建,陈峻,徐晓华,等.改进的增强型蚁群算法田[J].计算机工程,2005,31(2):176-178.
[2] Gutjahr W J.A graph-based An t System and its convergence[J].Future Generation Computer System,2000,16(8),873-888.
[3] Liang G S,Chou,17 U,HAN T C.Cluster analysis based on fuzzy equivalence relation[J].European Journal of Operational Re・search,2005,166(1):160-171．
[4] Ai exy U,Verena S P,Wolfgang S H.,et a1.Cluster analysis of individuals with similar trends of fat intake during childhood and adolescence:a new approach to analyzing dietary data[J].Nutrition Research,2005,25(3):251,260．
[5] Arulampalam S., Maskell S., Gordon N., et al. A tutorial on particle filters for on-linenon-linear/non-gaussian bayesian tracking[J].IEEE Transactions on Signal Processing, 2002,50(2):174-188.
[6] Mutapi F., Mduluza T.,RODDAM A W．Cluster analysis of schistosome-specific an tibody responses artitions the population into distinct epidemiological groups[J].Immunology Letters,2005，96(2):231,240．
（上接第725页）
[7] 段海滨．蚁群算法原理及其应用[M].北京:科学出版社，2005．
[8] 秦玲.蚁群算法的改进与应用[D].扬州:扬州大学,2004.
[9] Gendron B．Parallel computing in combinatorial optimization[M]．Pisa：[s.n]，2005．[10] D. Haehnel, W. Burgard, D. Fox, K.P. Fishkin, and M. Philipose, "Mapping and localization with RFID technology," IEEE Int. Conf. Robotics and Automation, pp.1015C1020, 2004.
[10] Yuan H，Parrill A．Cluster analysis and three．Dimensional QSAR studies of HIV-1 integrase inhibitors[J]．Journal Of Molecu?lar Graphics and Modelling，2005，23(4):317,328．
[11] 胡小兵,黄席樾.对一类带聚类特征TSP问题的蚁群算法求解[J].系统仿真学报,2004(9):2683-2686.
[12] 张宗永,孙静,谭家华.蚁群算法的改进及其应用[J].上海交通大学报,2002,56(11):1 564-1 566．
[13] 马良,项培军.蚂蚁算法在组合优化中的应用[J].管理科学学报,2001,4(2):52-57.
第8篇：路径规划典型算法范文
[关键词]电视制导 视觉显著性 地标选择 航迹规划
[中图分类号]TP[文献标识码]A[文章编号]1007-9416(2010)02-0115-03
引言
电视制导导弹作为一种空地精确制导武器,具有命中精度高、威力大和射程远等优点,已成为现代空战中打击敌方纵深战略目标的重要手段之一,人工参与的电视末制导方式是其中主要方法之一。完成精确打击的关键在于两个核心环节:一是在确定了目标点的情况下,综合考虑导弹机动性能、地形高程、障碍、威胁以及飞行任务约束条件等多种因素,选择合理的起始点;二是在起始点到目标点的飞行路径中,尽可能设计若干有效的地标点,以满足飞行员视觉判断需要,合理判断和调整导弹飞行方向,以提高打击精度。
目前公开的飞行器航迹规划方法中,大多假定起始点和目标点已事先给出,其间路径的地标点为已知,但如何在明确目标点的前提下,获取有效的攻击通道和典型的地标点序列,尚有许多问题亟待解决。鉴于视觉主观判断在前述工作流程中的重要性,引入视觉显著性计算,在视频序列中间断地提取显著地物(对应为地标点、对应帧为显著帧)作为候选地标序列是一种可行的分析思路。目前主流的显著区域检测算法,文献[1]将其分为三大类:第一类方法从候选区域内部提取显著特征,如Kadirt[2]方法。第二类方法从候选区域与外界的比较中提取显著性特征,以Itti[3]的中心-周边算子为代表。第三类从候选区域内部和外部提取显著性特征,这类方法将上述两种特征结合起来作为候选区域的显著性特征,如Priviterat[4]方法。
本文尝试以高分辨率遥感图像数据为分析数据源,提出了一种简单的基于视觉显著性度量筛选地标序列的方法,在一定几何约束关系下以目标点为中心,导弹飞行航迹距离为半径的限定扇区中,自动检测候选地标点,通过显著性综合度量函数,评估攻击路径的有效性,实现在有效扇区内选择有效攻击起始点并确定攻击通道,并给出地标序列的功能。典型实验验证了方法的有效性。本方法可作为人工选择攻击通道和地标点的辅助工具,缩小候选范围,提高工作效率。
1 地标显著性度量方法
1.1 视觉显著性
注视(Attention)机制的研究表明,人类视觉在描述场景时往往将注意力集中在某些明显与众不同、视觉效果突兀的区域,这种特性称为视觉显著性[5]。例如,在图1中,A要比其他部分更加突出,能够迅速引起观察者的注意。这种突出性就是视觉显著性,突出性较强的A部分就是该图像的显著区域。
1.2 遥感图像定义地标显著性
研究表明,位于图像中心位置且与周边亮度差异较大的区域容易引起观察者的注意。基于这一特性,考虑遥感图像的特点及计算复杂度和实时性的要求,我们把位于图像中心、与周边视觉反差大、容易识别的地物作为候选地标点。根据上述思想,鉴于视频序列图像数据量大的特点,为减少计算量,选取灰度值作为其特征,通过地物显著性度量参数进行度量,M值越大显著性越强,反之显著性就越弱。相关公式如下:
(1)
;
式中:表示第帧图像的显著性度量值,表示第个窗口内的平均灰度值,表示第个窗口外的平均灰度值。
1.3 给定路径的综合显著性
对给定路径(明确始点、终点的前提下),在提取了序列地标后,可通过设计综合显著性度量函数评估该打击路径的有效性,这样可为在限定扇区中找到最优攻击路径提供客观判断依据。
首先生成给定路径遍历帧,帧图像的显著性度量值由(1)式计算得到,形成该路径视频序列显著值曲线图,再由2.3节地标筛选算法,找到该路径上的地标点,地标点始终处于曲线图的峰值位置。给定路径的综合显著性体现在两个方面:一是该路径的平均显著性度量值;二是地标点所在帧的显著性度量值(图中圆圈所处的峰值点)与其前后显著性谷值(黑点所处位置)的差值的平均值。综合以上两个因素,可得到如下计算公式:
(2)
式中:表示通道综合显著性度量值,表示地标点个数,表示当前地标点的显著性峰值,表示前一显著性谷值,表示后一显著性谷值,表示视频帧数,表示显著性度量值。
2 攻击通道自动筛选方法
2.1 成像几何参数
导弹飞行过程中,弹载摄像机不断拍摄战场视频图像,摄像机拍摄到的战场范围是由其成像几何[6]决定的,它对于地标选取具有非常重要的作用。假设导弹飞行高度为,摄像机此刻所处位置的俯仰角为。
又已知相机可视角度为,则可根据几何关系计算得到前沿宽度分别为,视场纵深L。计算公式如下:
(3)
(4)
2.2 候选攻击通道划分
以可行攻击候选扇区为研究对象,导弹从弧线上的任意点出发飞向目标点都是安全的,沿摄像机主光轴方向将扇区划分成N条候选攻击通道(CH(1)、CH(2)… CH(N))。候选攻击通道划分得越密,相互交叉的部分越多,划分数量也就越多,找到的地标点也会越多,但计算量越会很大;划分得越疏,候选通道就越少,找到的地点标也就会越少,计算量也会越小。因此,基于以上问题,我们按照下列方式进行划分:从扇区的某一边开始,把该边作为导弹的飞行路线,根据(2)式计算得到的后沿宽度D1为范围划分导弹飞行通道,再间隔/2的宽度作为飞行路线依次划分,这样相邻两条通道相交部分为后沿宽度的1/4,目标始终处于各通道的中心位置。
将条通道分别生成视频帧图像,生成的视频帧数根据导弹的飞行速度、导弹起始点到目标的距离、每秒采集帧数确定,则:
(5)
同时,可以计算得到视场纵深L所包含帧数为:
=(/)*m(6)
2.3 地标筛选
地标的筛选必须满足以下三个条件:
(1)为保证地标在视频中稳定可见,必须要求含地标视频帧的帧数在一秒所采集帧数中超过一定比例,则:
即:视场中至少要保证存在一个地标且要持续数帧,且当临界状态出现,一个地标即将消失时,下一个地标要出现,这样才能避免地标丢失。
(2)要突出地标显著性,便于人眼识别,即显著值要大。
(3)地标点数目要合适,不能选得太多,选得太多,相邻地标点之间距离太近,没有实际意义,选得太少,地标点距离远,就会导致有些帧丢失地标,不利于视觉连续性跟踪和判断。
为了满足以上条件,我们采用以下四个步骤进行:
根据(1)式对各个通道的视频帧图像进行显著性度量,计算每帧图像的显著性度量值。
将每个通道帧图像的显著性度量值形成显著性曲线图,横坐标表示帧数,纵坐标表示显著性度量值,这样就形成了条显著性曲线图。
找到曲线上的各个峰值点和谷值点,把峰值点作为候选地标。
从第一帧开始,先在帧内找到一个峰值最大的点作为第一个地标点,为了减少不必要的地标,与前一个地标点间隔/2帧,在+/2至+帧内找一个峰值最大的点作为下一个地标点,通过同样的方法依次找出后面所有的地标点。
2.4 攻击通道选择
由1.3节计算得到各条路径的综合显著性度量值后,找到综合显著性度量值最大的一条路径作
为最终的攻击通道,公式如下:
(8)
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文
3 实验结果及分析
假设导弹飞行高度=600m,飞行速度=250/,视频采集帧频=5帧/,摄像机俯角=18o,摄像机可视角度为γ=17.5o。实验用地图为Google Earth下载的某地区高分辨率全色数据,限定某候选扇区在40o度范围内,选取10条候选通道,按照成像几何关系仿真生成视频序列图,每条通道生成180帧灰度图像。按照上述方法,通过仿真,下面是其中3组典型地标筛选结果对比分析,图中x坐标表示视频帧数,y坐标表示显著性度量值,d圈住的峰值点为地标点所在帧。
由图7、8、9和表1可以看出,第一候选通道筛选了11个地标,但160-180帧之间没有地标,存在地标丢失现象;第二候选通道筛选了11个地标,但其第2、6、7、10、11个地标点的峰值不够明显,显著性不强;第三候选通道选择了13个地标点,峰值明显的点全部被选中。通过(2)式计算得到三幅图像的综合显著度值分别为:1.1179、1.0991和1.1305,根据(8)式得出CH(3)选择的地标点显著性程度更高。同时,通过三个候选通道的地标帧图像对比也可以发现,第三候选通道优于第一、二候选通道。图10是第三候选通道找到的地标视频帧图像,位于帧图像中心位置的地物(即地标点)亮度与周边差异较大,易于人眼识别,因此选择第三候选通道为最终的攻击通道。
4 结语
本文提出了一种基于视觉显著性的空地电视制导导弹攻击通道地标选择算法。该算法在地标筛选,攻击通道选择方面得到了较为满意的结果。本文算法在复杂背景和较强噪声干扰的情况下,还有待进一步改进。
[参考文献]
[1] 张鹏,王润生,静态图像中的感兴趣区域检测技术[J].中国图像图形学报,2005;10(2):142～148
[2] Kadir T.Brady M.Saliency,scale and image description[J].International Journal of Computer Vision,2001;45(2):83-105.
[3] Itti L,Koch putational modeling of visual attention[J].Nature Reviews Neuroscience,2001:2(3):194～230
[4] Privitera C M.Stark L W.Algorithms for defining visual regions-of-interest:comparison with eye fixations[J].IEEE Transactions on Pattern Analysis and Machine Intelligenc,2000;22(9):970～982.
[5] 王璐,蔡自兴,未知环境中基于视觉显著性的自然路标检测[J].模式识别与人工智能,2006,19(1):100～105.
[6] 李永宾,黄长强,郝晓辉,对电视制导空地导弹巡航飞行高度的分析[J].导弹学报,2001:13(4):82-87.
第9篇：路径规划典型算法范文
关键词：动态路由协议；链路状态路由协议；OSPF；router-id冲突；自治系统；CE；RFC2328
1 OSPFv2协议研究
1.1 OSPF协议概述
IETF为了满足建造越来越大基于IP网络的需要，形成了一个工作组，专门用于开发开放式的、链路状态路由协议，以便用在大型、异构的IP网络中。新的路由协议已经取得一些成功的一系列私人的、和生产商相关的、最短路径优先（SPF）路由协议为基础，在市场上广泛使用。包括OSPF在内，所有的SPF路由协议基于一个数学算法Dijkstra算法。这个算法能使路由选择基于链路状态，而不是距离向量。
OSPF由IETF在20世纪80年代末期开发，OSPF是SPF类路由协议中的开放式版本。最初的OSPF规范体现在RFC1131中，第1版（OSPF版本1）很快被进行重大改进的版本所代替，新版本体现在RFC1247文档中，RFC1247OSPF称为OSPF版本2是为了明确指出其在稳定性和功能性方面的实质性改进。OSPF版本2中有许多更新文档，每一个更新都是对开放标准的精心改进，后续的规范出现在RFC 1583、2178和2328中。
链路是路由器接口的另一种说法，因此OSPF也称为接口状态路由协议。OSPF通过路由器之间通告网络接口的状态来建立链路状态数据库，生成最短路径树，每个OSPF路由器使用这些最短路径构造路由表。
OSPF路由协议是一种典型的链路状态（Link-state）的路由协议，一般用于同一个路由域内。在这里，路由域是指一个自治系统（Autonomous System），即AS，它是指一组通过统一的路由政策或路由协议互相交换路由信息的网络。在这个AS中，所有的OSPF路由器都维护一个相同的描述这个AS结构的数据库，该数据库中存放的是路由域中相应链路的状态信息，OSPF路由器正是通过这个数据库计算出其OSPF路由表的。作为一种链路状态的路由协议，OSPF将链路状态广播数据LSA（Link State Advertisement）传送给在某一区域内的所有路由器，这一点与距离矢量路由协议不同，运行距离矢量路由协议的路由器是将部分或全部的路由表传递给与其相邻的路由器。
1.2 OSPFv2协议研究
RFC2328中明确OSPF仅通过在IP包头中的目标地址来转发IP包，IP包在AS中被转发，而没有被其他协议再次封装。OSPF是一种动态路由协议，它可以快速地探知AS中拓扑的改变（例如路由器接口的失效），并在一段时间的收敛后计算出无环路的新路径，收敛的时间很短且只使用很小的路由流量。
在连接状态路由协议中，每台路由器都维持着一个数据库以描述AS的拓扑结构，这个数据库被称为连接状态数据库，所有参与的路由器都有着同样的数据库，数据库中的各项说明特定路由器自身的状态（如该路由器的可用接口和可以到达的邻居）。该路由器通过洪泛将其自身的状态传送到整个AS中。所有的路由器同步地运行完全相同的算法。根据连接状态数据库，每台路由器构建出一棵以其自身为树根的最短路径树，最短路径树给出了到达AS中各个目标的路径，路由信息的起源在树中表现为树叶。当有多条等值的路径到达同一目标时，数据流量将在这些路径上平均分摊，路径的距离值表现为一个无量纲数。
OSPF允许将一些网络组合到一起。这样的组被称为区域area。区域对AS中的其他部分隐藏其内部的拓扑结构，信息的隐藏极大地减少了路由流量；同时，区域内的路由仅由区域自身的拓扑来决定，这可使区域抵御错误的路由信息，区域通常是一个子网化的IP网络。OSPF允许灵活的配置IP子网，由OSPF的每条路径都包含目标和掩码，同一个IP网络的两个子网可以有不同的大小（即不同的掩码），这常被称为变长子网variable length subnetting，数据包按照最佳匹配（最长匹配）来转发，主机路径被看作掩码为“全1”（0xffffffff）的子网来处理。
OSPF协议中所有的信息交换都经过验证。这意味着，在AS中只有被信任的路由器才能参与路由，有多种验证方法可以被选择；事实上，可以为每个IP子网选用不同的验证方法。来源于外部的路由信息（如路由器从诸如BGP的外部网关协议中得到的路径）向整个AS内部宣告，外部数据与OSPF协议的连接状态数据相对独立，每条外部路径可以由所宣告的路由器作出标记，在自制系统边界路由器（ASBR）之间传递额外的信息。
2 OSPF域router-id冲突研究
两台路由器R1与R2之间建立域内OSPF，当R1和R2出现router-id 10.1.1.1重复时，通过查看OSPF数据库可以得到以下信息，详情请查阅下图3、图4。
我们从以上数据分析得出，每种LSA的age数值都非常的小，每种LSA的seq数值都非常的大，这也说明当出现router-id重复，那么LSDB中的LSA表现得非常不稳定，最终将导致SPF算法不停的工作、路由表不稳定、路由条目丢失。通过查看路由器日志告警文件可以见一旦出现router-id重复，那么日志信息表现为下图5的形式，其中adv-rtr为重复的router-id。
综上所述，从router-id冲突分析后得出以下结论：
（1）整个ospf域内会泛洪错误LSA，database不断更新（seq很大，age很小），网络极其不稳定；
（2）由于整个ospf域database不断更新，导致整个ospf域中routing-table抖动（route flapping），丢失路由条目。
3 结束语
移动通信网络IP承载网工程建设中涉及IP地址分配，工程建设过程中使用分配的IP地址开启建立动态路由协议OSPF的router-id，需重视并严格按照设计规范及要求，加强IP地址的分配及使用，杜绝分配IP地址冲突导致OSPF域router-id的重复使用，避免因router-id冲突影响OSPF协议的正常工作，避免因router-id冲突导致的网络事故影响用户业务的发生。
[参考文献]
