路径规划典型算法精品(七篇)

序论：写作是一种深度的自我表达。它要求我们深入探索自己的思想和情感，挖掘那些隐藏在内心深处的真相，好投稿为您带来了七篇路径规划典型算法范文，愿它们成为您写作过程中的灵感催化剂，助力您的创作。

篇(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 移动机器人路径规划技术的发展展望

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

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

参考文献

[1]陈陈.优化方法与最优控制[M].北京:机械工业出版社,1993.

篇(2)

关键词：移动机器人；路径规划；A*算法；栅格法

中图分类号：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.

WANG Hongwei， MA Yong， XIE Yong， et al. Mobile robot optimal path planning based on smoothing A* algorithm[J]. Journal of Tongji University：Natural Science， 2010，38（11）：1647-1651.（In Chinese）

篇(3)

关键词：储位分配；订单分批；拣选路径；仿真技术

中图分类号：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.

[4]吴迪，李苏剑，李海涛.基于时间满意度的混合渠道库存及分配策略[J].山东大学（理学版），2013，48（6）：51-60

篇(4)

关键词：库存配送系统；联合优化；遗传算法；C-W算法

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

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）多个零售商的不同货物可以拼车运货，这一点由供应商统一管理库存，统一配送可以比较好地解决。

2.符号表示。本文考虑的是由供应商管理库存，由单供应商与多个零售商构成的一对多的简单二级供应链，用数字序号下标表示供应商与零售商，i∈（0，1，2，...，N），0表示供应商，1至N表示零售商。货物由供应商负责配送，共有M辆运输车，每辆车的载重相等为Q，供应商的补货周期为T，eij表示供应商及各零售商之间的距离，di表示零售商的需求率，A0，Ai表示供应商与零售商的补货成本，h0与hi表示供应商与零售商的库存成本，C表示车辆的运输成本，在供应商的补货周期内，ni表示零售商的订货次数，ti表示零售商的订货周期，则T=niti，令Xijkt表示车辆k在时间t从点i开往j进行配送，是则值为1，否则为0，令Qjkr表示车辆k在时间r为点j配送的货物量。

篇(5)

关键词：迷宫问题，机器人，深度优先

 

0 引言

迷宫最短路径问题是一个典型的搜索、遍历问题，目前很多学者提出了一些新的迷宫路径求解算法如如遗传算法[1]、脉冲耦合神经网络[2] 、蚁群算法[3]、反应扩散搜索[4]等，在迷宫最优路径仿真搜索方面做出了一定的成绩，但上述算法需要进行大规模的运算，对处理器的要求很高，因此只能应用于仿真层次，对于实际的物理系统来说实现起来是有困难的。

迷宫问题经典的算法是深度优先算法和广度优先算法，深度优先算法是从迷宫的入口出发，顺着某一方向向前探索，若能走通，则继续前进，否则沿原路退回（回溯)，换一个方向再继续探索，直到所有可能的通路都探索到为止，深度优先算法可以在未知迷宫中找到一条可行但不一定是最优的通路。广度优先搜索是从入口出发，离开入口后依次搜索与当前位置相邻的单元格，然后分别从这些相邻单元格出发依次访问它们的邻接格，依次类推直到找到迷宫出口，算法可以找到迷宫的最优路径，但探索点会随着探索的深入急剧增加，需要大量的内存空间用来保存探索过程的记录。

考虑到实际物理系统内存容量和运算速度的限制以及以上算法的优缺点，带回溯的深度优先算法具有占用内存空间少，对处理器的速度要求不高，不需要知道迷宫内部的具体结构的特点，因此适合于机器人在未知迷宫中进行路径搜索。免费论文参考网。

1迷宫机器人结构描述

