路径规划典型算法汇总十篇

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

篇（1）

中图分类号 TP242 文献标识码 A 文章编号 1674-6708(2009)10-0067-02

路径规划是指机器人从起始点到目标点之间找到一条安全无碰的路径,是机器人领域的重要课题。移动机器人技术研究中的一个重要领域是路径规划技术,它分为基于模型的环境已知的全局路径规划和基于传感器的环境未知的局部路径规划。本文综述了移动机器人路径规划的发展状况,对移动机器人路径规划技术的发展趋势进行了展望。

根据机器人工作环境路径规划模型可分为两种:基于模型的全局路径规划,这种情况的作业环境的全部信息为已知;基于传感器的局部路径规划,作业环境信息全部未知或部分未知,又称动态或在线路径规划。

1 全局路径规划

全局路径规划主要方法有:可视图法、自由空间法、栅格法、拓扑法、神经网络法等。

1.1 可视图法

可视图法视移动机器人为一点,将机器人、目标点和多边形障碍物的各顶点进行组合连接,并保证这些直线均不与障碍物相交,这就形成了一张图,称为可视图。由于任意两直线的顶点都是可见的,从起点沿着这些直线到达目标点的所有路径均是运动物体的无碰路径。搜索最优路径的问题就转化为从起点到目标点经过这些可视直线的最短距离问题。

1.2 拓扑法

拓扑法将规划空间分割成具有拓扑特征的子空间,根据彼此连通性建立拓扑网络,在网络上寻找起始点到目标点的拓扑路径,最终由拓扑路径求出几何路径。拓扑法基本思想是降维法,即将在高维几何空间中求路径的问题转化为低维拓扑空间中判别连通性的问题。

1.3 栅格法

栅格法将移动机器人工作环境分解成一系列具有二值信息的网格单元,多采用四叉树或八叉树表示,并通过优化算法完成路径搜索,该法以栅格为单位记录环境信息,有障碍物的地方累积值比较高,移动机器人就会采用优化算法避开。对栅格的改进采用以障碍物为单位记录的信息量大大减少,克服了栅格法中环境存储量大的问题。

1.4 自由空间法

自由空间法应用于移动机器人路径规划,采用预先定义的如广义锥形和凸多边形等基本形状构造自由空间,并将自由空间表示为连通图,通过搜索连通图来进行路径规划。自由空间的构造方法是从障碍物的一个顶点开始,依次作其它顶点的链接线,删除不必要的链接线,使得链接线与障碍物边界所围成的每一个自由空间都是面积最大的凸多边形。连接各链接线的中点形成的网络图即为机器人可自由运动的路线。

1.5 神经网络法

可视图法缺乏灵活性,且不适用于圆形障碍物的路径规划问题。神经网络法用于全局路径规划可以解决以上问题。算法定义了整条路径的总能量函数,相应于路径长度部分的能量和相应于碰撞函数部分的能量。由于整个能量是各个路径点函数,因此通过移动每个路径点,使其朝着能量减少的方向运动,最终便能获得总能量最小的路径。

2 局部路径规划

局部路径规划包括人工势场法、模糊逻辑算法、神经网络法、遗传算法等。

2.1 人工势场法

人工势场法基本思想是将移动机器人在环境中的运动视为一种虚拟人工受力场中的运动。障碍物对移动机器人产生斥力,目标点产生引力,引力和斥力周围由一定的算法产生相应的势,机器人在势场中受到抽象力作用,抽象力使得机器人绕过障碍物。

2.2 模糊逻辑算法

模糊逻辑算法基于对驾驶员的工作过程观察研究得出。驾驶员避碰动作并非对环境信息精确计算完成的,而是根据模糊的环境信息,通过查表得到规划出的信息,完成局部路径规划。模糊逻辑算法的优点是克服了势场法易产生的局部极小问题,对处理未知环境下的规划问题显示出很大优越性,对于解决用通常的定量方法来说是很复杂的问题或当外界只能提供定性近似的、不确定信息数据时非常有效。

2.3 神经网络法

模糊控制算法有诸多优点,但也有固有缺陷:人的经验不一定完备;输入量增多时,推理规则或模糊表会急剧膨胀。神经网络法则另辟蹊径。路径规划是感知空间行为空间的一种映射,映射关系可用不同方法实现,很难用精确数学方程表示,但采用神经网络易于表示,将传感器数据作为网络输入,由人给定相应场合下期望运动方向角增量作为网络输出,由多个选定位姿下的一组数据构成原始样本集,经过剔除重复或冲突样本等加工处理,得到最终样本集。

2.4 遗传算法

遗传算法以自然遗传机制和自然选择等生物进化理论为基础,构造了一类随机化搜索算法。利用选择、交叉和变异编制控制机构的计算程序,在某种程度上对生物进化过程作数学方式的模拟,只要求适应度函数为正,不要求可导或连续,同时作为并行算法,其隐并行性适用于全局搜索。多数优化算法都是单点搜索,易于陷入局部最优,而遗传算法却是一种多点搜索算法,故更有可能搜索到全局最优解。

3 移动机器人路径规划技术的发展展望

随着计算机、传感器及控制技术的发展,特别是各种新算法不断涌现,移动机器人路径规划技术已经取得了丰硕研究成果。从研究成果看,有以下趋势:首先,移动机器人路径规划的性能指标要求不断提高,这些性能指标包括实时性、安全性和可达性等;其次,多移动机器人系统的路径规划。协调路径规划已成为新的研究热点。随着应用不断扩大,移动机器人工作环境复杂度和任务的加重,对其要求不再局限于单台移动机器人。在动态环境中多移动机器人的合作与单个机器人路径规划要很好地统一;再次,多传感器信息融合用于路径规划。移动机器人在动态环境中进行路径规划所需信息都是从传感器得来。单传感器难以保证输入信息准确与可靠。此外基于功能/行为的移动机器人路径规划,这是研究的新动向之一。

总之,移动机器人的路径规划技术已经取得了丰硕成果,但各种方法各有优缺点,也没有一种方法能适用于任何场合。在研究这一领域时,要结合以前的研究成果,把握发展趋势,以实用性作为最终目的,这样就能不断推动其向前发展。

参考文献

篇（2）

中图分类号：TP306文献标识码：A文章编号：1009-3044(2008)21-30523-02

An Algorithm Based on Improved A* Restrictions on the Path to Search Regional Planning Approach

XU Zhan-peng, LIN Kai

(Qingdao Technical College Information Institute of Qingdao,Qingdao 266555,China)

Abstract: According to A* algorithm has been given an improved optimal path planning method, this algorithm in accordance with the actual situation of the road network of layered LO at the same time, according to the actual network topology of the region to search for reasonable Restrictions experiment proved that the algorithm in the path planning saving time

Key words: Path planning; Search region; A* algorithm

1 引言

路径规划是在车辆行驶前或行驶过程中寻找车辆从起始点到达目的地的最佳行车路线的过程[1], 它属于智能交通

系统中的最短路径问题的一个具体应用。

最短路径规划产生的路径分为两种：距离最短的路径和时间最短路径,其中前者相对比较易于实现，但是它容易忽略路径的具体情况和行车实际环境以及人为因素。因为在实际车辆行驶中要求不但在此路径上行车距离尽可能短，而且路径的行车环境尽可能好，即尽量走道路较宽、路面质量较好、红绿灯较少、红绿灯设置间隔较大、车流量较小的路径，避免走行车环境太差的路径。作者针对最短路径规划存在的不足之处 ,根据已有A*算法，给出了一种改进的最优路径规划算法，此算法在根据道路的实际情况对路网进行分层的同时，根据实际路网的拓扑特性对搜索区域进行合理的限制。

2 A*算法

A*算法是人工智能中一种典型的启发式搜索算法．也是路径规划算法中的常用算法，它通过选择合适的估计函数，指导搜索朝着最有希望的方向前进．以期求得最优解限制搜索区域的多层最优路径规划算法，A*算法评价函数的定义为[2]：

f(n)=g(n)+h(n) （1）

f(n)是从初始点通过节点n 到达目标点的估价函数；

g(n)是在状态空间中从初始节点到n节点的实际代价；

h(n)是从节点n到目标节点最佳路径的估计代价。它决定了搜索的效率和可采纳性。对于几何路网来说，可以取两点间欧氏距离（直线距离）作为估价值，即

其中，(xd,yd)、(xn,yn)分别为节点n 和目标节点在数字地图中的坐标。由于估价值h(n)≤n 到目标节点的距离实际值，算法具有可采纳性，能得到最优解。[3]

3 改进的A*算法球最短路径

本文在三个方面对传统的A*算法进行了更改：1)A*算法提到的权值会根据用户的不同查询条件来调用相对应的计算权值的公式；2) 添加了一个判断过程。当查询下一个临近边的时候首先查询交通控制策略，判断是否有管制信息并将相映的点从v中删除；3) 减少路径搜索的范围，以出发点与目的地点连线的中间点为圆心，以两点之间直线距离的二分之一再加上几公里为半径画圆，在圆范围内的路径参加搜索，在圆范围之外的路径不参加搜索。

具体实现如下：

创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点，设各个点的权值（也称为费用值）为g。遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,计算X的估价值[4]。

