[發明專利]基于主次種群蟻群算法的物流配送路徑規劃方法

在審

• 申請號: 201611254003.3
• 申請日: 2016-12-30
• 公開（公告）號: CN108268959A
• 公開（公告）日: 2018-07-10
• 發明（設計）人: 鄒立斌;李青海;侯大勇;簡宋全
• 申請（專利權）人: 廣東精點數據科技股份有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06N3/00
• 代理公司: 北京隆源天恒知識產權代理事務所(普通合伙) 11473
• 代理人: 閆冬

1.基于主次種群蟻群算法的物流配送路徑規劃方法，其特征在于，包括以下步驟：

S1：設定參數初始值：snum為次種群的數量；mnum為次種群內部所有螞蟻的個數；τmax為主種群和所述次種群的信息素表的初始值，禁忌表Tabu的大小為snum*mnum，L為路徑距離；同時初始化參數信息素啟發因子ρ、啟發因子α、距離啟發因子β及迭代次數NC；

S2：用NC＝NC+1計數循環次數；

S3：用little_sub＝little_sbu+1計數次種群；

S4：用little_Tabu記錄所述次種群little_sub的路徑，并為所述次種群內部mnum個體設定任意的城市為起點；

S5：用ant＝ant+1計數螞蟻個體；

S6：螞蟻ant開始遍歷依據的信息表是第little_sub個種群，每個螞蟻從貨物中心出發，根據轉移概率選擇下一個城市，若滿足車輛的容量限制，則將該服務點拉入該條路徑，否則，車輛返回起點，重新開辟另一條路徑，直到完成所有服務店，完成一次遍歷，s為產生的路徑；

S7：用2opt對生成的所述路徑s進行相應的處理后，將其記錄在所述表little_Tabu中；

S8：判斷ant是否等于mnum，若相等，繼續算法，若不相等，從所述步驟S5：開始繼續算法；

S9：當所述little_sub被全部記錄滿之后，同步對所述禁忌表Tabu和所述路徑距離L進行更新；

S10：判斷所述little_sbu是否等于所述snum，若相等，繼續算法，若不相等，從所述步驟S3開始繼續算法；

S11：對所述主種群和次種群的信息素進行更新，若迭代次數NC大于最大迭代次數NC_max，則尋優結束，輸出最優路徑，否則從所述步驟S2開始繼續算法。

2.根據權利要求1所述的基于主次種群蟻群算法的物流配送路徑規劃方法，其特征在于，

所述步驟S11中，主種群信息素的更新公式如下：

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

其中，Δτ_ij(t)表示時間為t時，主種群信息素的增量，Q表示常數，ρ表示信息素增量系數，snum表示次種群數量的大小，表示次種群k里最優的螞蟻走過的路徑長度。

3.根據權利要求1所述的基于主次種群蟻群算法的物流配送路徑規劃方法，其特征在于，

所述步驟S11中，次種群信息素的更新公式如下：

其中，表示時間為t時，第k個次種群中邊(i,j)上的信息素濃度；表示時間為t時，第k個次種群中邊(i,j)上的信息素增量，mnum表示次種群內部螞蟻的數量；是表示時間為t時第k個次種群內部第mnum只螞蟻所經過的路徑長度；表示時間為t時，其他次種群分享給第k個次種群的信息素增量；snum表示次種群總量；表示時間為t時，次種群m內邊(i,j)上的信息素值；ε為一個貢獻量的系數，指的是其他次種群的貢獻，其值可以設置為ε＝1/(2×(snum-1))；表示時間為t時，主種群提供給次種群的信息素量。