雙種群灰狼優化算法的物流配送中心選址策略

李衛星

DOI：10.16644/j.cnki.cn33-1094/tp.2021.11.007

摘? 要： 針對物流配送中心選址模型具有多約束和非線性的特點，導致難以求解的問題。提出一種改進灰狼優化算法的求解策略。文章通過引入交叉變異策略，改進了傳統灰狼算法在迭代后期易早熟收斂的問題;通過加入雙種群尋優策略，豐富了灰狼算法的種群多樣性，提高了算法的收斂速度。將改進后的灰狼算法針對物流配送中心選址模型進行求解，實驗結果表明，該改進灰狼優化算法具有較高的全局搜索能力，針對物流配送中心選址模型具有較高的搜索精度，很大程度的提高了物流配送效率。

關鍵詞： 灰狼優化算法; 物流配送中心選址; 交叉變異; 雙種群尋優

中圖分類號：U4-9? ? ? ? ? 文獻標識碼：A? ? 文章編號：1006-8228（2021）11-25-04

Location selection strategy of logistics distribution center based on

dual population grey wolf optimizer

Li Weixing

（Taiyuan City Vocational College， Taiyuan， Shanxi 030027， China）

Abstract： Aiming at the problem that the location model of logistics distribution center has the characteristics of multi constraints and nonlinearity， which is difficult to be solved， an improved gray wolf optimizer（GWO） is proposed. In this paper， by introducing the cross mutation strategy， the issue of premature convergence of the traditional GWO in the later stage of iteration is improved; by adding the dual population optimization strategy， the population diversity of GWO is enriched and the convergence speed of the algorithm is increased. Using the improved GWO to solve the location model of logistics distribution center， the experimental results show that the improved GWO has high global search ability， and high search accuracy for the logistics distribution center location model， which greatly improves the logistics distribution efficiency.

Key words： gray wolf optimizer; location of logistics distribution center; cross mutation; double population optimization

0 引言

隨著網絡經濟的迅速發展，線上購物在人們生活中的普及程度也越來越高，物流配送產業隨之成為了國家的重點產業之一[1]。物流配送的主要內容分為配送中心選址模型優化和物流配送路徑優化兩個方面，其中配送中心選址模型優化是提高配送效率的核心問題[2]。配送中心位置的合理選取，可以有效地節約配送路徑，降低配送時間，節約配送成本。物流配送中心選址模型是一類具有多約束和非線性的復雜數學模型，各約束之間具有耦合性，因此眾多學者開始針對此問題進行了深入的研究。

文獻[3]提出一種基于主動集算法的配送中心選址策略，在主動集算法中加入懲罰函數，增強算法的全局收斂性，優化后求解所得配送中心位置使配送成本最小化。文獻[4]提出一種改進模擬退火算法的物流配送中心選址策略，通過加入粒子群算法提高算法的收斂精度，提高了求解配送中心模型的優化速度。文獻[5]提出一種改進帝國算法的配送中心選址策略，在優化選址模型的過程中考慮了運輸油耗的成本花費和二氧化碳排場污染的兩類約束。文獻[6]提出一種多目標進化算法的物流配送中心選址策略，該策略在考慮配送成本的同時，對配送時間做出約束，通過動態領域分配策略對算法進行改進，提高了配送中心選址模型優化的求解精度。文獻[7]提出一種改進神經網絡配送中心選址模型優化策略，節約了配送成本，提高了配送效率。文獻[8]提出一種基于K-means聚類方法的物流配送中心選址策略，通過K-means聚類方法對配送中心的聚類單元進行計算，并求解均值，最終得到配送中心的位置。以上策略均從不同方面對優化算法進行改進，提高了算法的收斂精度，但是單一機制的人工智能算法難以有效應用于復雜多約束非線性模型的求解問題上，這是由于單一機制的優化算法在迭代后期會逐漸喪失種群多樣性，陷入早熟收斂陷入局部最優。