1)初始的OPEN表仅包含原节点．其费用值g为0，令CLOSED为空表，设其他节点的费用为∞ 。

2)若OPEN表为空．则宣告失败：否则，选取OPEN表中所有的节点移至CLOSED表，将此CLOSED表作为新的OPEN表。重复第二步，直到深度达到4。

3)对第二步在深度4时形成的OPEN表进行操作，若OPEN表为空．则宣告失败：否则，选取OPEN表中具有最小权值的节点，并叫做最佳节点NEXT．把NEXT从OPEN表移至CLOSED表．判断此NEXT是否是一目标节点。若NEXT为目标节点．转步骤3，若NEXT不是目标节点。则根据地图数据库包含的联接路段属性扩展并生成NEXT的后继节点。对于每一个后继节点n，进行下列过程：

①计算节点n的费用：g(n)= NEXT费用+从NEXT到n的费用

②如果n与OPEN表上的任一节点相同．判断n是否具有最小的g值。若是最低的g值，用n的费用代替OPEN表中相同的节点费用。且建立匹配节点的后向指针指向NEXT

③如果n在CLOSED表中与一节点相匹配。检查节点n是否具有最小的g值，如果n具有最小的g值，则用节点n的费用代替匹配节点的费用。并把匹配节点的后向指针指向NEXT。并把该匹配节点移到OPEN表

④如果n不在OPEN表。也不在CLOSED表上，则把n的后向指针指向NEXT。井把n放入OPEN表中。计算节点n的估价函数：f(n)=g(n)+h(n)

例如图1，为带权的有向图。

根据步骤三，针对图1，算法的具体实现如图2。

4)重复第三步：

若在深度为7的搜索中找到目标结点且仅有一条路径，则该路径为最终路径，返回；

若在若在深度为7的搜索中找到目标结点并且有多条路径则回朔，比较找到的路径费用，取权值最小的作为最终路径；

若在在深度为7的搜索中未找到任何目标点则跳转到第五步。

5)从深度为7的搜索中的所有的NEXT节点回朔，即从NEXT的后向指针一直到原节点遍历节点，最后报告若干条路径，比较个路径费用，取费用最小的前100条路径继续重复第三步、第四步。由于h函数在满足h下限得条件下，愈趋近于h效率愈高，因此实际应用中，我们取的是节点到目的点的直线距离保证满足下限的情况下，尽可能的趋近h。

4 结语

实践表明基于改进A*算法的限制搜索区域的路径规划方法不仅在进行路径规划时节省了时间，而且规划后的路径大部分道路位于高层路网上，路径长度与最短路径长度之比小于1.1,可以被人接受，是行车意义上的最优路径。

参考文献：

[1] 付梦印.限制搜索区域的距离最短路径规划算法[J].北京理工大学学报,2004(10).

[2] 赵亦林.车辆定位与导航系统[M].北京:电子工业出版社,1999:1-7.

篇（3）

当前，智能电网的发展在一定程度上带动了电网技术的发展，并且成为了电网技术发展的重要方向。实际上，智能电网的重要组成部分在于智能配电网，智能配电网的主要特征为拥有完备的自愈能力，同时还能够最大程度的减少电网故障给用户带来的影响。而配电网故障的恢复是智能配电网自愈功能实现的重要过程，配电网故障恢复问题主要指配电网发生故障以后，在故障定位与故障隔离的基础之上，应用一定的故障恢复策略对其进行操作，从而确保供电的平稳与正常。

一、对最佳路径的分析

配电网故障区域恢复供电的最佳路径事实上是在故障情况下的配电网络重构。主要的目的在于，能够快速的将非故障区域供电恢复，与此同时，还能够有效的满足线路负载容量的要求以及线损最小等各个方面的条件。现阶段，在配网自动化领域中研究最多的在于怎样能够快速的实现故障隔离以及快速的恢复费故障区域的供电技术方法，因此，在恢复路径的最优化选择方面出现了较多的研究。

一般而言，配电网故障区域恢复供电的路径为多目标最佳路径问题，现阶段在最佳路径问题的研究上较多的便是城市交通网络中的最短路径问题的研究。由于问题解决的思路存在着极大的不同点，因此最短路径问题能够被分为单元最短路径算法与基于启发式搜索最短路径算法[1]。这与邓群，孙才新，周驳仍凇恫捎枚态规划技术实现配电网恢复供电》一文中的观点极为相似。其中，单元最短路径算法主要体现在几个方面，即：

第一，在GIS空间查询语言方面的最短路径。该职工路径的研究方法在当前还停留在理论研究方面，例如在MAX中定义了一套空间查询语言，该套语言对其完备性给予了相关证明，同时通过举证的方式，对范围查询与时态查询等进行了应用分析。

虽然，对于GIS空间发展研究GeoSQL为一种有效的处理最短路径的手段，但是GIS受到数据库技术发展的制约与影响，导致实际的应用领域和背景的不同，使其和商用之间还有很长的一段距离。

第二，在功能模块思想路径方面，需要按照不同的分类方法实施，而单元最短路径问题的算法能够被分为很多种，例如神经网络法与基于人工智能的启发式搜索算法等，对于不同的背景应用需求和具体软件应用的环境，各种算法在空间的复杂程度与时间的复杂程度等都有明显的体现[2]，这与李振坤，周伟杰，钱啸等在《有源配电网孤岛恢复供电及黑启动策略研究》一文中有着相似的观点。并且各种算法在故障恢复方法中各具特色。

另外，启发式搜索最短路径算法也是一种有效的手段。基于启发式方向策略最短路径算法，其中包括空间有效方向的可控参数法，该方法能够有效的调节相关系数，在有效方向上路径无效的时候，能够确保得到有效的路径。

二、最佳路径的选择方法分析

事实上，配电网故障区域恢复供电的最佳路径并不是简单的路径问题，而是多目标最佳路径问题。为此，在研究配电网非故障区域恢复供电的最佳路径过程中，需要对其展开综合的分析。

首先，在多目标分析方面，通常在选择配电网非故障区域恢复供电最佳路径的时候，最为重视的目标为：

第一，在恢复供电路径的过程中，馈线负荷不能过载，同时，还需要确保恢复区域的电压质量能够与实际规定的标准要求相吻合。当供电质量可靠性最高的时候，那么恢复的时间将会很短[3]；这与邓昆英，汪凤娇，饶杰等在《智能配电网有功自治互动建模研究》一文中的观点极为相似。另外，供电过程中，线损最低，证明开关拉合的次数最少，同时现场的操作点也会最少。

第二，在动态规划技术恢复供电的最短路径方面需要明确，动态规划主要是运筹学的一个分支，它是求解决策过程的最优的数学方式。早在很久以前，就已经有研究人员对多阶段过程转化问题转化为一系列的单阶段问题，并且逐一进行求解，这标志着解决这类过程优化问题的新方法的创立，即动态规划技术。

本文主要将一典型的复杂配电网络作为研究例子，该连通系包括10个电源点，8个分支点，同时联络开关有16个。将其加入到配网潮流方向和典型的运动方式中，将联络开关和电源点作为定点，那么可以将其分为26个定点。尽管从数量上顶点比较多，但是由于存在着较为复杂的网络关系，使得该问题成为一个极为简单的最短路径问题[4]。这与杨建在《配电网无功补偿系统的关键技术研究》一文中的观点有着相似之处。加之恢复路径主要指费故障区域相关的联络开关与相应路由，为此我们可以将其理解为从不同电源点出发到各个联络开关的最短路径问题，这样一来，故障恢复工作的实施便简单的多。

总结

本文主要从两个方面左手，共同分析了采用动态规划技术实现配电网恢复供电的方法与效果，一方面着手于最佳路径的分析，另一方面着手于最佳路径的选择方法。从这两个方面可以看出，利用动态规划技术去实现配电网恢复供电是一种可行的方法。但是，受到历史原因的影响，我国城市配电网络还缺少标准的规范要求，导致配电网常常出现一些事故。因此，恢复配电网供电已经成为当务之急。随着科技的发展，智能配电网已经被广泛的应用在供电方面，这为平稳供电提供了一定的保障，同时也为恢复配电网故障供电创建了良好的环境与条件等。

参考文献

[1]邓群，孙才新，周驳.采用动态规划技术实现配电网恢复供电[J].重庆大学学报（自然科学版），2006，29（3）：40-44.

[2]李振坤，周伟杰，钱啸等.有源配电网孤岛恢复供电及黑启动策略研究[J].电工技术学报，2015，30（21）：67-75.

[3]邓昆英，汪凤娇，饶杰等.智能配电网有功自治互动建模研究[J].机电工程技术，2014，（2）：4-7.

篇（4）

中图分类号：TP391.4 文献标志码：A

Mobile Robot Path Planning Based on an Improved A* Algorithm SUN Wei1， LV Yunfeng1， TANG Hongwei1，2， XUE Min1

（1. College of Electrical and Information Engineering， Hunan University， Changsha 410082， China；

2. Department of Electrical Engineering， Shaoyang University， Shaoyang 422000， China）

