[發明專利]考慮交叉口轉向的最短路徑標號算法

無效

• 申請號: 200910033090.3
• 申請日: 2009-06-11
• 公開（公告）號: CN101571995A
• 公開（公告）日: 2009-11-04
• 發明（設計）人: 程琳;杜牧青
• 申請（專利權）人: 東南大學
• 主分類號: G08G1/00
• 分類號: G08G1/00
• 代理公司: 南京經緯專利商標代理有限公司
• 代理人: 許 方

技術領域

本發明涉及對道路最短路徑網絡表示方法改進中的一種考慮交叉口轉向的最短路徑標號算法。

背景技術

最短路徑標號算法(如Dijkstra算法)是通過從路徑起點產生最短路徑樹，求解網絡最短路徑問題，適用于求解一個起點和多個終點的情況。

目前，不論是在交通規劃中利用最短路進行交通量分配，還是在導航系統中求解最短行車路線，普遍采用的最短路徑算法是以無約束網絡條件為前提的。在無約束道路網絡中，車輛通過交叉口時所產生的延誤或在交叉口的禁止轉向限制是被忽略的。然而，實際道路網絡是有限制條件的網絡，主要表現在：

(1)由交通管理措施產生的交叉口轉向限制，如在某些交叉口禁止車輛左轉彎，路段單行限制等。

(2)由于不同流向車流之間的干擾和信號控制手段產生的交叉口轉向延誤，例如，由于各行駛方向信號燈配時的不同時，相同進口道直行、左轉車輛的延誤也不相同。

在計算這類最短路徑時的主要困難就是難以用一個經濟、緊湊且易于管理的方法表示道路網絡。傳統的方法是將每一個交叉口擴展為一個子網，以路段表示轉向行為，擴展后的網絡不再涉及交叉口約束，并可以用任何標準的算法求解最短路徑。但是，這種方法存在著占用空間多、修改復雜、冗余度高等主要缺點，例如僅對于普通的四路交叉口，將被擴展為一個包含8個結點和16條路徑的子網絡。

發明內容

本發明要解決的技術問題是針對背景技術中存在的缺陷而提出一種基于擴展前向星型結構的考慮交叉口轉向的最短路徑標號算法。

本發明的考慮交叉口轉向的最短路徑標號算法，包括如下步驟：

對于有向網絡G(V，E)：

(1)初始化

創建鏈表S，將路徑起點r加入鏈表S中，初始化標號如下：

λi,mj=∞,pi,mj=(0,0),∀i∈V]]>

λr,mk=0,∀k∈Γ(r)]]>

(2)取鏈表S中第一個結點為以下步驟中的上游結點i

A.檢測該上游結點i下游的結點j，并通過步驟B檢查每個結點j的標號；

B.如果所有的結點j都被檢查過，返回步驟(1)，否則，選擇一個沒有被檢查過的結點j，作如下步驟：

a.對每個結點j的動作m_k作如下運算：