[發明專利]揀貨路徑規劃方法與裝置

有效

• 申請號: 201711321490.5
• 申請日: 2017-12-12
• 公開（公告）號: CN109919345B
• 公開（公告）日: 2021-06-29
• 發明（設計）人: 王天文;董紅宇;莫澤
• 申請（專利權）人: 北京京東振世信息技術有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06N3/00
• 代理公司: 北京律智知識產權代理有限公司 11438
• 代理人: 闞梓瑄;王衛忠

1.一種基于蟻群算法的揀貨路徑規劃方法，其特征在于，包括：

以多個節點為起點，啟動多只螞蟻的路徑遍歷，所述節點包括多個揀貨節點、揀貨起點、揀貨終點；

根據多個所述節點之間的路徑的信息素數值計算所述螞蟻轉移到其他所述節點的轉移概率，將螞蟻移動到所述轉移概率最大的所述節點上；

判斷一只螞蟻遍歷所有所述節點后，更新路徑的信息素數值，記錄一個遍歷路徑；

根據多個遍歷路徑確定最優路徑；

其中，所述根據多個遍歷路徑確定最優路徑包括：

獲取歷史最優路徑與一個遍歷路徑，所述歷史最優路徑為同一巷道揀貨順序從外到里的遍歷路徑方案；

將所述歷史最優路徑與所述遍歷路徑中路徑長度小的選擇為當前最優路徑；

多次獲取遍歷路徑，將所述遍歷路徑與所述當前最優路徑二者中路徑長度小的方案選擇為當前最優路徑；

重復上一步驟n次，在判斷所述當前最優路徑連續k次被選擇時，將所述當前最優路徑確定為最優路徑，其中n為預設的最大總循環次數；

確定倉庫揀貨路徑的所述揀貨起點，根據所述揀貨起點對所述最優路徑進行修改，生成最優揀貨路徑；

其中，所述根據所述揀貨起點對所述最優路徑進行修改包括：

當實際揀貨起點在最優路徑中處于非首尾節點時，以所述實際揀貨起點為原點選擇順時針遍歷或逆時針遍歷兩個方案中路徑最短的方案，生成最終的遍歷方案。

2.如權利要求1所述的揀貨路徑規劃方法，其特征在于，所述獲取歷史最優路徑包括根據S型策略方法獲取遍歷所述節點的歷史最優路徑。

3.如權利要求1所述的揀貨路徑規劃方法，其特征在于，還包括：

將螞蟻經過的所述節點計入與該螞蟻對應的禁忌表中；

在判斷沒有路徑被連續k次選擇為當前最優路徑時，清空所述禁忌表與所述當前最優路徑，重新啟動所述螞蟻的路徑遍歷循環。

4.如權利要求1所述的揀貨路徑規劃方法，其特征在于，所述計算所述螞蟻轉移到其他所述節點的轉移概率包括通過以下公式計算：

其中，為螞蟻k在第i節點上轉移到第j節點的轉移概率，t為所述路徑行走循環的次數，C為所有節點的集合，tabu_k為螞蟻k已經走過的節點，dij為i和j兩個節點之間的距離，α為取值范圍為[0,5]的信息素指數，β為取值范圍為[0,5]的啟發式因子指數，τ_ij為節點i和j之間路徑的當前信息素數值。

5.如權利要求1所述的揀貨路徑規劃方法，其特征在于，所述更新路徑的信息素數值包括通過以下公式更新：

τ_ij(t+n)＝(1-ρ)·τ_ij(t)+Δτ_ij

其中，τ_ij為節點i和j之間路徑的當前信息素數值，Δτ_ij表示更新的信息素增量，L_k表示第k只螞蟻在本次循環中所走路徑的總長度，Q表示螞蟻循環一周在經過路徑上所釋放的信息素總量，γ表示權重參數，T^bs表示當前最優路徑；L_bs表示當前最優路徑的長度，ρ表示蒸發系數。