Abstract：An improved A* algorithm was presented for global path planning of mobile robot. Firstly， the environment model was described using the grid method， and the preliminary path was obtained by traditional A* algorithm. Secondly， the path planned by A* method was flaw with much redundant points， large path length， and turning angle. The original path was partitioned by tiny step to obtain a series of path point. The finish point from the start point was connected by using straight line in sequence. To decrease the path length and turning angle， the path node can be removed if there are no obstacles on the line. The analysis and comparison between the proposed algorithm， traditional A* algorithm and another improved A* method were then given in the simulation experiment and physical experiments. Additionally， the merits of the proposed algorithm and other algorithms were compared when the obstacle rate， amount of task point， and step length were different. The experiment results show that the proposed algorithm effectively reduces the path length and turning angle.

Key words：mobile robot； path planning； A* algorithm； grid method

路径规划问题一直是智能机器人领域的一个研究岬.移动机器人路径规划是指机器人基于机载传感器获得的环境信息规划出一条从起点到终点的无碰、安全的可行路径，并在此基础上尽可能地优化路径[1].移动机器人路径规划主要解决以下三个问题：第一是规划出的路径能使机器人从起点运动到终点；第二是采用相应的算法使得机器人能够避开环境中的障碍物；第三是在满足前面两点要求的基础上，尽可能地优化机器人的运动轨迹，通常是以规划出的路径最短作为优化目标[2].根据机器人对环境信息的感知程度，路径规划问题分为全局路径规划和局部路径规划.前者是指机器人在拥有全部环境信息的基础上进行的路径规划，又称为离线路径规划；后者是指机器人在只有部分环境信息的基础上进行的路径规划，又称为在线路径规划[3].本文主要讨论全局路径规划.

移动机器人路径规划的研究起始于20世纪70年代，到目前为止，已有大量的研究成果.针对全局路径规划，主要方法有可视图法、拓扑学法、人工智能算法和栅格法[4].文献[5]针对自由空间法当环境发生变化时，需要重新建立网络连接模型，因而导致路径规划算法的环境适应性差和实时性不高的缺陷，提出了一种基于可视图的全局路径规划算法，该方法是直接在环境地图上进行路径规划，从而提高了算法的环境适应能力和实时性.神经网络作为人工智能中一种重要的算法也被应用到了移动机器人路径规划领域，如文献[6]，首先建立了一个障碍物罚函数的神经网络模型，并得到了整条路径的能量函数；然后求得该函数的极小值点，且应用了模拟退火算法避免陷入局部最优；最终对得到的路径进行了优化，使得路径更加平滑和安全.除此之外，学者们还采用其它的智能算法来解决移动机器人路径规划问题，如模糊逻辑[7-9]，蚁群算法[10]，粒子群优化[11]，遗传算法[12-13]等.

栅格法是将机器人运动环境建立成一系列具有二值信息的网格模型，再用搜索算法获取最优路径.文献[14]提出了一种改进的A*算法，解决了传统A*算法得到的路径包含过多冗余点问题，并得到机器人在拐点处的最小转折角度.但该算法并没有减小机器人的路径长度和转折角度.文献[15]针对传统A*算法得到的路径折线多、累计转折角度大的问题，提出了一种平滑A*算法，减少了不必要的路径点并减小了路径长度和转折角度.但只是在原有的路径点上进行处理，路径长度和转折角度的减少量有限.本文提出了另一种改进的A*算法，将进一步地减少移动机器人的总路径长度和总转折角度.

1 环境模型描述

众所周知，移动机器人工作环境地图建立是路径规划中十分重要的一步.地图建立是指将各种传感器获得的环境信息进行融合并抽象成地图模型[16].采用栅格单位描述二维环境信息非常简单有效，应用广泛.所以，本文也使用栅格法来建立移动机器人工作环境模型.如图1所示，栅格法将机器人工作环境分割成一系列具有相同尺寸的栅格，并将这些栅格分成两类：可通过栅格和不可通过栅格.图1中，空白栅格表示可通过栅格，即移动机器人能自由通过的地方，黑色栅格表示不可通过栅格，即该栅格有静态的障碍物.

为了方便研究又不失一般性，本出以下3点合理的假设：1）障碍物边界是在实际边界的基础上加一个移动机器人安全距离得到的，这样就可以将移动机器人看作是环境中的一个质点；2）在这有限的二维空间中，机器人的移动方向可以是任意的，并且不考虑高度的影响；3）在整个路径规划过程中，环境信息是不变的.图1是一个10*10的移动机器人工作环境，S是机器人起点，D是终点.本文的工作就是找到一条从起点到终点的无碰的最优路径.

2 A*全局路径规划算法

A*算法是一种典型的启发式搜索方法.通过估价函数来引导和决定它的搜索方向.从起点开始搜索周围的节点，由估价函数得到每个节点的价值，选择价值最低的作为下一个扩展节点，循环重复这一过程直到搜索到终点，则停止搜索，获得最终路径.由于每一次都是以估价值最低的节点作为扩展节点，所以最终的路径代价是最低的.估价函数由式（1）给出：

式中：g（n）是状态空间中从起始节点到节点n的实际代价，h（n）是从节点n到终点的启发式估计代价函数，本文采用曼哈顿距离作为启发式函数[14].

xd是目标点的横坐标，yd是目标点的纵坐标，xn是节点n的横坐标，yn是节点n的纵坐标.

在A*算法搜索路径的过程中，需要不断地更新两个列表，一个是开启列表，另一个是关闭列表.开启列表存储的是所有的周围节点.A*算法从开启列表中选择具有最小估价值的节点作为下一个扩展节点.关闭列表存储的是所有经过的节点和环境中的障碍节点.应用A*算法进行路径搜索的具体流程如下所述：

Step1 把起始节点放入开启列表.

Step2 检查开启列表是否为空，如果为空，则表示搜索失败；不为空，则执行Step3.

Step3 选取开启列表中具有最低f（・）的节点作为当前扩展节点，对扩展节点的每个周围节点作如下处理：①当该节点的周围节点是障碍点或者是关闭列表中的节点，则没有任何动作；②当该节点的周围点不在开启列表中，则把该节点的周围节点添加进开启列表中，并将当前扩展节点作为该节点的周围节点的父节点，计算该节点的周围节点的f（・）和g（・）；③当该节点的周围节点在开启列表中，如果以当前扩展节点作为父节点，该节点的周围节点的g（・）比原来更低，则把当前扩展节点作为父节点，并重新计算该节点的周围节点的f（・）和g（・）.否则，不作任何改变.

Step4 将当前扩展节点放入关闭列表中，并检查终点是否在开启列表中.如果不在开启列表中，则跳回Step2继续搜索；否则，最优路径已经找到，结束搜索.

Step5 从终点开始，沿着每一个父节点移动，回到起始点，这就是最终的路径.

3 改进的A*算法

采用A*算法进行移动机器人路径规划虽然能获得一条安全无碰的路径，但路径点较多，折线多，导致路径的总长度和总转折角度较大.这在移动机器人实际应用中将消耗更多的能量和花费更多的r间.本文提出了一种改进的A*算法，能有效地减少路径长度和转折角度.

图2的实线是在一个任意环境中A*算法规划出的路径，本文方法是在原路径的基础上，从起点开始以较小的步长分割原路径，得到更多路径点，如图2的路径点a1到a20.按照一定的规则剔除冗余路径点，将剩余的路径点按顺序连接，最终获得更加优化的路径.

图3是本文算法的流程图，图中符号的定义如下：

k为分割路径的步长；c，m，i分别是当前路径点下标、待连接路径点下标和新路径点下标；A为以步长k分割原始路径得到的路径点集合A={a1，a2，…，aN}，其中a1是起始点，aN是终点；ac为当前路径点；am为当前待连接点；

lcm为连接ac与am的直线；lc，c+1为连接ac与ac+1的直线；B为新的路径点集合，B={b1，b2，…，bs }.

注意，以步长k分割路径是在原路径的直线段进行的.例如，对图4中A*算法得到的路径进行分割，先进行直线段L1的分割，从起点开始依次得到路径点a1，a2，…，a7，此时a8与原路径点的距离小于步长k，则将原路径点作为a8，并从路径点a8开始重复上述过程，分割直线段L2和L3直到将终点作为路径点a20时，分割过程结束.

图4中的实线是在任意环境中A*算法规划出的路径1，由直线段L1 ，L2 和L3组成，本文方

法规划出的路径3由直线段La1a6，La6a9，La9a10和La10a20组成，其中Laiaj是指起点为ai，终点为aj的直线段.由图4可以直观地看出：路径1的路径长度明显大于路径3的路径长度.另外，路径1的总转折角度：

路径3的总转折角度：

其中α2=∠ba6a9 ， β2=∠da9a10，γ1=∠ca10a20.而α1=α2+β2，β1=γ1+γ2，γ2=∠a15a20a10，则θ1=α1+β1=α2+β2+γ1+γ2=θ3+γ2.所以，θ1>θ3.相对于A*算法，本文方法缩短了总路径长度，减小了总转折角度.

文献[15]提出的平滑A*算法直接地剔除A*算法规划出的路径点，使得路径更加平滑.而本文方法是先进行分割，再剔除冗余的路径点.图4中直线段La1a8，La8a11和La11a20是文献[15]中平滑A*算法得到的路径2.显然，路径2的长度大于路径3的长度.另外，路径2的转折角度：

