基于多目标的车辆导航最优路径规划研究

李 勇 仝春灵*

(山东交通学院 信息科学与电气工程学院，山东 济南 250357)

车辆导航系统是一种综合利用GIS（地理信息系统）、计算机和通信技术进行全球定位的自动导航系统。它通过自动获取交通网络中道路的交通状况和车辆的地理位置，为出行者找到从所在位置到目的地最优的行驶路线，帮助出行者轻松地前往他们想要到达的地方。

1 国内外发展概况

公元2600年前中国古代发明家马钧发明的指南车可以看成人类历史上最早的车辆导航系统，19世纪导航技术开始真正用于汽车行驶，20世纪60年代末，在美国公共道路管理局的呼吁和支持下开发了电子路径引导系统ERGS(Electronic Route Guidance System)。日本和德国在20世纪70年代也开始着手这方面技术的研究，进行了许多类似车辆导航方面的项目实验。进入80年代后，车辆导航系统等相关技术在全球范围内得到了快速发展，GPS技术迅速应用于车载导航系统中。通过在车辆上安装GPS接收机，可以获得车辆的当前位置、行驶速度和方向。但是车辆的GPS定位精准度通常容易受到卫星信号状况和道路环境地势的影响，因而简单的GPS定位系统仍存在定位精度低、可靠性不理想等问题[1-2]。从20世纪90年代开始，国外导航研究者们将组合定位技术应用到车辆导航系统中,使得车辆的定位精度有了极大提高[3-5]。相对而言，我国的车载导航系统起步较晚，直到1980年才逐渐形成体系。但是随着汽车导航系统的研究工作越来越受到人们的重视，汽车导航系统相关的专业论坛不断举行，又加上政府和有关部门的重视，高德、百度、腾讯、谷歌、360等大型科技公司都开发出了自己的导航系统并投入正常使用。目前，北斗导航APP也已上线。尽管这些系统已被广泛应用，但是这些系统在最优路径选择方面还不是很完善，把车辆导入楼顶、河沟、断崖的事件时有发生，因而在导航的准确性和灵活性方面还需要进一步改进[6]。

车辆导航系统的核心是最优路径规划[7-8]。最优路径规划是将城市交通信息管理中心发布的实时交通信息与车辆当前的路况信息进行综合分析，利用车载导航设备在城市交通网络中寻找出一条满足出行者要求的从起始点到目的地的最优路径。最优路径规划在军事和民用领域都有广泛的应用。车辆在道路上的行驶需要路径规划，导弹发射轨迹和飞机飞行航线也需要路径规划。目前，已有多种路径规划算法应用于导航系统中为人们的出行提供便捷的服务[9-11]。

本文在充分分析现有路径规划算法的基础上，全面考虑到车辆行驶过程中影响路径规划的各种因素，通过优化目前的车辆导航路径规划算法，使车辆导航系统能够满足不同用户的特殊需求，提供给出行者更加精准、灵活且符合个人要求的最优行驶路线。

2 研究内容、技术路线和创新点

路径规划能帮助驾驶员在特定的交通网络中找到符合自身要求的最优行驶路线。根据规划目标的不同，路径规划可划分为多车辆综合路径规划和单车辆导航路径规划。其中多车辆综合路径规划主要应用于车队整体调度和交通控制，单车辆导航路径规划就是通常所说的车辆导航系统。根据用户在实际应用过程中的不同要求，路径规划可以以行车距离、花费时间、行驶费用、经过的交叉路口或路线的复杂程度等标准进行优化。无论采用哪种标准进行优化，最优路径规划最终都可以归结为在特定的交通网络中寻找代价最小的路径问题，即图论中的最短路径问题。本文以实时交通信息为基础，研究出最优的交通路径以满足用户需求。

2.1 研究内容

本文研究的主要内容有：影响最优路径的主要交通因素分析、基于多目标的车辆导航最优路径规划算法设计以及最优路径的计算和选择。

