车辆导航系统中基于街区分块的分层路网路径规划

张照生 杨殿阁 张德鑫 连小珉

清华大学汽车安全与节能国家重点实验室，北京，100084

0 引言

随着智能交通技术的不断发展，车辆导航技术越来越广泛地应用于驾驶辅助系统中［1-3］。路径规划是车辆导航技术的一个重要功能［4-5］，在目前的寻路算法中，经典的路径规划算法是Dijkstra算法［6］和 A* 算法［7-8］。但由于当前导航电子地图数据庞大(350万路口、560万路段)，在平面路网［9］中运行Dijkstra算法或A*算法均不能满足规划速度的需求，另外，受嵌入式导航设备硬件条件的限制，地图数据不能一次性读入系统内存［10］，因此需要对地图数据按照一定的准则进行模块化处理，以满足嵌入式系统计算及显示的需要。目前针对路径规划的导航路网大多采用分层分块的方法来提高数据的读取效率并减少节点拓展数量［11-15］，传统的地图分块［16］按照固定经纬度范围划分网格，该方法中路网密集的地方数据量过多，而路网稀疏的地方数据量过少，导致路径规划数据使用效率低。

本文提出一种路网分块方法，考虑实际路网中街区路段分布特性(路网稀疏则街区面积较大，否则街区面积较小)，在不同等级路网中按照街区特性在路网中自然分块，每个街区作为地图中的一个块。同时利用路径规划的起终点距离及所在的块控制路网拓展等级，利用拓展半径和邻接块范围控制路网拓展范围。最后采用路网分层方法结合街区分块在大规模路网中实现了路径规划算法。

1 路网分层分块

分层分块路网的路径规划如图1所示，在路径规划过程中，在起点附近尽快上升到高层路网中拓展，在高层路网中拓展到终点附近然后降级拓展，最终在底层路网拓展到终点。高层路网中路段稀疏，拓展到的节点少，与平面路网规划算法相比，明显提高了路径规划的速度。

图1 分层分块路网路径规划思路图

图1中，路网按照路段等级分层，每层路网按街区分块，s与t分别为路径规划的起点和终点，箭头表示拓展方向，深色区域为拓展区域。

路网中路段集合E表示为

式中，i为路段等级;e(i)为路网中等级为i的路段集合;N为路网级别总数。

第i层路网中路段集合E(i)={e(j)|j≥i}。

城市路网包括骨干路网及连接骨干路网的区域路网，城市管理部门在城市规划中已经考虑道路的分布，道路稀疏的地方区域路网面积较大，道路稠密的地方区域路网面积较小，因此不同区域路网内部道路数量相差不大。这里将区域路网做为一个街区(街区内部道路等级较低，周边道路等级较高)，本文利用路网的街区特性，将第i层路网中形成的最小封闭区域作为第i－1层路网中的“块”。路径规划升级过程中，总是由低级路网的边界升级到高级路网，其在低层路网中的拓展过程恰好就是街区内部区域的拓展，拓展范围与街区分块方法一致。另外因为“块”以高等级路网做边界，因此与按照经纬度进行物理分块相比，这种分块方法不会破坏实际道路的拓扑结构，并且由于单位块中道路数量分布均匀，路径规划中读取的数据在路径拓展中能得到较好使用，因此在数据使用过程中该分块方法数据利用效率高。

在路径拓展的过程中，考虑用户的出行习惯，对于一些距离较长的路线，通常并不刻意选择距离最短的路径，而是尽快找到起点附近的高等级道路，通过高级路网到达终点附近后，再进入区域内部的低层次路网到达终点。这里按照路段的等级将路网分为N级，等级越高路网越稀疏，分层路网如下:

式(2)中，V(i)为第i层路网节点集合，高级路网中的元素集合从属于低级路网元素集合，上层路网形成的最小封闭区域称为下级路网中的“块”，路网的分级分块如图2所示。

图2 双层路网分层分块模型

图2中，低等级路段(细实线)与低等级路段之间的交点为低等级节点，高等级路段(粗实线)与低等级路段的交点或高级路段之间的交点为高等级节点。高等级路段和高等级节点构成的路网为高层路网，粗实线构成的封闭区域为低层路网的“块”。在分块过程中，从任意一个低等级节点出发，以广度优先原则拓展该节点，遇到高等级节点则该拓展方向停止，待最优队列中所有节点都为高等级节点，则拓展到的节点集合为块节点集合。

2 路径规划

2.1 路网拓展范围及拓展等级

路网的拓展范围R由起点所在的块及起点的面积拓展范围共同确定，表示如下:

式中，A为起点s的面积拓展范围;B为起点s的块拓展范围。

面积拓展范围A表示为

式中，r为半边长;S为面积函数。

S(r，s)是一个以点s为中心、以r为半边长的正方形。起点的块拓展范围B为

路径规划前，首先确定路径的拓展等级，即路径最高在第几层路网中拓展，拓展等级H由路径的距离和起终点所在的块两个因素确定:

