麻雀搜索算法在物流配送中心選址的應(yīng)用

阮信波 劉麗華 陳麗瑾

[摘要]介紹了求解選址問題的麻雀搜索算法，并將該算法應(yīng)用于物流配送中心選址問題的求解，最后進(jìn)行了一個案例分析，在實(shí)例中與粒子群算法進(jìn)行對比，通過使用麻雀搜索證明該算法的有效性。

[關(guān)鍵詞]物流配送中心;選址;麻雀搜索算法

[中圖分類號]F224.0;F252.14[文獻(xiàn)標(biāo)識碼]A[文章編號]1005-152X（2021）12-0040-04

Application of Sparrow Search Algorithm in Location Selection of Logistics Distribution Center

RUAN Xinbo，LIU Lihua，CHEN Lijin

（School of Science，Guangxi University ofScience& Technology，Liuzhou 545006，China）

Abstract：In this paper，we introduced the sparrow search algorithm for solving the location problem，then applied it to the location problem of a logistics distribution center，and finally，through a case analysis，compared it with the particle swarm algorithm，which proves the effectiveness of the algorithm.

Keywords：logistics distribution center;location selection;sparrow search algorithm

0引言

已經(jīng)有很多學(xué)者就物流中心選址問題提出了很多辦法。如楊茂盛，等[1]采用重心法解決了離散模型的配送研究，劉海燕，等[2]提出了物流配送中心選址模型，杜穎[3]提出了基于聚類分析解決物流中心選址的問題，黃敏鎂[4]使用粒子群算法求解物流選址中心模型，王振中[5]研究了層次分析法在物流選址中心問題的應(yīng)用，武明帥，等[6]提出了使用布谷鳥算法解決以配送中心總成本最低為目標(biāo)函數(shù)的混合整數(shù)規(guī)劃模型的辦法，程賜勝，等[7]提出了離散粒子群算法求解城市物流節(jié)點(diǎn)選址模型，并證明該算法的有效性。

使用科學(xué)合理的方法建立一個物流配送中心可以有效地降低配送成本，并且在此基礎(chǔ)上提高物流配送的效率，同時還能提高客戶的滿意度，從而能夠間接地增加物流公司的收益。本文將使用麻雀搜索算法解決物流選址中心問題，并與粒子群算法（本文均稱為PSO算法）在實(shí)例中作對比加以驗(yàn)證該算法的有效性。

1求解選址問題的麻雀搜索算法

麻雀搜索算法[8]（Sparrow Search Algorithm，SSA）是在2020年提出的，該算法是受麻雀覓食與反捕食行為而啟發(fā)的群體智能優(yōu)化算法。在SSA中，每個優(yōu)化問題的解類似于搜索空間中的一只麻雀，每只麻雀都有各自的能量，每只麻雀的能量值使用函數(shù)適應(yīng)值來表示。其中麻雀分為發(fā)現(xiàn)者與參與者，發(fā)現(xiàn)者的適應(yīng)值通常大于參與者的適應(yīng)值，主要規(guī)則如下：

（1）有些麻雀作為發(fā)現(xiàn)者，在整個麻雀種群中具有較高的能量，它們主要負(fù)責(zé)搜尋資源充足的區(qū)域并且所有作為參與者的麻雀都是以發(fā)現(xiàn)者的位置來探查到最好的覓食區(qū)域。

（2）當(dāng)發(fā)現(xiàn)者發(fā)現(xiàn)捕食者時，它會向整個麻雀種群發(fā)送警報信號，當(dāng)預(yù)警信號的值大于安全閾值時，作為發(fā)現(xiàn)者的麻雀會引導(dǎo)作為參與者的麻雀到其他安全區(qū)域覓食，而沒有收到預(yù)警信號的麻雀則會自由移動尋找食物資源以補(bǔ)充能量。

（3）每只麻雀都能在發(fā)現(xiàn)者和參與者之間隨意切換，但兩者的比例在種群中是固定的。

（4）麻雀覓食時，作為參與者的麻雀總是可以通過爭奪發(fā)現(xiàn)者的食物資源，在發(fā)現(xiàn)者周圍的區(qū)域?qū)さ阶钬S富的資源和飼料。

1.1模型假設(shè)

（1）待定物流配送中心的庫存總能滿足需求點(diǎn)的需求。

（2）不考慮從工廠到待定物流配送中心的運(yùn)輸成本。

（3）不考慮選定區(qū)域內(nèi)待確定配送中心的建設(shè)成本。

