一種基於阻抗匹配的Dijkstra最優交通路徑規劃方法及系統與流程
2023-12-09 21:59:11 3
本發明屬於Dijkstra優化算法技術領域，具體涉及一種基於阻抗匹配的Dijkstra最優交通路徑規劃方法及系統。
背景技術：
傳統的Dijkstra算法用於龐大的交通網路時，計算量十分巨大，時間複雜度很大，搜索效率很低。對於錯綜複雜的交通網路，利用Dijkstra算法計算出的最短路徑未必是最優路徑，由於道路質量、擁堵情況等導致交通道路存在一定的交通阻抗，進而導致該算法求取的最短路徑缺少實際價值和意義；如何研究出一種能夠解決上述問題的方法和系統成為了本領域技術人員亟待解決的問題。
技術實現要素：
有鑑於此，本發明實施例提供了一種基於阻抗匹配的Dijkstra最優交通路徑規劃方法及系統，用於解決傳統Dijkstra算法求得的最短路徑缺乏實際價值和意義的技術問題。
本發明提供了一種基於阻抗匹配的Dijkstra最優交通路徑規劃方法，包括步驟：
求取預設範圍內所有有向弧段的集合；
通過融合交通阻抗的Dijkstra最優路徑算法獲取所有有向弧段的時間花費；
取從源點到終點中時間花費最短的有向弧段集合作為最終結果輸出，即最優路徑集合。
進一步的，所述通過融合交通阻抗的Dijkstra最優路徑算法獲取所有有向弧段的時間花費的步驟包括：
設S為已求得最優路徑的弧段的集合，A為預設範圍內城市道路網絡中的路段集合；令初始最優路徑時間花費k(r0)＝0；將弧段r0放入到S中；令k(ri)＝+∞，ri∈A-S；
計算以源點s為出發點的所有有向弧段時間花費，求出k(ri)＝k(r0)+tsi,其中tsi表示從s到i的交通時間阻抗值，求出k(r*)＝min{k(ri)},ri＝；則將弧r*放入S中；如此，得到首節點h(r*)＝s，末節點f(r*)＝i,最優路徑節點序列Pi＝(s，f(r*))；
計算以弧段r*末點為出發點的所有有向弧段的時間花費；首先根據弧段r*和每一條要接入的弧段rj的走行方向進行轉向方向的判定,並考慮交叉口延誤；接著求出k(rj)＝min{k(r*)+tij；k(rj)},其中tij表示從i到j的交通時間阻抗值；最後k(r*)＝min{k(rj)},將弧段r*放入S中，得到本弧段前節點h(r*)＝i，後節點f(r*)＝j，最優路徑節點序列Pj＝Pi+f(r*)；
判斷A是否等於S，即判斷預設範圍內城市道路網絡中的路段集合A是否都已包含在已求得最優路徑的弧段的集合S中；
若A＝S，則轉入輸出最終結果的步驟；若A≠S，則轉入計算以弧段r*末點為出發點的所有有向弧段的時間花費的步驟再繼續；
輸出最終結果；若k(r*)<+∞,則k(r*)為最優路徑的所需要花費的時間，Pj為最優路徑集合。本方案中，S是以求出最優路徑的有向弧段的集合，從源點開始，S中最初只包含源點s，花費時間為0，以源點s為中心向外層層擴展，逐步的將A中的有向弧段進行計算並加入S中，當從源點到終點所有的有向弧段都被求出最優路徑時，從源點到終點的最優路徑集合也就被求出來了；其中，最優路徑的計算主要考慮在弧段和交叉口花費的時間，時間花費最短即為最優路徑，而不是路徑最短。
進一步的，所述交通時間阻抗值包括路段時間阻抗值和交叉路口時間阻抗值；
其中，交通時間阻抗值tij包括路段時間阻抗值yij和交叉路口時間阻抗值dij；
所述yij在任意兩路段i和j之間車輛行駛所需要的時間；dij表示交叉路口所花費的時間。當然，該tsi的求得與tij相類；很多時候，最短路徑並不是最優路徑，特別的，例如最短路徑中存在禁止通行情況下，我們通過該最短路逕到達終點需要花費的時間是無限大的，這時候就需要考慮交通時間阻抗值了，而交通時間阻抗值包括路段行駛所需花費的時間，以及通過交叉路徑所需花費的時間。
進一步的，求得所述路段時間阻抗值yij的函數表達式稱為：
式中
ta(0)：路段a上的車輛在無阻礙的情況下行駛的平均時間；
ea：路段a的通行能力；
qa：路段a上的交通流量；
α、β：待標定的參數。在車輛在沒有交通阻礙的情況下，行駛時間和行駛距離是成正比的關係，但在實際的交通道路中，車輛不可能無阻礙的行駛。所以道路上行駛時間與行駛距離不能簡單的用正比函數來表示，其行駛時間與距離和流量之間的關係是一種負載的關係函數；本方案中，採用應用最廣發的是BPR函數，該函數由美國道路局幵發；路段行駛需要的時間是尋求最優路徑需要考慮的重要因素，而正確求得路段時間阻抗值需要通過在交通道路的各種觀測數據的支持，如此才能更正確的求得時間花費。
進一步的，求得所述交叉路口時間阻抗值dij的函數表達式稱為：
式中
d：延誤阻抗；
Tc：信號燈周期長；
μ：綠信比；
q：進口車道實際到達的交通流量；
x：飽和度。雖然正常情況下，路段阻抗值是時間花費的主力，但是某些情況下，特別是對於大城市的道路網來說，交叉口密集，車輛在交叉路徑耗費的時間也是不容忽視的，在交叉路口，信號燈周期長、綠信比和進口車道實際到達的交通流量等因素都是需要考慮的，如此求解最優路徑的時間花費的計算才更為合理和實用。
進一步的，所述求取預設範圍內所有有向弧段的集合的步驟包括：
利用已有的節點坐標信息，將預設範圍設定為以源點和終點連線為對角線的矩形範圍內。在通常情況下，源點和終點之間的最優路徑基本囊括在以源點和終點連線為對角線的矩形範圍內，本方案中，採用限制搜索區域，大大減少了遍歷節點的數量，提高了運算時間。
進一步的，所述求取預設範圍內所有有向弧段的集合的步驟包括：
利用已有的節點坐標信息，將搜索的區域設定為以源點和終點連線為對角線的矩形範圍內，並在將該矩形範圍擴大兩個節點範圍後，將其作為預設範圍。在通常情況下，源點和終點之間的最優路徑基本囊括在以源點和終點連線為對角線的矩形範圍內，再考慮到有時需要從源點先繞行至矩形範圍以外的節點路徑，因而將矩形範圍擴大兩個節點範圍作為預設範圍，本方案中，採用限制搜索區域，大大減少了遍歷節點的數量，提高了運算時間。
進一步的，在所述求取預設範圍內所有有向弧段的集合的步驟之前還包括步驟：
建立交通網絡模型，將整個路網抽象為「{節點集合}+{弧段集合}+{路權集合}」的有向賦權圖；
其中，節點指道路的交叉口、道路盡頭或道路屬性改變的地方的點；而弧段則表示路網中相鄰兩個交叉口間的路段。將交通網絡模型抽象為有向賦權圖，有利於後續Dijkstra算法的計算，提高計算效率。
進一步的，所述有向賦權圖使用鄰接表作為存儲方式得到道路網絡圖；
鄰接表是表示節點之間的相鄰關係的n個單向鍊表,由順序表和鍊表構成；順序表的元素表示路網節點,每個節點對應一個鍊表,鍊表中的元素表示與鍊表頭中的節點元素相鄰接的路網節點口。採用鄰接表存儲方式，節省大量的存儲空間，並提高算法的搜索速度。
本發明還公開了一種基於阻抗匹配的Dijkstra最優交通路徑規劃系統，包括：
有向弧段求取模塊，用於求取預設範圍內所有有向弧段的集合；
時間花費計算模塊，耦合於所述有向弧段求取模塊，用於計算通過融合交通阻抗的Dijkstra最優路徑算法獲取所有有向弧段的時間花費；
最終結果輸出模塊，耦合於所述時間花費計算模塊，用於輸出最優路徑集合，該最優路徑集合取自源點到終點中時間花費最短的有向弧段集合。
進一步的，所述時間花費計算模塊包括Dijkstra最優路徑算法單元，耦合於所述Dijkstra最優路徑算法單元的路段時間阻抗值計算單元和交叉路口時間阻抗值計算單元。很多時候，最短路徑並不是最優路徑，特別的，例如最短路徑中存在禁止通行情況下，我們通過該最短路逕到達終點需要花費的時間是無限大的，這時候就需要考慮交通時間阻抗值了，而交通時間阻抗值包括路段行駛所需花費的時間，以及通過交叉路徑所需花費的時間；相對的，在計算時間花費時，則需要Dijkstra最優路徑算法單元、路段時間阻抗值計算單元和交叉路口時間阻抗值計算單元共同配合計算。
採用上述技術方案，本發明至少可取得下述技術效果：本發明中，由於在尋求最優路徑的過程中考慮了交通阻抗的因素，避免通過傳統Dijkstra算法求得的最優路徑無法通行而花費的延遲代價無限大的情況發生，而是確實的考慮了交通阻抗後真實可行的最優交通路徑，降低交通出行代價，使最優交通路徑計算更具有應用價值和意義；對於用戶，可以減少出行能耗和時間花費，特別的可以解決出行者對於陌生城市路況情況的認知，而對於整個城市來說，則可以減少車輛能源消耗和汙染，並且能夠協調和控制城市車輛的路徑規劃，進而實現提高城市路況的使用效率，降低城市交通堵塞；本發明中，最優路徑的考量主要考慮時間花費因素，當然，在實際情況中亦可將路徑最短等因素作為最優路徑的主要考量因素，特別是在交通阻抗幾乎可以忽略的情況下；另外，該預設範圍可以是整個道路網絡，也可以是一個限制範圍內的道路網絡，根據實際需求不同而定。
附圖說明
為了更清楚地說明本發明實施例中的技術方案，下面將對本發明實施例描述中所需要使用的附圖作簡單的介紹，顯而易見地，下面描述中的附圖僅僅是本發明的一些實施例，對於本領域普通技術人員來講，在不付出創造性勞動的前提下，還可以根據本發明實施例的內容和這些附圖獲得其他的附圖。
圖1是本發明一種基於阻抗匹配的Dijkstra最優交通路徑規劃方法的流程圖；
圖2為某城區的局部道路網絡圖；
圖3是傳統的Dijkstra算法的計算結果示意圖；
圖4是基於交通阻抗的最優路徑算法的計算結果；
圖5是本發明一種基於阻抗匹配的Dijkstra最優交通路徑規劃系統的示意圖。
具體實施方式
為使本發明解決的技術問題、採用的技術方案和達到的技術效果更加清楚，下面將結合附圖對本發明實施例的技術方案作進一步的詳細描述，顯然，所描述的實施例僅僅是本發明一部分實施例，而不是全部的實施例。基於本發明中的實施例，本領域技術人員在沒有作出創造性勞動前提下所獲得的所有其他實施例，都屬於本發明保護的範圍。
下面結合附圖並通過具體實施方式來進一步說明本發明的技術方案。需要說明的是，本發明的實施例XXX為例對本發明的技術方案進行說明，但並非以此作為限制。本領域技術人員能夠明了，本發明所提出的XXX除用於XXX之外，還可以廣泛應用於其他相同或相近領域中，並取得類似的技術效果。
實施例一：
圖1是本發明一種基於阻抗匹配的Dijkstra最優交通路徑規劃方法的流程圖，參考圖1，本發明公開了一種基於阻抗匹配的Dijkstra最優交通路徑規劃方法，包括：
S1:求取預設範圍內所有有向弧段的集合；
S2:通過融合交通阻抗的Dijkstra最優路徑算法獲取所有有向弧段的時間花費；
S3:取從源點到終點中時間花費最短的有向弧段集合作為最終結果輸出，即最優路徑集合。
採用上述技術方案，本發明至少可取得下述技術效果：本發明中，由於在尋求最優路徑的過程中考慮了交通阻抗的因素，避免通過傳統Dijkstra算法求得的最優路徑無法通行而花費的延遲代價無限大的情況發生，而是確實的考慮了交通阻抗後真實可行的最優交通路徑，降低交通出行代價，使最優交通路徑計算更具有應用價值和意義；對於用戶，可以減少出行能耗和時間花費，特別的可以解決出行者對於陌生城市路況情況的認知，而對於整個城市來說，則可以減少車輛能源消耗和汙染，並且能夠協調和控制城市車輛的路徑規劃，進而實現提高城市路況的使用效率，降低城市交通堵塞；本發明中，最優路徑的考量主要考慮時間花費因素，當然，在實際情況中亦可將路徑最短等因素作為最優路徑的主要考量因素，特別是在交通阻抗幾乎可以忽略的情況下；另外，該預設範圍可以是整個道路網絡，也可以是一個限制範圍內的道路網絡，根據實際需求不同而定。
其中，交通阻抗是車輛運行在交通道路上時，根據運行的距離、時間、舒適度、擁堵情況、交通費用和人的舒適度等綜合因素，需要考慮到即人、車、路、環境相互影響，對交通出行的阻力作用值。
本實施例優選的，通過融合交通阻抗的Dijkstra最優路徑算法獲取所有有向弧段的時間花費的步驟包括：
設S為已求得最優路徑的弧段的集合，A為預設範圍內城市道路網絡中的路段集合；令初始最優路徑時間花費k(r0)＝0；將弧段r0放入到S中；令k(ri)＝+∞，ri∈A-S；
計算以源點s為出發點的所有有向弧段時間花費，求出k(ri)＝k(r0)+tsi,其中tsi表示從s到i的交通時間阻抗值，求出k(r*)＝min{k(ri)},ri＝；則將弧r*放入S中；如此，得到首節點h(r*)＝s，末節點f(r*)＝i,最優路徑節點序列Pi＝(s，f(r*))；
計算以弧段r*末點為出發點的所有有向弧段的時間花費；首先根據弧段r*和每一條要接入的弧段rj的走行方向進行轉向方向的判定,並考慮交叉口延誤；接著求出k(rj)＝min{k(r*)+tij；k(rj)},其中tij表示從i到j的交通時間阻抗值；最後k(r*)＝min{k(rj)},將弧段r*放入S中，得到本弧段前節點h(r*)＝i，後節點f(r*)＝j，最優路徑節點序列Pj＝Pi+f(r*)；
判斷A是否等於S，即判斷預設範圍內城市道路網絡中的路段集合A是否都已包含在已求得最優路徑的弧段的集合S中；
若A＝S，則轉入輸出最終結果的步驟；若A≠S，則轉入計算以弧段r*末點為出發點的所有有向弧段的時間花費的步驟再繼續；
輸出最終結果；若k(r*)<+∞,則k(r*)為最優路徑的所需要花費的時間，Pj為最優路徑集合。本方案中，S是以求出最優路徑的有向弧段的集合，從源點開始，S中最初只包含源點s，花費時間為0，以源點s為中心向外層層擴展，逐步的將A中的有向弧段進行計算並加入S中，當從源點到終點所有的有向弧段都被求出最優路徑時，從源點到終點的最優路徑集合也就被求出來了；其中，最優路徑的計算主要考慮在弧段和交叉口花費的時間，時間花費最短即為最優路徑，而不是路徑最短。
本實施例優選的，交通時間阻抗值包括路段時間阻抗值和交叉路口時間阻抗值；
其中，交通時間阻抗值tij包括路段時間阻抗值yij和交叉路口時間阻抗值dij；yij在任意兩路段i和j之間車輛行駛所需要的時間；dij表示交叉路口所花費的時間。當然，該tsi的求得與tij相類；很多時候，最短路徑並不是最優路徑，特別的，例如最短路徑中存在禁止通行情況下，我們通過該最短路逕到達終點需要花費的時間是無限大的，這時候就需要考慮交通時間阻抗值了，而交通時間阻抗值，特別是城市交通系統的交通阻抗主要分為兩類，包括路段行駛所需花費的時間，以及通過交叉路徑所需花費的時間。
本實施例優選的，求得路段時間阻抗值yij的函數表達式稱為：
式中
ta(0)：路段a上的車輛在無阻礙的情況下行駛的平均時間；
ea：路段a的通行能力；
qa：路段a上的交通流量；
α、β：待標定的參數。在車輛在沒有交通阻礙的情況下，行駛時間和行駛距離是成正比的關係，但在實際的交通道路中，車輛不可能無阻礙的行駛。所以道路上行駛時間與行駛距離不能簡單的用正比函數來表示，其行駛時間與距離和流量之間的關係是一種負載的關係函數；本方案中，採用應用最廣發的是BPR函數，該函數由美國道路局幵發；路段行駛需要的時間是尋求最優路徑需要考慮的重要因素，而正確求得路段時間阻抗值需要。
本實施例優選的，求得交叉路口時間阻抗值dij的函數表達式稱為：
式中
d：延誤阻抗；
Tc：信號燈周期長；
μ：綠信比；
q：進口車道實際到達的交通流量；
x：飽和度。雖然正常情況下，路段阻抗值是時間花費的主力，但是某些情況下，特別是對於大城市的道路網來說，交叉口密集，車輛在交叉路徑耗費的時間也是不容忽視的，在交叉路口，信號燈周期長、綠信比和進口車道實際到達的交通流量等因素都是需要考慮的，如此求解最優路徑的時間花費的計算才更為合理和實用。
本實施例優選的，求取預設範圍內所有有向弧段的集合的步驟包括：
利用已有的節點坐標信息，將預設範圍設定為以源點和終點連線為對角線的矩形範圍內。在通常情況下，源點和終點之間的最優路徑基本囊括在以源點和終點連線為對角線的矩形範圍內，本方案中，採用限制搜索區域，大大減少了遍歷節點的數量，提高了運算時間。
本實施例優選的，求取預設範圍內所有有向弧段的集合的步驟包括：
利用已有的節點坐標信息，將搜索的區域設定為以源點和終點連線為對角線的矩形範圍內，並在將該矩形範圍擴大兩個節點範圍後，將其作為預設範圍。在通常情況下，源點和終點之間的最優路徑基本囊括在以源點和終點連線為對角線的矩形範圍內，再考慮到有時需要從源點先繞行至矩形範圍以外的節點路徑，因而將矩形範圍擴大兩個節點範圍作為預設範圍，本方案中，採用限制搜索區域，大大減少了遍歷節點的數量，提高了運算時間。
本實施例優選的，在求取預設範圍內所有有向弧段的集合的步驟之前還包括步驟：
建立交通網絡模型，將整個路網抽象為「{節點集合}+{弧段集合}+{路權集合}」的有向賦權圖；
其中，節點指道路的交叉口、道路盡頭或道路屬性改變的地方的點；而弧段則表示路網中相鄰兩個交叉口間的路段。將交通網絡模型抽象為有向賦權圖，有利於後續Dijkstra算法的計算，提高計算效率。
本實施例優選的，有向賦權圖使用鄰接表作為存儲方式得到道路網絡圖；
鄰接表是表示節點之間的相鄰關係的n個單向鍊表,由順序表和鍊表構成；順序表的元素表示路網節點,每個節點對應一個鍊表,鍊表中的元素表示與鍊表頭中的節點元素相鄰接的路網節點口。採用鄰接表存儲方式，節省大量的存儲空間，並提高算法的搜索速度。
為了更好地解釋本發明的規劃方法，下面展示一個最優路徑算法的實例
圖2為某城區的局部道路網絡圖,路段均為雙向路段,考慮到實際交通路況，將車輛在路段上的行駛時間標註於圖中弧段的旁邊,在各交叉口的右轉、直行和左轉平均延誤分別為0、30s、60s。路口6是禁止從西向東行駛的車輛左轉彎。假設某一車輛車速30公裡/小時，1-3道路長度為1.5公裡，每段道路延誤時間具體如圖2，應用基於阻抗的Dijkstra算法,計算從交叉口1和交叉口9之間的最優路徑。
圖3是傳統的Dijkstra算法的計算結果示意圖，圖4是基於交通阻抗的最優路徑算法的計算結果；
如表1，利用傳統的Dijkstra算法獲得的最優路徑(如圖3中粗實線所示)為1-3-6-7-9，由於路口6為禁止左轉，故所需要花費的延誤代價為無限大。利用融合交通阻抗的dijkstra最優路徑算法，獲得的最優路徑(如圖4中粗實線所示)為1-3-5-8-9。所需要花費的延誤代價為16min，這才是真實可行的最優路徑。
表1：傳統的Dijistra算法與融合交通阻抗的Dijkstra算法的對比
從以上分析可以看出,改進的Dijkstra算法是採用數學算法來解決交通路網中最優路徑的問題,對交通網絡結構本身沒有進行任何修改,不但減少了工作量,而且清楚地表示出交通網絡的連通性特徵，有效地描述道路網絡中的交叉口轉向延誤和限制,體現了城市道路交通的方向性及交叉口延誤，從而更有效找到真實可行的城市最優交通路徑。
實施例二：
圖2是本發明一種基於阻抗匹配的Dijkstra最優交通路徑規劃系統的示意圖，本發明的系統適用了本發明公開的最優交通路徑規劃方法，參考圖2可知，該系統，包括：
有向弧段求取模塊10，用於求取預設範圍內所有有向弧段的集合；
時間花費計算模塊20，耦合於有向弧段求取模塊10，用於計算通過融合交通阻抗的Dijkstra最優路徑算法獲取所有有向弧段的時間花費；
最終結果輸出模塊30，耦合於時間花費計算模塊30，用於輸出最優路徑集合，該最優路徑集合取自源點到終點中時間花費最短的有向弧段集合。
採用上述技術方案，本發明至少可取得下述技術效果：本發明中，由於在通過時間花費模塊尋求最優路徑的過程中考慮了交通阻抗的因素，避免通過傳統Dijkstra算法求得的最優路徑無法通行而花費的延遲代價無限大的情況發生，而是確實的考慮了交通阻抗後真實可行的最優交通路徑，降低交通出行代價，使最優交通路徑計算更具有應用價值和意義；對於用戶，可以減少出行能耗和時間花費，特別的可以解決出行者對於陌生城市路況情況的認知，而對於整個城市來說，則可以減少車輛能源消耗和汙染，並且能夠協調和控制城市車輛的路徑規劃，進而實現提高城市路況的使用效率，降低城市交通堵塞；本發明中，最優路徑的考量主要考慮時間花費因素，當然，在實際情況中亦可將路徑最短等因素作為最優路徑的主要考量因素，特別是在交通阻抗幾乎可以忽略的情況下；另外，該預設範圍可以是整個道路網絡，也可以是一個限制範圍內的道路網絡，根據實際需求不同而定。
本實施例優選的，時間花費計算模塊20包括Dijkstra最優路徑算法單元21，耦合於Dijkstra最優路徑算法單元21的路段時間阻抗值計算單元22和交叉路口時間阻抗值計算單元23。很多時候，最短路徑並不是最優路徑，特別的，例如最短路徑中存在禁止通行情況下，我們通過該最短路逕到達終點需要花費的時間是無限大的，這時候就需要考慮交通時間阻抗值了，而交通時間阻抗值包括路段行駛所需花費的時間，以及通過交叉路徑所需花費的時間；相對的，在計算時間花費時，則需要Dijkstra最優路徑算法單元、路段時間阻抗值計算單元和交叉路口時間阻抗值計算單元共同配合計算。
以上實施例提供的技術方案中的全部或部分內容可以通過軟體編程或專用硬體設備實現，其中軟體程序存儲在可讀取的存儲介質中，存儲介質例如：計算機中的硬碟、光碟或軟盤；專用硬體設備可以是ASIC、FPGA、SoC、或具有相應電路的IP Core。
注意，上述僅為本發明的較佳實施例及所運用技術原理。本領域技術人員會理解，本發明不限於這裡所述的特定實施例，對本領域技術人員來說能夠進行各種明顯的變化、重新調整和替代而不會脫離本發明的保護範圍。因此，雖然通過以上實施例對本發明進行了較為詳細的說明，但是本發明不僅僅限於以上實施例，在不脫離本發明構思的情況下，還可以包括更多其他等效實施例，而本發明的範圍由所附的權利要求範圍決定。