智能移动机器人技术是机器人研究领域的一个重要分支，智能移动机器人是指机器人在完全未知的环境中，实时自主运动，是集环境感知、动态决策与规划、行为控制与执行等功能于一体的具有高度自动化程度的智能化装置。因此走迷宫机器人是在没有人工干预的情况下，通过机器人自身的传感器系统感知迷宫环境，并根据不同的迷宫环境做出不同的决策并驱动执行装置执行相应的动作来完成走迷宫的过程的一种机器人。免费论文参考网。

1.1机械结构描述

机器人的移动方式有很多种，但大致可分为车轮式

和足步式两种，车轮移动方式的大部分技术比较成熟，

控制也比较容易，而足步行走方式的控制要困难得多，

因此本文的迷宫机器人采用轮式移动机构，其机械结构如图1所示：它有三个车轮，其中前轮为从动轮，为万向自由轮，后两轮为相互独立的驱动轮，固定不可转向，并且每个轮子都有独立的电气驱动模块和变速机构，车身的方向和速度依靠改变两轮的速度来实现。

1.2传感器系统

环境感知能力是移动机器人除了移动之外最为基本的一种能力，感知能力的高低直接决定了一个机器人的智能性高低，它的作用是建立合理的机器人感觉系统，以便机器人能够建立起完整的信息获取渠道。机器人要具备智能行为就必需依靠传感器不断感知外界环境，从而做出相应的决策行为。目前传感器的种类繁多，功能越来越丰富，像超声波传感器、红外传感器、光电传感等。传感器系统是机器人很重要的

部分，选择机器人传感器完全取决于机器人的工作需要和应用特点，因此迷宫机器人具有如下传感器系统：其传感器系统包括3个红外传感器和2两个光电传感器，3三个红外传感器位于机器人的左前右方（如图1中箭头3所示），探测距离是6cm，分别对机器人左前右三个方向的迷宫墙壁进行探测，以便机器人建立起迷宫障碍物的完整信息，光电传感器1用来检测是否进入一个新的迷宫格中，而传感器2主要用来和1配合以识别机器人是否到达终点。

1.3 控制系统

控制系统主要包括单片机及其外围电路以及电机驱动模块、串行通讯模块等，单片机采用了ATMEL公司的ATmega16微控制器，在16MHZ频率下速度为16MIPS的8位RISC结构单片机，其内含硬件乘法器和16K的flash，支持ISP编程，运算速度比普通的单片机要快的多，因此可以满足系统的需要。

2 迷宫问题描述

迷宫问题是图形学、图论和数据结构等领域中广为人知的一个经典问题，我们把迷宫简化成如右图2所示：图中‘1’表示障碍物，‘0’表示通路，机器人从入口处进入，从出口出来就算成功的走出迷宫。

3算法仿真试验

3.1算法描述如下：

：初始化，随机生成符合要求的m行n列的迷宫maze（m，n），通过调整迷宫数组中0和1的个数比调节迷

宫的可行通路数量，0越多，则迷宫的可行路径就越多，就越容

易找到出口。设定方向数组dir：规定搜索迷宫只能向上下左右四个方向搜索，对于正方形迷宫，设边长为1个单位，因此可以设定方向数组dir（4，2）=[1 0;0 1;0 -1;-1 0]。行进经过结点记录数组jiedian（i，j）用来记录机器人探索过的每个结点，如果机器人走过结点（i，j），则jiedian（i，j）=1，否则为0。走过路径记录数组way用来记录机器人行走过程的可行路径信息。

：机器人开始行走，从当前结点开始向三个方向搜索，如果没有障碍物（即该方向的迷宫壁为0）且不是终点并且没有走过（即jiedian（i，j）=0），则把该结点记录到jiedian中。

：如果只有一个结点符合要求，则以该结点为起点继续过程，同时把该结点记录到way中，如果有两个或两个以上的结点，则从中随机选择一个结点为起点继续过程，并把该结点记录到way中。免费论文参考网。