針對上述問題，本文提出一種基于雙種群交叉變異灰狼優化算法的物流配送中心選址策略。針對基本灰狼優化算法在迭代后期易早熟收斂的問題，通過引入交叉變異策略，使得灰狼個體在迭代后期可以獲得外部擾動力，幫助粒子跳出局部最優，同時將灰狼種群分成兩個子種群，提高基本灰狼算法[9]的全局搜索能力。最后將改進灰狼優化算法求解物流配送中心選址模型。

1 物流配送中心選址數學模型

對于物流配送中心選址模型而言，設待配送點的個數為N，則需從N個待配送點中，合理的選取M個配送點，作為配送中心，使得配送車輛從M個配送中心出發，到達配送中心對應的配送點距離最短。由于所處地理位置不同，每個配送中心的建設費用以及存放貨物的總量不同，因此本文建立了帶有多約束條件的物流配送中心選址模型。

⑴ 設每個待配送點所需配送的貨物總量不得超過其對應配送中心的貨物總量，否則無配送中心可以對其進行配送，該約束的數學模型如下：

其中，[γi，j]表示第j個配送中心所對應的第i個配送點的配送貨品的總量。[Tj]表示第j個配送中心的總貨品存放量。

⑵ 設在N個待配送點中，任意一個待配送點的貨品均應由距其最近的配送中心進行發貨，該約束的數學模型如下：

其中，[Zi，j]為配送中心選取標志，若[Zi，j=1]，則表示第i個配送點的配送貨品應由第j個配送中心進行配送。若[Zi，j=0]，則表示第i個配送點的配送貨品不應由第j個配送中心進行配送。

⑶ 設無配送中心的區域，無配送客戶，既無待配送點，該約束的數學模型如下：

其中，[hj]為0或1，當[hj]為0時，表示第j個配送點不可成為配送中心。當[hj]為1時，表示第j個配送點可作為配送中心。

⑷ 設在N個待配送點中，任意一個待配送點i到與其對應的第j個配送中心的距離，應小于等于第j個配送中心點可配送的最大距離[Lenthmax]，該約束的數學模型如下：

根據上述約束條件，建立物流配送中心選址模型的數學表達式如下所示：

其中，[Fj]表示第j個配送中心的建設費用。

2 改進的灰狼優化算法

2.1 基本灰狼優化算法

基本灰狼優化算法作為一類新型元啟發人工智能優化算法，將種群中的全部灰狼個體分四個等級，其中等級最高的作為首領狼，記為[α]。首領狼負責決策狼群中的各項事務，在算法中表現為決定種群的移動方向。第二等級的狼負責協助首領狼對各項事務就行決策，記為[β]。第三等級的狼負責整個狼群的狩獵以及防御外敵，記為[δ]。等級最低的狼負責協助[α]，[β]和[δ]三個等級狼完成任務，可記為[ω]。因此設灰狼群體的種群規模為[NP]，維數為[ND]，對灰狼群體中的全部個體進行位置初始化，其數學表達式如下：

其中，[i=1，2，…，NP]，[Xi]表示第[i]個灰狼個體的初始位置。首領狼[α]負責選定獵物目標，既全局最優解，并與[β]和[δ]一起對獵物發起攻擊，其數學表達式如下：

其中，[t=1，2，…，tmax]表示算法當前迭代次數，[tmax]表示算法可執行的最大迭代次數，[Xpt=（X1p，X2p，…，XDp）]表示獵物的當前位置，既當前迭代產生的最優解的位置，因此灰狼優化算法中[α]，[β]和[δ]的位置更新公式為：

其中，[rand1]和[rand2]為0到1之間的隨機數，[a]為控制因子。此外，由于灰狼個體中的其余個體[ω]均會圍繞[α]，[β]和[δ]的位置進行小范圍運動，以待尋找更優的解，因此灰狼優化算法中[ω]的位置更新公式為：