2.1.1 影响最优路径选择的交通因素分析

影响最优路径选择的交通因素主要包括：

（1）经过的交叉路口数量及交叉路口红绿灯的等待时间；

（2）单行线和禁止转弯情况；

（3）是否收通行费；

（4）路径的复杂程度；

（5）上下班高峰期和节假日车辆出行量。

2.1.2 基于多目标的最优路径规划算法设计

基于多目标的最优路径规划算法分为以下4步：

（1）基于交通道路状况实时信息建立路况交通网络；

（2）对各种影响最优路径的因素进行量化讨论，使之转化为节点和边的权重；

（3）根据优化目标，设计最优路径规划算法；

（4）对（3）进行复杂性分析，并不断改进最优路径规划算法，设法降低算法的时间复杂度。

2.1.3 最优路径的计算和选择

（1）根据2.1.2 设计的多目标最优路径规划算法，求不同优化目标下的最优路径；

（2）对所求的最优路径进行模拟分析，并根据结果逐步优化路径的选择，求得最佳路径。

2.2 技术路线

最短路径是加权有向图中从一个顶点到另一顶点的权值总和最小的路径。如果将路径规划中的优化目标量转化为车辆行驶成本，则最优路径规划问题可以转化为在特定交通网络中寻找总行驶成本最小的路径问题。常用的求解最短路径的算法有蛮力算法、Dijkstra算法、Floyd算法和动态规划算法。在深入分析各种算法的效率和适用范围的基础上，结合车辆导航的多目标优化的要求，本文选择Dijkstra算法来求最优路径。但是由于不同的驾驶员对路径的要求不一样，本文在应用Dijkstra算法求最短路径时不仅根据不同的优化目标分别求出满足出行者要求的最短路径，而且对Dijkstra算法进行扩展：除了传统的对有向边进行赋值(权重)外，还对交通网络图的节点根据交叉路口红绿灯的等待时间进行赋值调整，即：把节点扩展为路径，将交通网络图转化为其剖分图，然后计算该剖分图的单源最短路径。图1、2，显示了某个交通网络图及其剖分图。

图1 交通网络图

图2 交通网络图的剖分图

当然，因为剖分图有更多的点和有向边，计算最短路径的复杂性将大大增加，这又会带来有关计算复杂度的一个问题，本文采用回溯和分支限界策略降低计算复杂度、提高计算效率。

2.3 创新点

2.3.1 在分析影响最优路径的交通因素时考虑了路线的复杂性，并在目标优化中增加了以此为标准的最短路径计算，为新手或路盲上路提供了更好的选择。

2.3.2 将路口红绿灯的等待时间转换为交通网络中节点的权值，从而把求交通网络图的最短路径转化为求其剖分图的最短路径，扩展了传统的Dijkstra最短路径算法。

2.3.3 在求交通网络图的剖分图的最短路径的过程中，为了降低复杂度、提高计算效率，使用了回溯和分支限界策略。

3 结论

本文通过全面分析影响最优路径的各种交通因素，按照用户的不同需求，进行合理量化赋值；而且根据不同的优化目标扩展传统的Dijkstra最短路径算法，从而为导航系统提供更加灵活、准确的最优行驶路线。同时，应用回溯和分支限界技术降低了最优路径规划算法的复杂度，加快了系统响应时间，提高了导航速度。本文中研究的最优路径规划算法应用到导航系统后，可以减少车辆在道路上的停留时间，提高出行效率；还可以合理避开交通拥堵，降低事故发生率。具体地说：

(1)在以距离、时间和费用为优化目标的最优路径规划中，使用本文提出的最优路径规划算法，车辆的行驶距离、时间或费用可以降低(或减少)5%-10%。

(2)在以线路的简单性为目标的最优路径规划中，使用本文提出的最优路径规划算法，新手或路盲的导航使用满意率可以提高12%-15%,事故发生率可以降低8%-10%。