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

清華大學(xué)汽車安全與節(jié)能國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京，100084

0 引言

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

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

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

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

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

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

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

式中，i為路段等級(jí);e(i)為路網(wǎng)中等級(jí)為i的路段集合;N為路網(wǎng)級(jí)別總數(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)做為一個(gè)街區(qū)(街區(qū)內(nèi)部道路等級(jí)較低，周邊道路等級(jí)較高)，本文利用路網(wǎng)的街區(qū)特性，將第i層路網(wǎng)中形成的最小封閉區(qū)域作為第i－1層路網(wǎng)中的“塊”。路徑規(guī)劃升級(jí)過(guò)程中，總是由低級(jí)路網(wǎng)的邊界升級(jí)到高級(jí)路網(wǎng)，其在低層路網(wǎng)中的拓展過(guò)程恰好就是街區(qū)內(nèi)部區(qū)域的拓展，拓展范圍與街區(qū)分塊方法一致。另外因?yàn)椤皦K”以高等級(jí)路網(wǎng)做邊界，因此與按照經(jīng)緯度進(jìn)行物理分塊相比，這種分塊方法不會(huì)破壞實(shí)際道路的拓?fù)浣Y(jié)構(gòu)，并且由于單位塊中道路數(shù)量分布均勻，路徑規(guī)劃中讀取的數(shù)據(jù)在路徑拓展中能得到較好使用，因此在數(shù)據(jù)使用過(guò)程中該分塊方法數(shù)據(jù)利用效率高。

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

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

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

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

2 路徑規(guī)劃

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

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

式中，A為起點(diǎn)s的面積拓展范圍;B為起點(diǎn)s的塊拓展范圍。

面積拓展范圍A表示為

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

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

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

圖3 點(diǎn)的拓展范圍影響因素

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

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

由距離確定的拓展等級(jí)hs如下:

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

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

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

2.2 節(jié)點(diǎn)拓展

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

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

節(jié)點(diǎn)顏色uc的表達(dá)式為

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

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

已有代價(jià)ug的計(jì)算式為

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

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

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

啟發(fā)代價(jià)uh為節(jié)點(diǎn)u到達(dá)終點(diǎn)t的預(yù)估代價(jià)，其計(jì)算公式為

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

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

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

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

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

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

2.3 最優(yōu)路生成

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

圖5 節(jié)點(diǎn)的升級(jí)拓展

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

路網(wǎng)拓展結(jié)束后，會(huì)得到一顆拓?fù)錁洌瑢?duì)拓?fù)錁溥M(jìn)行回溯，就會(huì)得到最優(yōu)路路徑節(jié)點(diǎn)的序列。節(jié)點(diǎn)回溯如圖6所示。

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

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

圖7 最優(yōu)拓?fù)渎窂?/p>

3 試驗(yàn)驗(yàn)證

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

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

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

本文提出了一種基于街區(qū)的路網(wǎng)分塊方法，該方法利用路網(wǎng)的分布特性，自適應(yīng)調(diào)整路網(wǎng)分塊中數(shù)據(jù)的大小，在保持路網(wǎng)拓?fù)浣Y(jié)構(gòu)的情況下提高了路網(wǎng)數(shù)據(jù)的讀取效率;路網(wǎng)分層使規(guī)劃在高層稀疏路網(wǎng)中拓展，從而減少路徑規(guī)劃拓展節(jié)點(diǎn)的數(shù)量，在距離較遠(yuǎn)的路徑規(guī)劃中分層路網(wǎng)對(duì)速度提高更明顯，分塊分層的路徑規(guī)劃算法可以應(yīng)用于大規(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］王檀彬，陳無(wú)畏，焦俊，等.多傳感器融合的智能車輛導(dǎo)航研究［J］.中國(guó)機(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)邦濾波的智能車輛多傳感器組合導(dǎo)航的研究［J］.中國(guó)機(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ǎo)航的廣域蛛式地圖與點(diǎn)狀路網(wǎng)跨層路徑規(guī)劃［D］.北京:清華大學(xué)，2008.

［5］王文璽，肖世德，孟祥印，等.模糊神經(jīng)網(wǎng)絡(luò)下基于強(qiáng)化學(xué)習(xí)的自主式地面車輛路徑規(guī)劃研究［J］.中國(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)絡(luò)層次拓?fù)浣Y(jié)構(gòu)的分層路徑規(guī)劃算法［J］.中國(guó)圖象圖形學(xué)報(bào)，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ǎo)航系統(tǒng)中的最優(yōu)路徑規(guī)劃［D］.北京:清華大學(xué)，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ū)的動(dòng)態(tài)路徑規(guī)劃算法研究［D］.廣州:華南理工大學(xué)，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ī)劃的導(dǎo)航路網(wǎng)數(shù)據(jù)模型研究［D］.北京:中國(guó)礦業(yè)大學(xué)，2009.