：如果三个方向都有障碍物，则机器人进行回溯，退回上一个结点，选择排除已经探索方向的其它方向继续搜索，如果没有可通路径则继续回溯直到回到起点，转到，否则转到继续搜索直到找到终点，转。

：给出没有可行路径信息。

：输出可行路径。

3.2实验结果过程及结果：

为了验证算法的有效性，我们随机生成一个22*22规模的迷宫，应用深度优先算法进行迷宫路径搜索，其仿真结果如3图所示：图中‘o’表示迷宫的‘0’，‘’表示迷宫中的1，左上角为迷宫的入口，右下角为迷宫的出口，深色部分表示算法找到的可行迷宫路径，从图3中可以看到：深度优先算法可以在迷宫中找到一条可行路径。

4 物理系统实现：

图 3 深度优先算法找到的路径示意图

机器人路径规划问题可以分为两种，一种是基于环境先验完全信息的全局路径规划，另一种是基于传感器信息的局部路径规划，后者环境是未知或者部分未知的。基于实际物理系统的特点，我们把该算法应用到我们研制的迷宫机器人上，在不影响算法正确性的情况下，我们采用图4所示的简化迷宫进行实验：带箭头的白线是机器人实际所走路线图，可以看到机器人从入口出发，按照带回溯的深度优先算法行走，经过一定的时间后能够顺利的找到出口，完成了在未知迷宫中的行走过程，实验证明了算法的有效性。

5结论：

迷宫问题是一个经典的遍历问题，求解算法很多，但对于实际的物理系统，考虑到其运算速度和内存大小的局限，运用深度优先算法进行迷宫路径的搜索是可行的，从仿真实验和物理实验都可以看出，深度优先算法是有效的。

 

参考文献：

[1] SU S,Tsuchiya K. Learning of a maze using a genetic algorithm[c]. IndustrialElectronics, Control and Instrumentation 1993, Proceedings of the IECON’93International Conference On, 1993, 1: 376-379.

[2] 宋寅卯，袁端磊.基于PCNN的迷宫最短路径求解算法[J].电路与系统学报.2005,10(3)： 72-75.

[3] 胡小兵，黄席樾. 蚁群算法在迷宫最优路径问题中的应用[J].计算机仿真.2005，22（4）：115-116.

篇(6)

关键词TSP问题 0-1规划 智能算法

中图分类号：O158 文献标识码：A 文章编号：1007-9416（2014）05-0139-02

旅行商问题（Traveling Salesman Problem， TSP）是典型的组合优化问题，很多优化问题都可以直接或间接的转为为TSP问题，而且TSP问题已被证明具有NPC计算复杂性，有很大的求解难度，因此研究TSP问题的求解方法有着很大的实际意义。本文旨在介绍求解TSP的几种常用解法，并结合实例比较这些算法的性能，为TSP的求解提供一些参考。

1 TSP问题描述

TSP问题的数学表述为：一个有穷的城市集合C={C1，C2，…，Cm}，对于每一对城市Ci，Cj∈C有距离d（Ci，Cj）∈R+。问：经过C中所有城市的旅行路线，记为序列，是否存在最小的正数B，对所有可能的序列都有

2 TSP问题几种常用求解方法

TSP问题有着很多求解算法，主要有。

2.1 贪婪算法

贪婪算法[2]（Greedy algorithm）是求解大规模TSP问题的常用算法之一，是一种求解优化问题的简单、迅速的求解办法。贪婪法有限考虑当前情况下最优的优化测度，自顶向下，逐步迭代，具有算法简单，耗时短的特点。但贪婪算法的求解结果往往不是最优的，甚至可能与全局最优解间有不小的差距。

2.2 模拟退火算法

模拟退火（Simulated Annealing，SA）算法是求解TSP问题的有效方法之一，容易编程实现，求解速度快。模拟退火是一种全局优化算法，加入了随机状态模型，使算法以概率选择的方式逼近最优状态，其收敛性可以得到严格的理论证明。模拟退火算法具有一整套完整的退火搜索计划，包括足够高的初始温度、缓慢的退火速度、大量的迭代次数及足够的概率扰动[3]。

