趙 琦，曾 燁，張立立，王 力

(1.北方工業(yè)大學城市交通智能控制技術(shù)北京市重點實驗室，北京100144；2.北京石油化工學院信息工程學院，北京102617)

0 引 言

在城市道路交通系統(tǒng)中，指路標志是道路信息的重要載體，幫助機動車駕駛員方便快捷地抵達目的地[1].合理地規(guī)劃指路標志的布設(shè)位置不僅能正確引導駕駛員駕駛車輛，同時也是提升城市交通系統(tǒng)運行效率，改善路網(wǎng)交通流狀態(tài)的必要手段.

學者就指路標志的布設(shè)方法進行了很多研究.肖國榮[2]基于各個OD(Origin-destination，交通出行的發(fā)生點和吸引點)對間出行者偏離最優(yōu)路徑的概率，提出一種定量評價指路標志規(guī)劃方案合理性的方法，得到出行者偏離最優(yōu)路徑概率最小的指路標志布設(shè)方案.郭敏[3]基于樹狀圖模型，建立了一種宏觀的路網(wǎng)指路信息分配模型，指導城市復雜路網(wǎng)指路標志系統(tǒng)的整體規(guī)劃，但未涉及具體路徑指路標志的布設(shè)研究.黃敏[4]運用雙圈覆蓋法定義路網(wǎng)中的兩種等級區(qū)域，基于Dijkstra算法對路網(wǎng)中的重要興趣點(Point of Interest,POI)進行指引路徑規(guī)劃，保證指路信息的連續(xù)性，但不能避免指引路徑中特定節(jié)點出現(xiàn)指路信息過載問題.有學者為提高指引路徑規(guī)劃模型的運行效率，采取啟發(fā)式算法對現(xiàn)有規(guī)劃模型進行改進.Zheng Jian[5]通過對比遺傳算法和人工蜂群算法在指引路徑規(guī)劃中的應用，驗證了人工蜂群算法在優(yōu)化過程中具有更高的收斂速度.張騰[6]改進了人工蜂群算法的搜索策略，建立指引路徑優(yōu)化模型，優(yōu)化同一路網(wǎng)中的多條指引路徑，但同樣未對指路信息過載問題進行研究.

現(xiàn)有研究大都忽略了路網(wǎng)特定節(jié)點發(fā)生指路信息過載問題，而該問題使駕駛員無法及時、有效地獲取道路信息，帶來不必要的安全隱患及尋路成本.因此，為有效避免指引路徑中特定節(jié)點產(chǎn)生信息過載問題，優(yōu)化指引路徑的規(guī)劃方案，本文將信息過載問題視為指引路徑規(guī)劃的重要影響因素，基于A*算法提出一種含有懲罰系數(shù)的指引路徑規(guī)劃模型.

1 問題描述

興趣點是路網(wǎng)中重要的地理位置信息，包括人們出行密切相關(guān)的地理實體，例如學校、商場等.2015年批準實施的中國《城市道路交通標志和標線設(shè)置規(guī)范》規(guī)定：根據(jù)指引地點的交通重要程度，宜在指引地點周邊的1～3個交叉口處增設(shè)地點信息.然而，一旦某區(qū)域重要興趣點比較集中，指路標志又沒有得到正確設(shè)置，容易引發(fā)該區(qū)域內(nèi)特定節(jié)點(受附近重要興趣點影響，需要增設(shè)過多指路信息的交叉口指路標志的設(shè)置位置)指路信息過載問題.

通過對指引路徑規(guī)劃方法進行研究，能夠有效解決上述問題.指引路徑是由路網(wǎng)道路及指路信息構(gòu)成的路徑，其中，指路信息是指路標志承載的特定信息，一般為區(qū)域內(nèi)主要OD 對服務(wù)，可以向位于起點的駕駛員傳遞其所需的、與終點相關(guān)的地點信息，協(xié)助駕駛員對行駛路線進行規(guī)劃.指引路徑規(guī)劃可視為基于路網(wǎng)拓撲結(jié)構(gòu)，從指定起點出發(fā)，綜合考慮指路標志布設(shè)成本，駕駛員尋路成本等重要因素，求解路網(wǎng)中實際成本最低，對指定終點可達性強的有向路段的集合.因此，路網(wǎng)拓撲結(jié)構(gòu)、指路標志、興趣點三者之間相互影響.

