[發明專利]基于最大生成樹的車輛運輸載重量最大化的方法及裝置

在審

• 申請號: 201810970173.4
• 申請日: 2018-08-24
• 公開（公告）號: CN109255475A
• 公開（公告）日: 2019-01-22
• 發明（設計）人: 高鷹;魏楷聰
• 申請（專利權）人: 廣州大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06F17/50
• 代理公司: 廣州三環專利商標代理有限公司 44202
• 代理人: 顏希文;麥小嬋

1.一種基于最大生成樹的車輛運輸載重量最大化的方法，適于在計算設備中執行，其特征在于，至少包括如下步驟：

采用拓撲建模法，對車輛載重量問題進行建模，得到帶權值的連通圖；

根據所述連通圖，設定運輸任務；

根據所述連通圖，采用Kruskal算法構造最大生成樹；具體的，將所述連通圖中所有的邊按照權值從大到小進行排序，并存放在一個數組中，每次循環僅彈出所述數組的第一個元素即為當前具有最大權值的邊，并采用并查集將該元素添加到最大生成樹的子集合中；當所述子集合的大小等于最大生成樹的邊的數量時，循環結束，最大生成樹構造完畢，此時，所述子集合即為最大生成樹的邊的集合；

根據所述最大生成樹，確定并輸出與所述運輸任務對應的最大載重量路徑。

2.根據權利要求1所述的基于最大生成樹的車輛運輸載重量最大化的方法，其特征在于，所述運輸任務包括出發地點和目的地點。

3.根據權利要求1所述的基于最大生成樹的車輛運輸載重量最大化的方法，其特征在于，所述采用拓撲建模法，對車輛載重量問題進行建模，得到帶權值的連通圖，具體為：

將每個地點設定為圖的頂點，并將地點與地點之間的每條道路設定為圖中連接頂點的邊，得到初始連通圖；

根據每條道路對車輛的載重量限制，定義所述初始連通圖中每條道路對應的邊的權值，從而得到帶權值的連通圖。

4.根據權利要求1所述的基于最大生成樹的車輛運輸載重量最大化的方法，其特征在于，所述并查集為一種不限制孩子節點個數的樹形的數據結構，以創建數組來實現，每個數組的元素對應連通圖的頂點，而元素的值對應該元素在樹型結構中的父結點，當元素的值為-1時，表示該元素為所在樹型結構的根結點；同時，所述并查集還創建數組rank記錄每一棵樹型結構的根結點的高度，而每一棵樹型結構將對應最大生成樹形成過程中的每一塊，通過判斷所要添加的邊的兩個頂點各自所在的樹型結構的根結點是否為同一結點，以決定忽略該邊或將高度較低的樹型結構添加到高度較高的樹型結構中。

5.一種基于最大生成樹的車輛運輸載重量最大化的裝置，其特征在于，包括：

建模模塊，用于采用拓撲建模法，對車輛載重量問題進行建模，得到帶權值的連通圖；

運輸任務設定模塊，用于根據所述連通圖，設定運輸任務；

最大生成樹構造模塊，用于根據所述連通圖，采用Kruskal算法構造最大生成樹；具體的，將所述連通圖中所有的邊按照權值從大到小進行排序，并存放在一個數組中，每次循環僅彈出所述數組的第一個元素即為當前具有最大權值的邊，并將該元素添加到最大生成樹的子集合中；當所述子集合的大小等于最大生成樹的邊的數量時，循環結束，最大生成樹構造完畢，此時，所述子集合即為最大生成樹的邊的集合；

輸出模塊，用于根據所述最大生成樹，確定并輸出與所述運輸任務對應的最大載重量路徑。

6.根據權利要求5所述的基于最大生成樹的車輛運輸載重量最大化的裝置，其特征在于，所述運輸任務包括出發地點和目的地點。

7.根據權利要求5所述的基于最大生成樹的車輛運輸載重量最大化的裝置，其特征在于，所述采用拓撲建模法，對車輛載重量問題進行建模，得到帶權值的連通圖，具體為：

將每個地點設定為圖的頂點，并將地點與地點之間的每條道路設定為圖中連接頂點的邊，得到初始連通圖；

根據每條道路對車輛的載重量限制，定義所述初始連通圖中每條道路對應的邊的權值，從而得到帶權值的連通圖。