版权信息
省级大型综合性科技类期刊
主管部门:自治区科技厅
主办单位:自治区科学技术信息研究院 
协办单位:自治区科学技术情报学会
编辑出版:科技期刊编译室
刊社地址:呼和浩特新城西街149号本刊杂志社
邮政编码:010000
电      话:0471-2536371

E-mail  :

nmgkjzz@vip.163.com 

网站地址:www.nmgkjzz.com


往期杂志
当前位置: 首页>往期杂志>详细介绍

基于BDS的车载导航系统路径优化问题研究

时间:2016-09-05来源: 作者: 点击: 245次

                                                                            邓科1、2,郝金明1、2,丛佃伟1、3,陈逸伦1、2

1.信息工程大学导航与空天目标学院,郑州,450001

2.北斗导航应用技术河南省协同创新中心,郑州,450001

3.地理信息工程国家重点实验室,西安,710000

  要:随着北斗卫星导航系统全球组网的进行和现代交通网络的发展,北斗应用于民用领域,尤其是车载导航系统中将会更加普及。车载导航系统中的核心的问题,则是路径优化问题,本文总结分析了道路路阻模型和交叉口阻抗模型;研究了最优路径搜索算法,分析了各算法的时间复杂度,针对现有算法,提出了改进经典最短路径算法、采用先进搜索技术、采用地图分层和分级搜索技术等优化建议。在此研究基础上,分析总计了未来最优路径问题研究的重点和难点。

关键词:北斗卫星导航系统;车载导航系统;路径优化;算法

A Study on Optimal Path Problem in a Vehicle Navigation SystemBased on Beidou Navigation satellite System

DENG Ke12, HAO Jin Ming12, CONGDianwei12, CHENYilun12

1. Institute of Navigation and Aerospace Target, University of Information Engineering, Zhengzhou  450001, China;

2. Beidou Navigation Technology Collaborative Innovation Center of Henan, Zhengzhou 450001, China

Abstract: With the development of Beidou Navigation satellite System and modern transportation network, BDS will be become more widespread in a Vehicle Navigation System apply forcivil operators. In this system, the key question is the method to search optimal path problem. This paper summarizes and analyzes road impedance function model and intersection delay model; researches on the algorithms for searching optimal path problem, and analyzes time complexity for all algorithms. This paper presents recommendation columns for existing algorithms, such as improving the classical shortest route algorithm, using of the advanced search algorithm and using of hierarchical thinking to search map, and summarizes and analyzes the key and difficult points for optimal path problem.

Keywords:BDSVehicle Navigation System; Optimal Path; algorithms

0引言

随着北斗卫星导航系统全球组网进行,和全国各省北斗地基增强系统的建设,北斗技术与北斗服务在民用领域应用将越来越普及。2016616日,国新办发布了《中国北斗卫星导航系统》白皮书,指出我国将积极培育北斗系统的应用开发,引导大众应用,推动北斗兼容其他卫星导航系统的定位功能称为车载导航、智能导航的标准配置。同时与其他卫星导航系统相比,BDS不仅可为用户提供位置信息服务,还可以提供短播文通信服务,这将极大的促进和拓展北斗在民用领域的普及应用。

现代交通网络快速发展,人们的出行方式日趋方便快捷,与此同时,伴随着车辆快速普及,交通拥挤、交通事故等问题又频繁发生,给人们的生活带来极大的困扰。为了增加行车效率、减少行车时间,结合北斗卫星导航系统与地理信息系统的车载导航系统已成为人们正确行车的最佳利器。车载导航系统的核心,则是车辆导航过程中路径优化问题[1][5]。现在交通网络的复杂性和车载用户数量的庞大,导致路径优化问题需要考虑的因素更多[2][4],问题更加复杂,数据处理量更大。如何更好的处理这些问题,称为目前研究的热点。

1路径优化问题

1.1车载导航系统工作原理

1车载导航系统工作原理

车辆行驶过程中,车载导航系统向车辆提供最优路径,引导车辆按照最优路径到达目的地,是车载导航系统的核心问题。

1.2最优路径目标

