張照生 楊殿閣 張德鑫 連小珉

清華大學汽車安全與節(jié)能國家重點實驗室，北京，100084

0 引言

隨著智能交通技術(shù)的不斷發(fā)展，車輛導航技術(shù)越來越廣泛地應用于駕駛輔助系統(tǒng)中［1-3］。路徑規(guī)劃是車輛導航技術(shù)的一個重要功能［4-5］，在目前的尋路算法中，經(jīng)典的路徑規(guī)劃算法是Dijkstra算法［6］和 A* 算法［7-8］。但由于當前導航電子地圖數(shù)據(jù)龐大(350萬路口、560萬路段)，在平面路網(wǎng)［9］中運行Dijkstra算法或A*算法均不能滿足規(guī)劃速度的需求，另外，受嵌入式導航設(shè)備硬件條件的限制，地圖數(shù)據(jù)不能一次性讀入系統(tǒng)內(nèi)存［10］，因此需要對地圖數(shù)據(jù)按照一定的準則進行模塊化處理，以滿足嵌入式系統(tǒng)計算及顯示的需要。目前針對路徑規(guī)劃的導航路網(wǎng)大多采用分層分塊的方法來提高數(shù)據(jù)的讀取效率并減少節(jié)點拓展數(shù)量［11-15］，傳統(tǒng)的地圖分塊［16］按照固定經(jīng)緯度范圍劃分網(wǎng)格，該方法中路網(wǎng)密集的地方數(shù)據(jù)量過多，而路網(wǎng)稀疏的地方數(shù)據(jù)量過少，導致路徑規(guī)劃數(shù)據(jù)使用效率低。

本文提出一種路網(wǎng)分塊方法，考慮實際路網(wǎng)中街區(qū)路段分布特性(路網(wǎng)稀疏則街區(qū)面積較大，否則街區(qū)面積較小)，在不同等級路網(wǎng)中按照街區(qū)特性在路網(wǎng)中自然分塊，每個街區(qū)作為地圖中的一個塊。同時利用路徑規(guī)劃的起終點距離及所在的塊控制路網(wǎng)拓展等級，利用拓展半徑和鄰接塊范圍控制路網(wǎng)拓展范圍。最后采用路網(wǎng)分層方法結(jié)合街區(qū)分塊在大規(guī)模路網(wǎng)中實現(xiàn)了路徑規(guī)劃算法。

1 路網(wǎng)分層分塊

分層分塊路網(wǎng)的路徑規(guī)劃如圖1所示，在路徑規(guī)劃過程中，在起點附近盡快上升到高層路網(wǎng)中拓展，在高層路網(wǎng)中拓展到終點附近然后降級拓展，最終在底層路網(wǎng)拓展到終點。高層路網(wǎng)中路段稀疏，拓展到的節(jié)點少，與平面路網(wǎng)規(guī)劃算法相比，明顯提高了路徑規(guī)劃的速度。

圖1 分層分塊路網(wǎng)路徑規(guī)劃思路圖

圖1中，路網(wǎng)按照路段等級分層，每層路網(wǎng)按街區(qū)分塊，s與t分別為路徑規(guī)劃的起點和終點，箭頭表示拓展方向，深色區(qū)域為拓展區(qū)域。

路網(wǎng)中路段集合E表示為

式中，i為路段等級;e(i)為路網(wǎng)中等級為i的路段集合;N為路網(wǎng)級別總數(shù)。

第i層路網(wǎng)中路段集合E(i)={e(j)|j≥i}。

城市路網(wǎng)包括骨干路網(wǎng)及連接骨干路網(wǎng)的區(qū)域路網(wǎng)，城市管理部門在城市規(guī)劃中已經(jīng)考慮道路的分布，道路稀疏的地方區(qū)域路網(wǎng)面積較大，道路稠密的地方區(qū)域路網(wǎng)面積較小，因此不同區(qū)域路網(wǎng)內(nèi)部道路數(shù)量相差不大。這里將區(qū)域路網(wǎng)做為一個街區(qū)(街區(qū)內(nèi)部道路等級較低，周邊道路等級較高)，本文利用路網(wǎng)的街區(qū)特性，將第i層路網(wǎng)中形成的最小封閉區(qū)域作為第i－1層路網(wǎng)中的“塊”。路徑規(guī)劃升級過程中，總是由低級路網(wǎng)的邊界升級到高級路網(wǎng)，其在低層路網(wǎng)中的拓展過程恰好就是街區(qū)內(nèi)部區(qū)域的拓展，拓展范圍與街區(qū)分塊方法一致。另外因為“塊”以高等級路網(wǎng)做邊界，因此與按照經(jīng)緯度進行物理分塊相比，這種分塊方法不會破壞實際道路的拓撲結(jié)構(gòu)，并且由于單位塊中道路數(shù)量分布均勻，路徑規(guī)劃中讀取的數(shù)據(jù)在路徑拓展中能得到較好使用，因此在數(shù)據(jù)使用過程中該分塊方法數(shù)據(jù)利用效率高。