其中α1=∠ba8a9，β3=∠a15a20a10，而α1=α2+β2，β3=γ1+γ3，γ3=∠a11a20a10，则θ2=α1+β3=α2+β2+γ1+γ3=θ3+γ3，所以θ2>θ3.相对于文献[15]提出的平滑A*算法，本文方法得到的路径也更加优化.

4 实 验

为了验证本文算法的可行性和有效性，进行了计算机仿真实验和实物实验.考察了不同情形下算法的性能，以下将从4个方面进行仿真实验： 1）探究同样的条件下本文算法与A*算法以及文献[15]的平滑A*算法的性能；2）环境障碍率p对各算法的影响；3）不同目标点数n下算法的优劣；4）本文算法在不同的分割步长k下的效果.以下的4种情形都是在边长为200个单位的正方形环境下进行实验，将实验环境分割成20*20个栅格元素，每个元素是边长为10个单位的正方形栅格.将实验环境分割成20*20个栅格元素，每个元素是边长为10个单位的正方形栅格.

情形1 环境障碍率（障碍栅格数量占总栅格数量的比例）p=30%，取本文算法的分割步长k=0.1，目标数n=1即只有一个终点，起点是（4，4），终点是（198，198），机器人在起点的角度为90°.进行了50次实验，图5和图6是不同算法规划出的路径长度和转折角度，表1是3种算法50次实验的各项平均值比较.从实验结果中可以看出，本文提出的改进A*算法相对于A* 算法和文献[15]的平滑A* 算法，有效地减少了路径长度和转折角度.注意，虽然环境障碍率都是30%，但障碍栅格是随机分布的，这就导致了不同的环境复杂度，所以同样的算法和实验条件在不同的实验次数下却有不同的实验结果.

情形2 考察在不同的环境障碍率下，各个算法的性能.令分割步长k=0.1，目标数n为1，起点（4，4）、终点（198，198），机器人在起点的角度为90°.分别在环境障碍率为10%，20%，30%，40%，50%时，进行了50次实验，并求得不同障碍率下路径长度的均值和转折角度的均值，实验结果如图7、图8所示.可以看出，一方面当环境障碍率增大时，各个算法得到的路径长度和转折角度也在不断增大.这是因为环境障碍率一定程度上代表了环境的复杂度，当环境越复杂时，那么规划的路径长度和转折角度也就越大；另一方面，在图7和图8中，方框内的数据是本文算法相对于A*算法路径长度和转折角度的减少量.当环境障碍率越大时，路径长度和转折角度的减少量也不断增大，这说明相对于A*算法，本文方法更加适合在障碍物较多的环境中使用.

情形3 在移动机器人的工作空间中可能存在多个任务点，这就意味着环境中会有多个不同的终点.这里将研究当机器人有多个任务点时，各个路径规划算法的优劣性.这里做以下两点规定：1）对环境中的任务点进行了编号，任务点1，（198，198）；任务点2，（4，198）；任务点3，（95，95）；任务点4，（198，4）.2）当机器人有n个任务需要执行时，它的执行顺序是由任务点1递增至任务点n.取障碍率p=30%，分割步长k=0.1，分别在n等于1，2，3，4时，进行了50次实验，并求得路径长度和转折角度的均值，实验结果如图9和图10所示，图中方框内的数据是本文算法相对于A*算法路径长度和转折角度的减少量.显而易见，当机器人的任务点越多，本文算法相对于A*算法规划的路径长度和转折角度的减少量越大.

情形4 本文算法中存在一个分割步长k，这里将考察参数k对算法效果的影响.令环境障碍率p=30%，仅有一个任务点（198，198），起点是（4，4），机器人在起点的角度为90°.在不同的分割步长下进行了50实验，并求出相应的均值，验结果如图11和图12所示.可以得出这样的结论：当分割步长越小时，本文算法得到的路径长度和转折角度也越小.显然，这是因为分割步长越小，路径分割得越精细，路径长度和转折角度也就相应减小.

在实物实验中，本文采用的移动机器人是Turtlebot2，移动底座的最大移动速度：0.7 m/s，最大角速度：180°/s.采用ThinkPad E450C笔记本电脑作为移动机器人的控制器.移动机器人的实际运动空间如图13所示，是3.6 m×6.6 m的矩形环境.起点（0.9 m，0.9 m），终点（2.7 m，6.3 m），机器人在起点的角度为90°.为了使用本文改进的A*算法进行路径规划，需要先建立环境的栅格模型，设置栅格元素为0.6 m×0.6 m的正方形，对实际障碍物进行膨化处理，映射成图14的黑色栅格.分别采用A*算法、文献[15]的平滑A*算法和本文算法进行移动机器人的路径规划.图14的直线段La1a5，La5a11，La11a21，La21a27，La27a32，La32a44 和

La44a53是A*算法规划出的路径；文献[15]中平滑A*算法得到的路径是直线段La1a5，La5a11，La11a21，La21a27，La27a32和La32a53；直线段La1a8，La8a24，La24a25，La25a35和La35a53是本文算法得到的结果.由于移动机器人的运动总是存在外界干扰和运动精度等因素，其运动的实际路径长度与转折角度总是比规划的路径长度和转折角度要稍稍大一些，如表2所示.但无论是规划的路径长度和转折角度，还是移动机器人实际运动的路径长度和转折角度，本文算法得到的实验结果都比A*算法和文献[15]平滑A*算法更加优化.

5 结 论

采用A*算法进行移动机器人路径规划，可以得到一条从起点连接终点的无碰安全路径，但路径的冗余点较多，路径长度和转折角度较大.针对这些问题，本文提出了一种改进A*算法，能有效地减少路径冗余点和减小路径长度及转折角度.并且，分析比较了不同的环境障碍率、任务点数量、分割步长对算法性能的影响.一方面，相对于A*算法，本文方法更加适合多任务点，高障碍率环境下的移踊器人路径规划；另一方面，采用较小的分割步长可使得规划出的路径更加优化.

参考文献

[1] 席裕庚，张纯刚.一类动态不确定环境下机器人的滚动路径规划[J].自动化学报，2002，28（2）： 161-175.

XI Yugeng， ZHANG Chungang.Rolling path planning of mobile robot in a kind of dynamic uncertain environment[J]. Acta Automatica Sinica， 2002，28（2）：161-175.（In Chinese）

[2] 张捍东，郑睿，岑豫皖.移动机器人路径规划技术的现状与展望[J].系统仿真学报，2005， 17（2）： 439-443.

ZHANG Handong， ZHENG Rui， CEN Yuwan. Present situation and future development of mobile robot path planning technology[J]. Journal of System Simulation， 2005，17（2）：439-443.（In Chinese）

[3] 朱大奇，颜明重.移动机器人路径规划技术综述[J].控制与决策，2010， 25（7）： 961-967.

ZHU Daqi， YAN Mingzhong. Survey on technology of mobile robot path planning[J]. Control and Decision， 2010，25（7）：961-967.（In Chinese）

[4] 吴乙万，黄智.基于动态虚拟障碍物的智能车辆局部路径规划方法[J].湖南大学学报：自然科学版，2013，40（1）： 33-37.

WU Yiwan， HUANG Zhi. Dynamic virtual obstacle based local path planning for intelligent vehicle[J]. Journal of Hunan University：Natural Sciences， 2013，40（1）：33-37.（In Chinese）

[5] 杨淮清，肖兴贵，姚栋.一种基于可视图法的机器人全局路径规划算法[J].沈阳工业大学学报，2009，31（2）： 225-229.

YANG Huaiqing， XIAO Xinggui， YAO Dong. A V-graph based global path planning algorithm for mobile robot[J]. Journal of Shenyang University of Technology， 2009，31（2）：225-229.（In Chinese）

[6] 梁瑾，宋科璞.神经网络在移动机器人路径规划中的应用[J].系统仿真学报，2010，22（增刊1）： 269-272.

LIANG Jin， SONG Kepu. The application of neural network in mobile robot path planning[J]. Journal of System Simulation， 2010，22（s1）：269-272.（In Chinese）

[7] 郝冬，刘斌.基于模糊逻辑行为融合路径规划方法[J].计算机工程与设计，2009，30（3）： 660-663.

HAO Dong， LIU Bin. Behavior fusion path planning method for mobile robot based on fuzzy logic[J]. Computer Engineering and Design， 2010，30（3）：660-663.（In Chinese）

[8] ARPINO C P， MELENDEZ W M， GUZMAN J， et al. Fuzzylogic based speed planning for autonomous navigationunder velocity field control[C]//2009 IEEE Int Conf on Mechatronics. Malaga， 2009： 201-212.

[9] ZOUMPONOS G T， ASPRAGATHOS N A. Fuzzy logic pathplanning for the robotic placement of fabrics on a worktable[J]. Robotics and Computer Integrated Manufacturing， 2008， 24 （2）： 174-186.

[10]邓高峰，张雪萍，刘彦萍.一种障碍环境下机器人路径规划的蚁群粒子群算法[J].控制理论与应用，2009，26（8）： 879-883.