根据交通网络特性和图论知识,可以将交通网络转换为图论中的赋权有向图。其中,交通网络中的十字路口可简化为图中的结点,交通网络中的道路可简化图中的边或弧,则路径优化问题可转化为图论中的最短路径问题。

其中最优目标的选取根据不同的出行需求有以下定义[3][6]

1)时间最短,以车辆通过路段的平均行程时间为权重;

2)费用最少,以车辆在路段的平均运行费为权重;

3)距离最短,以道路长度为权重;

4)广义路阻最少,也称为广义费用最少,是指出行者为了完成从出发点到终点的出行而付出的代价及其为社会带来的负影响的总和。

5)广义时间最短,车辆在路段上的运行时间和将其他货币量和非货币量按一定标准转化成的时间。 

2最优路径函数模型

2.1 道路时间路阻函数模型

路段路阻是边或弧的量化表示,通常指路段长度、车道数及交通堵塞程度等影响车辆行驶的因素。通常用一个函数模型表示不同路段的路阻情况。国内外道路路阻函数模型主要有以下模型:

1)美国联邦公路局BPR阻抗函数模型及其改进型

BPR模型)

1

(改进型)

2

表示两交叉口之间的路段行驶时间;表示自由流车速时路段行驶时间;和表示回归系数;表示服务水平参数;表示路段实用通行能力;表示路段机动车交通量。

2)英国运输部TRRL模型

城市中心区新建道路交通阻抗模型:

3

其他城市道路或者较高车速道路交通阻抗模型

4

表示交通量为时的道路行车速度;W表示行车道宽度;R表示行车道宽度的减少值。

3)日本和德国线性路段阻抗函数模型

5

β表示回归系数,其余符号含义同BPR模型

4)考虑非交通机动车影响因素的BPR改进模型

6

表示机动车、非机动车路段交通量;表示机动车、非机动车路段使用通行能力;表示回归参数,由道路交通量、车速调查数据和最小二乘拟合确定。

3.2 交叉口阻抗模型

随着现代道路网络发展和路网交通量增加,道路交叉口成为交通流交汇、冲突的高发地段,车辆在交叉口的阻抗比例将逐渐增加。为了在交叉口阻抗计算中反映出由于交通组织而导致的各种转向阻抗值的不同,则必须建立准确的交叉口阻抗函数模型。交叉口阻抗模型主要有以下模型:

1)美国HCM2000模型,其主要包括信号控制交叉口阻抗模型、主路优先控制交叉口阻抗模型和全无控制交叉口阻抗模型。

2)信号交叉口排队长度分布模型。

3)信号灯控制交叉口停车线车辆阻抗模型。

除了上述对于交叉口权重的进行建模计算,还可以针对交叉口的交通管制、转向限制措施进行权重转换。若规划问题中的结点处存在权重,则通常的最优路径算法无法对其进行处理,为此可以在结点处增设虚拟边进行问题转化,其原理如下图所示:


2交叉口1的西进口和北进口禁止左转

通过增设虚拟边法将转向行为直接转化为虚拟边,故转向行为对应的结点权重也自然转化为虚拟边的权重,从而消除了结点权重,故可以直接利用一般的路线优化算法求解。

4 最优路径算法

4.1 Dijkstra算法

算法由E. W. Dijkstra1959年提出的,是目前公认的求解最短路问题的经典算法 [9][11]

假设,表示()的权,,若()∉E,则令,求G中到的最短距离。用表示从到经过已选结点的最短路径的权。

1)令,,

   (2)在R中寻找一个顶点,使得:

7

        若,则算法终止,不存在最短路径,否则,置,

        若,终止算法,若,转(3

3)修正,对R中每个,令

8

转回2);

Dijkstra算法搜索过程来看,此算法简单、容易实现,但只适合小范围内的最短路径计算。

4.2 启发式搜索算法----A*算法

A*算法[7]建立在Dijkstra算法上的,其创新之处在于选择下一个被检查点时引入已知的全局信息,对当前结点距终点的距离做出估计,作为评价该点处于最优路线上的可能性的度量,这样就可以首先搜索可能性较大的结点,提高搜索效率。

