[發(fā)明專利]基于Dijkstra算法的車輛運(yùn)輸載重量最大化的方法及裝置

在審

• 申請(qǐng)?zhí)枺?/td>: 201810993766.2
• 申請(qǐng)日: 2018-08-29
• 公開（公告）號(hào): CN109242172A
• 公開（公告）日: 2019-01-18
• 發(fā)明（設(shè)計(jì)）人: 高鷹;魏楷聰
• 申請(qǐng)（專利權(quán)）人: 廣州大學(xué)
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04;G06Q10/08;G06Q50/30
• 代理公司: 廣州三環(huán)專利商標(biāo)代理有限公司 44202
• 代理人: 顏希文;麥小嬋

1.一種基于Dijkstra算法的車輛運(yùn)輸載重量最大化的方法，適于在計(jì)算設(shè)備中執(zhí)行，其特征在于，至少包括如下步驟：

采用拓?fù)浣７ǎ瑢?duì)車輛載重量問題進(jìn)行建模，得到帶權(quán)值的連通圖；

根據(jù)所述連通圖，設(shè)定運(yùn)輸任務(wù)；

采用Dijkstra算法對(duì)所述運(yùn)輸任務(wù)進(jìn)行運(yùn)輸載重量最大化的路徑規(guī)劃，得到所述運(yùn)輸任務(wù)對(duì)應(yīng)的最大載重量路徑；

輸出所述運(yùn)輸任務(wù)對(duì)應(yīng)的最大載重量路徑。

2.根據(jù)權(quán)利要求1所述的基于Dijkstra算法的車輛運(yùn)輸載重量最大化的方法，其特征在于，所述運(yùn)輸任務(wù)包括出發(fā)地點(diǎn)和目的地點(diǎn)。

3.根據(jù)權(quán)利要求1所述的基于Dijkstra算法的車輛運(yùn)輸載重量最大化的方法，其特征在于，所述采用拓?fù)浣７ǎ瑢?duì)車輛載重量問題進(jìn)行建模，得到帶權(quán)值的連通圖，具體為：

將每個(gè)地點(diǎn)設(shè)定為圖的頂點(diǎn)，并將地點(diǎn)與地點(diǎn)之間的每條道路設(shè)定為圖中連接頂點(diǎn)的邊，得到初始連通圖；

根據(jù)每條道路對(duì)車輛的載重量限制，定義所述初始連通圖中每條道路對(duì)應(yīng)的邊的權(quán)值，從而得到帶權(quán)值的連通圖。

4.根據(jù)權(quán)利要求3所述的基于Dijkstra算法的車輛運(yùn)輸載重量最大化的方法，所述連通圖以鄰接鏈表的方式進(jìn)行存儲(chǔ)，具體的，根據(jù)所述連通圖，創(chuàng)建一個(gè)數(shù)組存儲(chǔ)所述連通圖的所有頂點(diǎn)，并為數(shù)組的每個(gè)元素創(chuàng)建一個(gè)鏈表，所述鏈表存放與元素所對(duì)應(yīng)的頂點(diǎn)相鄰的所有頂點(diǎn)；其中，每個(gè)頂點(diǎn)均包含狀態(tài)、權(quán)值和父頂點(diǎn)三個(gè)信息。

5.根據(jù)權(quán)利要求1所述的基于Dijkstra算法的車輛運(yùn)輸載重量最大化的方法，所述采用Dijkstra算法對(duì)所述運(yùn)輸任務(wù)運(yùn)輸載重量最大化的路徑規(guī)劃，得到所述運(yùn)輸任務(wù)對(duì)應(yīng)的最大載重量路徑，具體為：

將所有的頂點(diǎn)狀態(tài)全部設(shè)置為0；

將所述運(yùn)輸任務(wù)中的出發(fā)地點(diǎn)的狀態(tài)變?yōu)?，并將與所述出發(fā)地點(diǎn)相鄰的頂點(diǎn)的狀態(tài)變?yōu)?；

