麻雀搜索算法在物流配送中心選址的應用

阮信波 劉麗華 陳麗瑾

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

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

[中圖分類號]F224.0;F252.14[文獻標識碼]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引言

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

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

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

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

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

（2）當發現者發現捕食者時，它會向整個麻雀種群發送警報信號，當預警信號的值大于安全閾值時，作為發現者的麻雀會引導作為參與者的麻雀到其他安全區域覓食，而沒有收到預警信號的麻雀則會自由移動尋找食物資源以補充能量。

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

（4）麻雀覓食時，作為參與者的麻雀總是可以通過爭奪發現者的食物資源，在發現者周圍的區域尋到最豐富的資源和飼料。

1.1模型假設

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

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

（3）不考慮選定區域內待確定配送中心的建設成本。

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

1.2符號假設

（1）U表示總運輸成本。

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

（3）w_i表示產品從配送中心到需求點i的單位運費率。

（4）c_i表示產品從配送中心到需求點i的出貨量。

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

1.3建立模型

設有n個需求點和一個物流配送中心，物流配送中心到每個需求點需要一定的貨物量以及一定的配送費用，以待定物流配送中心到所有需求點的總體配送費用最少為目標函數建立模型如下：

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

其中，x，y分別為待定物流配送中心的橫縱坐標，x_i，y_i別為需求點i的橫縱坐標。

1.4將麻雀搜索算法應用于物流配送中心選

址問題的求解

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

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

所有麻雀的適應值F_x可以表示為：

發現者的位置更新方式如下：

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

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

1.5算法的主要步驟

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

步驟2分配發現者與參與者的數量，獲取當前最優麻雀位置和全局最優的麻雀位置，并隨機設置警戒者位置。

步驟3計算每只麻雀在當前位置的適應值，并尋出最好的個體與最壞的個體及當前適應值最優的麻雀位置與全局最優的麻雀位置。

步驟4根據式（1）—式（3）分別更新發現者與參與者的位置并更新警戒者的位置。

步驟5更新最優適應值的麻雀位置。

步驟6判斷是否結束，若結束則算法結束，否則轉步驟2。

2實例分析

問題分析：某公司要在某地區建立一個物流中心，要求各個需求到物流中心的運輸成本最小，現有需求點的數據見表1。

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

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

運行程序得到如圖1-圖4所示結果。

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

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

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

圖4表示本文算法結束時得到各個需求點與最優選址中心之間都有最小的適應值，即每個需求點到達最優選址中心都有最小的物流成本，因此得到各個需求的適應值之和到達最優選址中心也有總體最小的物流成本，其中橫坐標軸與縱坐標軸分別對應需求點與可行解的橫縱坐標。

3結果分析

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

[參考文獻]

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

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

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

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

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

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

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

[8]薛建凱.一種新型的群智能優化技術的研究與應用[D].上海：東華大學，2020.