胡繼華，黃 澤，鄧 俊，謝海瑩

(中山大學(xué)工學(xué)院智能交通中心，廣州 510006)

1 引 言

近幾年來，智能交通系統(tǒng)(ITS)快速發(fā)展，路徑規(guī)劃算法作為其中的一個關(guān)鍵技術(shù)，能夠有效地幫助司機(jī)規(guī)劃駕駛路線，避免擁堵、減少出行成本.目前，大部分車輛導(dǎo)航中的路徑規(guī)劃算法具有的一個共同特點是力求通過計算機(jī)數(shù)據(jù)結(jié)構(gòu)和運籌學(xué)方法，從理論上減少搜索算法的時間復(fù)雜度，而忽略了實際城市道路網(wǎng)絡(luò)中的道路一般都具有不同的等級，容量限制等特性，得到的是數(shù)學(xué)意義上的最短路徑，不能真正符合駕駛員的行車期望和要求.層次搜索策略則是結(jié)合了道路網(wǎng)絡(luò)的分層特性和經(jīng)典的最短路徑算法所提出的一種新型搜索策略，可以有效地提高搜索效率，更好地符合駕駛員的實際駕駛要求.因此，對于層次搜索策略的研究也得到了越來越多學(xué)者的關(guān)注.

層次搜索策略，在人工智能領(lǐng)域比較著名，也被稱為“抽象”問題解決策略.Plolya首次在道路網(wǎng)絡(luò)搜索中引入層次概念.此后，這個概念被Sacerdoti［1］，Korf［2］和許多其他研究人員［3-7］進(jìn)一步探索.國內(nèi)不少學(xué)者對此進(jìn)行了深入研究，利用層次搜索策略對路徑規(guī)劃算法進(jìn)行優(yōu)化［8-11］.在以往大部分研究中，是根據(jù)道路屬性對路網(wǎng)進(jìn)行分層，這樣的分層方式有兩方面不足:一是所得到的分層路網(wǎng)是靜態(tài)的，不能很好地反映實際的動態(tài)路況;二是沒有充分考慮駕駛員的駕駛期望.

近幾年，在國內(nèi)外的車輛導(dǎo)航研究中，出租車駕駛員經(jīng)驗的重要性逐漸凸顯出來，越來越多的研究學(xué)者們將其應(yīng)用到基于實時交通信息的動態(tài)導(dǎo)航中［12，13］.結(jié)合出租車駕駛員經(jīng)驗設(shè)計的路徑規(guī)劃算法，能夠根據(jù)歷史經(jīng)驗，避開發(fā)生擁堵概率高的路段，減少出行時間，計算得到的路徑可能不是最短路徑，但卻是最優(yōu)路徑.因此將出租車駕駛員路徑選擇經(jīng)驗融入到路徑規(guī)劃算法，可以為公眾出行提供一個更加合理、快捷的規(guī)劃路徑.

本文以廣州市為研究區(qū)域，利用匹配后的廣州市出租車浮動車數(shù)據(jù)，提取出廣州市出租車行駛軌跡，并根據(jù)各路段行駛頻率高低對路網(wǎng)進(jìn)行合理分層，構(gòu)建基于出租車經(jīng)驗路徑的分層路網(wǎng).結(jié)合經(jīng)典的Dijkstra算法，本文設(shè)計一種融合出租車駕駛經(jīng)驗的路徑規(guī)劃方法.最后，將本文提出方法計算得到的規(guī)劃路徑與經(jīng)典路徑規(guī)劃算法的結(jié)果作比較，從路徑長度，行程時間等方面進(jìn)行對比分析與驗證.

2 技術(shù)路線

出租汽車駕駛員選擇的路徑往往綜合考慮了擁堵程度、行程時間、道路等級、周邊環(huán)境及費用等多種因素.因此，本文結(jié)合出租車駕駛員經(jīng)驗和層次搜索策略，通過構(gòu)建經(jīng)驗等級路網(wǎng)的方法對最短路徑算法進(jìn)行優(yōu)化.

