期刊发表网电话

全国热线
022-83699069

GPS导航仪中基于Dijkstra算法的路径规划的优化研究

作者: 发布时间:2020-01-17 11:38:10 阅读: 41 次

1前言

随着我国经济的发展、城市化水平的提高、遥感技术(RS)、地理信息系统(GIS)、全球定位系统(GPS)的发展成熟,出现了以GPS接收机为载体,以GIS(主要是指电子地图)为数据,以路径规划算法为核心的GPS导航仪,使得用户仅需要输入目的地,就可以进行实时路径规划导航。这项技术可以为出行者提供出行路线信息,并在出行过程中对驾驶员适时地做出路线指导,是智能交通系统(ITS)的重要组成部分,它不仅极大地方便了出行者,使他们可以按照自己选定的目标获得路线信息。而且可以从宏观上降低城市交通拥堵情况,提高出行效率,对优化交通流在整个路网的分配方面产生积极的影响[3]

但是,由于GPS导航系统对路径规划求解的快速性有很高的要求,因此以往研究人员更加注重于提高速度而忽略了对求解的更优性。现阶段,GPS导航系统在实际使用上,由于成本、技术原因,存在着路径规划不准确、道路权值确定不准确的问题,导致用户使用GPS导航系统进行路径规划时未能选择更优路径,引导出行时效率不高,未能充分发挥其作为交通流量调节器的作用。这不仅影响使用者的出行效率,也不利于城市交通体系的高效运作。本文将会分析该问题产生的原因,并提出一种切实可行的解决方案。

2GPS路径规划中的一些性质

2.1GPS导航与图论

从图一容易看出,GPS导航中的路径规划是以储存在GPS导航仪中的地理信息系统——主要是其中的电子地图为数据的。因此,从计算机的观点出发,地图实质是一张带权有向图,而路径规划实质就是寻找两点之间的更优路径。这使我们可以联想到图论〔Graph Theory〕的一些性质和定理来寻求更优路径的寻找方法。

2.2道路网络的数学模型

在数字地图中,定义一条道路的交叉点或端点作为道路网的节点,节点有相对的经度、纬度地理坐标;两节点间的路段定义为网络的边,路段的距离定义为边的权值,从而构成了一张描述城市道路的数学意义上的“图”,对于道路的通行代价,对应图论的概念“权”,我们称之为“路权”

这样,城市中的路径规划就转换了一个经典的图论问题——最短路径问题。最短路径问题是图论研究中的一个经典算法问题,旨在寻找图中两结点之间的最短路径(最小代价路径)。算法具体的形式包括:Dijkstra算法、SPFA算法、Bellman-Ford算法等。

3传统Dijkstra最短路径算法运用的可行性分析

对传统算法最短路径算法能否运用于GPS导航仪的关键就在于其时间复杂度能否为GPS导航仪所需的快速性相适应。因此,本文选择最为经典的Dijkstra算法进行分析。

我们以深圳为例,在个人电脑上制作了一张简易电子地图并使用Dijkstra最短路径算法进行测试。

经过统计,深圳市存在上万个节点。通过实际测试,我们发现即使使用个人计算机,需要计算出15000个节点的图的单源最短路径,需要3379ms,通过简单线性回归分析,我们得出了经典Dijkstra算法在GPS导航仪上运行时的耗时估计值,其中红色字体部分为较为接近实际的耗时情况。