2.2 灰狼優化算法的改進策略

從基本灰狼優化算法的位置更新策略可知，部分灰狼個體會在局部極值點附近進行小范圍精確搜索，以期尋找位置更優的全局極值點，此類尋優策略可提高灰狼算法的局部搜索能力。但其缺陷在于算法在迭代后期，種群中的全部個體均在尋優過程中向局部極值點靠近，導致群體在尋優過程中極大程度的喪失群體多樣性，導致粒子早熟收斂，陷入局部最優，降低了算法的全局搜索能力。

針對上述問題，本文考慮了一種遺傳算法與基本灰狼算法相結合的改進算法，目的是幫助陷入局部極值的個體獲得一個較大的擾動力，幫助粒子跳出局部最優。在基本灰狼優化算法中加入交叉變異策略，使得灰狼個體在迭代過程中，均會進行不同范圍的隨機搜索，并且此類搜索過程具有一定的方向指引性可以有效提高算法的全局搜索能力，加快算法在迭代前期的搜索速度。二項式交叉的數學表達式如下：

其中，[θ1=0.35]表示交叉因子，[rand（）]表示[0，1]之間的隨機數。[Xti，j]表示第[i]個灰狼個體的第[j]維分量，[Vti，j]表示灰狼個體[Xti，j]進行二項式變異后所得到的位置。二項式變異的數學表達式為：

其中，[Xts1，j]、[Xts2，j]，[Xts3，j]分別表示第[t]次迭代過程中產生的三個位置互異的三個灰狼個體，[θ2=0.45]為變異因子。

加入較差變異策略后，雖然可以有效提高算法的全局搜索能力，但在迭代后期，由于計算量過大，會導致算法計算停滯。針對上述問題，本文考慮一類雙種群信息交流尋優策略。該策略將[NP]個灰狼個體平均分成兩個子種群，分別為[S1]和[S2]，子種群[S1]按照基本灰狼優化算法的位置更新策略進行尋優，子種群[S2]按照加入交叉變異后的灰狼優化算法進行位置更新，并在每次迭代過程中，對兩個子種群進行信息交流和貪婪選擇，將適應度值較優的個體交換到子種群1中，將適應度值較差的個體交換到子種群2中。

具體的改進灰狼優化算法的尋優流程如下。

Step1：初始化種群中[NP]個灰狼個體的初始位置，設置維數[ND]和最大迭代次數[tmax]，設置變異因子[θ2=0.45]，交叉因子[θ1=0.35]。

Step2：將種群平均分為兩個子種群[S1]和[S2]。

Step3：計算兩個子種群[S1]和[S2]中灰狼個體的適應度，并進行排序，選擇出[α]，[β]，[δ]和[ω]。

Step4：對種群[S1]中的個體按照式⑻、式⑼和式⑽進行位置更新，既按照基本灰狼算法進行尋優。

Step5：對種群[S2]中的個體按照式⑻、式⑼和式⑽進行位置更新后，通過式⑾和式⑿對個體進行交叉變異操作，并對所得解進行邊界處理。

Step6：計算兩個子種群中個體的適應度函數值，并進行信息交流和貪婪選擇，將適應度值較優的個體存放到子種群[S1]中，將適應度值較差的個體存放到子種群[S2]中。

Step7：判斷是否達到最大迭代次數，若是，則跳出循環，保存最優解。若否，則跳轉到Step3據需執行求解流程。

3 IGWO算法在物流配送中心選址中的應用

本文將改進灰狼優化算法（Improved Gray Wolf Optimization， IGWO）用于優化物流配送中心選址模型。IGWO算法中，每一個灰狼個體的每個維度上的解均標志一個配送點，每一個灰狼個體均代表一個所求解，既優化所得配送中心地址。設每一個灰狼個體可表示為[X=x1，x2，…，xN]，其中[N]為物流配送點。設物流配送中心選址模型中，具有8個配送點，并將在8個配送點中選擇3個作為配送中心，若[X=1，0，0，1，1，0，0，0]則表示將第1，4，5個配送點作為配送中心。