主要技術(shù)路線如下:

首先，對采集得到的出租車浮動車數(shù)據(jù)進(jìn)行預(yù)處理，在地圖匹配的基礎(chǔ)上，提取基于GPS數(shù)據(jù)的出租車行駛軌跡.

然后，通過速度閾值的方法從大量的出租汽車行駛軌跡中篩選出經(jīng)驗路徑，并且統(tǒng)計每條道路在限定時間內(nèi)通行的次數(shù)，根據(jù)次數(shù)的高低構(gòu)建經(jīng)驗道路等級路網(wǎng).

最后，在等級路網(wǎng)的基礎(chǔ)上，實現(xiàn)基于出租車經(jīng)驗路徑的層次路徑規(guī)劃算法.

技術(shù)流程如圖1所示.

圖1 技術(shù)流程Fig.1 Technical process

3 出租車經(jīng)驗路徑提取

出租車在空載和重載的時候其行為特點有較大的不同，因此，在地圖匹配的基礎(chǔ)上，本文對出租車的行駛軌跡進(jìn)行分割，分別為空載和重載時的軌跡.通過車輛狀態(tài)的轉(zhuǎn)變，將出租車的每一次載客或空載的行駛軌跡信息進(jìn)行分割，通過車輛狀態(tài)的切換得到出租車的行駛軌跡集，從而可以提取出租車的每一次載客或空載的軌跡.

圖2為出租車一次載客軌跡中序列，圖中粗線路段為軌跡序列.

圖2 出租車一次載客軌跡中的Seq序列Fig.2 Sequence of taxi trajectories

4 經(jīng)驗分層路網(wǎng)下的路徑規(guī)劃

4.1 經(jīng)驗軌跡集篩選

由于出租車在載客和空車時的駕駛行為有所不同，因而我們需要通過軌跡的平均行駛速度進(jìn)行篩選，將速度低于給定閾值的行駛軌跡排除在外.設(shè)vi為軌跡i的平均速度，vT為速度閾值，一般為所有載客路徑的平均速度.則符合經(jīng)驗路徑篩選條件的軌跡集如下式所示:

由于不同的時段，路段的交通狀況不同，出租車駕駛員對道路的選擇會不同，對出租車的出行需求也不同，因而有必要將符合經(jīng)驗路徑篩選條件的軌跡集限制在某個時間段內(nèi).設(shè)時間間隔為T，則有在時間區(qū)間T內(nèi)的經(jīng)驗軌跡集為

式中tis為軌跡的開始時間;tim為軌跡的結(jié)束時間.

4.2 基于經(jīng)驗軌跡的道路分層

城市道路一般分為快速路、主干道、次干道和支路四個等級，但是城市道路等級并不能完全反映實際交通狀況的等級.本文根據(jù)篩選得到的出租車行駛的經(jīng)驗軌跡集，對城市路網(wǎng)各時段出租車在各道路的出現(xiàn)次數(shù)進(jìn)行統(tǒng)計，作為城市道路經(jīng)驗分級的依據(jù)，實現(xiàn)對城市路網(wǎng)各道路的經(jīng)驗分級.設(shè)ni(t)為給定時間區(qū)間內(nèi)路段的出租車軌跡通行次數(shù)總和，則有

式中ni(t)，Ni為路段i在時間間隔T內(nèi)的經(jīng)驗軌跡集中的所有浮動車通過路段i的軌跡總和;m為出租汽車總數(shù);n為路段總數(shù).

ni(t)的值越大，說明出租車司機(jī)越偏向選擇路段i，反之亦然.通過將其值按高到低進(jìn)行排序?qū)Φ缆愤M(jìn)行分級.假設(shè)城市路網(wǎng)的所有路段被分成d個等級，gd為第d等級的最小滿足通過次數(shù)，Hd為屬于d等級的道路集，則有

4.3 算法實現(xiàn)

