[發明專利]遍歷多點歸原的車輛路徑規劃方法

有效

• 申請號: 202110263504.2
• 申請日: 2021-03-11
• 公開（公告）號: CN112947467B
• 公開（公告）日: 2021-11-02
• 發明（設計）人: 李斌;駱劍鋒;朱展延;陳逸婷;曾雄;庾文聰
• 申請（專利權）人: 東莞職業技術學院;駱劍鋒
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 東莞市十方專利代理事務所(普通合伙) 44391
• 代理人: 黃云

1.一種遍歷多點歸原的車輛路徑規劃方法，其特征在于包括如下步驟：

1)先知條件：

已知原點及其它地點的經緯度，并且所有的點的數目超過10個，其中出發點和終點同為一點，即為原點，其它地點指目的地；

已知所有點之間的最短路程，并且形成最短路程矩陣；

兩點間的路程不分方向，路徑的正反向路程值相等；

通過上述條件，得到這些點的網絡圖GA和最短路程矩陣PT；

2)求最小生成樹：

基于第1)步的條件，求最小生成樹；

通過上述步驟得最小生成樹鄰接矩陣TM并得到最小生成樹圖；

3)取最小生成樹中的各子樹：

根據得到的最小生成樹鄰接矩陣TM以及最小生成樹圖，并根據取子樹的組合公式，進行計算；

得各子樹的根節點集合B0、各子樹的點的集合、各子樹圖；

4)求最密子樹：

根據前面步驟的條件，結合子樹密度組合公式，得各子樹密度值；

把各子樹密度值作為條件，用取最密子樹公式，篩選出最密子樹集；

5)在最密子樹中找到最邊沿葉子1；

使用數據結構技術中的后序遍歷方法，對最密子樹進行遍歷，得到各節點的遍歷順序集合；

在集合中的第一個節點為最邊沿葉子1；

6)針對最密子樹找最邊沿葉子端點2：

根據第5)步的遍歷順序集合，以集合作為條件，通過取葉子公式，可得后序遍歷順序的葉子端點集合；

葉子端點集合的最后一個節點為最邊沿葉子端點2；

7)在兩個最邊沿葉子端點中，確定一個是最密子樹始點，另外一個是最密子樹終點：

根據綜合路程值公式，求兩個最邊沿葉子端點的綜合路程值；

綜合路程值小者為最密子樹始點，另外一個是最密子樹終點；

8)以最密子樹根節點和最密子樹始點和最密子樹終點組成的回路為主線，把最密子樹中的葉子端點合并到主線中：

以最密子樹根節點和最密子樹始點和最密子樹終點組成的回路為主線；

把最密子樹中，不在主線上葉子端點合并到主線中，形成新的主線；

刪除最密子樹中葉子的分支；

判斷最密子樹中是否有葉子端點，如果有，就重復步驟8)中所述的形成新的主線以及刪除最密子樹中葉子的分支的步驟，一直到最密子樹中沒有葉子端點為止；

在進行上述步驟的同時，最小生成樹鄰接矩陣TM作相應的設置；

9)原點與主線合并，形成回路：

使用Jsprit的Rebuild方法，把原點合并到主線中；

根據刪除公式，刪除原點與最密子樹根節點間的路徑；

經過上面的步驟，從而形成一個：以原點為始點，經過原來的最密子樹上的點，回到根節點的回路；

10)對剩下的子樹進行判斷，點數超過1的子樹重復步驟4)到步驟9)，讓子樹形成回路，過程如下：

除了原點，排除現有的回路上的點和路徑；

把剩下的點所組成的各個子樹，逐個經過步驟4)到步驟9)，都各自形成回路；

重復上面操作，一直進行到沒有點數超過1的子樹為止；

點數為1的子樹就當成一個回路，它們都是從原點出發，經過葉子，回到原點的回路；

第1顆最密子樹形成的回路，用H1代表，按順時針方式，在H1旁的回路，用H2代表；

11)求各回路的回路始點與回路終點：

針對只有2點的回路，其葉子端點就是回路始點，也是回路終點；

針對超過2點的回路，從原點開始，順時針遍歷回路；

除了根節點，第一個遍歷的節點是回路始點，用as代表，最后一個是回路終點，用ae代表；

所有超過2點的回路用同樣的方法，都得到它們各自的回路始點與回路終點；

12)使用回路間節約里程公式，求節約里程值：

根據回路間節約里程公式，求上一回路終點與下一回路始點間的節約里程數值；

13)根據節約里程數值，使用節約里程方法，對回路進行合并：

根據節約里程數值，使用節約里程方法，對節約里程值大的兩個回路先進行合并；

重復步驟11)至步驟13)的過程，一直合并到回路數量為1時停止；

14)所有的回路合并后，最終的回路就是最終的車輛路徑規劃結果。