為了驗證本文所提IGWO算法具有較強的搜索精度和優化能力，可以用于求解物流配送中心選址模型，本文選擇30個目標城市的經緯度城市坐標作為配送點，記錄其貨品需求量，具體信息如表1所示。通過IGWO算法對模型進行求解，將求解結果與改進模擬退火算法的求解結果[4]以及BP人工神經網絡算法的求解結果[7]進行對比驗證。實驗結果如表2、圖1、圖2和圖3所示。BP人工神經網絡算法和改進模擬退火算法的算法參數詳見文獻[7]和文獻[4]。三種算法的迭代次數均為100。

從表2、圖1、圖2和圖3的對比求解結果可知，相較其他兩種算法的求解結果而言，本文所提改進灰狼優化算法求解的物流配送路徑最短，為5325.9KM，說明本文IGWO算法具有較高的收斂精度，求解的配送中心地址，很大程度的降低了配送距離，節約了配送成本，提高了配送效率。此外，通過算法的求解時間可知，本文IGWO算法的求解時間僅為10.4s，并且在第22次迭代可收斂的穩態，說明本文IGWO算法相較其他兩種優化算法而言，計算時間最短，算法的初值尋優精度更高，收斂速度更快，更適用于物流配送中心選址模型的計算優化。

4 結束語

本文針對物流配送中心選址模型具有非線性和多約束性能以優化的問題，提出一種改進的灰狼優化算法的求解策略。通過將基本灰狼優化算法與遺產算法相結合，改進后的灰狼優化算法不再通過單一機制進行尋優，并且豐富了算法的種群多樣性，提高了算法跳出局部最優的能力。為避免算法在迭代后期陷入尋優停滯，通過雙種群策略對算法進行改進，提高了算法的尋優速度。最后將改進的灰狼算法優化物流配送中心選址模型，實驗結果證明，IGWO算法很大程度的縮短了配送里程，降低了配送成本，節約了配送時間，這也驗證了該算法具有較高的全局搜索精度和優化能力，可以快速的選擇出合理的物流配送中心地址。

參考文獻（References）：

[1] Zhang Q， Hong L. Location of logistics distribution center?with grey demand and grey production capacity based on hybrid PSO.[C]// IEEE International Conference on Systems Man and Cybernetics.IEEE，2010.

[2] GuanghuaW， Zhanjiang S. Application of AHP and Steiner tree problem in the location-selection of logistics' distribution center[C]// International Conference on Networking and Digital Society. IEEE，2010.

[3] Y. Abo-Elnaga and B. El-Sobky and L. Al-Naser. Anactive-set trust-region algorithm for solving warehouse location problem[J]. Journal of Taibah University for Science，2017.11（2）：353-358

[4] 劉婧.基于改進模擬退火算法的船舶物流配送中心選址研究[J].艦船科學技術，2020.42（16）：199-201

[5] 李銳，李曉會，陳鑫.可靠性綠色物流配送選址-路徑問題研究[J].計算機工程與應用，2020.56（23）：237-244

[6] 吳洋.多目標進化算法在物流配送中心選址中的研究與應用[D].浙江工業大學，2020.

[7] 劉娟，劉祥偉.基于改進的BP人工神經網絡的物流配送中心選址問題研究[J].喀什大學學報，2018.39（6）：14-19

[8] 王勇，黃思奇，劉永，許茂增.基于K-means聚類方法的物流多配送中心選址優化研究[J].公路交通科技，2020.37（1）：141-148

[9] 向子權，楊家其，李慧琳，梁學恒.基于離散灰狼算法的資源分配問題求解[J/OL].華中科技大學學報（自然科學版）：1-5[2021-05-07].