構(gòu)建好經(jīng)驗道路網(wǎng)絡(luò)之后，我們可以應(yīng)用分層路網(wǎng)的路徑規(guī)劃算法進(jìn)行路徑搜索.算法流程如下:

Step1如圖3(a)所示，如果起點S、D都在經(jīng)驗路網(wǎng)層，那么直接在經(jīng)驗路網(wǎng)層搜索最短路徑.

圖3 算法實現(xiàn)Fig.3 Implementation of algorithm

Step2如果起點S不在經(jīng)驗路網(wǎng)層，若設(shè)定的矩形區(qū)域R2中存在經(jīng)驗路網(wǎng)層道路，則在R2中以最短路徑算法搜索離S點最近的經(jīng)驗路網(wǎng)層入口S'，并且記錄S-S'，同理，在R2中范圍內(nèi)的基礎(chǔ)路網(wǎng)中搜索終點D的出口D'，并記錄D-D'，否則轉(zhuǎn)Step4.

Step3以S'，D'在經(jīng)驗路網(wǎng)層搜索最短路徑，并且拼接各段局部路徑得到完整的路徑.

Step4在R2范圍內(nèi)的基礎(chǔ)路網(wǎng)上用Dijkstra算法搜索最短路徑.

本文算法中，通過限定搜索區(qū)域的方法，確定是否需要尋找高層的出入口和在合適的范圍內(nèi)尋找高層的出入口.如圖3(b)所示，首先根據(jù)S和D的連線為對角線形成一個矩形R1，然后將R1的各邊向外擴(kuò)展一個閾值h，形成矩形R2，R2則為算法中用于判斷是否需要搜索經(jīng)驗路網(wǎng)層出入口以及搜索出入口時的范圍條件，算法中h的值取0.001度.算法流程圖如圖4所示.

圖4 算法流程Fig.4 Algorithm flow

5 實例計算與結(jié)果分析

5.1 數(shù)據(jù)基礎(chǔ)

本文選取廣州市交通道路電子地圖為基礎(chǔ)實驗數(shù)據(jù)，路段數(shù)為3 042，節(jié)點數(shù)為2 112.出租車GPS數(shù)據(jù)是廣州市1.7萬多輛出租車在2011年6月18至7月18一個月時間的GPS采樣點數(shù)據(jù)，經(jīng)過提取得到約2 900多萬條有效軌跡.由于路網(wǎng)規(guī)模不大，所以在本文中，將路網(wǎng)分為兩層，分別為高使用頻率路網(wǎng)層與低使用頻率路網(wǎng)層，實驗中計算路徑的行程時間需要的道路速度，是通過廣州市主干路網(wǎng)交通狀態(tài)分析與評價系統(tǒng)中的一個月的以5分鐘為間隔的道路平均速度在對應(yīng)的四個時段計算得到的平均速度.

實驗分析的圖表中，SP代表最短距離路徑算法，EHP代表基于經(jīng)驗道路分層路網(wǎng)的路徑規(guī)劃算法，RHP代表城市路網(wǎng)中以道路等級為5和6的道路形成的高等級路網(wǎng)的道路分層路徑規(guī)劃算法.三種算法均用于計算任意OD對間的最短路徑，因此，實驗中隨機(jī)生成了30個OD對，分別用以上三種算法計算其不同的路徑.

對于EHP算法，由于城市交通各路段在不同時段交通流量是在時刻變化的，出租車司機(jī)在平峰和高峰時段對于道路的選擇也會進(jìn)行相應(yīng)的調(diào)整，根據(jù)出租汽車的經(jīng)驗路徑構(gòu)成的道路等級劃分也會有所不同，因而對路網(wǎng)道路進(jìn)行經(jīng)驗分層時需要結(jié)合時間進(jìn)行考慮.本文根據(jù)廣州城市道路交通的特點與狀況，選取了4個具有代表性的時間段分別建立4個經(jīng)驗道路等級及路網(wǎng)，并且用EHP算法分別計算不同時段的路徑.具體的時間段劃分如表1所示.