在路徑拓展的過程中，考慮用戶的出行習慣，對于一些距離較長的路線，通常并不刻意選擇距離最短的路徑，而是盡快找到起點附近的高等級道路，通過高級路網(wǎng)到達終點附近后，再進入?yún)^(qū)域內(nèi)部的低層次路網(wǎng)到達終點。這里按照路段的等級將路網(wǎng)分為N級，等級越高路網(wǎng)越稀疏，分層路網(wǎng)如下:

式(2)中，V(i)為第i層路網(wǎng)節(jié)點集合，高級路網(wǎng)中的元素集合從屬于低級路網(wǎng)元素集合，上層路網(wǎng)形成的最小封閉區(qū)域稱為下級路網(wǎng)中的“塊”，路網(wǎng)的分級分塊如圖2所示。

圖2 雙層路網(wǎng)分層分塊模型

圖2中，低等級路段(細實線)與低等級路段之間的交點為低等級節(jié)點，高等級路段(粗實線)與低等級路段的交點或高級路段之間的交點為高等級節(jié)點。高等級路段和高等級節(jié)點構(gòu)成的路網(wǎng)為高層路網(wǎng)，粗實線構(gòu)成的封閉區(qū)域為低層路網(wǎng)的“塊”。在分塊過程中，從任意一個低等級節(jié)點出發(fā)，以廣度優(yōu)先原則拓展該節(jié)點，遇到高等級節(jié)點則該拓展方向停止，待最優(yōu)隊列中所有節(jié)點都為高等級節(jié)點，則拓展到的節(jié)點集合為塊節(jié)點集合。

2 路徑規(guī)劃

2.1 路網(wǎng)拓展范圍及拓展等級

路網(wǎng)的拓展范圍R由起點所在的塊及起點的面積拓展范圍共同確定，表示如下:

式中，A為起點s的面積拓展范圍;B為起點s的塊拓展范圍。

面積拓展范圍A表示為

式中，r為半邊長;S為面積函數(shù)。

S(r，s)是一個以點s為中心、以r為半邊長的正方形。起點的塊拓展范圍B為

路徑規(guī)劃前，首先確定路徑的拓展等級，即路徑最高在第幾層路網(wǎng)中拓展，拓展等級H由路徑的距離和起終點所在的塊兩個因素確定:

圖3 點的拓展范圍影響因素

式(6)中，hs為由距離確定的拓展等級，hb為起終點共同所在的塊確定的拓展等級，若起終點在第i級路網(wǎng)中同屬于一個塊，則塊拓展等級hb等于i，即

式中，b(j)為起點或終點在第j層所在的塊。

由距離確定的拓展等級hs如下:

式中，ls，t為起點和終點的直線距離;l(i)為第i層路網(wǎng)距離拓展閾值。

各層路網(wǎng)的距離拓展閾值如表1所示。

表1 各層路網(wǎng)的距離拓展閾值

2.2 節(jié)點拓展

路徑規(guī)劃的過程即為節(jié)點拓展的過程，拓展過程中，所有拓展到的節(jié)點都存儲在拓展節(jié)點集合U中，拓展節(jié)點集合U表示為

式中，uj為拓展節(jié)點;j為節(jié)點序;ud為節(jié)點ID;up為節(jié)點經(jīng)緯度位置;uf為起點s經(jīng)過節(jié)點u到達終點t的總代價;ug為起點s到節(jié)點u的已有最小代價;uc為節(jié)點顏色;uz為節(jié)點u的父節(jié)點在拓展節(jié)點集合U中的節(jié)點序，起點s對應節(jié)點的父節(jié)點序為 －1。