1.1 路網(wǎng)表示

為直觀展示路網(wǎng)拓撲結(jié)構(gòu)，本文基于圖論，用節(jié)點—弧段表示路網(wǎng)結(jié)構(gòu)[7].G表示區(qū)域路網(wǎng)，G={N,A}；N為路網(wǎng)G的節(jié)點集合，N={ni}，ni為節(jié)點；A為路網(wǎng)G的路段集合，A={aij=(ni,nj)}，aij表示起點為ni，終點為nj的路段；P表示路網(wǎng)中重要興趣點集合，P={pi}；R(ni,pi)表示從節(jié)點ni至興趣點pi的指引路徑，R(ni,pi)={aij,ajk,…,aopi} 表示指引路徑的路段集合，i、j、k、o分別為節(jié)點ni、nj、nk、no，pi為興趣點.

為利用路網(wǎng)拓撲結(jié)構(gòu)進行指引路徑規(guī)劃，對真實路網(wǎng)進行柵格化處理，如圖1所示.圖1(a)表示一個G0={N0,A0} 的簡單路網(wǎng)環(huán)境，N0為節(jié)點集合，N0={n1,n2,n3,n4,n5}，A0為弧段集合，A0={a12,a23,a24,a25}，在節(jié)點n2處需設(shè)置指路標志.圖1(b)是經(jīng)過處理的簡單路網(wǎng)示意圖，節(jié)點N0的坐標值由節(jié)點所在柵格坐標決定，弧段A0的長度由對應節(jié)點間的距離決定.

1.2 目標函數(shù)

影響指引路徑成本W(wǎng)的關(guān)鍵因素包括指引路徑長度和指路標志數(shù)量[7]，故綜合考慮這兩種成本，即W(L)和W(S)，求解最小成本的指引路徑.由于路徑長度L和指路標志數(shù)量S的量綱不一致，采用min-max標準化對兩種成本進行歸一化處理[4].

式中：W(L)為指引路徑R(O,D)的路徑長度成本函數(shù)；O為路徑起點；D為路徑終點；L[R(O,D)]為指引路徑R(O,D)的路段總長度；W(S)為指引路徑R(O,D)上指路標志數(shù)量成本函數(shù)；S[R(O,D)]為指引路徑R(O,D)中指路標志總數(shù)量.

圖1 路網(wǎng)柵格化處理示例Fig.1 Example of rasterized network

參考文獻[8]，假設(shè)起點O至終點D的直線距離為V，則max(L) 的值為2V；假設(shè)路網(wǎng)中路段平均長度為l，則max(S) 的值為2V/l.指引路徑總成本W(wǎng)表示為

式中：α，β分別為W(L)、W(S)在W中所占權(quán)重.參考文獻[8]，將α、β分別取0.5，即認為指路標志數(shù)量和指引路徑長度對目標成本函數(shù)的影響相同.

2 模型構(gòu)建

2.1 A＊算法

A*算法是由Hart[9]提出的一種啟發(fā)式搜索算法.該算法在Dijkstra 算法的基礎(chǔ)上，加入計算從當前節(jié)點到終點成本估計值的啟發(fā)函數(shù)h(i)，具備更高的搜索效率和靈活性[10].A*算法的主函數(shù)——估價函數(shù)f(i)為

式中：g(i)為指引路徑起點O至節(jié)點ni所花費的成本，為當前成本；啟發(fā)函數(shù)h(i)為節(jié)點ni到終點D的指引路徑估算成本.當h(i)值不大于節(jié)點ni到終點D的實際成本值時，算法不會遺漏最優(yōu)指引路徑的解.