表1 時段劃分表Table 1 Period division

5.2 不同時段經(jīng)驗路網(wǎng)

由于不同的時段，各道路的交通狀態(tài)會有所不同，因此經(jīng)驗軌跡集也根據(jù)不同的時段進(jìn)行提取，圖5為未經(jīng)分層處理的廣州路網(wǎng)圖，圖中(a)(b)(c)(d)分別為圖中方框部分在不同時段經(jīng)過分層處理的經(jīng)驗等級道路圖，圖中黑色粗線的路段為高使用頻率道路，即被劃分為經(jīng)驗等級道路.從圖中可以看出，盡管4個時間的道路層次分布圖比較類似，但是還是較為細(xì)微的差別，這說明，不同的時間段出租車司機(jī)對道路的選擇還是有區(qū)別的.

圖5 不同時段的經(jīng)驗等級道路圖Fig.5 Experiential road hierarchy for four time intervals

5.3 路徑長度比較

圖6顯示的是四種算法得到的路徑的長度比較，柱體的高度代表的是路徑的長度，右手邊的垂直軸代表的是RHP，EHP，SP三種算法與最短路徑算法的長度之比.在此，本文選取了時間段7:00-9:00和12:00-14:00以作說明.從圖6中可以看出，RHP算法的路徑長度與SP算法的路徑長度的比值幅度變化大，尤其是路徑較短時，更為明顯.RHP算法由于趨向于走高等級道路，因此容易出現(xiàn)繞路的情況，即使OD之間的距離很近，也會選擇走高等級道路，EP算法得到的路徑長度與SP算法的路徑長度之比相對平穩(wěn).

圖7為三種算法下的30個OD對的路徑總長在各個時段的對比圖，總體來看SP算法的路徑總長最短，RHP算法的路徑總長最長，而EHP算法的路徑則處于兩者之間.

5.4 行程時間比較

圖8顯示的是四種算法得到的路徑的行程時間比較，柱體的高度代表的是行程時間，右手邊的垂直軸代表的是RHP，EHP，SP三種算法的行程時間之比.在此，本文選取了時間段7:00-9:00和12:00-14:00以作說明.對于EHP算法而言，算法的結(jié)果在大約只有75%左右的結(jié)果小于或等于SP算法的結(jié)果，而RHP得到的結(jié)果只有66%左右的OD對的行程時間等于或小于SP算法得到的行程時間.與EHP算法得到的路徑的行程時間相對于路徑長度最短SP算法的行程時間的比值而言，ratio(RHP/SP)的值不穩(wěn)定性較大，在路徑長度較短時波動較大.

圖9表明在行程時間總體上EHP算法最短，接著為RHP，SP算法的行程時間總和最長.但是RHP與SP的相差不大.

圖9 三種算法30個OD對的行程時間總和對比圖Fig.9 Total travel time comparison for three algorithms

6 研究結(jié)論

本文針對出租車GPS數(shù)據(jù)的特點，提取出租車行駛軌跡.結(jié)合出租車行駛軌跡對不同時段下的出租車在各個路段的通過頻次進(jìn)行統(tǒng)計，提取了基于出租車駕駛員經(jīng)驗選擇的等級路網(wǎng)，在此基礎(chǔ)上提出融合出租車駕駛經(jīng)驗的層次路徑規(guī)劃方法.相比于經(jīng)典的最短路徑規(guī)劃算法，該方法具有兩方面的優(yōu)勢:一是利用了層次搜索策略，在分層路網(wǎng)的基礎(chǔ)上進(jìn)行遍歷，大大減少了計算量;二是融合了駕駛員經(jīng)驗，所得到的分層路網(wǎng)是動態(tài)路網(wǎng)，能夠反映實時路況，使規(guī)劃結(jié)果更加合理.