節(jié)點顏色uc的表達式為

式(11)中，cb(黑色)表示已經(jīng)拓展節(jié)點;cw(白色)表示未拓展節(jié)點，cg(灰色)表示正在拓展節(jié)點。在路徑拓展的過程中，黑色節(jié)點不可以向外拓展也不可以被拓展，灰色節(jié)點可以向灰色節(jié)點或白色節(jié)點拓展，白色節(jié)點只能被拓展。

拓展規(guī)則如圖4所示。

已有代價ug的計算式為

圖4 節(jié)點拓展規(guī)則

式中，Nu為從起點s到節(jié)點u所經(jīng)過的路段條數(shù);k為路段序號;W(ek)為路段ek的代價。

總代價uf為已有代價ug和啟發(fā)代價uh之和，即

啟發(fā)代價uh為節(jié)點u到達終點t的預估代價，其計算公式為

式中，eu，t為節(jié)點u與終點t兩點連線形成的虛擬路段。

路徑規(guī)劃中灰色拓展節(jié)點的節(jié)點序存儲在拓展隊列Q中，如下所示:

拓展隊列中節(jié)點序Qm按照該節(jié)點的總代價由小到大順序排列，c(j)是節(jié)點序號為j的節(jié)點顏色。

拓展到的白色節(jié)點加入到拓展節(jié)點集合U中，其節(jié)點序加入到拓展隊列Q中，且節(jié)點顏色變?yōu)榛疑?。拓展隊列中的灰?jié)點若再次被拓展到，將本次拓展得到的已有代價ug與上次拓展已有代價u'g比較，若ug較小，則本次的拓展數(shù)據(jù)替換上次的拓展數(shù)據(jù)，表達式為

在路徑拓展的過程中，考慮人們的出行習慣，對于一些距離較長的路線，通常是盡快找到起點附近的高等級道路，這就需要節(jié)點的升級拓展，節(jié)點的升級拓展需要滿足3個條件:①有上級節(jié)點;②當前路網(wǎng)級別不是最高拓展等級;③上級節(jié)點在拓展范圍內(nèi)。

以第一級和第二級路網(wǎng)為例，節(jié)點的升級如圖5所示。節(jié)點u(1)的上層節(jié)點u(2)不在拓展區(qū)域內(nèi)，則該節(jié)點不能升級拓展。

2.3 最優(yōu)路生成

最優(yōu)路的拓展結(jié)束需滿足以下條件:①待拓展節(jié)點與終點t對應節(jié)點重合;②拓展隊列為空。其中條件①表示搜索得到最優(yōu)路徑，條件②表示從起點s到終點t無最優(yōu)路徑。拓展終止條件為

圖5 節(jié)點的升級拓展

式中，NQ為拓展隊列Q中節(jié)點個數(shù);“∨”表示邏輯“或”。

路網(wǎng)拓展結(jié)束后，會得到一顆拓撲樹，對拓撲樹進行回溯，就會得到最優(yōu)路路徑節(jié)點的序列。節(jié)點回溯如圖6所示。

圖6 最優(yōu)路節(jié)點回溯

如圖6所示，實線箭頭表示節(jié)點的拓撲方向，虛線箭頭表示節(jié)點回溯方向?；厮輹r根據(jù)節(jié)點的父節(jié)點序號從節(jié)點數(shù)組循環(huán)查找父節(jié)點，當父節(jié)點序號為 －1(起點s父節(jié)點序號為－1)時，終止循環(huán)。節(jié)點回溯可以找到最優(yōu)路徑節(jié)點集合，將這些節(jié)點順次連接起來，就生成了最優(yōu)拓撲節(jié)點路徑，如圖7所示。

圖7 最優(yōu)拓撲路徑

3 試驗驗證

本文所有試驗在嵌入式平臺上完成，試驗平臺為主頻500MHz的ARM處理器，內(nèi)存128MB;實驗路網(wǎng)選用全國路網(wǎng)，路網(wǎng)中路口個數(shù)為3 479 368，路段數(shù)為5 643 890，算法用 Visual C++編程實現(xiàn)。

路網(wǎng)按照路段級別共分為6層，路網(wǎng)中路段級別與類型如表2所示。

表2 路網(wǎng)中道路級別與分類