耗时(ms

GPS导航仪耗时(估计)(ms

500

200

1

55

2000

1000

19

1,258

10000

5000

366

13,760

100000

20000

6091

355,403

(注:本表数据有计算机随机产生,所用计算机配置:

CPUIntel(R)Core(TM)2Duo CPU E7400 @2.80Ghz 2.80GhzRAM3.25G可用;Windows 7 32位操作系统,下同)

可以看出,如果在GPS导航仪上使用经典的Dijkstra算法在深圳市区内进行路径规划,用户将需要等待70余秒,甚至有可能需要5分钟。显然,这不足以满足用户实际需求,这也是GPS导航仪厂商没有采用经典Dijkstra算法来解决最短路径问题的原因。

4针对经典Dijkstra算法的优化

4.1一种特殊的数据储存方式

经过思考,我认为,由于需要计算单源最短路径,可以使用如下的数据储存方式:

定义一个数列a和一个变量sign。集合a中储存的是集合S中未被标记的顶点,sign记录的是数列a的项数。初始时,a中只有1项,记作a[1]其值为初始顶点v的编号,sign等于数列a中的项数,初始时,sign的值为1。稍后,我们将使用数列a及其一些特殊操作来储存集合S中的顶点,这种数据储存方式的特点为:

对于数列a中的任意一项a[n],均有a[n]a[n*2](n*2sign)a[n]a[n*2+1]n*2+1sign)。即保证a[1]为整个数列中的最小一项。

4.2几种特殊操作的定义与分析

使用4.1提出的这种数据储存方式,需要定义四种操作:

1、加入数列:令sign增加1,将集合S中未被输入数列a的顶点中的一个顶点S[i]放入a[sign]

2、维护加入(n):本操作中n为参数。比较a[](为对n向下取整),a[n]的大小。

如果a[]>a[n]则将它们交换位置并进行“维护加入()

3、取出项:先取出a[1],然后令a[1]=a[sign],sign减少1

4、维护取出(n):本操作中n为参数,比较a[n]a[n*2]a[n*2+1],三个数的大小,令其中最小的与a[n]交换位置。

如果a[n*2]a[n*4]a[n*2]a[n*4+1]则进行“维护取出(n*2)

如果a[n*2+1]a[(n*2+1)*2]a[n*2+1]a[(n*2+1)*2+1]

则进行“维护取出(n*2+1)”。

4.2.1操作“加入数列”的时间复杂度分析

上述例子展示了n个数加入到数列a的完整过程。通过此实例,可以看出,不论数的大小如何,我们总是只需进行一次“加入数列”操作,因此“加入数列”操作与数据大小无关,操作“加入数列”的时间复杂度为O(1)

4.2.2操作“维护加入(n)”的时间复杂度分析

对于“维护加入(n)”的操作次数,我们设想,如果数列a中已经有sign个元素,现在我们通过操作“加入数列”在a[sign+1]处多放入一个元素k,令k的位置为loc(此时loc=sign+1),假定a[sign+1]比数列a中所有项都小,则此时性质一已经被破坏,需要通过执行操作“加入维护(n)”来维护,其维护顺序为:

调整a[sign+1]的位置,将a[sign+1]a[],交换位置,此时k的位置loc=。如果此时的a[]a[]还小,则再次进行调整,直到符合5.1所述的性质为止。

操作“维护加入(n)”实际是每次把小的项a[n]前调整到a的位置,如果将位置为a[n]项调整到a[1],例如调整a[256]a[1],其过程为:a[256]->a[128]->a[64]->a[32]->a[16]->a[8]->a[4]->[2]->a[1]。可以看出,其过程类似二分法,时间复杂度为(LogN)

4.2.3 操作“取出项”的时间复杂度分析

显然,操作“取出项”其操作仅一项,因此时间复杂度为O(1)

4.2.4操作“维护取出(n)”的时间复杂度分析

操作“维护取出(n)”的执行过程为:将最小的元素取出,并将数列中最后一项元素放到项,然后进行与操作“维护加入(n)”相反的操作。显然,实质上,操作“维护取出(n)”为操作“维护加入(n)”的逆向操作,因此,其时间复杂度亦为O(LogN)

4.3特殊数据储存方式与Dijkstra算法的结合

本章节我们将具体地将上文介绍的特殊出具储存方式与Dijkstra算法相结合,使得Dijkstra算法可以用于GPS路径规划。

4.3.1 算法时间复杂度分析对比

上述说明的数据储存方式,是用于在O(LogN)的时间复杂度下,找到整个集合中的最小值,如果将其用于改进上文4.1所介绍的经典Dijkstra算法中的步骤(5),将使Dijkstra算法的时间复杂度由O(N2)下降到O(NLogN)。可以看出,O(NLogN)相对于O(N2)是巨大的进步。

4.4改进型算法适用性测试

5.4.1所述,时间复杂度从O(N2)降低到O(NLogN)是一个巨大的进步。最后,我们实测了原数据于改进型算法的实际耗时,并根据简单回归分析,预测算法用于GPS导航仪的时间,如下表:

Dijkstra耗时

改进型算法耗时

省时倍数

GPS导航仪耗时(估计)

100

100

1

太短无法测得

500

200

1

1

1

52

10000

5000

366

12

30.5

453

100000

15000

3,379

112

27.69

5,302

100000

20000

6,091

114

49.12

5,309

上表中红色部分为接近实际情况的耗时。可以看出:

1、使用改进型算法,其更大耗时不超过6s(实际使用中一般不会出现最长耗时的情况),完全适用于GPS导航仪所进行的路径规划。

2、通过对比第12345组数据,可以发现,随着点数、边数的增加,Dijkstra改进型算法的时间优化倍数更加明显。

综合上述,该改进型算法可以运用于GPS导航仪上进行的路径规划并给出最短路径。

5结论

本文的研究通过图论路网建模、算法分析、应用程序编写、算法性能检验等工作。根据深圳市的城市形态环境建立图论模型,找到了GPS导航仪为用户进行路径规划是路径规划不准确的原因,并提出了了改进方案,即“基于特殊数据储存方式的路径规划算法改进方案”,此方案使得经典路径规划算法的时间复杂度从原来的O(N2)大幅下降为O(NLogN),使算法在GPS导航仪上运行的平均最长等待时间不超过6秒并得出最短路径,完全满足了用户体验,可以用于改进GPS导航仪。

本文对GPS存在的问题进行了一些探讨。但是,由于水平限制,本研究存在一些问题。研究仅考虑了Dijkstra算法一种情况,未针对其他最短路径算法如SPFAFloyd进行研究比较。同时,也未对更多的优化方法进行讨论,未对数据结构的改进进行讨论,这些问题希望可以在以后的学习中可以做进一步的研究。

6参考文献

[1]中国社会科学院城市发展与环境研究中心.《中国城市发展报告》.社会科学文献出版社,2009

[2]李罗明.武汉市交通拥堵问题研究[D].武汉理工大学硕士学位论文,2005

[3]彭飞,柳重堪,张其善.车辆定位与导航系统中的快速路径规划算法[J].北京航空航天大学学报,2002

[4]毕军,付梦印,周培德.一种适于车辆导航系统的快速路径规划算法[J].北京理工大学学报,2002

[5]苟喜霞.车载导航系统更优路径规划的研究[D].北京交通大学硕士学位论文,2009

[6]车载卫星定位导航系统使用和说明书.瑞图万方.20082