（4）不考慮交貨時間、天氣和車輛情況。

1.2符號假設(shè)

（1）U表示總運(yùn)輸成本。

（2）用（x，y）表示待確定物流配送中心的橫坐標(biāo)和縱坐標(biāo)。

（3）w_i表示產(chǎn)品從配送中心到需求點(diǎn)i的單位運(yùn)費(fèi)率。

（4）c_i表示產(chǎn)品從配送中心到需求點(diǎn)i的出貨量。

（5）d_i表示待定配送中心與需求點(diǎn)i之間的歐式距離。

1.3建立模型

設(shè)有n個需求點(diǎn)和一個物流配送中心，物流配送中心到每個需求點(diǎn)需要一定的貨物量以及一定的配送費(fèi)用，以待定物流配送中心到所有需求點(diǎn)的總體配送費(fèi)用最少為目標(biāo)函數(shù)建立模型如下：

d_i使用歐幾里得距離公式計(jì)算，即：

其中，x，y分別為待定物流配送中心的橫縱坐標(biāo)，x_i，y_i別為需求點(diǎn)i的橫縱坐標(biāo)。

1.4將麻雀搜索算法應(yīng)用于物流配送中心選

址問題的求解

在SSA算法中，建立虛擬麻雀來尋找食物，所有麻雀的位置X可以通過以下方式來表達(dá)：

其中，m為麻雀的個數(shù)，X_j=（x_j，y_j）（j= 1，…，m）即待定最優(yōu)的物流配送中心的第j個可行解。

所有麻雀的適應(yīng)值F_x可以表示為：

發(fā)現(xiàn)者的位置更新方式如下：

參與者的位置更新公式如下：

在模擬實(shí)驗(yàn)中，隨機(jī)生成麻雀在種群中的初始位置，假設(shè)10%至20%的麻雀會意識到危險，則收到危險信號的麻雀更新它的位置如下：

1.5算法的主要步驟

步驟1初始化基本參數(shù)：麻雀搜索算法的最大迭代次數(shù)G，麻雀總數(shù)M，麻雀的發(fā)現(xiàn)者數(shù)量PD，麻雀的參與者數(shù)量M-PD，感知危險的麻雀數(shù)量SD，麻雀感知到危險信號的參數(shù)R₂。

步驟2分配發(fā)現(xiàn)者與參與者的數(shù)量，獲取當(dāng)前最優(yōu)麻雀位置和全局最優(yōu)的麻雀位置，并隨機(jī)設(shè)置警戒者位置。

步驟3計(jì)算每只麻雀在當(dāng)前位置的適應(yīng)值，并尋出最好的個體與最壞的個體及當(dāng)前適應(yīng)值最優(yōu)的麻雀位置與全局最優(yōu)的麻雀位置。

步驟4根據(jù)式（1）—式（3）分別更新發(fā)現(xiàn)者與參與者的位置并更新警戒者的位置。

步驟5更新最優(yōu)適應(yīng)值的麻雀位置。

步驟6判斷是否結(jié)束，若結(jié)束則算法結(jié)束，否則轉(zhuǎn)步驟2。

2實(shí)例分析

問題分析：某公司要在某地區(qū)建立一個物流中心，要求各個需求到物流中心的運(yùn)輸成本最小，現(xiàn)有需求點(diǎn)的數(shù)據(jù)見表1。

表1中，S_i表示10個物流需求點(diǎn)的名稱，每個需求點(diǎn)的位置使用（x_i，y_i）來表示，物流中心到各個需求點(diǎn)的運(yùn)價與需求量分別為w_i與c_i，其中i=1，…，10。

采用麻雀搜索算法求解該實(shí)例，并且與粒子群算法做對比。其中麻雀搜索算法的每只麻雀，粒子群算法的每一個粒子都稱為一個可行解，任一可行解依據(jù)位置更新公式式（1），式（2），式（3），更新一次其橫縱坐標(biāo)稱為可行解的一次算法迭代次數(shù)，可行解個體在算法開始到結(jié)束的過程中，依據(jù)位置更新公式發(fā)生橫縱坐標(biāo)變換次數(shù)的總和稱為一個可行解的算法迭代總數(shù)。麻雀搜索算法的參數(shù)設(shè)置：最大迭代次數(shù)G=1000，麻雀總數(shù)M= 100，麻雀的發(fā)現(xiàn)者數(shù)量PD = 20，感知危險的麻雀數(shù)量SD = 20，麻雀感知到危險信號的參數(shù)R₂=0.8。