參照式(3)，建立指引路徑規(guī)劃模型的估價函數(shù)f(i) 為

根據(jù)研究問題的不同，A*算法一般使用曼哈頓距離、歐幾里得距離或切比雪夫距離建立啟發(fā)函數(shù)h(i)[11].為確保h(i)小于節(jié)點ni至終點D的實際成本，且車輛在城市道路中一般朝4個方向移動，本文選取曼哈頓距離構(gòu)建啟發(fā)函數(shù)h(i)[12]為

式中：Dx，Dy分別為終點D的橫、縱坐標；ix，iy分別為當前節(jié)點ni的橫、縱坐標.

2.2 懲罰系數(shù)

從f(i) 的組成來看，指引路徑長度越短，路徑上指路標志越少時，路徑成本W(wǎng)越低.現(xiàn)有研究表明，指路標志版面承載的指路信息超過5 條時，會給駕駛員帶來過高的信息負荷，使其不能及時地處理指路信息，錯失尋路時機[13].因此，對指引路徑進行規(guī)劃時，應當避開可能產(chǎn)生指引信息過載的特定節(jié)點，優(yōu)化指引路徑方案.故迫使算法改變當前搜索方向，放棄訪問指路信息過載的節(jié)點，在原算法中增加對尋路成本f(i)的懲罰系數(shù)M，原尋路成本函數(shù)演變?yōu)?/p>

式中：k為節(jié)點指路信息過載的指示參數(shù)，當節(jié)點指路信息過載時，k值為1，否則為0；λ為懲罰參數(shù)，當λ取值足夠大時，若節(jié)點ni存在指路信息過載問題，其尋路成本f(i) 的值會突增，算法隨即放棄訪問節(jié)點ni.為確保模型最終輸出的指引路徑中不存在指路信息過載的問題，將λ取值為10.

2.3 節(jié)點信息

為獲取有向路段集合R(O,D)的尋路成本f(i)、當前成本g(i)和估算成本h(i)的值，模型需要遍歷路網(wǎng)中各個節(jié)點，并讀取節(jié)點存儲的成本值.路段aij的當前成本g(aij)，估算成本h(aij)，估價函數(shù)f(aij)分別為

式中：L(aij)為路段aij的長度；S(aij)為路段aij交叉口處增設(shè)的指路標志數(shù)量，值為1；pix、piy分別為興趣點pi的橫縱坐標；jx、jy分別為節(jié)點nj的橫縱坐標.根據(jù)《城市道路交通標志和標線設(shè)置規(guī)范》中關(guān)于地點識別標志的規(guī)定(需要在重要興趣點周邊1～3 個交叉口處設(shè)置指路信息)，假設(shè)興趣點pi與交叉口節(jié)點nj的距離dpi j滿足式(13)時，在節(jié)點nj處相應地增設(shè)一條地點指路信息.

交叉口指路標志一般包含3條道路信息，交叉口需要同時增設(shè)終點的地點信息，故某個交叉口節(jié)點ni增設(shè)了3條及以上指路信息時，該節(jié)點的k值為1，否則k值為0.

設(shè)定節(jié)點信息后，需要對路網(wǎng)進行柵格化處理.將有向路段aij分成m個柵格，每個柵格的單位長度保持一致，同時將路段aij的成本分配至各個柵格上，除交叉口節(jié)點ni外，交叉口節(jié)點nj成本為wj，其余柵格成本均為wij.

2.4 算法流程

指引路徑規(guī)劃算法基于VB6.0平臺實現(xiàn)，算法搜索從起點O開始，根據(jù)f(i)值確定搜索方向，直至搜索到終點D.算法流程如圖2所示.

3 仿真驗證

(1)仿真分析.

本文利用VB6.0 對VISSIM 實驗路網(wǎng)進行二次開發(fā)，以展示指引路徑規(guī)劃模型的應用過程，實驗路網(wǎng)如圖3所示.路徑起點O為路網(wǎng)中高架路的出口匝道，路徑終點D為某重要興趣點的入口處.

