指引路徑規劃模型的建模與仿真驗證

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

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

0 引 言

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

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

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

1 問題描述

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

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

1.1 路網表示

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

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

1.2 目標函數

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

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

圖1 路網柵格化處理示例Fig.1 Example of rasterized network

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

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

2 模型構建

2.1 A＊算法

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

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

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

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

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

2.2 懲罰系數

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

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

2.3 節點信息

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

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

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

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

2.4 算法流程

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

3 仿真驗證

(1)仿真分析.

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

通過COM 接口獲取實驗路網內路段及節點信息，得到起點O距終點D的直線距離V、路段平均長度l、節點ni數量、路段aij數量，如表1所示.

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

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

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

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

圖3 實驗路網結構圖Fig.3 Structure diagram of road network for experiment

表1 實驗路網靜態數據Table 1 Static data of experimental road network

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

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

(2)統計對比分析.

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

表3 VISSIM 參數調整說明Table 3 Instructions of VISSIM parameters adjustment

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

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

4 結 論

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

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