图3 点的拓展范围影响因素

式(6)中，hs为由距离确定的拓展等级，hb为起终点共同所在的块确定的拓展等级，若起终点在第i级路网中同属于一个块，则块拓展等级hb等于i，即

式中，b(j)为起点或终点在第j层所在的块。

由距离确定的拓展等级hs如下:

式中，ls，t为起点和终点的直线距离;l(i)为第i层路网距离拓展阈值。

各层路网的距离拓展阈值如表1所示。

表1 各层路网的距离拓展阈值

2.2 节点拓展

路径规划的过程即为节点拓展的过程，拓展过程中，所有拓展到的节点都存储在拓展节点集合U中，拓展节点集合U表示为

式中，uj为拓展节点;j为节点序;ud为节点ID;up为节点经纬度位置;uf为起点s经过节点u到达终点t的总代价;ug为起点s到节点u的已有最小代价;uc为节点颜色;uz为节点u的父节点在拓展节点集合U中的节点序，起点s对应节点的父节点序为 －1。

节点颜色uc的表达式为

式(11)中，cb(黑色)表示已经拓展节点;cw(白色)表示未拓展节点，cg(灰色)表示正在拓展节点。在路径拓展的过程中，黑色节点不可以向外拓展也不可以被拓展，灰色节点可以向灰色节点或白色节点拓展，白色节点只能被拓展。

拓展规则如图4所示。

已有代价ug的计算式为

图4 节点拓展规则

式中，Nu为从起点s到节点u所经过的路段条数;k为路段序号;W(ek)为路段ek的代价。

总代价uf为已有代价ug和启发代价uh之和，即

启发代价uh为节点u到达终点t的预估代价，其计算公式为

式中，eu，t为节点u与终点t两点连线形成的虚拟路段。

路径规划中灰色拓展节点的节点序存储在拓展队列Q中，如下所示:

拓展队列中节点序Qm按照该节点的总代价由小到大顺序排列，c(j)是节点序号为j的节点颜色。

拓展到的白色节点加入到拓展节点集合U中，其节点序加入到拓展队列Q中，且节点颜色变为灰色。拓展队列中的灰节点若再次被拓展到，将本次拓展得到的已有代价ug与上次拓展已有代价u'g比较，若ug较小，则本次的拓展数据替换上次的拓展数据，表达式为

在路径拓展的过程中，考虑人们的出行习惯，对于一些距离较长的路线，通常是尽快找到起点附近的高等级道路，这就需要节点的升级拓展，节点的升级拓展需要满足3个条件:①有上级节点;②当前路网级别不是最高拓展等级;③上级节点在拓展范围内。

以第一级和第二级路网为例，节点的升级如图5所示。节点u(1)的上层节点u(2)不在拓展区域内，则该节点不能升级拓展。

2.3 最优路生成

最优路的拓展结束需满足以下条件:①待拓展节点与终点t对应节点重合;②拓展队列为空。其中条件①表示搜索得到最优路径，条件②表示从起点s到终点t无最优路径。拓展终止条件为

图5 节点的升级拓展

式中，NQ为拓展队列Q中节点个数;“∨”表示逻辑“或”。

路网拓展结束后，会得到一颗拓扑树，对拓扑树进行回溯，就会得到最优路路径节点的序列。节点回溯如图6所示。

图6 最优路节点回溯

如图6所示，实线箭头表示节点的拓扑方向，虚线箭头表示节点回溯方向。回溯时根据节点的父节点序号从节点数组循环查找父节点，当父节点序号为 －1(起点s父节点序号为－1)时，终止循环。节点回溯可以找到最优路径节点集合，将这些节点顺次连接起来，就生成了最优拓扑节点路径，如图7所示。

图7 最优拓扑路径

3 试验验证

本文所有试验在嵌入式平台上完成，试验平台为主频500MHz的ARM处理器，内存128MB;实验路网选用全国路网，路网中路口个数为3 479 368，路段数为5 643 890，算法用 Visual C++编程实现。

路网按照路段级别共分为6层，路网中路段级别与类型如表2所示。

表2 路网中道路级别与分类

在分层路网中，采用街区分块的方法，在路网密度较大的北京市路网进行了短距离寻路，起点设在北京市清华大学，终点设在北京市通州区西太平庄，将平面路网规划和分层路网方法进行比较，规划效果如图8所示。

图8 局域路网中分层路网拓展区域与单层路网拓展区域比较

如图8所示，图中黑色粗实线为最优路，黑色细实线为拓展到的道路，灰色细实线为未拓展的道路。图8中，平面路网规划拓展节点数为234 067，分层路网规划拓展节点数为29 684，由此可以看出，分层路网规划与平面路网规划相比，拓展点数大大减少。另外，本文对广域路网中长距离规划做了对比，规划起点设在山西省太原火车站，终点设在四川省成都市万隆花园，平面路网规划拓展节点数为346 843，分层路网规划拓展节点数为18 625，规划对比结果如图9所示。