DENG Gaofeng， ZHANG Xueping， LIU Yanping. Ant colony optimization and particle swarm optimization for robot-path planning in obstacle environment[J]. Control Theory & Applications， 2009，26（8）：879-883.（In Chinese）

[11]吴宪祥，郭宝龙，王娟.基于粒子群三次样条优化的移动机器人路径规划算法[J].机器人，2009，31（6）： 556-560.

WU Xianxiang， GUO Baolong， WANG Juan. Mobile robot path planning algorithm based on particle swarm optimization of cubic splines[J]. ROBOT， 2009，31（6）：556-560.（In Chinese）

[12]王雪松，高，程玉虎，等.知识引导遗传算法实现机器人路径规划[J].控制与决策，2009，24（7）： 1043-1049.

WANG Xuesong， GAO Yang， CHENG Yuhu， et al. Knowledge-guided genetic algorithm for path planning of robot[J]. Control and Decision， 2009，24（7）：1043-1049.（In Chinese）

[13]THEODORE M， KAVEH A， ROGER L W. Genetic algorithms for autonomous robot navigation[J]. IEEE In Strumentation and Measurement Magazine， 2007，12（1）： 26-31.

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

WANG Dianjun. Indoor mobile-robot path planning based on an improved A* algorithm[J]. Journal of Tsinghua University：Science and Technology，2012，52（8）：1085-1089.（In Chinese）

[15]王红卫，马勇，谢勇，等.基于平滑A*算法的移动机器人路径规划[J].同济大学学报：自然科学版，2010，38（11）： 1647-1651.

篇（5）

中图分类号:TP393文献标识码:A文章编号:1009-3044(2010)16-4487-03

Research on Path Planning for Mobile Multi-Agent

CHEN Cui-li, GAO Zhen-wei

(Henan Normal University, Xinxiang 453007,China)

Abstract: A path planning method based on both the benefits of global and local path planners is proposed for mobile Multi-Agent path planning in dynamic and unstructured environments. The global path planner uses A*algorithm to generate a series of sub-goal nodes to the target node, and the local path planner adopts an improved potential field method to smooth and optimize the path between the adjacent sub goal nodes. Taking into full consideration the kinematical constraints of the mobile robot, this method cannot only effectively generate a global optimal path using the known information, but also handle the stochastic obstacle information in time. and is simulated on simulation platform developed by using Visual Studio 2005 software, simulation result presents the validity and utility of the algorithm.

Key words: mobile Multi-Agent; global path; local path

在移动智能体相关技术研究中,路径规划技术是一个重要研究领域。移动智能体路径规划问题是指在有障碍的环境中,寻找一条智能体从起始点到目标点的运动路径,使智能体在运动过程中安全、无碰撞地绕过所有的障碍物。这不同于用动态规划等方法求得最短路径,而是指移动智能体能对静态及动态环境下做出综合性判断,进行智能决策。在以往的研究中,移动智能体路径规划方法大体上可以分为三种类型:其一是基于环境模型的路径规划,它能处理完全已知的环境下的路路径规划。而当环境变化时(出现移动障碍物)时,此方法效果较差,具体方法有:A*方法、可视图法、栅格化和拓扑图法等;其二是基于传感器信息的局部路径规划方法,其具体的方法有:人工势场法、模糊逻辑法和遗传算法等;其三是基于行为的导航行为单元,如跟踪和避碰等,这些单元彼此协调工作,完成总体导航任务。随着计算机、传感器及控制技术的发展,特别是各种新算法不断涌现,移动机器人路径规划技术已经取得了丰硕研究成果。

一个好的路径规划方法需要满足如下性能[1]:合理性、完备性、最优性、适时、环境变化适应性和满足约束。有些方法没有高深的理论,但计算简单,实时性、安全性好,就有存在的空间。如何使性能指标更好是各种算法研究的一个重要方向。

在未知的(或部分已知的),动态的非结构的环境下,多智能体利用传统的路径规划方法很难满足前面的性能要求,本文提出了一种将全局路径规划方法和局部规划方法相结合,将基于反应的行为规划和基于慎思的行为规划相结合的路径规划方法,其思路如下:多智能体分别采用A*算法进行全局路径规划,各自生成到达目标点的子目录节点序列,同时采用改进的人工势能对子目录节点序列中相邻节点进行路径的平滑和优化处理,该方法不但能够充分利用已知环境信息生成全局最优路径,而且还能及时处理所遇到的随机障碍(其它智能体)信息,从而提高了多智能体整体的路径规划的性能。

1 路径规划方法

1.1 相关研究

1) A*算法

在最佳优先搜索的研究中,最广范围应有的方法为A*搜索,其基本思想[2]是:它把到达节点的代价g(n)和从该节点到目标节点的代价h(n)结合起来对节点进行评价:f(n) = g(n) + h(n)(1)。A*算法用于移动多智能体的路径规划时,多智能体分别按照已知的地图规划出一条路径,然后沿着这条生成路径运动,但智能体传感探测到的环境信息和原来的环境信息不一致时,智能体重新规划从当前位置到目标点的路径。如此循环直至智能体到达目标点或者发现目标点不可达[3]。重新规划算法依旧是从当前位置到目标点的全局搜索的过程,运算量较大。而且由于采用A*方法规划出的最优路径并没有考虑到机器人的运动学约束,即使机器人可以采用A*方法规划出一条最优路径,机器人也未必可以沿着这条路径运动。

2) 人工势能法

人工势能法由 Khatib 提出的一种虚拟力法[4]。人工势场方法结构简单,便于低层的实时控制,在实时避障和平滑的轨迹控制方面得到了广泛的应用,但根据人工势场方法原理可知,引力势场的范围比较大,而斥力的作用范围只能局部的,当智能体和障碍物超过障碍物影响范围的时候,智能体就不受来自障碍物引起的排斥势场的影响。所以,势场法只能解决局部空间的避障问题,他缺乏所在的全局信息,,这样就造成产生局部最优解不能进行整体规划,智能于局部最小点的时候,智能体容易产生振荡和停滞不前。

1.2 路径规划方法描述

鉴于A*算法全局路径搜索的全局性与改进人工势场算法局部路径搜索的灵活性,通过一定的方法把两者结合起来,其思路如下:多智能体分别采用A*算法进行全局路径规划,各自生成到达目标点的子目录节点序列,同时采用改进的人工势能对子目录节点序列中相邻节点进行路径的平滑和优化处理,该方法不但能够充分利用已知环境信息生成全局最优路径,而且还能及时处理所遇到的随机障碍(其它智能体)信息,从而提高了多智能体整体的路径规划的性能。由于A*方法采用栅格表示地图,栅格粒度越小,障碍物的表示也就越精确,但是同时算法搜索的范围会按指数增加。采用改进人工势场的局部路径规划方法对A*方法进行优化,可以有效增大A*方法的栅格粒度,达到降低A*方法运算量的目的。

2 环境构造

目前主要有三种比较典型的环境建模方法:构型空间法、自由空间法和栅格法,本文仿真实验采用的环境建模方法是栅格法,栅格法将机器人路径规划的环境划分成二维网格,每格为一个单元,并假设障碍的位置和大小已知,且在机器人运动过程中不会发生变化。栅格法中的网格单元共有三种类型,即障碍网格、自由网格和机器人所在网格。目前常用的栅格表示方法有两种,即直角坐标法和序号法。这两种表示方法本质上是一样的,每个单元格都与(x, y)一一对应。本文采用序号法表示栅格,设栅格的中心点坐标为栅格的直角坐标,则每个栅格编号都与其直角坐标一一对应,地图中任意一点(x,y)与栅格编号N的映射关系为:N=INT(xGs)+xmaxGs×INT(yGs),(1)式中,xmax表示x轴的取值范围,Gs表示栅格尺寸的大小,INT函数表示取整,而栅格中心点的坐标为(xG,yG),它与栅格编号N之间的关系为:xG=(N%M)×Gs+Gs/2,yG=INT(N/M)×Gs+Gs/2,(2)式中,M=xmax/Gs,符号%表示取余操作。本文中根据机器人的尺寸来确定栅格的粒度,假设一个栅格能容纳一个智能体,这里选择栅格的大小为40cm×40cm[5]。本文的仿真环境为800cm×800cm,栅格号N=0~399,机器人的初始位置的栅格号为N=42,目标位置的栅格号为N=314。在Visual Studio 2005中进行仿真,仿真结果如图1所示,长方形和椭圆图形代表障碍物栅格,小圆圈所代表的栅格为机器人的起始栅格和目标栅格,剩下的是自由栅格。在路径规划中机器人可以选择自由栅格作为它的路径点。

建立栅格后,对栅格进行初始化。设置变量G_Obstacle为0表示自由栅格,G_Obstacle为1表示障碍网格包括机器人栅格。若障碍物或智能体占当前位置栅格面积大于1/3则设置变量G_Obstacle为1.

3 数据的采集

对于简单地形,我们将实际地形就行考察并进行测量、量化,转化为平面坐标数据最后转换相应的栅格编号。对于复杂地形在没有航摄资料的情况下,本实验以地图为数据源的DTM数据获取方法在,可利用已有的地形图采集地形数据,用手扶跟踪式数字化仪将平面图形转化为平面坐标数据,最后转换相应的栅格编号。