將與所述出發(fā)地點(diǎn)相鄰的頂點(diǎn)的權(quán)值設(shè)置為該頂點(diǎn)與所述出發(fā)地點(diǎn)之間的邊的權(quán)值大小，父頂點(diǎn)設(shè)置為出發(fā)地點(diǎn)；

遍歷所有狀態(tài)為1的頂點(diǎn)的權(quán)值，將權(quán)值最大的頂點(diǎn)的狀態(tài)變?yōu)?；

遍歷與狀態(tài)變?yōu)?的頂點(diǎn)v1相鄰的頂點(diǎn)v2，若頂點(diǎn)v2的狀態(tài)為0，則將頂點(diǎn)v2的狀態(tài)變?yōu)?，并比較頂點(diǎn)v1的權(quán)值與頂點(diǎn)v1和頂點(diǎn)v2之間的邊的權(quán)值，將偏小的權(quán)值賦予頂點(diǎn)v2，并將頂點(diǎn)v2的父頂點(diǎn)設(shè)置為頂點(diǎn)v1；若頂點(diǎn)v2的狀態(tài)為1，且頂點(diǎn)v2權(quán)值比頂點(diǎn)v1的權(quán)值、頂點(diǎn)v1和頂點(diǎn)v2之間的邊的權(quán)值都小，則比較頂點(diǎn)v1的權(quán)值與頂點(diǎn)v1和頂點(diǎn)v2之間的邊的權(quán)值，將偏小的權(quán)值賦予頂點(diǎn)v2，并將頂點(diǎn)v2的父頂點(diǎn)設(shè)置為頂點(diǎn)v1；重復(fù)上述步驟，直至將所述運(yùn)輸任務(wù)中的出發(fā)地點(diǎn)與目標(biāo)地點(diǎn)之間呈現(xiàn)一條所有頂點(diǎn)的狀態(tài)均變?yōu)?的路徑。

6.一種基于Dijkstra算法的車輛運(yùn)輸載重量最大化的裝置，其特征在于，包括：

建模模塊，用于采用拓?fù)浣７ǎ瑢?duì)車輛載重量問題進(jìn)行建模，得到帶權(quán)值的連通圖；

運(yùn)輸任務(wù)設(shè)定模塊，用于根據(jù)所述連通圖，設(shè)定運(yùn)輸任務(wù)；

最大載重量路徑規(guī)劃模塊，用于采用Dijkstra算法對(duì)所述運(yùn)輸任務(wù)進(jìn)行運(yùn)輸載重量最大化的路徑規(guī)劃，得到所述運(yùn)輸任務(wù)對(duì)應(yīng)的最大載重量路徑；

輸出模塊，用于輸出所述運(yùn)輸任務(wù)對(duì)應(yīng)的最大載重量路徑。

7.根據(jù)權(quán)利要求6所述的基于Dijkstra算法的車輛運(yùn)輸載重量最大化的裝置，其特征在于，所述建模模塊，具體用于將每個(gè)地點(diǎn)設(shè)定為圖的頂點(diǎn)，并將地點(diǎn)與地點(diǎn)之間的每條道路設(shè)定為圖中連接頂點(diǎn)的邊，得到初始連通圖；根據(jù)每條道路對(duì)車輛的載重量限制，定義所述初始連通圖中每條道路對(duì)應(yīng)的邊的權(quán)值，從而得到帶權(quán)值的連通圖。

8.根據(jù)權(quán)利要求7所述的基于Dijkstra算法的車輛運(yùn)輸載重量最大化的裝置，其特征在于，所述連通圖以鄰接鏈表的方式進(jìn)行存儲(chǔ)，具體的，根據(jù)所述連通圖，創(chuàng)建一個(gè)數(shù)組存儲(chǔ)所述連通圖的所有頂點(diǎn)，并為數(shù)組的每個(gè)元素創(chuàng)建一個(gè)鏈表，所述鏈表存放與元素所對(duì)應(yīng)的頂點(diǎn)相鄰的所有頂點(diǎn)；其中，每個(gè)頂點(diǎn)均包含狀態(tài)、權(quán)值和父頂點(diǎn)三個(gè)信息。