通過COM 接口獲取實驗路網(wǎng)內(nèi)路段及節(jié)點信息，得到起點O距終點D的直線距離V、路段平均長度l、節(jié)點ni數(shù)量、路段aij數(shù)量，如表1所示.

利用不含懲罰系數(shù)和本文提出的帶懲罰系數(shù)的指引路徑規(guī)劃模型，對實驗路網(wǎng)中指定的OD對求解最優(yōu)指引路徑，分別得到指引路徑規(guī)劃方案1、方案2，如圖4所示.

分析兩種指引路徑方案及VISSIM仿真結(jié)果，得到兩種模型輸出路徑規(guī)劃方案的對比情況，如表2所示.其中，行程時間t為自由流情況下，車輛從起點O至終點D所耗費的時間，指引路徑的目標成本W(wǎng)為

依據(jù)上述實驗結(jié)果發(fā)現(xiàn)：在指引路徑規(guī)劃模型中引入懲罰系數(shù)M后，車輛行程時間t下降1.93%，指引路徑長度L減少289 m，同時避免了節(jié)點發(fā)生指路信息過載問題；但方案2需布設(shè)的指路標志比方案1增加1塊，指引路徑的目標成本值W上升2.65%.

圖2 指引路徑規(guī)劃算法流程圖Fig.2 Flowchart of guiding path planning

圖3 實驗路網(wǎng)結(jié)構(gòu)圖Fig.3 Structure diagram of road network for experiment

表1 實驗路網(wǎng)靜態(tài)數(shù)據(jù)Table 1 Static data of experimental road network

圖4 指引路徑規(guī)劃方案Fig.4 Guiding path planning scheme

表2 兩種模型的運行結(jié)果對比Table 2 Comparison of results between two models

(2)統(tǒng)計對比分析.

為驗證兩種模型得到的指引路徑規(guī)劃方案是否具有顯著性區(qū)別，調(diào)整VISSIM 仿真中5 項關(guān)鍵參數(shù)值，進行100 次對照實驗，各參數(shù)屬性如表3所示.

表3 VISSIM 參數(shù)調(diào)整說明Table 3 Instructions of VISSIM parameters adjustment

利用SPSS 軟件，進行配對T 檢驗分析實驗結(jié)果，得到兩種方案的行程時間相關(guān)系數(shù)為0.962，sig 值為0.04，這說明兩方案之間存在很高的相關(guān)性和顯著性區(qū)別.

由此可以得出，基于A*算法提出的指引路徑規(guī)劃模型在引入懲罰系數(shù)后，能夠獲取最優(yōu)指引路徑規(guī)劃方案.雖然該方案的指引路徑成本值W略大，但能夠有效解決特定節(jié)點指路信息過載問題.

4 結(jié) 論

本文在傳統(tǒng)A*算法基礎(chǔ)上，在估價函數(shù)中引入懲罰系數(shù)，構(gòu)建一種新的指引路徑規(guī)劃模型.該模型考慮到指路信息過載問題對指引路徑實際成本的影響，改善指引路徑的規(guī)劃方法.通過仿真驗證結(jié)果可知，基于本文建立模型得到的指引路徑規(guī)劃方案的路徑成本雖略高于最低成本，但是能夠有效避免指引路徑上特定節(jié)點出現(xiàn)指路信息過載問題.這將為解決目前指路標志布設(shè)規(guī)劃中存在部分節(jié)點指路信息過載問題提供方法依據(jù).

本文所建立的模型只考慮了單個OD 對之間的指引路徑規(guī)劃，而現(xiàn)實中面臨的是多個OD對之間的指路標志指引路徑的優(yōu)化問題.后續(xù)將在本文提出模型的基礎(chǔ)上，針對這一問題展開研究.此外，未來還將利用駕駛模擬器及真實駕駛場景實驗來驗證模型的有效性.