4 实现过程

第1步:对环境信息进行数据采集并转化成相应的平面坐标数据。

第2步:确定各个智能体的初始位置和目标位置。

第3步:建立栅格,对栅格进行初始化。

第4步:智能体S(i)首先根据已知信息规划出各自的一条目标序列S(i)n。

第5步:智能体S(i)利用测试传感器探测到临界危险区L范围内的信息与原有信息是否一致,当智能体利用传感器探测到临界危险区L范围内的信息与原有信息一致时,利用改进后的人工势能算法搜索相邻目标点之间的轨迹,否则智能体搜索从当前序列点S(i)n到S(i)n+4路径。定义临界危险区L、目标序列点S(i)n(n>=1)。

第6步:智能体一旦移动到达目标栅格,则程序终止;否则返回第5步。系统的工作流程如图2所示。

5 仿真结果及结论

在Visual Studio 2005平台上进行了仿真,,首先根据已知环境信息,进行数据采集量化并进行栅格化处理,设置障碍和智能体的大小及位置(为了简单化,本实验所有障碍都设置为圆形),再进行初始化操作,采用0、1二元信息数组存储栅格化的地形。

智能体运用A*算法进行全局路径规划,图3显示两个智能体的运动过程,显然两个智能体的路径相交可能会发生碰撞,智能体为了避免碰撞应重新规划算法依旧是从当前位置到目标点的全局搜索的过程,运算量较大。而且显然只用A*算法规划出二维路径点序列,相邻两点之间的夹角一定是π/4的整倍数,机器人很难按照所生成的序列点运动。智能体采用改进后的人工势场进行目标序列点之间的局部路径规划,图4显示智能体的运动过程。显然智能体的整条运动轨迹显得比较平滑同时又实现实时避障的目的。

6 总结

本文对多智能体在动态环境下路径规划技术进行了研究探索,提出了一种能够将全局路径规划方法和局部路径规划方法相结合,通过仿真取得了很好的结果,证明A*和人工势场算法的结合可行。

参考文献:

[1] 刘华军,杨静宇,陆建峰,等.移动机器人运动规划研究综述[J].中国工程科学,2006,8(1):85-94.

篇（6）

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

一、路径规划的意义

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

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

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

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

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

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

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

（二）路径规划

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

（三）遗传算法

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

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

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

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

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

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

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

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

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

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

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

三、路径规划的仿真

（一）仿真系统的各要素

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

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

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

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

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

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

（二）仿真软件的选择

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

四、小结

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

参考文献：

篇（7）

中图分类号：F715.6 文献标识码：A 文章编号：1001-828X（2014）010-00-01

引言

对于B2C企业配送中心而言，拣选作业占配送中心作业总量的60%[1]。鉴于B2C企业多品种、小批量、多频次、快速响应的客户需求，如何提高配送中心的作业效率，从拣选作业入手效果更佳。纵观拣选作业的研究大多集中于以下几个方面：一是储位分配问题；二是订单分批问题；三是拣选路径优化问题。

一、储位分配问题

货物储位分配是指按照节约拣货时间、减少拣货路径、提高空间利用率等目标，将商品合理放置在合适的储位。合理的储位分配是提高配送中心出入库作业效率和降低搬运成本的有效途经。

1.确立货位分配目标，建立货位分配模型、使用算法进行优化研究。Ene Seval等人使用改进的数学模型和随机进化优化算法，并分两阶段来设计储位分配和拣选系统[1]。Park Changkyu等人聚焦于平面储位分配问题，采用改进的遗传算法，并建立数学模型进行了实证研究[2]。陈璐等人提出了一个混合整数规划模型对该问题进行优化建模，设计开发了一个基于有向连接图的优化算法对储位分配问题求初始解，并用禁忌搜索算法进行改进[3]。吴迪等人以最小化系统总成本及最大化时间满意度为目标建立双目标非线性整数约束规划模型，并提出了基于精英重组的混合多目标进化算法，在此基础上进行关键参数敏感度分析，得出双目标比单目标模型得出的储位分配结果更优[4]。

2.基于研究数据的关联性，解决储位分配问题。Glock Christoph 等人根据比较数据研究，提出不同的存储位置分配策略，并提出容易在实践中使用的启发式算法[5]。Chiang David等人提出一种数据挖掘的基础存储分配方法，在有空货架时为新产品找到最优存储分配，对未赋值的存储位置通过应用关联规则挖掘来解决存储分配问题[6]。王成林等人基于区域关联度的储位规划方法，对储位管理的关联度进行了定义和分析[7]。张志勇等人讨论了利用Apriori算法对仓储管理系统的大规模业务数据进行强关联挖掘，并结合IQ分析来分配货物的储位[8]。

二、订单分批问题

订单分批是指将多张客户订单合并生成一个批次拣货单，并对该批次拣货单进行拣货作业，货物拣选完成后，再将拣选品按照原始订单进行分拣。其目的在于减少拣货人员寻找储位时间、缩短拣货人员的行走距离、提高拣货效率。国内学者李诗珍通过仿真发现订单分批策略对减少作业总时间影响最大。订单分批问题，作为NP难题，针对配送中心订单分批问题的研究可以分为以下两类。

1.基于订单相似度分批，指订单是按照待拣品项所在的储存位置相似或者相近进行分批。伍经纬[9]通过对比订单分批的MAA，FIFS，GSM，COG，GS等五种算法，得出在S型路径下，MAA算法更有效。李诗珍[10]以最小化订单拣选行走距离为目标建立了订单分批模型，并通过以计算订单相似度为核心步骤的种籽算法以及其他与其原理相类似的节约算法、包络算法、基于聚类分析的启发式算法等对模型进行求解与实证分析，并分别对不分批、先到先服务分批、聚类分批下的行走距离进行计算与比较。国外的众多学者对于不同的拣货系统分别提出了不同的种子算法、节约算法等，但本质上都是种子算法。De Koster[11]在多货架矩形系统中结合拣选路径与分批数量，通过仿真模拟得出最简单的分批方法都比先进先出分批方法好，S型路径下拣选设备能与种子算法高效率结合。

2.基于时间窗分批，指在考虑客户的等待时间以及订单处理时间的同时，以最小化订单总时间为目标来决定时间窗大小，也就是将确定或不定的某一时间段的订单作为一个批次进行拣选，总作业时间除以时窗值，即得到分批次数。马士华 在解决配送中心拣货作业中问题中引入延迟制造思想，提出基于时间延迟的动态时窗分批策略，该策略可以消除目前拣货系统存在的等待时间和闲忙不均的现象，实现拣货作业的高效率。对于随即订单到达的情况，很多学者将可变时间窗固定分批批量问题处理为随机服务队列模型。De Koster[11]提出轮换检测动态模型，将分批、拣选、分类看作串联队列，从而实现优化平均拣选作业时间的目的。Won在处理基于客户响应时间的订单分批问题时，以最优化顾客响应时间为目标，提出SBJ和JBP算法以降低订单拣选时间来提高效率。

此外，国内外学者也提出采用遗传算法、启发式算法等来求解订单分批问题。

三、拣选路径问题

拣选作业路径优化的目的是为了减少行走距离与缩短拣货时间，以实现拣选效率的最大化。目前，大多数B2C企业采用固定矩形货架的人工拣货或自动化仓库。路径优化问题属于一类特殊的旅行商问题（TSP），对于拣选路径问题的优化算法主要有启发式算法、神经网络算法、弹性算法，以及近年发展迅速的遗传算法、模拟退货算法、禁忌搜索算法等智能算法。人工拣货作业常采用启发式拣货策略，即穿越策略、中点策略、最大间隙策略、混合策略等。对于B2C企业而言，特别是订单数量多，订购数量少的电商而言，通常采用最简单的S型路径，拣货人员从货架巷道的一端进入，从两边货架上拣取货品，然后转弯进入下一巷道，直至货品拣取完成。

四、拣选作业系统仿真技术

拣货作业问题不仅包括以上三个问题，还包括人员配置、设备选择、流程优化等很多问题，拣货作业系统作为配送中心的核心子系统，它的优化与改进对配送中心效率的提高意义重大。配送中心是典型的现代机械电子相结合的系统，也是典型的随机型离散事件系统，其复杂性与系统性可通过仿真的方法进行设计与优化。目前，物流系统仿真技术已经越来越多的被运用到决策中去，物流系统仿真软件也有了更多的选择性。二维平面式动画表现形式（2D）的有ARENA、Em-Plant、WITNESS、EXTEND，三维立体（3D）的有Flexsim、Automod、RalC、WITNESS等。本质上，物流仿真软件的建模大同小异，都是通过实体的组合来建模，参数的控制来调节，目标的设定来实现，并通过对结果的分析发现瓶颈和做进一步的优化调整。

参考文献：

[1]Ene Seval，Ozturk Nursel. Storage location assignment and order picking optimization in the automotive industry[J]. International Journal of Advanced Manufacturing Technology，2012，60：787-797.

