融合出租車駕駛經(jīng)驗(yàn)的層次路徑規(guī)劃方法

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

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

1 引 言

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

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

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

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

2 技術(shù)路線

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.3 算法實(shí)現(xiàn)

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

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

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

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

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

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

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

圖4 算法流程Fig.4 Algorithm flow

5 實(shí)例計(jì)算與結(jié)果分析

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

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

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

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

表1 時(shí)段劃分表Table 1 Period division

5.2 不同時(shí)段經(jīng)驗(yàn)路網(wǎng)

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

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

5.3 路徑長(zhǎng)度比較

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

圖7為三種算法下的30個(gè)OD對(duì)的路徑總長(zhǎng)在各個(gè)時(shí)段的對(duì)比圖，總體來(lái)看SP算法的路徑總長(zhǎng)最短，RHP算法的路徑總長(zhǎng)最長(zhǎng)，而EHP算法的路徑則處于兩者之間.

5.4 行程時(shí)間比較

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

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

圖9 三種算法30個(gè)OD對(duì)的行程時(shí)間總和對(duì)比圖Fig.9 Total travel time comparison for three algorithms

6 研究結(jié)論

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

最后，本文以廣州市路網(wǎng)為計(jì)算實(shí)例，隨機(jī)生成30個(gè)OD對(duì)，從行程時(shí)間和路徑長(zhǎng)度兩個(gè)方面與傳統(tǒng)以長(zhǎng)度為準(zhǔn)的最短路徑算法及自然道路分層的路徑規(guī)劃算法進(jìn)行了對(duì)比與分析.結(jié)果顯示，相比于其他兩種路徑規(guī)劃算法的計(jì)算結(jié)果，使用本文所提出的方法得到的路徑要更加優(yōu)越，行程時(shí)間較短，并且可根據(jù)不同的時(shí)段進(jìn)行動(dòng)態(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］翁敏，毋河海，杜清運(yùn)，等.基于道路網(wǎng)絡(luò)知識(shí)的啟發(fā)式層次路徑尋找算法［J］.武漢大學(xué)學(xué)報(bào):信息科學(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)等級(jí)啟發(fā)式策略的路徑搜索算法［J］.地球信息科學(xué)學(xué)報(bào)，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］.測(cè)繪信息與工程，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］鐘慧玲，章夢(mèng)，石永強(qiáng)，等.基于路網(wǎng)分層策略的高效路徑規(guī)劃算法［J］.西南交通大學(xué)學(xué)報(bào)，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)驗(yàn)知識(shí)建模與路徑規(guī)劃算法［J］.測(cè)繪學(xué)報(bào)，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áng).基于實(shí)時(shí)交通信息的最優(yōu)路徑規(guī)劃問(wèn)題的研究［D］.上海交通大學(xué)，2009.［YANG Y.Optimal path planning problem under real-time traffic network［D］.Shanghai Jiao Tong University，2009.］