2.3 遗传算法

遗传算法（Genetic Algorithm，GA）是一种常用的智能算法，具有全局搜索能力，对TSP问题有良好的效果。遗传算法是由Michigan大学的J.Holland教授于1975年提出，算法通常由编码、个体适应度评估和遗传运算三部分构成，其中遗传运算包括染色体复制、交叉、变异和倒位等[4]。

2.4 粒子群算法

粒子群算法（Particle Swarm Optimization，PSO）是依据鸟类觅食的群体性模型而发明的新型智能算法，是由美国电气工程师Eberhart和社会心理学家Kennedy于1995年提出，具有通用性强，参数少，容易实现，收敛速度快等优点，也是解决TSP问题的有效算法之一[5]。

2.5 蚁群算法

蚁群算法（Ant Colony Optimization，ACO）是根据蚂蚁发现路径的行为的而发明的用于寻求优化路径的机率型算法，由Marco Dorigo于1992年在他的博士论文中提出。蚁群算法是一种模拟进化算法，具有包括较强的鲁棒性在内的许多优良性质，在本质上是一种并行的分布式算法，容易实现，可以较好地求解TSP问题[6]。

3 实例计算

选取我国北京、天津、武汉、深圳、长沙、成都、杭州、西安、拉萨、南昌等十个城市，分别使用1-10对十个城市进行编号，获取十个城市的距离矩阵，使用上节所述算法进行求解。已知路径最小长度为12055，最优路径为2-1-8-9-6-3-5-4-10-7-2，求解结果如表1所示。

图1为四种智能算法的收敛状态。

4 各种求解算法的比较

根据本文的实例计算和相关文献[7]，可以给出各算法的比较。

5 结语

TSP问题有着很大的求解难度，但并不意味着无法进行有效的求解，使用一些比较成熟的智能化算法进行求解，可以获得较好的解答。当然各种近似求解算法还有着一些固有的缺陷，在不同情况下有着不同的性能表现，需要在使用时加以选择。

参考文献

[1]谢金星，薛毅.优化建模与Lindo/Lingo软件.北京：清华大学出版社，2005.

[2]黄辉，梁国宏等.求解一类线性规划问题的原始贪婪算法和对偶贪婪算法及其相互关系[J].兰州交通大学学报，2007，26（1）：149-152.

[3]田澎，王浣尘等.旅行商问题（TSP）的模拟退火求解[J].上海交通大学学报，1995，S1：111-116.

[4]胡玉兰.基于遗传算法的旅行商问题仿真实现[J].控制工程，2002，6：79-81.

[5]严露.粒子群算法研究与应用[D].电子科技大学硕士论文，2013.

篇(7)

交通信息采集技术研究现状

目前，交通信息采集手段可以分为2类:(1)通过人工采集获取，如:交通调查数据、交通事件信息等;(2)通过各类交通信息检测系统实时自动采集，自动采集技术包括移动型交通采集技术和固定型交通采集技术。固定型采集技术固定型采集技术是运用安装在固定地点的检测设备对道路进行交通参数检测的方法，能够提供交通流量、地点平均速度、车头时距、车型分类和车道占有率等参数。目前，常用的固定检测器有:环形线圈检测器、微波检测器、视频检测器、红外检测器、超声波检测器等。各种检测技术都有不同的优缺点(见表1)，在工程建设时，需根据环境条件和具体需求进行选择，也可在同一系统中采用多种检测方式，通过对多源交通数据的融合处理提高检测精度。移动型采集技术移动型采集技术是运用安装有GPS定位设备的移动车辆(浮动车)检测道路上的固定标识物来采集交通参数的方法。移动型采集技术主要有:电子标签、GPS、蜂窝网络和汽车牌照自动识别［8］。其中基于GPS的动态交通数据采集技术是当前最主要的移动型采集技术。目前，对该技术的理论研究重点主要包括提高采集数据质量的方法和计算样本量的方法等。目前市场上的车载终端硬件都有一些数据校正算法对数据进行预处理，剔除或修正异常数据，以保证数据质量。样本量计算，即根据信息检测要求或估计精度要求计算所需的浮动车数量，以求在满足应用精度要求和信息采集成本二者之间寻找平衡点，目前，相关计算方法研究已比较成熟。