在分層路網(wǎng)中，采用街區(qū)分塊的方法，在路網(wǎng)密度較大的北京市路網(wǎng)進行了短距離尋路，起點設(shè)在北京市清華大學，終點設(shè)在北京市通州區(qū)西太平莊，將平面路網(wǎng)規(guī)劃和分層路網(wǎng)方法進行比較，規(guī)劃效果如圖8所示。

圖8 局域路網(wǎng)中分層路網(wǎng)拓展區(qū)域與單層路網(wǎng)拓展區(qū)域比較

如圖8所示，圖中黑色粗實線為最優(yōu)路，黑色細實線為拓展到的道路，灰色細實線為未拓展的道路。圖8中，平面路網(wǎng)規(guī)劃拓展節(jié)點數(shù)為234 067，分層路網(wǎng)規(guī)劃拓展節(jié)點數(shù)為29 684，由此可以看出，分層路網(wǎng)規(guī)劃與平面路網(wǎng)規(guī)劃相比，拓展點數(shù)大大減少。另外，本文對廣域路網(wǎng)中長距離規(guī)劃做了對比，規(guī)劃起點設(shè)在山西省太原火車站，終點設(shè)在四川省成都市萬隆花園，平面路網(wǎng)規(guī)劃拓展節(jié)點數(shù)為346 843，分層路網(wǎng)規(guī)劃拓展節(jié)點數(shù)為18 625，規(guī)劃對比結(jié)果如圖9所示。

從圖9可以看出，在長距離規(guī)劃中，與平面路網(wǎng)規(guī)劃相比，其規(guī)劃拓展的節(jié)點更少，從而可以獲得更大的加速比。在路網(wǎng)中選擇不同位置的起點與終點進行了大量實驗，計算分層路網(wǎng)情況下的規(guī)劃時間，并與平面路網(wǎng)規(guī)劃時間對比，計算路網(wǎng)分層對路徑規(guī)劃效率的影響，計算結(jié)果如表3所示。

圖9 廣域路網(wǎng)中分層路網(wǎng)拓展區(qū)域與單層路網(wǎng)拓展區(qū)域比較

表3 分層路網(wǎng)路徑規(guī)劃與平面路網(wǎng)路徑規(guī)劃對比

由表3可以看出，分層路徑規(guī)劃算法在路網(wǎng)不同道路密度和分布的情況下，能夠在運算資源有限的嵌入式平臺下實現(xiàn)快速而準確的最優(yōu)路徑計算，在廣域路網(wǎng)中長距離路徑規(guī)劃的計算耗時最長約為7s，能夠滿足實際應用的要求。

4 結(jié)語

本文提出了一種基于街區(qū)的路網(wǎng)分塊方法，該方法利用路網(wǎng)的分布特性，自適應調(diào)整路網(wǎng)分塊中數(shù)據(jù)的大小，在保持路網(wǎng)拓撲結(jié)構(gòu)的情況下提高了路網(wǎng)數(shù)據(jù)的讀取效率;路網(wǎng)分層使規(guī)劃在高層稀疏路網(wǎng)中拓展，從而減少路徑規(guī)劃拓展節(jié)點的數(shù)量，在距離較遠的路徑規(guī)劃中分層路網(wǎng)對速度提高更明顯，分塊分層的路徑規(guī)劃算法可以應用于大規(guī)模路網(wǎng)中，路徑規(guī)劃的效果可以滿足用戶的需求。

［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］李旭，張為公.基于聯(lián)邦濾波的智能車輛多傳感器組合導航的研究［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］李挺.車輛自主導航的廣域蛛式地圖與點狀路網(wǎng)跨層路徑規(guī)劃［D］.北京:清華大學，2008.

［5］王文璽，肖世德，孟祥印，等.模糊神經(jīng)網(wǎng)絡下基于強化學習的自主式地面車輛路徑規(guī)劃研究［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］李清泉，鄭年波，徐敬海，等.一種基于道路網(wǎng)絡層次拓撲結(jié)構(gòu)的分層路徑規(guī)劃算法［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］顏波.車載自主導航系統(tǒng)中的最優(yōu)路徑規(guī)劃［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］鄭煙武.基于分層分區(qū)的動態(tài)路徑規(guī)劃算法研究［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］張靜.面向路徑規(guī)劃的導航路網(wǎng)數(shù)據(jù)模型研究［D］.北京:中國礦業(yè)大學，2009.