从图9可以看出，在长距离规划中，与平面路网规划相比，其规划拓展的节点更少，从而可以获得更大的加速比。在路网中选择不同位置的起点与终点进行了大量实验，计算分层路网情况下的规划时间，并与平面路网规划时间对比，计算路网分层对路径规划效率的影响，计算结果如表3所示。

图9 广域路网中分层路网拓展区域与单层路网拓展区域比较

表3 分层路网路径规划与平面路网路径规划对比

由表3可以看出，分层路径规划算法在路网不同道路密度和分布的情况下，能够在运算资源有限的嵌入式平台下实现快速而准确的最优路径计算，在广域路网中长距离路径规划的计算耗时最长约为7s，能够满足实际应用的要求。

4 结语

本文提出了一种基于街区的路网分块方法，该方法利用路网的分布特性，自适应调整路网分块中数据的大小，在保持路网拓扑结构的情况下提高了路网数据的读取效率;路网分层使规划在高层稀疏路网中拓展，从而减少路径规划拓展节点的数量，在距离较远的路径规划中分层路网对速度提高更明显，分块分层的路径规划算法可以应用于大规模路网中，路径规划的效果可以满足用户的需求。

［1］Zhang Tao，Yang Diange，Li Ting，et al.An Improved Virtual Intersection Model for Vehicle Navigation at Intersections［J］.Transportation Research Part C:Emerging Technologies，2011，19(3):413-423.

［2］王檀彬，陈无畏，焦俊，等.多传感器融合的智能车辆导航研究［J］.中国机械工程，2009，20(11):1381-1385.Wang Tanbin，Chen Wuwei，Jiao Jun，et al.Study on Navigation of Intelligent Vehicles Based on Multi－sensor Fusion［J］.China Mechanical Engineering，2009，20(11):1381-1385.

［3］李旭，张为公.基于联邦滤波的智能车辆多传感器组合导航的研究［J］.中国机械工程，2008，19(12):1446-1451.Li Xu，Zhang Weigong.Research on Multi－sensor Integrated Navigation Technique Based on Federated Filter for Intelligent Vehicle［J］.China Mechanical Engineering，2008，19(12):1446-1451.

［4］李挺.车辆自主导航的广域蛛式地图与点状路网跨层路径规划［D］.北京:清华大学，2008.

［5］王文玺，肖世德，孟祥印，等.模糊神经网络下基于强化学习的自主式地面车辆路径规划研究［J］.中国机械工程，2009，20(21):2536-2541.Wang Wenxi，Xiao Shide，Meng Xianyin，et al.ALV Path Planning Based on Reinforcement Learning in Fuzzy Neural－networks［J］.China Mechanical Engineering，2009，20(21):2536-2541.

［6］Dijkstra E W.A Note on Two Problems in Connexion with Graphs［J］.Numerische Mathematik，1959，1:269-271.

［7］Hart P E，Nilsson N J，Raphael B.A Formal Basis for the Heuristic Determination of Minimum Cost Paths［J］.IEEE Transportation System Science and Cybernetics，1968，4(2):100-107.

［8］Hart P E，Nilsson N J，Raphael B.Correction to“A Formal Basis for the Heuristic Determination of Minimum Cost Paths”［J］.ACM SIGART Bulletin，1972，37:28-29.

［9］李清泉，郑年波，徐敬海，等.一种基于道路网络层次拓扑结构的分层路径规划算法［J］.中国图象图形学报，2007，12(7):1280-1285.Li Qingquan，Zheng Nianbo，Xu Jinghai et al.A Hierarchical Route Planning Algorithm Based on Multilevel Topological Structure of Road Network［J］.Journal of Image and Graphics，2007，12(7):1280-1285.

［10］颜波.车载自主导航系统中的最优路径规划［D］.北京:清华大学，2004.

［11］Jagadeesh G R，Srikanthan T，Quek K H .Heuristic Techniques for Accelerating Hierarchical Routing on Road Networks［J］.IEEE Transactions on Intelligent Transportation Systems，2002，3(4):301-309.

［12］Geisberger R，Sanders P，Schultes D，et al.Contraction Hierarchies:Faster and Simpler Hierarchical Routing in Road Networks［J］.Lecture Notes in Computer Science，2008，5038:319-333.

［13］Rajagopalan R，Mehrotra K，Mohan C，et al.Hierarchical Path Computation Approach for Large Graphs［J］.IEEE Transaction on Aerospace and Electronic Systems，2008，44(2):427-440.

［14］郑烟武.基于分层分区的动态路径规划算法研究［D］.广州:华南理工大学，2011.

［15］Song Qing，Wang Xiaofan.Efficient Routing on Large Road Networks Using HierarchicalCommunities［J］.IEEE Transactions on Intelligent Transportation Systems，2011，12(1):132-140.

［16］张静.面向路径规划的导航路网数据模型研究［D］.北京:中国矿业大学，2009.