[發明專利]一種基于考慮城市交叉口時間延誤的實用路徑選擇方法

無效

• 申請號: 201410578490.3
• 申請日: 2014-10-24
• 公開（公告）號: CN104318794A
• 公開（公告）日: 2015-01-28
• 發明（設計）人: 張望;王慧
• 申請（專利權）人: 浙江大學
• 主分類號: G08G1/09
• 分類號: G08G1/09
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 杜軍

技術領域

本發明屬于交通工程領域，涉及一種基于考慮城市交叉口時間延誤的實用路徑選擇方法。

背景技術

為出行車輛提供路徑選擇是城市交通系統研究的重要組成部分。由于交叉口處信號控制及擁堵造成的排隊現象等原因，車輛行駛至交叉口處時將不可避免地產生時間延誤。對于車輛出行的整個行程時間而言，交叉口時間延誤的比重不可忽略。因此，在進行路徑選擇時，將交叉口時間延誤作為考慮因素之一是十分有必要的。此外，城市交通路網是一個動態變化的復雜系統，交通流參數是實時變化的，路徑選擇需要依據實時路況信息作出判斷，有選擇性地重新選擇路線。

目前，國內外對于路徑選擇算法的研究已較為成熟，但大多停留在理論階段，當結合到實際路網中時，這些算法需要進行一些改進才能進行應用。

發明內容

本發明的目的是針對現有技術的不足，提供一種基于考慮城市交叉口時間延誤的實用路徑選擇方法。

該方法包括以下步驟：

步驟(1).對待測實地區域采集路網數據，利用其生成路網,并用有向賦權網絡G＝(V,A,D,C)表示該路網；

其中V＝{v_i|i＝1,2,…,n}為網絡G＝(V,A,D,C)中的節點集合，表示城市道路交叉口；A＝{a_ij|i,j＝1,2,…,n}為網絡G＝(V,A,D,C)中的弧集合，表示城市道路相鄰交叉口之間的有向路段；C＝{c_ij|i,j＝1,2,…,n}為網絡G＝(V,A,D,C)中的弧權集合，c_ij表示車輛在弧a_ij上平均路段行程時間；D＝{d_ijk|i,j,k＝1,2,…,n}為網絡G＝(V,A,D,C)中的點權集合，d_ijk表示弧a_ij轉向弧a_jk時在節點v_j處產生的平均轉向延誤時間；

所述的路網數據包括交叉口地理坐標、相鄰交叉口間平均路段行程時間以及交叉口平均轉向延誤時間；

步驟(2).設定最優路徑的起點和終點，根據當前路網數據，調用改進啟發式A^*算法計算得到最優路徑,具體步驟如2.1～2.5：

所述的最優路徑起點為節點v_o，終點為節點v_d；最優路徑由多條首尾相連的弧a_ij構成，其中弧a_ij上的節點v_i和節點v_j分別為該弧的尾節點和頭節點；

2.1考察終點節點v_d的所有入弧，建立目標弧集T；目標弧集T存放以終點V_d為頭節點的所有入弧，初始化T_OPEN＝T,

2.2初始化估價值f_ij，令f_ij＝M，M為無窮大正數；

所述的估價值f_ij表示在弧a_ij上產生的起點v_o至終點v_d的估計行程時間；

2.3在起點v_o前添加虛擬節點v_o′，則弧a_o′o是一條虛擬弧，根據公式f_o′o＝g_o′o+h_o′o，g_o′o＝0，故f_o′o＝h_o′o,p_o′o＝NULL，將弧a_o′o移入OPEN表中；其中對于弧a_ij∈A而言，p_ij為起點V_o至弧a_ij頭節點v_j的最短路徑上弧a_ij緊前弧的尾節點的標號；

2.4判斷OPEN表是否為非空，若是則執行以下操作步驟2.4.1～2.4.4，若否則執行步驟2.5：

2.4.1對于OPEN表中的所有弧，選取最小f_ij值對應的弧，記為ars；將a_rs從OPEN表中刪除，并將a_rs插入到CLOSE表中；判斷弧a_rs是否在T_OPEN表中，若是則執行步驟2.4.2，若否則執行步驟2.4.3；