[2]Park Changkyu，Seo Junyong.Mathematical modeling and solving procedure of the planar storage location assignment problem[J]. Computers & Industrial Engineering，2009，57（3）：1062-1071.

[3]陈璐，陆志强.自动化立体仓库中的储位分配及存取路径优化[J].管理工程学报，2012，26（1）：42-47.

篇（8）

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

B-spline Curve based Trajectory Planning for Autonomous Vehicles

QU Pan-rang，LI Lin ， REN Xiao-kun ，JING Li-xiong

（Institute of Aeronautics Computing Technique Research， Xi’an 710065， China）

Abstract：Path planning is an important research topic in the field of the unmanned vehicle motion planning， and it directly affects the performance of unmanned vehicles in a complex traffic environment. Taking the requirement for smoothness into account， this paper proposed a method based on B-spline curve and built a planning model which can be divided into four steps， including path clusters， constraint of maximal curvature， collision detection and optimal path. This method works efficiently and simulation results show efficiency of the method.

Key words：B-spline curve； autonomous vehicle； path planning； collide detection； constraint of maximal curvature

1 引言

近年来，无人驾驶技术备受关注，各大研究机构和企业争相推出各自的无人驾驶平台。无人车作为未来智能交通的主要主体也逐渐融入到我们的日常生活中，比如自主巡航[1]和自动泊车等等。然而，为了使其更好地服务于我们，需要进一步提高其智能化水平，而路径规划作为连接环境感知和运动规划的桥梁，是无人车智能化水平的重要体现[2]。

由于受到自身动力学和运动学模型的约束，车辆的路径规划问题除过要严格满足端点状态约束之外，还要求其中间状态满足运动系统的微分约束。由于实现简单，并且高阶多项式曲线能够很好地满足运动系统的微分约束，生成高阶平滑的路径，所以很多路径规划系统选择使用基于多项式曲线的方法生成路径。B样条曲线是一种典型的多项式曲线，且因为其所有的中间状态均是由控制点加权生成，所以其能够完全满足端点状态约束。综合考虑无人车路径规划的要求和实现复杂度，在仅已知初始位姿和目标位姿的情况下，本文选择B样条曲线生成路径，重点讲述分步规划模型，即路径簇生成、最大曲率约束、碰撞检测以及最优评价四个过程，并通过Matlab仿真对本文方法进行了验证。

2 问题描述

本节分别描述了无人车路径规划问题和B样条曲线。

2.1 路径规划问题描述

路径规划得到的是一条从初始位置到目标位置的路径，即二维平面内一条从初始位置点到目标位置点的曲线，曲线上的每一个点表示车在行驶过程中的一个状态。考虑到实现方便，本文将路径描述成离散点序列[Sstart，S1，???，Sn，Sgoal]，如图1所示，序列中每一个点[Si（xi，yi，θi）]表示车的一个状态，其中[（xi，yi）]表示此时刻车辆的位置，[θi]表示车辆的航向，[Sstart]和[Sgoal]分别表示车辆的初始状态和目标状态。图1中的圆[（xobs1，yobs1，robs1）]表示环境中的障碍物，[（xobs1，yobs1）]表示障碍物的位置信息，[robs1]表示障碍物的半径。

2.2 B样条曲线

如果给定[m+n+1]个控制点[Pi（i=0，1，???，m+n）]，就可以构造[m+1]段[n]次B样条曲线，其可以表示为公式1：

[Pi，n（t）=k=0nPi+k?Fk，n（t） ，t∈[0，1]Fk，n（t）=1n！j=0n-k（-1）j?Cjn+1?（t+n-k-j）n ， t∈[0，1] ， k∈0，1，???，n] （1）

其中，[Pi，n（t）]表示第[i]个[n]次B样条曲线片段，[n]表示B样条曲线的次数，[t]为控制参数，其取值范围为[[0，1]]，[Pi+k]为控制点，[Fk，n（t）]为B样条基。依次连接全部[n]阶B样条曲线段就组成了整条B样条曲线。

3 本文算法

本节重点讲述基于B样条曲线的路径规划方法和基于该方法生成路径的过程。

3.1 基于B样条曲线的路径规划方法

选择三阶B样条曲线生成几何路径，即每四个控制点生成一个路径片段，然后通过片段的拼接就可以实现从初始状态到目标状态的路径规划，下面着重讲述基于六控制点的三阶B样条曲线生成满足车辆端点位姿约束路径的方法，如图2所示。

l 依据初始状态选择控制点[P0，P1，P2]。当[P0，P1，P2]三个控制点共线，并且[P1]为线段[P0P2]的中点时，生成的B样条曲线与线段[P0P2]相切于点[P1]。所以选择无人车的初始位置为控制点[P1]，将控制点[P0]和[P2]选在初始航向角[θstart]所在直线上，并关于控制点[P1]对称。如是，即能满足车辆的初始位姿约束；

l 依据目标状态选择控制点[P3，P4，P5]。当[P3，P4，P5]三个控制点共线，并且[P4]为线段[P3P5]的中点时，生成的B样条曲线与线段[P3P5]相切与点[P4]。所以选择无人车的目标位置为控制点[P3]，将控制点[P3]和[P5]选在目标航向角[θgoal]所在的直线上，并关于控制点[P3]对称。如是，即能满足车辆的目标位姿约束。

（a） 路径簇

（b） 最大曲率约束

（c） 碰撞检测

3.2 分步路径规划

本小节将以图3所给定的场景为例，讲述最优路径生成的过程。

3.2.1 路径簇生成

在选定控制点[P1]和[P4]之后，通过选择不同的控制点[P2]和[P3]，从而得到多组控制点，进而得到多条路径。将控制点选择的极限定为线段[P1P2]、[P3P4]与[P1P4]相等，但是[P1P2]和[P3P4]不能出现交叉。将这个范围等间隔量化，各取四个点，共组成16组控制点，得到16条路径，如图3（a）中的蓝色曲线所示。

3.2.3 最大曲率约束

理论上，车辆的最小转弯半径[Rmin=Lsin（θmax）]是其本身属性[3]，只取决于车辆的轴距[L]和最大前轮转角[θmax]。那么，车辆可行驶路径的最大曲率[κmax=1Rmin]也是固定的，假设无人车可行驶路径的最大曲率[κmax=16]，以此为约束条件，在路径簇中选择满足最大曲率约束的路径，如图3（b）所示，图中绿色曲线表示不满足最大曲率约束的路径。

3.2.4 碰撞检测

碰撞检测的目的是保证车辆在规划路径上行驶而不与障碍物发生碰撞。采取的碰撞检测的方法很简单，因为环境中的障碍物采用圆来描述，所以只要判断路径上每一点到圆心的距离与障碍物半径的关系，就能确定其是否发生碰撞。由两点间距离公式：

[d=（x1-x2）2+（y1-y2）2] （2）

如果[d]大于障碍物半径，则不发生碰撞；如果[d]小于障碍物半径，则发生碰撞。图3（c）中的蓝色曲线表示既满足最大曲率约束，又不与障碍物碰撞的路径。

3.2.2 最优路径

路径要求的侧重点不同，优化的目标函数也可以有多种选择，常用的目标函数有最短和最平滑等。其中，路径最短可以抽象成优化问题：

[traoptimal=arg mintraids] （3）

路径最平滑可以抽象成优化问题：

[traoptimal=arg mintraiκ2] （4）

式中，[traoptimal]为最优路径，[traids]为第[i]条路径的长度，[traiκ2]为第[i]条路径上所有点处的曲率平方之和。图3（d）中的红色曲线即为得到的最短可行驶路径。

如是，就能得到满足车辆运动学约束，并且无碰撞的最优路径。

4 结论

本文选择使用B样条曲线解决无人车路径规划问题，并建立了基于B样条曲线的分步规划模型。仿真结果表明，使用基于B样条曲线的路径规划方法能够很好地解决简单障碍物场景中无人车的路径规划问题，并且因为路径生成过程简单，所以该方法常常表现得十分高效，能够完全满足无人车路径规划系统对算法实时性的要求。

参考文献：

篇（9）

DOI：10.16640/ki.37-1222/t.2016.21.135

0 前言

移动机器人的实现涉及自动控制、智能、机械等多种学科。它通常被应用在医疗领域、工业领域等方面。从整体角度来讲，移动机器人的应用促进了生产效率的显著提升。路径规划技术是移动机器人的关键技术之一，研究该技术具有一定的现实意义。

1 路径规划技术的作用

将路径规划技术应用在移动机器人中，能够产生的作用主要包含以下几种：

（1）运动方面。路径规划技术的主要作用是其能够保证移动机器人完成从起点到终点的运动。（2）障碍物方面。设计移动机器人的最终目的是将其应用在实际环境中，在实际环境下，移动机器人的运行路线中可能存在一定数量的障碍物，为了保证最终目的地的顺利达到，需要利用路径规划技术实现对障碍物的有效避开[1]。（3）运行轨迹方面。对于移动机器人而言，除了实现障碍物躲避、达到最终目的地这两种作用之外，应用路径规划技术还可以产生一定的优化运行轨迹作用。在移动机器人的使用过程中，在路径规划技术的作用下，机器人可以完成对最佳运行路线的判断，进而更好地完成相应任务。