最后，本文以廣州市路網(wǎng)為計算實例，隨機(jī)生成30個OD對，從行程時間和路徑長度兩個方面與傳統(tǒng)以長度為準(zhǔn)的最短路徑算法及自然道路分層的路徑規(guī)劃算法進(jìn)行了對比與分析.結(jié)果顯示，相比于其他兩種路徑規(guī)劃算法的計算結(jié)果，使用本文所提出的方法得到的路徑要更加優(yōu)越，行程時間較短，并且可根據(jù)不同的時段進(jìn)行動態(tài)調(diào)整.

［1］Sacerdoti E D.Planning in a hierarchy of abstraction spaces［J］.Artificial Intelligence，1974，5(2):115-135.

［2］Korf R E.Planning as search:A quantitative approach［J］.Artificial Intelligence，1987，33(1):65-88.

［3］Jung S，Pramanik S.An efficient path computation model for hierarchically structured topographical road maps［J］.Knowledge and Data Engineering，IEEE Transactions on，2002，14(5):1029-1046.

［4］Jagadeesh G，Srikanthan T，Quek K.Heuristic techniques for accelerating hierarchical routing on road networks［J］. Intelligent Transportation Systems， IEEE Transactions on，2002，3(4):301-309.

［5］Chou Y L，Romeijn H E，Smith R L.Approximating shortest paths in large-scale networks with an application to intelligent transportation systems［J］.INFORMS Journal on Computing，1998，10(2):163-179.

［6］Liu B.Route finding by using knowledge about the road network［J］.Systems，Man and Cybernetics，Part A:Systems and Humans， IEEE Transactions on，1997，27(4):436-448.

［7］Car A，F(xiàn)rank A.General principles of hierarchical spatial reasoning:the case of wayfinding［C］.1994:646-664.

［8］翁敏，毋河海，杜清運，等.基于道路網(wǎng)絡(luò)知識的啟發(fā)式層次路徑尋找算法［J］.武漢大學(xué)學(xué)報:信息科學(xué)版，2006，31(004):360-363.［WENG M，WU H H，DU Q Y，et al.A heuristic and hierarchical wayfinding algorithm based on the knowledge of road network［J］.Geomatics and Information Science of Wuhan University.2006.31(004):360-363.］

［9］高松，陸鋒.一種基于路網(wǎng)等級啟發(fā)式策略的路徑搜索算法［J］.地球信息科學(xué)學(xué)報，2009，11(2):151-156.［GAO S，LU F.A path finding heuristic algorithm for a road network hierarchy［J］.Geo-Information Science，2009，11(2):151-156.］

［10］武雪玲，李清泉，任福.基于分層分塊數(shù)據(jù)組織的雙向A*算法［J］.測繪信息與工程，2006，31(6):1-2.［WU X L，LI Q Q，REN F.Bidirectional A*algorithm based on hierarchicaland block data organization［J］.Journal of Geomatics，2006，31(6):1-2.］

［11］鐘慧玲，章夢，石永強(qiáng)，等.基于路網(wǎng)分層策略的高效路徑規(guī)劃算法［J］.西南交通大學(xué)學(xué)報，2011，46(4):645-650.［ZHONG H L，ZHANG M，SHI Y Q，et al.Efficient route plan algorithm based on multi-level road network strategy［J］. JournalofSouthwest Jiaotong University，2011，46(4):645-650.］

［12］唐爐亮，常曉猛，李清泉.出租車經(jīng)驗知識建模與路徑規(guī)劃算法［J］.測繪學(xué)報，2010，39(4):404-409.［TANG L L，CHANG X M，LI Q Q.The knowledge modeling and route planning based on taxi'experience［J］.Acta Geodaetica et Cartographica Sinica，2010，39(4):404-409.］

［13］楊揚.基于實時交通信息的最優(yōu)路徑規(guī)劃問題的研究［D］.上海交通大學(xué)，2009.［YANG Y.Optimal path planning problem under real-time traffic network［D］.Shanghai Jiao Tong University，2009.］