運(yùn)行程序得到如圖1-圖4所示結(jié)果。

圖1表示可行解個體與需求點(diǎn)在地圖上的分布位置，其中x軸與y軸分別對應(yīng)需求點(diǎn)與可行解的橫縱坐標(biāo)，五角星表示可行解個體，圓圈表示需求點(diǎn)。

圖2表示從算法開始至結(jié)束各個可行解的算法迭代總數(shù)曲線。從中能夠看出可行解的算法迭代總數(shù)情況。SSA算法的可行解相較于PSO算法的可行解具有更少的變化，出現(xiàn)這樣情況的原因是SSA算法中擁有10%至20%的可行解（作為發(fā)現(xiàn)者的麻雀），整體的麻雀都會參照這10%至20%的可行解來更新（或稱為迭代）他們的位置，其中橫坐標(biāo)軸表示編號由1至100的可行解，縱坐標(biāo)軸表示每一個可行解的算法迭代總數(shù)。

圖3表示可行解隨著算法迭代次數(shù)的變化而不斷向最優(yōu)解趨近。從圖中可以看出，SSA算法與PSO算法的收斂曲線是十分相近的，由于PSO算法在搜索最優(yōu)解時有可能陷入局部最優(yōu)解的情況，因此SSA算法在此基礎(chǔ)上作了一些優(yōu)化，其可行解會嘗試跳出當(dāng)前已經(jīng)找到的最優(yōu)解情況并繼續(xù)尋找更好的解。SSA算法在迭代過程中如果確定了當(dāng)前的可行解就是全局最優(yōu)解時，其所有可行解都將收斂于最優(yōu)的適應(yīng)值。其中橫坐標(biāo)軸表示所有可行解在第0-1 000輪算法結(jié)束時，可行解個體的平均迭代次數(shù)?？v坐標(biāo)軸表示SSA與PSO算法的適應(yīng)值（物流成本），適應(yīng)值即為算法評估每個可行解在地圖上的好壞情況，可行解個體的適應(yīng)值越小，說明該可行解個體就越好，否則就越差。

圖4表示本文算法結(jié)束時得到各個需求點(diǎn)與最優(yōu)選址中心之間都有最小的適應(yīng)值，即每個需求點(diǎn)到達(dá)最優(yōu)選址中心都有最小的物流成本，因此得到各個需求的適應(yīng)值之和到達(dá)最優(yōu)選址中心也有總體最小的物流成本，其中橫坐標(biāo)軸與縱坐標(biāo)軸分別對應(yīng)需求點(diǎn)與可行解的橫縱坐標(biāo)。

3結(jié)果分析

運(yùn)用PSO與SSA算法求解此實(shí)例的最終結(jié)果都為（x，y）=（5.36，3.57），求解得到的最優(yōu)適應(yīng)值為55 291.68元，即說明該物流配送中心選址位置坐標(biāo)為（5.36，3.57），求得總體物流成本費(fèi)用最少。結(jié)果證實(shí)了麻雀搜索算法在解決物流配送中心選址問題是可行的，并且具有一定的擴(kuò)展性。采用麻雀搜索算法求解問題時只需要修改相關(guān)的參數(shù)即可運(yùn)用于不同的物流配送中心選址模型。

[參考文獻(xiàn)]

[1]楊茂盛，姜華.基于重心法與離散模型的配送中心選址研究[J].鐵道運(yùn)輸與經(jīng)濟(jì)，2007（7）：68-70.

[2]劉海燕，李宗平，葉懷珍.物流配送中心選址模型[J].西南交通大學(xué)學(xué)報，2000（3）：311-314.

[3]杜穎.基于聚類分析的江西省物流中心選址問題[J].中外企業(yè)家，2019（36）：227-228.

[4]黃敏鎂.粒子群算法在物流中心選址中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（4）：212-214.

[5]王振中.層次分析法在配送中心選址中的研究與應(yīng)用[J].物流工程與管理，2010，32（1）：97-100.

[6]武明帥，王巍，孫理越.基于布谷鳥搜索算法的物流配送中心選址[J].經(jīng)濟(jì)師，2021（2）：252-253，255.

[7]程賜勝，蒲云虎，高慧.基于離散粒子群算法的城市物流節(jié)點(diǎn)選址模型[J].長沙理工大學(xué)學(xué)報（自然科學(xué)版），2008（2）：20-24.

[8]薛建凱.一種新型的群智能優(yōu)化技術(shù)的研究與應(yīng)用[D].上海：東華大學(xué)，2020.