[發明專利]基于改進蟻群算法應用于物流配送的最佳路徑規劃方法

在審

• 申請號: 202011182041.9
• 申請日: 2020-10-29
• 公開（公告）號: CN112330006A
• 公開（公告）日: 2021-02-05
• 發明（設計）人: 許瓊;郝曉玲;謝季峰;王坤;李艷
• 申請（專利權）人: 西南石油大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/00;G06Q10/08
• 代理公司: 北京眾合誠成知識產權代理有限公司 11246
• 代理人: 王攀

本發明公開了路徑規劃技術領域的基于改進蟻群算法應用于物流配送的最佳路徑規劃方法，包括以下步驟：重新定義了各路徑上信息素含量的初始分配，使其不僅與路徑的長度有關，還與連接該路徑轉運點的道路選擇多樣性相關；此外本發明還對信息素更新規則重新定義，使其受迭代次數和歷史最優路徑長度的制約。通過以上措施，使得改進的蟻群算法具有較快收斂速度的同時具有較好的尋優性能，能夠快速找出最優路徑，降低了配送成本。

技術領域

本發明涉及路徑規劃技術領域，特別是針對路徑規劃問題中的蟻群算法， 具體為基于改進蟻群算法應用于物流配送的最佳路徑規劃方法。

背景技術

經典的蟻群算法在路徑規劃中存在搜索時間長，容易陷入局部最優等問 題。本發明重新定義了各路徑上信息素含量的初始分配，使其不僅與路徑的 長度有關，還與連接該路徑轉運點的道路選擇多樣性相關；此外本發明還對 信息素更新規則重新定義，使其受迭代次數和歷史最優路徑長度的制約。通 過以上措施，使得改進的蟻群算法具有較快收斂速度的同時具有較好的尋優 性能，能夠快速找出最優路徑，降低了配送成本。

發明內容

本發明的目的在于提供基于改進蟻群算法應用于物流配送的最佳路徑規 劃方法，以解決上述提到的問題。

為實現上述目的，本發明提供如下技術方案：基于改進蟻群算法應用于 物流配送的最佳路徑規劃方法，包括以下步驟：

S1：將改進蟻群算法的各項參數，包括螞蟻數目m、信息素量常量M、 最大迭代次數NC_max、信息素強度Q、信息素量的最小值τ_min和最大值τ_max進行 初始化；

S2：計算初始時刻各路徑的信息素量,路徑(i，j)上的信息素量的計算 公式為：

式(1)中，d_i為連接轉運點i的所有路徑總長度，d_j為連接轉運點j的 所有路徑總長度，d_ij為路徑(i，j)之間的距離，M為信息素量常量；

S3：將螞蟻隨機的放在初始城市，同時把該城市加入到每只螞蟻對應的 搜索禁忌表tabu_k中；

S4：螞蟻k在可選城市allowed_k范圍內按式計算將要轉移的城市，并將其 放入的對應的禁忌表tabu_k中,螞蟻k從轉運點i到轉運點j轉移的概率的計 算公式為：

式(2)中s∈allowed_k，α表示信息啟發因子，β表示期望啟發因子，表 示路徑(i，j)上的啟發式信息值，為t時刻路徑(i，j)上的殘留信息素量；

S5：如果allowed_k中還有未搜索到的城市，則繼續執行S4，否則轉向S6，

S6：更新信息素持久度ρ，其中信息素持久度ρ，計算公式為：

式(3)中NC為當前次循環的迭代次數，NC_max為最大迭代次數；

S7：更新各條路徑上的信息素濃度

蟻群在路徑節點尋優過程中，各節點的實時信息素含量范圍遵循以下規 則：

式(4)中，τ_min和τ_max為算法初始信息，規定了信息素量的最小值和最大值，

信息素濃度計算公式為: