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

無效

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

1.一種基于考慮城市交叉口時間延誤的實用路徑選擇方法，其特征在于該方法包括以下步驟：

步驟(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^*算法計算得到最優路徑：

所述的最優路徑起點為節點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值對應的弧，記為a_rs；將a_rs從OPEN表中刪除，并將a_rs插入到CLOSE表中；判斷弧a_rs是否在T_OPEN表中，若是則執行步驟2.4.2，若否則執行步驟2.4.3；

2.4.2若弧a_rs在T_OPEN表中，則將其從T_OPEN表中刪除，并將a_rs插入到T_CLOSE表中；然后判斷是否若是則執行步驟2.5，若否則跳轉執行步驟2.4；

2.4.3若弧a_rs不在T_OPEN表中，判斷弧a_rs的頭節點v_s的所有出弧a_st是否都在CLOSE表中，若是則執行步驟2.4，若否則對不在CLOSE表中的出弧進行考察；然后判斷是否成立f_st＞g_rs+d_rst+c_st+h_st，若是則重新賦予f_st＝g_rs+d_rst+c_st+h_st，p_st＝r后執行步驟2.4.4，若否則直接執行步驟2.4.4；

2.4.4判斷弧a_st是否在OPEN表中，若不在則將該弧移入OPEN表后跳轉執行步驟2.4；若在則直接跳轉執行步驟2.4；

2.5根據T_CLOSE表中各弧緊前弧的尾節點標號p_ij，回溯得起點v_o至該弧頭節點的最短路徑；比較終點v_d各入弧的估計值f_ij，取最小估計值對應的終點v_d入弧；該入弧頭節點所對應的最短路徑即為起點v_o至終點v_d的最優路徑；

步驟(3).按照步驟(2)得到的最優路徑行駛，每間隔Ts時間后，根據路面檢測器檢測到的實時路網數據對路網進行更新，并檢測車輛行駛位置；根據車輛當前行駛位置，選取最近的交叉口設定為當前考察節點，記為v_c；

所述的最近的交叉口是指路段上沿車輛行程方向距離車輛位置最近的交叉口；

步驟(4).判斷當前考察節點v_c是否為終點v_d，若是則算法終止；若否則執行步驟(5)；

步驟(5).根據當前考察節點v_c和終點v_d確定限制搜索區域Z：

所述的限制搜索區域Z是指根據路網中各交叉口的地理坐標，運用一些幾何規則，對路網范圍進行劃分；在最優路徑的搜索過程中只對落入限制區域Z內的節點和弧段進行考察，忽略限制搜索區域Z外的節點和弧段；

步驟(6).根據當前最優路徑所對應的路網數據，計算該時段限制搜索區域Z內各路段的行程時間變化率和各交叉口延誤時間變化率，最后取所有變化率的平均值λ；

步驟(7).判斷變化率平均值λ是否大于閾值α，若是則跳轉執行步驟(2)，并重新賦予v_c為起點，v_d為終點，以上述步驟(5)得到的限制搜索區域Z建立新路網；若否則執行步驟(3)。