交通信息处理技术研究现状

浮动车信息处理技术浮动车信息处理是实现对浮动车GPS数据的格式转换、预处理、统计分析、地图匹配、浮动车最小样本量估计、从而得到各路段的速度趋势、旅行时间、路况等交通信息。其中重点研究内容在地图匹配和行程速度估计2方面。在地图匹配问题研究方面，国内学者提出了很多算法，例如基于概率统计的地图匹配算法、基于曲线拟合的地图匹配算法、基于权重的地图匹配算法、基于卡尔曼滤波的地图匹配算法、基于模糊逻辑的地图匹配算法等［9－13］。针对浮动车数据大规模、长间隔的特点，其算法与传统的导航地图匹配算法有一定区别。刘彦挺提出了一种将基于权值、道路拓扑和最优路径选择相结合的综合地图匹配算法［14］，章威提出了浮动车地图匹配模型族的解决方案，设计了浮动车数据地图匹配算法体系［15］。在行程速度估计研究方面，QuirogaCesarA提出了行程速度积分计算方法［16］，董均宇建立了GPS浮动车路段平均速度估计的数据融合模型［17］，章威在对平均速度和平均通过时间算法误差分析的基础上，提出了基于浮动车技术的目标路段行车速度估计算法［18］。行程时间预测目前广泛应用的行程时间预测模型包括:历史平均模型、ARIMA模型、卡尔曼滤波模型、神经网络模型和非参数回归模型等［19］。例如:动态路径诱导系统中使用历史平均模型对行程时间进行预测，文献［20］中使用ARIMA模型对城市主干道的行程时间进行预测，朱中在文献［21］中使用卡尔曼滤波理论对行程时间进行预测，杨兆升在文献［22］中建立了基于BP神经网络的行程时间预测模型，朱耿先在文献［23］中使用RBF神经网络对行程时间进行预测。对于短时交通流预测，根据理论基础的不同，可以将预测方法分为2大类:统计预测方法和人工智能方法［24］。统计预测方法又可以分为回归分析预测、时间序列预测以及概率预测等。它们均尝试把交通流参数看成一个时间变量，从而找到这一时间序列中隐含的统计规律或关系。这些方法比较成熟、算法简单、速度快，但是过分依赖于用数学模型来刻画交通流特征或者需要很强的经验判断，这将直接影响到这类方法的有效性和预测精度。另外，传统统计学研究的是样本数目逼近无穷大的渐进理论，当样本数目有限时就难以取得理想的效果，因此很难适应目前复杂多变的交通状况。由于受到这些条件的制约，采用统计预测方法进行短时交通流预测的效果并不理想［25］。人工智能方法中的典型代表就是神经网络方法。神经网络凭借其逼近任意非线性函数的能力和所具有的容错、自学习等优点，已被国内外学者用于建立交通流量预测模型，并取得了不少有效的研究成果［26－28］。虽然神经网络能够根据历史数据进行学习训练和经验积累，具有自适应能力的优点，但是它得到的结果是基于经验风险最小化的，需要有足够大的样本数据数量，可能还会出现过学习问题以及求得局部极小解的问题［29］。这些不足，使神经网络在交通流量预测中的应用效果不如期望的那样好，对于非平稳的短时交通流，当输入信号中混有噪声时，神经网络预测的精度更差［30］。由Vapnik等提出支持向量机(SupportVectorMachines，SVM)的机器学习算法［31］，与传统的神经网络学习方法相比，实现了结构风险最小化原理(StructureRiskMinimization，SRM)，它同时最小化经验风险和VC维(Vapnik－ChervonenkisDimension)的界，这就取得了较小的实际风险，从而对未来的样本有较好的泛化性能。SVM能够有效解决小样本、非线性等回归问题，泛化能力强，并能找到全局最优解，克服了神经网络局部极值的难题［32－33］。路径规划最优路径规划是交通出行信息服务平台提供信息服务的重要内容之一。在国内外，有大量的关于路径规划算法的研究，常见的路径规划算法主要有Dijkstra算法，Bellman－Ford算法、Floyd算法、启发式搜索算法、A*算法等。还有很多为车辆导航而改进的算法，如K最短路径算法、遗传算法、蚁群算法和神经网络算法等［34－35］。为了改进算法的性能和提高算法的适用性，很多学者对相关问题进行了系统和深入的研究。陆峰从问题类型、网络类型和实现方法3方面对最短路径算法进行了系统的分类［36］;张可提出了基于路阻函数模型和信号交叉口延误模型，标定以出行时间度量的道路权重的方法体系，以及适合车辆导航的路径优化推荐算法［37］，郑年波根据对偶图思想，定义搜索节点结构，处理交叉口转向限制和延误，并提出了基于搜索节点的双向启发式A*算法［38］。Car＆Frank提出了基于层次空间推理的交通网络行车最优路径算法［39］。陆峰、付梦印、李清泉、吴一民等人也对分层路径规划算法进行了深入研究，提出了切实可行的推理规则和算法，并开展了相关的实验验证［40－43］。目前，还有一种研究趋势是利用从移动对象轨迹数据中挖掘出的“热点路径”来辅助路网分层，从而提高层次路径规划的合理性和可用性［44－45］。对于动态路径规划，苏永云和晏克非建立了路段动态行程时间计算模型，并运用到动态最短路径改进A*算法中［46－47］。

