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

在審

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

本發明公開了基于Dijkstra算法的車輛運輸載重量最大化的方法及裝置，所述方法適于在計算設備中執行，至少包括如下步驟：采用拓撲建模法，對車輛載重量問題進行建模，得到帶權值的連通圖；根據所述連通圖，設定運輸任務；采用Dijkstra算法對所述運輸任務進行運輸載重量最大化的路徑規劃，得到所述運輸任務對應的最大載重量路徑。本發明能夠實現通過建模實現利用現有地圖進行最大提升車輛載重量的目的。

技術領域

本發明涉及到圖論領域，尤其涉及基于Dijkstra算法的車輛運輸載重量最大化的方法及裝置。

背景技術

隨著國家公路的高速發展，中國公路貨運已成為世界第一規模的整體市場，當前，我國對提升物流效率的要求迫在眉睫。

物流管理系統，其特點是能夠大幅減少發送人和接收人相關業務操作的操作量，并且具有實時監控物品在運輸過程中的狀態的功能。因此，現有的提升物流效率的方法，主要通過使用物流管理系統進行操作，以提升管理效率和降低管理成本。但是，在對現有技術的研究和實踐過程中，本發明的發明人發現，現有的利用物流管理系統的方法，存在不能有效的提升載重量的問題。

發明內容

本發明所要解決的技術問題在于，提供基于Dijkstra算法的車輛運輸載重量最大化的方法及裝置，通過建模實現利用現有地圖進行最大提升車輛載重量的目的。

為了解決上述技術問題，一方面，本發明的一個實施例提供了基于Dijkstra算法的車輛運輸載重量最大化的方法，適于在計算設備中執行，至少包括如下步驟：

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

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

采用Dijkstra算法對所述運輸任務進行運輸載重量最大化的路徑規劃，得到所述運輸任務對應的最大載重量路徑。

輸出所述運輸任務對應的最大載重量路徑。

進一步地，所述運輸任務包括出發地點和目的地點。

進一步地，所述采用拓撲建模法，對車輛載重量問題進行建模，得到帶權值的連通圖，具體為：

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

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

進一步地，所述連通圖以鄰接鏈表的方式進行存儲，具體的，根據所述連通圖，創建一個數組存儲所述連通圖的所有頂點，并為數組的每個元素創建一個鏈表，所述鏈表存放與元素所對應的頂點相鄰的所有頂點。其中，每個頂點均包含狀態、權值和父頂點三個信息。

進一步地，所述采用Dijkstra算法對所述運輸任務運輸載重量最大化的路徑規劃，得到所述運輸任務對應的最大載重量路徑，具體為：

將所有的頂點狀態全部設置為0；

將所述運輸任務中的出發地點的狀態變為2，并將與所述出發地點相鄰的頂點的狀態變為1；

將與所述出發地點相鄰的頂點的權值設置為該頂點與所述出發地點之間的邊的權值大小，父頂點設置為出發地點；

遍歷所有狀態為1的頂點的權值，將權值最大的頂點的狀態變為2；