2023年7月30日发(作者：)

龙源期刊网

GPS导航仪路径规划算法及路权确定的优化研究

作者：孔令彤

来源：《硅谷》2013年第03期

摘 要 本研究针对现在GPS导航仪普遍采用的路径规划技术不能为用户规划出最优路径问题，通过建模、算法分析、算法改进等方式，根据深圳市的城市形态建立实际模型，找到了问题原因并提出了两个改进方案：“基于特殊数据储存方式的Dijkstra算法改进方案”与“基于动态交通信息的路权确定改进方案”。经过优化后的GPS导航仪，可引导驾驶员提高出行效率，并在一定程度上合理分配车流，减少城市交通压力。

关键词 GPS导航仪；算法优化；路权选定优化；Dijkstra算法

中图分类号：TP3 文献标识码：A 文章编号：1671—7597（2013）021-063-02

1 前言

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

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

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

2.1 GPS导航与图论

GPS导航中的路径规划是以储存在GPS导航仪中的地理信息系统——主要是其中的电子地图为数据的。因此，从计算机的观点出发，地图实质是一张带权有向图，而路径规划实质就