算法引入当前结点j的估计函数,当前结点j的估计函数定义为:

9

从起点到当前结点j的实际最短距离;

为从当前结点j到终点的最短距离的估计

引入两个链表,用T表示已经生成但尚未扩展的节点集合,S为已经扩展的结点集合。

   (1)设置初值:对起始结点vs,令;对其余结点,令,令,此时显然是T中具有最小f*值的结点。

2)若,则算法失败;否则,从T中选出具有最小值的结点v,即令。令

判断是否为目标结点。若是目标结点,转(4);否则,生成的后继结点。继续执(3

3)对于每个后继结点,计算,根据所处的位置,有三种情况:

a:若,判断是否有。若是,置,;

b:若,判断是否有。若是,置,;

c:若,令,,,计算结点的估计函数,转步(2

4)从结点v开始,根据利用回溯的方法输出起始结点到结点的最优路径以及最短距离,算法终止。

从算法A*搜索的过程来看,其搜索过程明显趋向于终点,搜索到的结点数少,故占用的存储空间少,搜索速度快。

4.3 Floyd算法

Floyd算法是由Floyd1962年提出的,是一种计算图中任意两点间的最短距离的算法。与对每一节点作一次Dijkstra算法的时间复杂度相同,但是实际的运算效果比Dijkstra算法要好。

4.4双向搜索算法

双向搜索算法由Danzig提出的基本思想,Nicholson正式提出算法。该算法在从起点开始寻找最短路径的同时也从终点开始向前进行路径搜索,最佳效果是二者在中间点汇合,这样可缩短搜索时间。

但是如果终止规则不合适,该算法极有可能使搜索时间增加1倍,即两个方向都搜索到最后才终止。

4.5算法时间复杂度分析

算法的时间复杂度是对算法进行评价的一个重要指标,它在一定程度上反映了算法运行效率的高低。算法的时间复杂度与算法采用的数据结构有直接的关系。

一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用表示,若有某个辅助函数,使得当n趋近于无穷大时,的极限值为不为零的常数,则称是的同数量级函数。记作,称为算法的渐进时间复杂度,简称时间复杂度。

1 最优路径算法时间复杂度分析

算法

时间复杂度

Dijkstra算法

A*算法

Floyd算法

双向搜索算法

为结点的平均出度;为从起始结点到目标结点的最短路径的搜索深度,搜索算法为了寻找最优解而必须遍历的树的层数

4.5 算法优化

1)改进经典最短路径算法--推广双向搜索算法

双向搜索的基本过程是从起点到终点计算最短路径(前向搜索) ,与此同时, 计算从终点到起点的最短路径(后向搜索) 。理论上,双向搜索至少可以减少50%的搜索运算量,从而大大节省了算法耗时。

2)采用先进的搜索技术减小搜索空间

为改变原始Dijkstra算法杂乱无章的搜索,在算法过程中借鉴A*算法的启发式搜索将有助于增加搜索的方向性。

3)采用地图分层和分级搜索技术控制规划路网的规模

道路有不同的级别,如公路分为高速公路、国道、省道、县道,城市道路分为城市快速路、主干道、次干道等。根据道路的不同级别特点,将路网分层。分层的路网是对原有路网的抽象,忽略不重要的细节,层次越高,所包含的结点和路段数越少。运用分层搜索可以降低时间复杂度,但进行分层搜索必须建立分层的地图数据库,另外在较高层次得到的最优解是不完全的,必须在下一层次中加以细化。

5 结束语

虽然车载导航系统的最优路径算法研究己经取得了相当的成果,但它仍然是一项具有挑战性的研究课题。未来一段时间,最优路径问题研究的重点和难点将主要表现在以下几个方面:

1)动态、随机网络模型研究

实际的交通网络是一个随时间不断变化的动态网络结构,不仅仅存在确定性的时间依赖的最优路径问题,而且普遍存在不确定性最优路径问题,即随机最优路径问题,以及同时具有时变性和随机性的最优路径问题。在这样一种网络中进行最优路径查找不能简单的照搬普通的最优路径规划算法。

