车辆导航动态路径规划的研究进展概要

第27卷 第11期2010年11月

公 路 交 通 科 技

Journal of H i gh w ay and T ranspo rtati on R esearch and D eve lop m ent

V o l 27 N o 11

N ov . 2010

文章编号:1002-0268(2010 11-0113-05

车辆导航动态路径规划的研究进展

葛 艳, 王 健, 孟友新, 江 峰

(青岛科技大学 信息科学技术学院, 山东 青岛 266061

摘要:针对车辆智能导航系统中的交通网络模型、路径规划算法以及交通流预测这三个主要方面的研究现状进行了较为详细的分析。首先着重描述了基于图论的交通路网模型的构建方法; 其次分析了D ijkstra 算法、F l oyd 算法、A*算法等经典路径规划算法的性能及研究方向; 然后详细介绍了交通流预测方法的研究进展; 最后对车辆导航动态路径规划的未来研究方向做了展望。

关键词:交通工程; 车辆导航; 路径规划; 交通路网模型; 最短路径算法; 交通流预测中图分类号:U 491 文献标识码:A

Research P rogr ess on Dyna m i c Route P l a nni n g of Vehi c l e Nav i g ati o n

GE Yan , WANG Jian , MENG Youx i n , JI ANG Feng

(School o f In f o r m ati on Sc i ence and T echnology , Q i ngdao U niversity of Science and T echno logy ,

Q i ngdao Shandong 266061, Ch i na

Abstr ac:t The research actua lities of traffic net w ork m ode, l path p lann i n g algor ith m and traffic fl o w prediction for intelligent nav igati o n syste m w ere described i n deta i. l Firs, t the constr ucti n g m ethod o f traffic net w or k m odel based on the graph theory w as descri b ed . Second , the perfor m ance and the research d irection of c lassica l path p lann i n g algor ith m s , suc h as D ijkstra a l g orit h m, F l o yd algor ith m and A algorith m, etc .

w ere ana l y zed . Th ir d, the research prog ress o f tra ffic flo w pred icti v e m ethods w as intr oduced in deta i. l A t las, t t h e future study directi o n of vehic le nav igati o n dyna m ic path p lanning w as discussed .

Key w ords :traffic eng i n eering ; vehic le nav i g ation ; route p lanning ; tra ffic net w or k m ode; l shortest path algorithm; traffic flo w prediction 0 引言

随着科学技术的发展进步, 汽车已成为人们日常生活中不可或缺的重要工具, 而伴随着车辆普及率的快速提高, 交通拥挤、交通堵塞、交通事故等交通问题频繁发生, 给人们的正常生活带来极大的困扰, 同时也造成了巨大的经济损失。面对这一系列问题, 车辆导航系统(V ehic le Location Syste m VLS 应运而生。车辆导航将全球定位系统技术、地理信息系统技术、电子技术及计算机技术等各种高

收稿日期:2009 09 22

基金项目:国家自然科学基金资助项目(60802042; 山东省自然科学基金资助项目(ZR2009GQ013; 青岛市科技计划资助项目(07 2 3

3 jch; 青岛科技大学科研启动基金资助项目(0022147

(, 女, , 博士, 副教授, ( com

*

新技术融合在一起, 是现代智能交通的一个分支

[1]

。

汽车通过车载的导航仪器接收卫星数据, 在电子地图上显示车辆的当前位置、行驶方向和离目的地的距离等信息, 根据距离最短准则在当前已知路网范围内选择最优的行驶路线。

目前, 投入市场应用的成熟车辆导航系统大多基于静态的路径规划, 然而面对存在众多不稳定因素的交通现实, 用户并不满足于现有的系统。尤其是发生交通事故和交通堵塞时, 静态路径规划不能及时改变路线。因此, 车辆导航动态路径规划就成

为新一代智能车辆导航系统的研究热点问题。车辆动态路径规划基于历史的、当前的交通信息数据对未来交通流量进行预测, 并用于及时调整和更新最佳行车路线, 从而有效减少道路阻塞和交通事故。近几年, 在国内外的车辆导航研究中, 交通信息预测的重要性逐渐凸显出来, 越来越多的研究学者们

[2][3]

应用卡尔曼滤波方法、时间序列方法、神经网络法等对交通信息预测进行了深入研究。

除交通信息智能预测以外, 路网模型和路径规划算法也是基于实时交通信息的车辆动态路径规划系统的研究重点。通过构建路网模型可以将物理上的道路网络抽象成一个使计算机能够处理的数据模型, 将道路上的各种因素都数据化。选取恰当的路径规划算法可以在路网模型上结合交通信息按照一定的最优目标规划最佳出行路线。当前国内外比较流行

的算法如D ijkstra 算法法

[7]

[5]

[4]

于左转。针对这一问题, 文献[10]和文献[11]在路网模型中添加了节点处的路阻。

为了降低搜索空间, 文献[12]根据城市道路网络的特点和实际的行车需求将路网按道路级别不同分为两层。这种分层的路网模型可以极大地降低算法的搜索规模, 虽然其结果不是以行程最短为最优路径, 但却更加符合行车的实际需求。

此外, 还有一种新的交通路网模型是将现实中的道路网络抽象成以车流通过的时间来连接交通路

[13-14]

口节点的集合。这种模型需要相关路段的历史的、实时的和预测的行驶时间数据, 比较符合实际的交通网络情况, 但是当前交通流预测技术的不成熟会实时交通信息预测的准确性, 致使对实时的交通紧急状况的处理能力较差。所以, 该类模型更好的模拟现实交通状况, 但由于部分支撑技术的不成熟性导致现在还停留在理论阶段, 没有应用到实际中。

2 车辆路径规划算法

根据车辆导航系统的研究历程, 车辆路径规划算法可分为静态路径规划算法和动态路径算法。静态路径规划是以物理地理信息和交通规则等条件为约束来寻求最短路径。静态路径规划算法已日趋成熟, 相对比较简单, 但对于实际的交通状况来说, 其应用意义不大。动态路径规划是在静态路径规划的基础上, 结合实时的交通信息对预先规划好的最优行车路线进行适时的调整直至到达目的地最终得到最优路径。下面介绍几种常见的车辆路径规划算法。

2 1 D ij kstra 算法

D ijkstra 算法是最短路算法的经典算法之一, 由E W D ij k stra 在1959年提出的。该算法适于计算道路权值均为非负的最短路径问题, 可以给出图中某一节点到其他所有节点的最短路径, 以思路清晰, 搜索准确见长。相对的, 由于输入为大型稀疏矩阵, 又具有耗时长, 占用空间大的缺点。其算法复杂度为O (n 2, n 为节点个数。2 2 Lee 算法

Lee 算法最早用于印刷电路和集成电路的路径追踪, 与D ij k stra 算法相比更适合用于数据随时变化的道路路径规划, 而且其运行代价要小于D ij k stra 算法。只要最佳路径存在, 该算法就能够找到最佳优

[15]

化路径。Lee 算法的复杂度很难表示, 而且对于、Lee 算法

[6]

、A 算

*

等。

1 车辆路径规划的路网模型

路网模型是路径规划的前提。要进行路径规划, 必须要将实际中的交通道路网络抽象为一个能被计算机识别和处理的模型, 即路网模型。对于路径规划来说, 这是一个至关重要的因素。

根据道路交通网络信息, 基于图论理论可将路网模型抽象为物理连通和逻辑连通两个层次。物理连通是指实际道路中道路与道路间的空间上的互相连通; 而逻辑连通是指在交通规则下的行为上的连通性, 如道路禁行、单行道等交通信息, 这些信息无法用物理连通来表示。

网络模型一般由节点、边及边的权重组成。节点代表路口, 边代表路段, 边的权重是路段路阻的量化表示。路段路阻指路段长度、车道数及交通堵塞程度(即该路段车辆的平均行驶速度 等影响车辆行驶的因素。根据实际需要不同, 路阻可以是单独的某个因素, 也可以是诸多因素的线性组合。通常用一个函数模型表示不同路段的路阻情况。路阻函数是路径规划路算法中一个至关重要的约束。当前已有的路阻函数模型有美国联邦公路局提出的

路阻函数模型、我国提出的回归型路阻函数模型、

[9]

交通流三参数路阻函数模型等。

交叉路口处的交通规则(如交通灯、左转弯等 所产生的延误, 常常被人们忽略。然而在实际汽车行驶过程中路口处的延误是不可忽视的, 而[8-9]

[8]

2 3 F l o yd 算法

Floyd 算法是由F l o yd 于1962年提出的, 是一种计算图中任意两点间的最短距离的算法。其时间复杂度为O (n 3, 与对每一节点作一次D ijkstra 算法的时间复杂度相同, 但是实际的运算效果比D ij k stra 算法要好。文献[16]对Floyd 算法进行了改进, 使其对无向图求解最短路径。

2 4 启发式搜索算法 A 算法

启发式搜索有很多的算法, 如:局部择优搜索

**

法、最好优先搜索法、A 算法等。其中A 算法是由H ar, t N ilsson , R aphae l 等人首先提出的, 算法通过引入估价函数, 加快了搜索速度, 提高了局部择优算法搜索的精度, 从而得到广泛的应用, 是当前较为流行的最短路算法。A 算法所占用的存储空间少于D ijkstra 算法。其时间复杂度为O (bd , b 为节点的平均出度数, d 为从起点到终点的最短路的搜索深度。

2 5 双向搜索算法

双向搜索算法由Dantzig 提出的基本思想, N icho lson 正式提出算法。该算法在从起点开始寻找最短路径的同时也从终点开始向前进行路径搜索, 最佳效果是二者在中间点汇合, 这样可缩短搜索时间。但是如果终止规则不合适, 该算法极有可能使搜索时间增加1倍, 即两个方向都搜索到最后才终止。2 6 蚁群算法

蚁群算法是由意大利学者M Dori g o 等于1991年提出的, 它是一种随机搜索算法, 是在对大自然中蚁群集体行为的研究基础上总结归纳出的一种优化算法, 具有较强的鲁棒性, 而且易于与其他方法相结合。文献[17]验证了蚁群算法的算法复杂度要优于D ijkstra 算法。

此外, 还有实时启发式搜索算法、基于分层路网的搜索算法、神经网络、遗传算法及模糊理论等, 由于实际需求不同对算法的要求和侧重点也会有所不用, 所以也出现了许多以上算法的各种改进算法。大多数算法应用于求解车辆路径规划问题时都会存在一定的缺陷, 所以目前的研究侧重于利用多种算法融合来构造混合算法3 交通信息预测算法

实时准确的交通信息预测是智能交通领域中研究热点之一。要实现车辆导航系统, 道路交通状况[18-24]

**

测未来几分钟或几十分钟内的交通状况更是动态路径规划的关键。对于多变的道路交通现状来说, 动态路径规划的优劣与对相关路段的交通信息预测的准确度有着十分密切的关系。

由于交通信息预测尤其是交通流预测对于动态路径规划具有重要意义, 所以交通流的预测特别是短时交通流预测是当前诸多学者重点研究的智能交通的核心问题之一, 它是动态路径规划中道路权重的重要因子。

目前, 许多预测方法已经被应用于短时交通流的预测中, 取得了诸多成果, 如卡尔曼滤波方法、时间序列方法、多元回归方法、神经网络方法、

[25]

M ar kov 预测及灰色预测理论等, 其中每一种方法又有很多种预测模型。当前的预测方法主要分为两

[26]

大类:一类是基于微积分和数理统计等传统数学和物理方法的预测模型, 如参数回归模

型、时间序列模型、卡尔曼滤波模型等; 另一类是利用现代科学研究技术和研究方法的预测模型, 如基于小波理论的方法、非参数回归模型、基于神经网络的复合预测模型等。

时间序列预测方法在短时交通流预测中应用广泛, 是当前的研究热点。该算法中的滑动平均模型(MA 、自回归模型(AR 、自回归滑动平均模型

[27]

(ARMA 是发展较早的交通信息预测模型, 优点是易于实时更新数据, 便于大规模应用的优点, 又有相对较高的计算精度。但是它很难反映交通状况的不确定性和非线性, 无法克服随机干扰对交通流量的影响, 所以一般配合优缺点互补的其他预测模型一同应用于实际需求中。

支持向量机(SUV 是在1963年由AT&TBe ll 实验室的Vapn i k 针对分类问题提出的, 在交通信息预测方面是一种新理论, 所以当前的研究成果相对较少, 已也被推广到时间序列分析中

[26]

。此外, 当

前还有很多预测理论被应用到交通流预测中, 如遗

[28]

传算法和神经网络的混合模型, 混沌理论、组合预测理论等。4 展望

本文对车辆路径动态规划问题中的几个关键点:路网模型、动态路径规划算法和交通信息的智能预测的国内外研究情况做了重点介绍。当前相对比较成熟的车辆导航系统, 大多是基于静态路径规划, 而基于动态路径规划的智能导航系统现在还没有发, 。

116公路交通科技

ZOU Xudong , L i m its [J ].

ZHENG Sifa ,

BAN X uegang,

第27卷et a. l

车辆导航动态路径规划方法已成为车辆智能导航系统的研究热点问题。

随着计算机科学技术、无线通信技术以及交通

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

参考文献:R eferences :

[1] 孙世博, 冯勇, 郑剑飞. 车辆导航系统最优路径规划

研究[J ].自动化技术与应用, 44-46.

S UN Sh i bo , FENG Y ong , Z H ENG Ji anfe. i O pti m a l P at h P l ann i ng f o r V eh icle N av i g ati on [J ].

T echn i ques of

44-46.

[12]

Au t om ati on and Appli cations , 2006, 25(9:

2006,

25(9:

[11][10]

Opti m a l P at h A l go rith m f o r R oad N e t w ith T raffic Capacity

Journa l o f H i ghway and T ransportation

R esearch and D ev elopment , 2002, 19(4 :82-83. 张可, 刘小明, 王笑京. 车辆自动导航的路线优化系统研究[J].系统工程, on R oute 48-53.

裴钟哲, 刘小明. 用方位角算法和转向角算法解决节点权重问题[J].公路交通科技, 103-108.

PEI Zhongzhe , L I U X i aom ing . U si ng A zi m uth A lgor i th m and T urn ang le A lgo rith m to So lve N odal W eigh t P roble m [J].Journa l ofH igh w ay and T ranspo rtati on R esearch and D eve l op m ent , 2007, 24(5:

103-108.

付梦印, 李杰, 邓志红. 基于分层道路网络的新型路径规划算法[J].计算机辅助设计与图形学学报, 2005, 17(4:FU M engy i n , N e t w ork [J ].

Journa l of

[13]

719-722. L I J i e ,

DENG Zhihong .

A N e w Route 2007,

24(5 :

P lanni ng

2001, 19(2:48-53.

f o r V eh i c l e A utom ati c

19(2 :

ZHANG K e , L I U X iaom i ng , W ANG X i ao jing . R esearch

System

N av i g ati on [J].

Syste m s Eng i nee ri ng , 2001,

[2] OKUTAN I I , STEPHANEDES Y J . Dyna m ic P redicti on of

T raffic V o l ume through K al m an F ilter i ng T heo ry [J ].T ransportation R esearch P art B :M e t hodo l og ica, l 1984, 18(1:1-11.

[3] S M I TH B L, DE M ETSKY M J . T ra ffic F l ow F orecasti ng :

Compar i son o f M ode li ng A pproaches [J].

T ransportation Eng i nee ri ng , 1997, 123(4:261-266.

[4] M ARK S D, M ARK R C . Short ter m In ter urban T ra ffi c

Forecasts U s i ng N eural N e t w orks [J ].

Internati ona l

Journa l of Forecasting , 1997, 13(1:21-31.

[5] D IJ K S TRA E W. A N o te on Two P roble m s i n Connec tion

w ith G raphs [J].N u m er ische M a t he m a tik , 269-271.

[6]

LEE C Y. A n A lgor i th m fo r P ath Connectiv i ty and Its A pp licati ons [J].E lectronic Co m puters , 1961, 3(10:346-365.

[7]

PE AR L J . H eur i stics :Co m puter Proble m A dd ison W esley , 1984.

[8] 郑年波, 李清泉, 徐敬海, 等. 基于转向和延误

的双向启发式最短路径算法[J].武汉大学学报:信息科学版,

2006, 31(3:

256-259.

XU Ji ngha , i e t a. l A

[16]

ZHENG N i anbo ,

L I Q i ngquan ,

Inte lli gent Search Strateg ies f o r

R ead i ng ,

M A:

[15]

So l v i ng [M ].

1959,

1:

[14]

P lanning A l gor it hm Based on t he H i erarch ica l R oad

Journa l of Co m pute r a i ded D esi gn &

719-722.

2007,

23

Co m puter G raph i cs , 2005, 17(4:

孙海鹏, 翟传润, 战兴群, 等. 基于实时交通信息的动态路径规划技术[J].微计算机信息, (8-3:

177-178.

Z HA I Chanrun , ZHAN X i ngqun ,

e t a. l

SUN H a i peng ,

Dyna m ic R oute P lann i ng T echniques Based on R ea l T i m e T ra ffic Info r ma ti on [J].Contro l&A uto m a tion , 2007, 23(8-3:[J ].

177-178.

2005,

26(10 :

柯健, 陈天滋. 基于实时信息的车辆导航路由算法

计算机工程与设计,

2662-26.

K E Jian , C H E N T i anz. i V eh i c le R outi ng A l go rith m Based on R ea l ti

m e Infor m a ti on [J],Computer Eng i neer i ng and D esi gn , 2005, 26(10:J OHN F , [J].20(3:

2662-26.

PETER R. A daptive R outi ng for R oad T ra ffi c 46-53.

5(29:

797-800.

IEEE Computer G raph ics and A pplica ti ons , 2000,

周程. 物流配送路径优化策略研究[J].武汉理工大学学报, 2005,

ZHOU Cheng. R esearch on O pti m i ze M e t hod o f Log istics D eli very R oute [J ].

Journal of W uhan U niversity of

T echno l ogy , 2005, 5(29 :797-800.

B idirecti ona lH eur i stic Shortest Pa t h A l go rith m w ith Turn P roh i b iti ons and D elay s [J].G eoma ti cs and Infor m a tion Science o fW uhan U niversity ,

2006, 31(3 :256-259.

[9] 邹旭东, 郑四发, 班学钢, 等. 具有交通约束的

道路网络最优路径算法[J].公路交通科技, (.

2002,

[17]

张国强, 晏克非. 动态随机状态下的车辆导航及其路径寻优算法[J].长沙交通学院学报, (3 :.

2002,

18

第11期葛 艳, 等:车辆导航动态路径规划的研究进展

(1:

61-70.

117

ZHANG Guoqiang , YAN K e f e. i V ehic l e P iloti ng unde r R andom Dyna m i c Conditi on and Its A l go rith m s for O pti m a l Route [J ].

[18]

Journa l of Changsha Communicati ons

U n i ve rsity , 2002, 18(3:72-76.

Z HAN F B . T hree F astest Sho rtest P ath A l go rith m s on R ea l Ro ad N et wo rks :[J].

[19]

D ata S tructures and P ro cedures

[24]

Journal of G eog raph ic Infor m ati on and D ec i sion

YANG Y , i GU Zhengq, i HU L i n , et a. l T he A ppli cation o f V irus Evo l u ti onary G enetic A lgor it h m to Dyna m ic Pa t h P lanning [J].A utomo ti ve Eng i neer i ng , 2007, 29(1 :61-70.

雷东升, 诸彤宇. 一种基于实时路况信息的动态路径规划算法[J ].28-30.

LEI D ongsheng , Z HU T ongyu . A Dyna m ic Path planni ng A lgor i th m Based on R ea l ti m e T ra ffic Infor m a tion [J].Co m pute r Sc i ence , 2008, 35(4 :28-30.

[25]

许伦辉, 傅惠. 交通信息智能预测理论与方法[M ].北京:科学出版社, 2009.

XU L unhun , FU Hu. i Inte lli gent P red i ction Theory and M ethods o f T raffi c Infor m ation [M ].P ress , 2009.

[26]

刘静, 关伟. 交通流预测方法综述[J].公路交通科技, 2004, 21(3:L I U J i ng ,

82-85.

Journal of H i gh w ay and

2004,

21

GUAN W e. i A Su mm ary of T raffic F low

Be iji ng :

Sc i ence

计算机科学,

2008,

35(4 :

A nalysis , 1997, 1(1:69-82.

张权, 王健. 安全最优路径分析与实现[J].中国人民大学学报, 2005(4:70-72.

ZHANG Q uan , WANG Jian . A na l ysis and R ealizati on to the Safe ty Opti m a l P ath [J].Journal o f Ch i nese P eople s pub lic Security U niversity , 2005(4:

[20]

路径算法[J].测绘信息与工程, 38-40.

LUO Y uejun , L I L i n , ZHEN L. i Shortest Pa t h A lgor it h m for Co m pli ca

ted Intersection w it h T raffic R ules [J ].Journal o f G eom atics , 2006, 31(5:38-40.

[21]

段莉琼, 刘立国. 基于车辆导航的路径分析与应用[J].地理信息世界, DUAN L i x iong ,

2005(4:44-47.

T he R oute P l ann i ng and

[27]

L I U L i guo .

70-72. 2006,

31(5:

罗跃军, 李霖, 郑莉. 顾及复杂路口交通规则的最短

Fo recasti ng M ethods [J ].(3 :82-85.

T ranspo rtati on R esea rch and D eve l op m ent ,

Appli cation Based on V eh icle N av i gation [J].G eo m atics W o rld , 2005(4 :44-47.

[22]

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

FU M engy in ,

ZHOU P eide .

A Q u i ck P at h

p lann i ng A lgor it h m f o r V eh icle N av i ga ti on Sy stem [J ].Journal o f Be ijing Institute of T echno logy , 2002, 22(2:188-191.

[23]

杨易, 谷正气, 胡林, 等. 病毒进化遗传算法在动态路径规划中的运用研究[J].汽车工程,

2007,

29

顾国民, 李未, 蔡家楣. 城市综合应急指挥系统的车辆路径规划研究与实现[D ].杭州:浙江工业大学,

2005.

L I W e, i CA I Ji ame. i T he R esearch and

GU Guo m i n ,

A pplicati on of V eh i c l e P l ann i ng i n Integrated Em ergency M anag e m ent Syste m [D ].H angzhou :Zhejiang U n i versity o f T echno logy , 2005.

[28]

BAH ER A, H I MAN S HU P , W ILL R. Short T er m F reeway T raffic F l ow Predicti on U s i ng Eneticall y opti m i zed T i m e de lay based N eura l N et w orks [D ].Berke l ey :U n i versity of Ca liforn ia , 1999.

(上接第112页

[12]

苏岳龙. 城市交通参与者行为分析和干预措施[D ].北京:清华大学, 2009. SU

Y uelong .

Behav ior Ana l ys i s

of U rban T ra ffi c

Be iji ng :

P arti c i pants and Interventi on M easures [D ].T si nghua U n i versity , 2009.

[13]

JI N X uex i ang, S U Y ue l ong , Z HANG Y , i et a. l M ode ling Spac i ng D i str i bu ti on o f Queui ng V eh icles i n Front of a S i gnalized J uncti on U si ng R andom ‐m a trix T heo ry [J].T si nghua Science &T echno l ogy ,

2009,

14(2:

[14]

252-254.

北京市交通委员会路政局. 2006年底城市道路里程数据[EB /OL].[2007-03-30].http :

//www bjl zj gov cn /zhbd /tj xx /200804/t20080420_1384 ht m

Be iji ng M unicipa lR oad w ay A d m i nistrati on Bureau D ata of U rban R oad L ength be f o re 2006in Beiji ng [EB /OL ].[2007-03-30].http :

//www bjl zj gov cn /zhbd /tj xx /200804/t 200804201384 h t m