2 移动机器人路径规划技术综述

移动机器人的路径规划技术主要包含以下几种：

2.1 局部路径规划方面

在局部路径规划方面，能够被应用在移动机器人中的技术主要包含以下几种：

（1）神经网络路径规划技术。从本质上讲，可以将移动机器人的路径规划看成是空间到行为空间感知过程的一种映射，因此，可以利用神经网络的方式将其表现出来。就神经网络路径规划技术而言，首先需要将相关传感器数据当成网络输入，并将网络输出看成是某固定场合中期望运动方向角增量。在这种情况下，原始样本集则可以用不同选定位置对应的数据代替。为了保证样本集数据的有效性，需要将原始样本集中的冲突样本数据以及重复样本数据剔除掉。对最终样本集应用模糊规则，实现神经网络的有效训练。当典型样本学习完成之后，移动机器人对规则的掌握水平发生了显著提升，进而使得移动机器人在产生智能性能的基础上，顺利完成相应运动[2]。

（2）人工势场路径规划技术。这种规划技术是指，将移动机器人在实际环境中的运动过程当成其在虚拟人工受力场中的一种运动。在虚拟人工受力场中，目标终点会对移动机器人产生一定的引力，而该受力场中的障碍物则会对其产生一定的斥力。在某固定算法的作用下，这两种不同的作用力会产生相应的势，进而形成势场。当移动机器人在该场中运动时，势场中的抽象力会作用在移动机器人上，使得其完成对障碍物的有效避开。在人工势场路径规划技术的实际应用过程中，由于结构简单等因素的影响，移动机器人在到达终点之前可能会停留在局部最优点位置上。对此，需要从数学的角度出发，对势场方程进行重新定义，通过这种方式排除势场中的局部极值，继而保证移动机器人运动的顺利进行[3]。

（3）遗传路径规划技术。这种路径规划技术建立在自然遗传机制等理论的基础上。这种技术通过变异、选择以及交叉对控制机构的正确计算程序进行合理编制，进而实现数学方式基础上生物进化过程的合理模拟。当移动机器人的适应度函数为正数时，允许适应度函数具有不连续或不可导特点。由于这种路径规划技术不涉及梯度信息，因此其能够更好地解决移动机器人在实际运动过程中遇到的问题。遗传路径规划技术的应用优势在于，它能够实现跟踪与规划的同时进行，因此，遗传路径规划技术通常被应用在具有时变特点的未知环境中。

2.2 全局路径规划方面

在该方面，可以被应用在移动机器人中的技术主要包含以下几种：

（1）栅格路径规划技术。这种技术是指，在将实际工作环境分成许多包含二值信息的网格单元的基础上，应用优化算法完成最佳路径的规划搜索。在这种规划技术中，其网格单元通常是由八叉树或者四叉树的方式表示出来。在该技术的应用中，栅格的作用是完成相关环境信息的记录。如果栅格中某位置的累计值相对较低，代表移动机器人可以从该位置通过；如果栅格中某个位置的累计值相对较高，则表示该位置存在障碍物，此时，移动机器人需要利用优化算法将该障碍物避开[4]。

（2）可视图路径规划技术。这种路径规划技术是指，将整个移动机器人看成一个点，然后分别将其与障碍物以及目标终点连接起来，上述连线要求为保证所连直线不会碰触障碍物。当所有连线都连完之后，即完成了一整张可视图。在该可视图中，由于起点到目标终点之间的连线都不涉及障碍物，因此上述所有连线都属于有效直线。在这种情况下，需要解决的问题主要是从这些连线中找出一条距离最短的连线。对此，需要应用优化算法将可视图中距离较长的连线删除，这种处理方式能够有效提升移动机器人的搜索时间。

（3）拓扑路径规划技术。这种规划技术是指，将移动机器人的移动范围，即规划区域分成多个具有拓扑特征的子空间，然后利用不同子空间之间的连通性完成拓扑网络的构建。当该网络构建完成后，直接从网络中找出能够使得机器人顺利从起点移动到终点的拓扑路径，将所得的拓扑路径作为参考依据完成几何路径的计算。这种规划技术的劣势主要表现为其拓扑网络的构建过程较为复杂。但这种规划技术可以实现移动机器人搜索空间的有效缩小[5]。

3 结论

路径规划技术主要分为局部规划和全局规划两方面。这两方面分别包含人工势场路径规划技术以及神经网络路径规划技术等。应用这些规划技术之后，移动机器人可以在避开障碍物的基础上，顺利完成起点到终点最优运行轨迹的运动。

参考文献：

[1]朱大奇，颜明重.移动机器人路径规划技术综述[J].控制与决策，2010（07）：961-967.

[2]张捍东，郑睿，岑豫皖.移动机器人路径规划技术的现状与展望[J].系统仿真学报，2005（02）：439-443.

[3]鲍庆勇，李舜酩，沈`，门秀花.自主移动机器人局部路径规划综述[J].传感器与微系统，2009（09）：1-4+11.

篇（10）

一、库存与配送系统联合优化研究分类

1.联合优化思路。在库存与配送联合优化研究提出之前，大多学者都是单独对企业库存与配送进行研究的，比如考虑输入输出对动态库存进行研究，单独进行配送线路规划，动态库存管理研究中输入输出是已知的，没有考虑输入输出受企业采购过程中供应商配送的影响，而单独的运输线路规划问题则没有考虑库存内部动态管理，因此，对库存与配送系统联合优化研究很有必要，目前该类研究大致可以分为以下类型：

一类研究基于供应链整体成本，构建模型求得整体的订货量与配送策略。此类研究综合考虑了供应链各节点企业的三大成本“库存、采购与运输”，基于各方需求统一确定，互相了解需求，并且不允许缺货情况的发生，运输服务统一由第三方提供，构建的目标优化模型以生产商的生产成本、零售商的采购、库存成本，以及运输服务提供方的运输成本，以此求得最优解。但是该类研究没有考虑供应链参与各方的合作情况，各方对于利益的分配、成本的分摊机制没有考虑，容易造成分配不均而产生摩擦。

另外一类研究则是是由供应商主导库存配送，考虑一个供应商对多个零售商的库存-配送进行管理，构建模型对各独立零售商的库存进行管理，基于各地库存对时间、数量的需求，以自身成本最小为目标，进行路线规划，及时给零售商补货。供应商管理库存与前一类研究不同，两类研究均从总体成本最优角度出发，但是前一类研究没有厘清供应链中各企业角色，及相应的职责，此类研究确定了供应商管理库存，则明确了研究的类型，对于成本分配问题有了较好的解决。通过建立合理的数学算法可以对基于库存考虑的线路规划问题求得最优解，通过供应链各节点的协同配合促进运作效率，各方均获得最大收益，为实际供应链运作提供参考。

2.算法研究分类。库存-配送系统可以视为库存-路径问题的升级版，但是本质考虑的重点仍然是供应链各方库存保有量、采购量、采购周期，与运输路径选择之间的合理调节。对于库存-路径问题的算法研究较多，我们可以借鉴其相关算法应用于库存-配送系统研究。

（1）启发式算法。运用启发式算法对库存-路径问题进行求解的研究比较普遍，如蚁群算法、邻域搜索算法、禁忌搜索算法、模拟退火算法、遗传算法及人工神经网络等智能算法都或多或少有应用于库存-路径研究领域，其中遗传算法有较好的收敛性，能较快地达到全局最优解，并且有优胜劣汰的算法规则，最多地被运用或改进后运用于库存-路径求解。

（2）C-W节约算法。C-W算法是解决旅行商提出的，基于节约的理念，适用于物流单元间流量较为稳定，变化不大的问题，是一种较为简洁实用的算法。由供应商主导库存，为多个零售商供货可以解决信息不对称造成的库存过度配置，配送次数多配送量过大的情形，可以达到配送次数最少，配送量最经济（供应商、零售商采用最佳采购量）的效果，此时配送路线上配送较为稳定，配送变化不会太大，不会因为市场需求变动过大而引起配送问题，因为供应商对零售商的库存需求情况十分了解。因此C-W算法比较适合研究库存-路径问题，多数学者采用遗传算法或其他优化算法是都会结合C-W算法特点进行研究。

（3）其他算法。除运筹学领域优化算法、智能算法与C-W算法这几类典型的库存-路径求解算法之外，一些学者还采用概率论领域的马尔科夫决策过程研究随机需求下的库存-路径算法，也有学者采用分散决策算法（DDA decentralized decision algorithm）以求解分散决策情形下的库存与运输问题）。

二、库存与配送系统联合优化模型构建

库存与配送系统联合优化是促进供应链一体化的有效手段，本文基于供应商统一管理库存构建一个供应商对多个零售商配送的简单两级供应链模型。

1.模型假设。（1）各零售商需求确定，且均与供应商形成直接连接网络；（2）零售商不允许缺货，不考虑提前期；（3）运输费用与距离成正比；（4）一个运输车辆一天只做一次配送，在不超过运输车辆的满载负荷前提下可以为多个零售商配送；（5）多个零售商的不同货物可以拼车运货，这一点由供应商统一管理库存，统一配送可以比较好地解决。