[發明專利]面向異構任務的車輛路徑優化方法及裝置

有效

• 申請號: 201910891830.0
• 申請日: 2019-09-20
• 公開（公告）號: CN110866629B
• 公開（公告）日: 2022-12-13
• 發明（設計）人: 羅賀;張鵬;王國強;雷星;王菊;朱默寧;胡笑旋;靳鵬;馬華偉;夏維
• 申請（專利權）人: 合肥工業大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 北京久誠知識產權代理事務所(特殊普通合伙) 11542
• 代理人: 余罡

1.一種面向異構任務的車輛路徑優化方法，其特征在于，包括：

獲取異構任務集合和路網數據；其中，所述異構任務集合中包括道路交點對應的點任務和道路線段對應的線任務；

構建車輛協執行所述異構任務集合的路徑規劃模型；其中，所述路徑規劃模型以將車輛從預設控制中心出發、執行完所述異構任務集合中所有任務并返回到所述預設控制中心所耗費的總時間最小化為優化目標，所述路徑規劃模型的約束條件為根據車輛執行所述異構任務集合的預設場景而設置；

確定所述異構任務集合中所有線任務的多種執行方向組合，構建每一種執行方向組合所對應的一個訪問距離矩陣；將所述訪問距離矩陣轉化為指派問題進行求解得到在對應執行方向組合下車輛單獨完成所述異構任務集合中所有任務時的最短路徑，將該最短路徑記為候選最短路徑；將多種執行方向組合下對應的多個候選最短路徑進行比較，將最小的候選最短路徑作為目標最短路徑；其中，所述訪問距離矩陣中第i行第j列的元素的值表示第i行對應的任務與第j列對應的任務之間的最短距離，所述異構任務集合中的所有任務作為行方向上的任務，且作為列方向上的任務。

2.根據權利要求1所述的方法，其特征在于，所述確定所述異構任務集合中所有線任務的多種執行方向組合，包括：

針對[0，2ⁿ-1]范圍內的每一個整數，確定一個對應的執行方向組合，具體為：將該整數轉化為對應的n位二進制數；根據所述n位二進制數，確定n個線任務對應的執行方向組合；其中，n為所述異構任務集合中所有線任務的數量。

3.根據權利要求1所述的方法，其特征在于，所述訪問距離矩陣中第i行第i列的元素的值為預設最大值。

4.根據權利要求1所述的方法，其特征在于，將所述訪問距離矩陣轉化為指派問題進行求解得到在對應執行方向組合下車輛單獨完成所述異構任務集合中所有任務時的最短路徑之后，所述方法還包括：判斷將所述訪問距離矩陣轉化為指派問題進行求解所得到的最短路徑是否為可行解，若否，則對所述訪問距離矩陣進行修改，直至將所述訪問距離矩陣轉化為指派問題進行求解所得到的最短路徑為可行解；其中，采用所述約束條件判斷得到的最短路徑是否為可行解，所述約束條件包括：所述車輛從所述預設控制中心出發的總次數為1、所述車輛返回到所述預設控制中心的總次數為1以及所述異構任務集合中所有的任務都被執行完成。

5.一種面向異構任務的車輛路徑優化裝置，其特征在于，包括：

任務輸入模塊，用于獲取異構任務集合和路網數據；其中，所述異構任務集合中包括道路交點對應的點任務和道路線段對應的線任務；構建車輛協執行所述異構任務集合的路徑規劃模型；其中，所述路徑規劃模型以將車輛從預設控制中心出發、執行完所述異構任務集合中所有任務并返回到所述預設控制中心所耗費的總時間最小化為優化目標，所述路徑規劃模型的約束條件為根據車輛執行所述異構任務集合的預設場景而設置；

路徑計算模塊，用于確定所述異構任務集合中所有線任務的多種執行方向組合，構建每一種執行方向組合所對應的一個訪問距離矩陣；將所述訪問距離矩陣轉化為指派問題進行求解得到在對應執行方向組合下車輛單獨完成所述異構任務集合中所有任務時的最短路徑，將該最短路徑記為候選最短路徑；將多種執行方向組合下對應的多個候選最短路徑進行比較，將最小的候選最短路徑作為目標最短路徑；其中，所述訪問距離矩陣中第i行第j列的元素的值表示第i行對應的任務與第j列對應的任務之間的最短距離，所述異構任務集合中的所有任務作為行方向上的任務，且作為列方向上的任務。

6.根據權利要求5所述的裝置，其特征在于，所述路徑計算模塊執行的所述確定所述異構任務集合中所有線任務的多種執行方向組合，包括：針對[0，2ⁿ-1]范圍內的每一個整數，確定一個對應的執行方向組合，具體為：將該整數轉化為對應的n位二進制數；根據所述n位二進制數，確定n個線任務對應的執行方向組合；其中，n為所述異構任務集合中所有線任務的數量。

7.根據權利要求5所述的裝置，其特征在于，所述訪問距離矩陣中第i行第i列的元素的值為預設最大值。