如何建立动态交通路网模型,如何表示及处理动态交通信息,并在能够接受到实时交通流量信息的条件下,确定适用于车辆导航的动态路径规划算法,是今后研究的热点。

2)算法研究

随着一些新型的路线优化算法的引入,比如遗传算法、基于神经网络的算法等,应用新型算法可以改善经典算法存在的一些不足。同时随着大规模时变、随机网络最短路径算法的出现,计算机处理数据量逐渐增多,运行在服务器端的最短路径算法可以向基于图分解的并行算法的方向发展,以满足大量的实时最短路径查询的需要。

3)多导航器相互协调规划

随着计算机科学技术、无线通信技术以及交通运输业的高速发展,车辆导航系统的动态路径规划研究趋势还将向多导航器相互协调规划的方向发展。现在的车辆导航都是单个车辆为对象进行路径引导,而没有考虑到总体的大局协调,这样容易引起新的交通拥塞等问题,所以多导航器协调规划将是一种更加符合实际需求的规划方法。

随着我国北斗卫星导航系统的发展,和地理信息系统、通信系统及嵌入式软硬件技术的进一步发展,基于北斗卫星导航系统的车载导航系统的开发研制会更进一步深入,从而向更适用于用户的角度发展。同时随着国产北斗芯片等设备的成熟发展,产品精度会逐步提高、价格逐步降低,其市场规模将会不断扩大,因此该系统会有更为广阔的发展前景。

 

参考文献:

[1]沈国杰.车载导航系统的最优路径规划算法研究[D].大连:大连理工大学学位论文.2013.

[2]陈碧峰,陆昊娟等. 车辆导航系统的动态最优路径搜索模型及算法[J].武汉:武汉理工大学学报,2002,24:46-48.

[3]张钟. 大规模图上的最短路径问题研究[D].合肥:中国科学技术大学,2014.

[4]张怡. 复杂环境下车辆导航系统最优路径规划算法研究[J]. 弹箭与制导学报,200425:9-11.

[5] 张其善,吴今培,杨东凯著.智能车辆定位导航系统与应用[M].北京:科学出版社,2002.

[6] 陈涛. 车辆导航系统中大区域路径规划算法的设计与实现[D].郑州:解放军信息工程大学,2005.

[7] 徐洪勇. 基于GIS的最短路径算法改进对比研究[D]. 北京:中国地质大学(北京),2008.

[8]王建宇,许震洪,周献中.基于数字地图的多属性最优路径问题的算法研究[J].测绘信息与工程,2003, 28(4):9-11.

[9]龚洁辉,白玲,高健美.最短路径算法的改进及其实现方法[J].解放军测绘学院学报,1998, 15(2):121-124.

[10]魏唯,欧阳丹彤,吕帅,冯宇轩.动态不确定环境下多目标路径规划方法[J].计算机学报,2014, 34(5):836-846.

[11] 邱洋洋. 基于城市路网的最优路径规划算法研究[D].河北:燕山大学,2015.

 

第一作者简介:邓科(1991-),男,陕西西安人,硕士研究生,研究方向为GNSS精密定位工作。

通讯作者:郝金明(1962-),男,山东曹县人,博士,教授,主要从事GNSS精密定位工作。

基金项目:地理信息工程国家重点实验室开放研究基金项目(SKLGIE2015-M-2-5

本刊创刊于1982年,是由自治区科技厅主管、自治区科技信息研究院主办,由自治区科技情报学会协办、国内外公开发行的省级综合性科技刊物,是反映内蒙古自治区科技与经济发展的窗口。杂志入选《中国期刊全文数据(CJFD)》全文收录期刊和《中国学术期刊综合评价数据(CAJCED)统计刊源期刊,《中国核心期刊(遴选)数据库》收录。本刊是公开发行的综合性科技期刊,为月刊,大16开本。本刊坚持以科技创新为目标,融科技、经济、信息、产业、市场为一体,是促进科技成果转化、推动科技进步、加强技术创新,促进经济发展的专业性期刊。