[發明專利]車輛路徑規劃方法、裝置、設備和存儲介質

有效

• 申請號: 202110012924.3
• 申請日: 2021-01-06
• 公開（公告）號: CN112633609B
• 公開（公告）日: 2022-10-25
• 發明（設計）人: 藍文興;葉梓元;阮沛鈞;劉佳琳;姚新
• 申請（專利權）人: 南方科技大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q10/08;G06Q50/30
• 代理公司: 北京品源專利代理有限公司 11332
• 代理人: 潘登

1.一種車輛路徑規劃方法，其特征在于，包括：

a、根據車輛任務信息確定初始路徑S₀；

b、基于所述初始路徑S₀進行鄰域交換優化得到第一路徑S₁；

c、基于所述第一路徑S₁隨機進行交換、插入、逆轉三種優化方式中的一種或多種得到第二路徑S₂；

d、判斷所述第二路徑S₂的成本是否低于所述初始路徑S₀的成本，若不是則跳轉至步驟f；

e、若是則更新所述初始路徑S₀為所述第二路徑S₂，并跳轉至步驟f；

f、基于所述初始路徑S₀判斷是否達到預設停止條件，若未達到所述預設停止條件則跳轉至步驟b；

g、若達到所述預設停止條件，則將所述初始路徑S₀作為規劃結果得到規劃的車輛路徑；

所述基于所述初始路徑S₀進行鄰域交換優化得到第一路徑S₁，包括：

基于所述初始路徑S₀進行鄰域單點交換得到第三路徑S₃，隨機從所述初始路徑S₀中選擇一條路徑R_k，對于R_k中的每一個服務點o，如果存在一個與o的距離在ρ₁內的點o′，且o′在另外一條路徑R_k′中，然后將o和o′進行交換得到新的兩條路徑R′_k和R′_k′，若新的兩條路徑R′_k和R′_k′的距離之和比原先的兩條路徑的距離之和短，則保留這種交換得到第三路徑S₃；

基于所述第三路徑S₃進行鄰域單段交換得到所述第一路徑S₁，隨機從S₃中選擇一條路徑R_3k，再從R_3k中隨機選擇一個服務點c，如果存在另外一個服務點c′在另外一條路徑R_3k′中，且c′與c的距離在ρ₂內，則將c′與c后面的一整段進行交換得到新的兩條路徑R′_3k和R′_3k′，如果新的兩條路徑的距離之和比原先的兩條路徑的距離之和短，則保留這種交換得到第一路徑S₁；

所述基于所述第一路徑S₁隨機進行交換、插入、逆轉三種優化方式中的一種或多種得到第二路徑S₂包括：

隨機從S₁中選擇一條路徑R_1k，從R_1k中隨機選擇兩個服務點a和a′，將其兩者的位置進行交換得到新路徑R′_k，如果路徑R′_k的距離變短，則保留交換操作得到S₂，和/或，從R_1k中隨機選擇一個服務點a，并將它插入到路徑R_1k中的最好位置，即使路徑的距離最短得到S₂，和/或，從R_1k中隨機選擇兩個服務點a和a′，將其兩者之間的服務點進行逆轉得到新路徑R′_1k，如果路徑R′_1k的距離變短，則保留交換操作得到S₂。

2.根據權利要求1所述的車輛路徑規劃方法，其特征在于，所述車輛任務信息包括車輛約束信息和節點信息，所述車輛約束信息包括車輛的工作時長、數量和容量，所述節點信息包括節點的位置、任務量和節點間的路線。

3.根據權利要求1所述的車輛路徑規劃方法，其特征在于，所述更新所述初始路徑S₀為所述第二路徑S₂之后，還包括：

基于所述初始路徑S₀進行路徑合并得到第四路徑S₄，并更新所述初始路徑S₀為所述第四路徑S₄。