李衛(wèi)星

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

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

關(guān)鍵詞： 灰狼優(yōu)化算法; 物流配送中心選址; 交叉變異; 雙種群尋優(yōu)

中圖分類號：U4-9? ? ? ? ? 文獻(xiàn)標(biāo)識碼：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 引言

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

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

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

1 物流配送中心選址數(shù)學(xué)模型

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

⑴ 設(shè)每個待配送點(diǎn)所需配送的貨物總量不得超過其對應(yīng)配送中心的貨物總量，否則無配送中心可以對其進(jìn)行配送，該約束的數(shù)學(xué)模型如下：

其中，[γi，j]表示第j個配送中心所對應(yīng)的第i個配送點(diǎn)的配送貨品的總量。[Tj]表示第j個配送中心的總貨品存放量。

⑵ 設(shè)在N個待配送點(diǎn)中，任意一個待配送點(diǎn)的貨品均應(yīng)由距其最近的配送中心進(jìn)行發(fā)貨，該約束的數(shù)學(xué)模型如下：

其中，[Zi，j]為配送中心選取標(biāo)志，若[Zi，j=1]，則表示第i個配送點(diǎn)的配送貨品應(yīng)由第j個配送中心進(jìn)行配送。若[Zi，j=0]，則表示第i個配送點(diǎn)的配送貨品不應(yīng)由第j個配送中心進(jìn)行配送。

⑶ 設(shè)無配送中心的區(qū)域，無配送客戶，既無待配送點(diǎn)，該約束的數(shù)學(xué)模型如下：

其中，[hj]為0或1，當(dāng)[hj]為0時，表示第j個配送點(diǎn)不可成為配送中心。當(dāng)[hj]為1時，表示第j個配送點(diǎn)可作為配送中心。

⑷ 設(shè)在N個待配送點(diǎn)中，任意一個待配送點(diǎn)i到與其對應(yīng)的第j個配送中心的距離，應(yīng)小于等于第j個配送中心點(diǎn)可配送的最大距離[Lenthmax]，該約束的數(shù)學(xué)模型如下：

根據(jù)上述約束條件，建立物流配送中心選址模型的數(shù)學(xué)表達(dá)式如下所示：

其中，[Fj]表示第j個配送中心的建設(shè)費(fèi)用。

2 改進(jìn)的灰狼優(yōu)化算法

2.1 基本灰狼優(yōu)化算法

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

其中，[i=1，2，…，NP]，[Xi]表示第[i]個灰狼個體的初始位置。首領(lǐng)狼[α]負(fù)責(zé)選定獵物目標(biāo)，既全局最優(yōu)解，并與[β]和[δ]一起對獵物發(fā)起攻擊，其數(shù)學(xué)表達(dá)式如下：

其中，[t=1，2，…，tmax]表示算法當(dāng)前迭代次數(shù)，[tmax]表示算法可執(zhí)行的最大迭代次數(shù)，[Xpt=（X1p，X2p，…，XDp）]表示獵物的當(dāng)前位置，既當(dāng)前迭代產(chǎn)生的最優(yōu)解的位置，因此灰狼優(yōu)化算法中[α]，[β]和[δ]的位置更新公式為：

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

2.2 灰狼優(yōu)化算法的改進(jìn)策略

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

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

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

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

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

具體的改進(jìn)灰狼優(yōu)化算法的尋優(yōu)流程如下。

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

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

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

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

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

Step6：計算兩個子種群中個體的適應(yīng)度函數(shù)值，并進(jìn)行信息交流和貪婪選擇，將適應(yīng)度值較優(yōu)的個體存放到子種群[S1]中，將適應(yīng)度值較差的個體存放到子種群[S2]中。

Step7：判斷是否達(dá)到最大迭代次數(shù)，若是，則跳出循環(huán)，保存最優(yōu)解。若否，則跳轉(zhuǎn)到Step3據(jù)需執(zhí)行求解流程。

3 IGWO算法在物流配送中心選址中的應(yīng)用

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)（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ìn)模擬退火算法的船舶物流配送中心選址研究[J].艦船科學(xué)技術(shù)，2020.42（16）：199-201

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

[6] 吳洋.多目標(biāo)進(jìn)化算法在物流配送中心選址中的研究與應(yīng)用[D].浙江工業(yè)大學(xué)，2020.

[7] 劉娟，劉祥偉.基于改進(jìn)的BP人工神經(jīng)網(wǎng)絡(luò)的物流配送中心選址問題研究[J].喀什大學(xué)學(xué)報，2018.39（6）：14-19

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

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