基于物联网智能交通系统车辆路径规划算法优化探究

《基于物联网智能交通系统车辆路径规划算法优化探究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于物联网智能交通系统车辆路径规划算法优化探究摘要：本文提出了适用于智能交通系统的基于双向搜索的改进算法。典型的最短路径算法被认为是Dijkstra算法，其时间复杂度是052)。但一个城市的路网地图有很多节点,该算法的时间复杂度高和解决速度慢。为了改变这种情况，我们从算法的设计方面进行了讨论，提出了改进的双向搜索算法。实践证明，改进后的算法能够提高了搜索速度，适用于智能交通系统。关键词：物联网；智能交通；路径规划；双向搜索算法中图分类号：U492.22文献标识码：A文章编号：1007-9599(2012)17-0000-021引言智能交通系统的核心即动态车辆的路径

2、规划问题，如何能提高路径规划算法的速度是保证整个智能交通更好更快发展的前提。目前具有代表性的最短路径算法是Dijkstra算法，其时间复杂度为0(n2)。但因Dijstra算法是一个NP完备算法，面对城市交通路网的众多结点，此算法的时间复杂度高，很难满足导航系统中的实时性要求。本文从算法设计方面对现有的双向搜索算法进行优化，实验证明，能够达到提咼算法效率的目的，使其适用于智能交通中的车辆导航系统。2算法的优化原理所谓双向搜索指的是搜索沿两个方向同时进行，正向搜索：从初始结点向目标结点方向搜索；逆向搜索：从目标结点向初始结点方向搜索；每个新结点生成后，不仅要与本队列

3、中的每个结点判重，还要和对方队列中的节点判重，如果有相同结点，即发生双向搜索相遇事件，搜索完成，搜索步数等于两个方向搜索步数之和，生成的搜索树是菱形的，极大的减少了搜索结点的数量，提高了搜索效率。实验表明，和单向搜索展开的结点数相比，双向搜索展开的结点数至少可以减少1/2,搜索效率明显提高。此算法的最优状态是正向和逆向的搜索在图中相遇，最不利的情况是正向搜索和逆向搜索没有相遇的结点，这样反而使算法的搜索时间增加了一倍。因此适当的放宽搜索终止条件才能真正缩短搜索时间。我们的优化就是在不增加算法的时间复杂度基础上，解决在双向搜索中结点没有相遇的情况。算法的优化在搜索过

4、程中，将每次搜索到的新结点向源结点和目标结点的连线做投影，计算从正向搜索到的新结点的投影到源结点的距离和从逆向搜索到的新结点的投影到目标结点的距离，并计算这两个距离的和，如果距离之和比源结点和目标结点的连线的直线距离长，我们认为双向搜索不会有重合点，立刻停止某一方向的路径搜索，继续另一方向的结点搜索，双向搜索中选择某个方向继续进行搜索或某个方向停止搜索，主要取决于哪个方向的结点个数较少，就向那个方向进行扩展。众所周知，“两点之间直线距离最短”，如果我们所要寻找的结点恰好在同一条边上，这条边就是我们要找的最短路径，否则，和两点间连线的夹角最小的边是最短路径的可能性较

5、大。如图1所示，在城市路网中搜索两点A和E之间的最短路径的优化后算法的步骤如下：(1)结点A为出发地，结点E为目的地。在结点A和结点E之间，建立一条连线AE,若AE之间存在一条边和AE连线重合，则这条边就是我们所求的最短路径。(2)若不满足上述条件，则我们从出发点A和目的地E同时向中部搜索与AE这条直线夹角最小的边，在搜索过程中，每次都选择结点个数较少的那个方向先扩展。(3)重复步骤(2)直到两个方向的搜索能汇合于同一结点或同一条边。把两个方向搜索过的结点聚集，就能得出从A到E的完整最短路径。(4)在搜索过程中，将双向搜索到的新结点向AE直线做投影，计算从A方向搜

6、索到的结点的投影到A的距离和从E方向搜索到的结点的投影到E的距离，并计算这两个距离之和，如果距离之和比AE直线距离长，我们就认为双向搜索不会有重合点，立刻停止某一方向的路径搜索，继续向结点个数较少的那个方向进行扩展，搜索结果为单向扩展的结点为所求的最短路径。3路径规划算法设计3.1算法的实现。设置两个队列c：array[0..1,1..maxn]ofjid,分别表示正向搜索和逆向搜索的扩展队列；两个头指针head：array[0..1]ofinteger分别表示正向搜索和逆向搜索中当前将扩展结点的头指针；设置两个尾指针tail：array[0..1]ofinteg

7、er分别表示正向搜索和逆向搜索的尾指针。主程序：选择节点数较少且队列未空、未满的方向先扩展if(tail[0]=tail[0])or(tail[0]>=maxn))thenexpand(0)；if(tail[1]二tail[1])or(tail[1]>=maxn))thenexpand(1)；如果一方搜索终止，继续另一方的搜索，直到两个方向都终止ifnot((head[0]>=tail[0])or(tail[0]>=maxn))thenexpand(0)；ifnot((head[l]>=tail[1])or(tail[1]>=maxn))thenexpand(1)

8、；((he