交通信息技术发展现状

交通信息技术常常被研究者所忽视，国内相关的研究不多，工程实践中也缺乏可行的标准指导。交通信息技术的研究侧重包括信息方式和内容的选择与设计、信息子系统架构、交通信息协议和用于交通信息的移动通信技术。交通信息方式提供信息服务的方式和载体有:交通信息咨询服务热线电话、交通信息服务网站查询、电子信箱定制、移动通信短信息定制或点播、触摸屏终端查询、静态指示牌、电子情报板、交通信息广播电台、车载智能交互显示终端、路侧广播系统等。通常，由于公众出行信息服务平台服务对象的广泛性和服务内容的多样性，需要多种信息方式综合以达到最佳效果。交通信息协议目前，面向移动终端的交通信息协议在国际上主要有3个:TMC、TPEG和VICS。TPEG是TMC未来的替布协议，VICS则是日本VICS系统应用的协议［6］。我国的RDS-TMC标准是在参考国际标准中的ISO14189-1/14189-2/14189-3的基础上，结合我国特点，于2006年11月正式［48］。但目前没有配套全国统一的位置表(LocationTable)，因此，使用企业内部信息标准，是各交通信息服务商的现实选择，如文献［6］中提出的基于LINK的面向移动终端的交通信息协议。交通信息的无线通信技术对移动终端实时交通信息，必须使用无线数据通道，目前可选择的无线通信技术主要包括:调频多工数据系统(RDS、DARC)、数字广播(DAB、CMMB)、蜂窝网络(2G、2.75G、3G)、专用短程通信(DSRC)。目前国内已建成的WiFi/WLAN和WiMAX网络由于城市覆盖范围小、没有规模商用、建成该网络的城市不多等因素，还难以使用于交通信息［6］。(1)RDS广播数据系统(RDS)由欧洲广播联盟组织开发，数据传输速率为1.2kbps左右。RDS数据内容可以包括电台类型、节目类型、交通公告、广告信息、标准时间、天气预报等，同时提供了开放式数据接口，为特殊要求用户提供数据文本应用通道。(2)DARC日本广播协会(NHK)开发的DARC数据传输速率为16kbps，能够和RDS兼容。VICS系统就是采用DARC完成中心向车载移动接收设备的信息传输。RDS和DARC成本低廉、技术成熟、覆盖范围广，且不干扰音频广播，目前国内部分城市利用RDS和DARC技术路况信息，终端设备通过嵌入式的FM副载波接收芯片获取路况信息并实现动态导航过程。(3)DAB数字音频广播(DAB)是继调幅、调频广播之后的第3代广播，具有接收质量高、抗干扰性能强、发射功率小、覆盖面积大、频谱利用率高、适合高速移动接收等特点，其数据带宽为1.2Mbps。DAB目前已在国内部分城市投入商用，路况、新闻、电视与数字广播等地方性信息服务，相关导航产品也已面世。(4)CMMB中国移动多媒体广播CMMB是国内自主研发的第一套面向多种移动终端的数据广播系统，速率范围在2.7～12Mbps，可以通过无线广播电视覆盖网，向各种小屏幕便携终端提供数字广播电视节目和信息服务，在2008北京奥运会前开始提供服务，目前已覆盖全国大部分主要城市和地级市。早在2006年，国家广电总局就已对CMMB和DAB进行了区别定位和明确划分:CMMB通过卫星实现全国统一覆盖，由单一运营商运营;DAB侧重本地多媒体业务，由地方不同的运营商分别运营。(5)蜂窝网络蜂窝网络是目前最常用的交通信息的通信通道，常用技术包括2.5、2.75G和3G。2.5G是在GSM基础上添加了GPRS(传输速率115.2kbps);2.75G是在GSM基础上添加了EDGE(传输速率384Kbps)，可以说是从2G到3G的最后过渡阶段，在CDMA基础上发展起来的CDMA1X(传输速率153.6kbps)也称为2.75G技术;3G就是TD－SCDMA(传输速率2.8Mbps)、CDMA2000EVDO(传输速率3.1Mbps)、WCDMA(传输速率14.4Mbps)这些更加高速的网络。2011年，我国移动通信用户已经超过8.6亿，3大运营商2011年净利润突破1200亿。作为移动通信增值服务的出行信息服务具有巨大的市场发展潜力。(6)DSRC专用短程通信(DSRC)技术是ITS的基础之一，传输速率为250～500kbps，能够提供高速的数据传输，是专门用于车辆通信的技术，它负责在车－路以及车－车之间建立信息双向传输。

交通信息服务质量评价研究现状

科学的交通出行信息质量评价是评估交通出行信息是否满足公众需求的重要手段。目前我国对交通信息质量的评价体系的研究还很少。美国ITS协会于1999年召开了一个关于ATIS数据质量的研讨会，并了一份报告，该报告提出了关于检测器数据、交通事件、图像和气象检测器数据的质量评估准则。美国联邦公路管理局于2003年了一份关于ATIS系统中的行程时间质量评估报告，在该报告中定义了行程时间的评估内容及评估方法。2004年，美国联邦公路管理局了“交通数据质量评估报告”，在该报告中，介绍了交通信息质量的评估框架和准则，这些准则针对不同信息使用用户和使用环境。但在这些文献有一些缺陷，评价要素(交通参数)不全面或评价指标不全面，而且也没有多指标的综合评价方法，不能对交通信息质量进行综合评价。我国交通信息质量标准尚未，各服务机构尚未以统一的质量标准提供信息，这在一定程度上影响了人们对交通信息的使用［49］。因此，迫切需要形成一个完整的交通信息质量评价体系，为制定国家交通信息质量标准提供理论依据和数据支撑。