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

李衛(wèi)星

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

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

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

中圖分類號(hào)：U4-9? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? 文章編號(hào)：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)化兩個(gè)方面，其中配送中心選址模型優(yōu)化是提高配送效率的核心問題[2]。配送中心位置的合理選取，可以有效地節(jié)約配送路徑，降低配送時(shí)間，節(jié)約配送成本。物流配送中心選址模型是一類具有多約束和非線性的復(fù)雜數(shù)學(xué)模型，各約束之間具有耦合性，因此眾多學(xué)者開始針對(duì)此問題進(jìn)行了深入的研究。

文獻(xiàn)[3]提出一種基于主動(dòng)集算法的配送中心選址策略，在主動(dòng)集算法中加入懲罰函數(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)化算法的物流配送中心選址策略，該策略在考慮配送成本的同時(shí)，對(duì)配送時(shí)間做出約束，通過動(dòng)態(tài)領(lǐng)域分配策略對(duì)算法進(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聚類方法對(duì)配送中心的聚類單元進(jìn)行計(jì)算，并求解均值，最終得到配送中心的位置。以上策略均從不同方面對(duì)優(yōu)化算法進(jìn)行改進(jìn)，提高了算法的收斂精度，但是單一機(jī)制的人工智能算法難以有效應(yīng)用于復(fù)雜多約束非線性模型的求解問題上，這是由于單一機(jī)制的優(yōu)化算法在迭代后期會(huì)逐漸喪失種群多樣性，陷入早熟收斂陷入局部最優(yōu)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中，[i=1，2，…，NP]，[Xi]表示第[i]個(gè)灰狼個(gè)體的初始位置。首領(lǐng)狼[α]負(fù)責(zé)選定獵物目標(biāo)，既全局最優(yōu)解，并與[β]和[δ]一起對(duì)獵物發(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]為控制因子。此外，由于灰狼個(gè)體中的其余個(gè)體[ω]均會(huì)圍繞[α]，[β]和[δ]的位置進(jìn)行小范圍運(yùn)動(dòng)，以待尋找更優(yōu)的解，因此灰狼優(yōu)化算法中[ω]的位置更新公式為：

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

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

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

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

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

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

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

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

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

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

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

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

Step6：計(jì)算兩個(gè)子種群中個(gè)體的適應(yīng)度函數(shù)值，并進(jìn)行信息交流和貪婪選擇，將適應(yīng)度值較優(yōu)的個(gè)體存放到子種群[S1]中，將適應(yīng)度值較差的個(gè)體存放到子種群[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算法中，每一個(gè)灰狼個(gè)體的每個(gè)維度上的解均標(biāo)志一個(gè)配送點(diǎn)，每一個(gè)灰狼個(gè)體均代表一個(gè)所求解，既優(yōu)化所得配送中心地址。設(shè)每一個(gè)灰狼個(gè)體可表示為[X=x1，x2，…，xN]，其中[N]為物流配送點(diǎn)。設(shè)物流配送中心選址模型中，具有8個(gè)配送點(diǎn)，并將在8個(gè)配送點(diǎn)中選擇3個(gè)作為配送中心，若[X=1，0，0，1，1，0，0，0]則表示將第1，4，5個(gè)配送點(diǎn)作為配送中心。

為了驗(yàn)證本文所提IGWO算法具有較強(qiáng)的搜索精度和優(yōu)化能力，可以用于求解物流配送中心選址模型，本文選擇30個(gè)目標(biāo)城市的經(jīng)緯度城市坐標(biāo)作為配送點(diǎn)，記錄其貨品需求量，具體信息如表1所示。通過IGWO算法對(duì)模型進(jìn)行求解，將求解結(jié)果與改進(jìn)模擬退火算法的求解結(jié)果[4]以及BP人工神經(jīng)網(wǎng)絡(luò)算法的求解結(jié)果[7]進(jìn)行對(duì)比驗(yàn)證。實(shí)驗(yàn)結(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的對(duì)比求解結(jié)果可知，相較其他兩種算法的求解結(jié)果而言，本文所提改進(jìn)灰狼優(yōu)化算法求解的物流配送路徑最短，為5325.9KM，說明本文IGWO算法具有較高的收斂精度，求解的配送中心地址，很大程度的降低了配送距離，節(jié)約了配送成本，提高了配送效率。此外，通過算法的求解時(shí)間可知，本文IGWO算法的求解時(shí)間僅為10.4s，并且在第22次迭代可收斂的穩(wěn)態(tài)，說明本文IGWO算法相較其他兩種優(yōu)化算法而言，計(jì)算時(shí)間最短，算法的初值尋優(yōu)精度更高，收斂速度更快，更適用于物流配送中心選址模型的計(jì)算優(yōu)化。

4 結(jié)束語

本文針對(duì)物流配送中心選址模型具有非線性和多約束性能以優(yōu)化的問題，提出一種改進(jìn)的灰狼優(yōu)化算法的求解策略。通過將基本灰狼優(yōu)化算法與遺產(chǎn)算法相結(jié)合，改進(jìn)后的灰狼優(yōu)化算法不再通過單一機(jī)制進(jìn)行尋優(yōu)，并且豐富了算法的種群多樣性，提高了算法跳出局部最優(yōu)的能力。為避免算法在迭代后期陷入尋優(yōu)停滯，通過雙種群策略對(duì)算法進(jìn)行改進(jìn)，提高了算法的尋優(yōu)速度。最后將改進(jìn)的灰狼算法優(yōu)化物流配送中心選址模型，實(shí)驗(yàn)結(jié)果證明，IGWO算法很大程度的縮短了配送里程，降低了配送成本，節(jié)約了配送時(shí)間，這也驗(yàn)證了該算法具有較高的全局搜索精度和優(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] 李銳，李曉會(huì)，陳鑫.可靠性綠色物流配送選址-路徑問題研究[J].計(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é)報(bào)，2018.39（6）：14-19

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

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