基于混合多策略免疫算法的配送中心選址研究

摘 "要：為提升基本免疫算法的尋優性能，降低城市物流配送中心選址的成本，提出一種混合多策略免疫算法。首先，使用Tent混沌映射快速構成均勻分布的初始解，豐富種群的多樣性；其次，結合差分進化算法中的更新機制增強免疫算法的尋優能力，并使用線性增量規則平衡算法的全局和局部搜索能力；最后，采用非均勻變異策略對整個解空間進行干擾，避免算法的“早熟”現象。實驗結果表明，所提出的算法收斂速度更快，魯棒性更好，并能在短時間內給出物流成本更低的選址方案。

"關鍵詞：選址應用；免疫算法；混沌映射；差分進化；非均勻變異

"中圖分類號：TP301.6; F252.14 " "文獻標志碼：A

DOI：10.13714/j.cnki.1002-3100.2024.23.003

Abstract： In order to improve the optimization performance of the basic Immune Algorithm and reduce the cost of urban logistics distribution centre location， a Hybrid multi-strategy Immunity Algorithm is proposed. Firstly， Tent chaotic mapping is used to quickly form a uniformly distributed initial solution to enrich the diversity of the population. Second， the update mechanism in the differential evolutionary algorithm is combined to enhance the optimization search capability of the Immune Algorithm， and the linear incremental rule is used to balance the global search capability and local search capability of the algorithm. Finally， the non-uniform mutation strategy is used to interfere with the whole solution space to avoid the \"premature\" phenomenon of the algorithm. The experimental results show that the proposed location algorithm not only has faster convergence speed and better robustness， but also can give a location plan with lower logistics cost in a short time.

Key words： location application; immune algorithm; chaotic mapping; differential evolution; non uniform mutation

0 "引 nbsp;言

"隨著互聯網的浪潮，線上消費模式的飛速發展，城市配送中心的物流優化問題也更加重要。為響應習近平總書記提出的“降低物流成本，推動流通體制改革”理念[1]，眾多學者對當前影響物流的關鍵因素進行研究，通過選址來優化城市配送中心的物流成本。

目前，選址主要應用于物流配送、醫療設施、戰略軍事等領域[2-4]。選址的方法主要分為兩類，基于傳統方法和基于群智能優化算法的選址方法。傳統的選址方法主要分為定性方法[5]和定量方法[6]。定性方法主要包含層次分析法[7]、模糊評價法[8]等。定量方法主要包含重心法[9]、p-中值模型法[10]等。由于配送中心選址問題屬于復雜的多目標優化問題，傳統方法只能在一定程度上優化，很難找到最優解。群智能優化算法[11]是求解選址問題方法中的一種重要方法，主要受人類、動物群體或自然規律啟發而提出的搜索算法，在求解配送中心選址問題等多極值問題時，群智能優化算法比傳統算法更具有獨特的優勢。目前，眾多學者已經利用群智能算法對選址問題進行研究，例如禿鷹算法[12]、遺傳算法[13]、鯨魚算法[14]和免疫算法[15]等。其中，免疫算法（Immune Algorithm， IA）是六十年代提出的一種求解多目標實際問題的群智能算法，相比于其他群智能算法，免疫算法不僅模仿生物免疫系統的運行方式，還具有強大的自我調節功能，因而被廣泛應用于配送中心選址研究。Dou et al.[16]在約束條件中加入食品新鮮度和時間窗，建立冷鏈物流的配送中心選址模型，并將免疫算法的特性引入狼群算法，提高了算法的收斂速度和搜索精度，該算法降低了冷鏈物流的配送食品總成本和腐爛程度。Xu et al.[17]在研究充電站選址問題時考慮用戶滿意度和充電便利性，設計了加入停止條件和優化變異算子的免疫算法并對模型求解，相較于傳統免疫算法，該算法的穩定性和準確性均有所提高。

"盡管上述方法使免疫算法的性能有所提升，但仍存在易陷入局部最優以及解的分布性差的問題。針對此問題，本文提出一種混合多策略免疫算法（Hybrid multi-strategy Immune Algorithm， HIA），并應用于選址問題中。首先采用混沌映射均勻初始化種群，豐富種群的多樣性；其次，在免疫交叉操作中采用兩種模式的差分進化策略，并引入線性增量規則調節每種差分進化策略在算法不同迭代時期的比重，提升算法前期的全局搜索能力，并在算法后期加速收斂；最后，在免疫變異階段采用非均勻變異策略，避免造成免疫算法的“早熟”現象。

1 "城市配送中心選址問題描述

"城市配送中心選址問題可以描述為：已知一個客戶需求點的地址集合，從中選取一定數量的地址作為配送中心，建立一系列的配送區域，實現城市配送中心對各個客戶需求點高效率且低成本的配送服務。

1.1 "選址模型假設

"城市配送中心選址需要在有限個地址中滿足各個客戶位置相應的需求，為了避免建立的配送中心選址模型過于復雜，需要做出幾點假設：

"假設1：配送中心的容量不小于客戶需求點的需求量；

"假設2：政府允許建設的最大配送中心數量和建設費用為固定常數；

"假設3：單個配送中心可以同時配送其輻射范圍內的多個客戶需求點；

"假設4：一個客戶需求點只能被一個配送中心配送；

"假設5：配送中心到客戶點的運輸過程使用貨車運輸，并且貨車統一規格型號；

"假設6：不考慮城市配送中心和生產商之間的物流成本。

1.2 "選址問題模型

"基于上述的選址問題描述和模型假設，為了使物流成本最小化，本文以配送中心到客戶的距離與客戶需求量的乘積最小為目標函數構建城市配送中心數學模型。綜合考慮影響物流成本因素的配送中心選址數學模型如下：

2 "混合多策略免疫算法

2.1 "混沌分布的種群初始化結構

"在智能優化算法中，搜索空間中的初始解越均勻，越有利于算法的求解。免疫算法在初始化種群階段采取隨機分布的方式，這種初始化方法在整個解空間內是不均勻分布的，阻礙了種群多樣性。在初始化階段采用混沌映射初始化種群，可以豐富種群多樣性。

Tent混沌映射機制：

"混沌映射[18]具有隨機性，多樣性等優勢。為快速構成可行的初始解，采用混沌映射初始化種群，其以Logistic映射、ICMIC映射、Henon映射、Tent映射等為代表。

"Tent映射具有更強的遍歷性和均勻分布性。個體通過映射關系生成混沌序列，然后轉化為種群搜索空間。Tent混沌映射表達式為：

式中：μ為混沌狀態參數；μ∈0，1。免疫算法加入Tent混沌映射前后的種群分布圖如圖1和圖2所示。

通過比較圖1和圖2可以看出，加入Tent混沌映射的種群分布更加均勻，說明加入Tent混沌映射的免疫算法豐富了種群多樣性，為算法期的迭代提供一個均勻分布在0，1區間的環境。

2.2 "融合DE策略的免疫交叉操作

免疫算法的交叉操作采用隨機交叉的方式，這種方式容易導致算法的收斂速度較慢。差分進化算法中的更新機制具有更好的尋優能力，在免疫交叉操作中融合差分進化算法，可以有效提升算法的性能。

2.2.1 "差分進化策略

2.2.2 "兩種模式的差分進化策略

"DE/rand/2/bin模式在算法初期種群分布均勻且廣泛，通過擴大全局搜索的范圍，實現對整個解空間的搜索，隨著算法不斷迭代，個體大多分布在最優個體周圍，但在迭代過程中的收斂方向比較發散，導致收斂速度較慢。

DE/best/2/bin模式由基準個體引導收斂方向，收斂速度較快，但是個體與個體之間的差異性較小，算法的全局搜索能力較弱。

由于進化個體之間存在差異性，需要盡可能地探索搜索空間，在算法整個迭代過程中單一的差分進化策略對算法性能提升有限。結合兩種策略的優點將DE/rand/2/bin， DE/best/2/bin兩種進化策略引入到交叉算子中，兩種進化策略的選擇方式如下：

由式（10）可以看出，rand是0～1之間隨機產生的實數；p表示選擇不同進化策略的概率，兩種進化策略在不同時期所占比重不同，因此，p的值十分重要。

2.2.3 "線性增量規則

為了平衡算法的探索能力和開發能力，采用線性增量規則[20]，使p的值從0線性增加至1。線性增量規則的表達式如下：

式中：G表示當前迭代數；G表示最大迭代數。若隨機實數小于p，選擇DE/rand/2/bin模式的進化策略，當隨機實數大于p，此時的進化策略變為DE/best/2/bin。因此在算法迭代前期，選中基于隨機個體進化的概率就會大于選中基于最優個體進化的概率，隨著p的值逐漸從0增至1，算法迭代進入后期，選中基于最優個體進化的概率就大于選中基于隨機個體進化的概率，在增強算法搜索能力的同時加快了收斂速度。

2.3 "融合非均勻變異策略的免疫變異操作

為避免免疫算法的“早熟”現象，采用非均勻變異策略[21]。對原有的抗體位置做一個擾動，擾動后產生一個新抗體，對每個抗體都以相同方式進行操作，從而對整個解空間擾動。非均勻變異策略表達式如下：

式中：η的值隨機取0或1；G表示當前迭代次數；G示最大迭代數；rand表示0～1范圍內的隨機實數；b表示擾動對迭代次數G的依賴程度，通常隨機取2～5之間的實數。由式（13）可以看出迭代次數的增加導致結果逐漸趨近至0。

3 "配送中心選址結果及分析

3.1 "參數設置

"為驗證算法在選址問題中的有效性，選取國家基礎地理信息數據庫中的31個地址集合，并從中選取6個地址作為配送中心，其余作為客戶需求點[22]。本次實驗均在相同環境的PC機上進行，操作系統為Windows 10，CPU處理器為inter core i7

-10750H，GPU為NVIDIA GeForce GTX1650 Ti 4GB，仿真軟件為MATLAB 2014a。

"算法的參數設置如下：初始種群規模為50，記憶庫容量為10，迭代次數為200。各城市坐標及客戶需求量如表1所示。

3.2 "算法驗證

"本文選用自適應粒子群算法（APSO）[23]、基本免疫算法（IA）[24]、偽反向蜘蛛猴算法（LOBSMO）[25]作為對比方法。圖3至圖6為本文方法及其對比方法的城市配送中心選址方案結果圖，其中，綠色節點表示客戶需求點，藍色方框表示配送中心地址，節點旁邊的數字表示城市序號。

"從圖3至圖6中可以看出，四種算法求解的配送中心選址結果不盡相同，IA算法的選址結果為9，27，5，18，25，14，LOBSMO算法的選址結果為12，5，27，17，20，9，APSO算法的選址結果為31，18，5，12，25，9，而本文算法（HIA）所求解的選址結果為9，25，17，29，28，5。本文及其對比方法的具體選址方案如表2所示。

通過對比四種算法的物流成本和迭代次數來驗證算法在選址問題中的可行性，各算法收斂曲線如圖7所示。

根據圖7可知，HIA算法由于融合了差分變異策略，相較于IA算法、APSO算法和LOBSMO算法，HIA算法能以更快的速度達到最優值，且結果優于其他算法，證明該算法在求解選址問題時具有更好的尋優能力。具體物流成本和迭代次數如表3所示。

從表3中的結果可以看出，HIA算法以最少的迭代次數達到最低物流成本，說明該算法的尋優能力最強。與IA算法、APSO算法和LOBSMO算法相比，成本分別降低3.91%、2.25%和0.69%，說明該算法求解選址問題時更具合理性。

為進一步驗證算法的收斂性能和魯棒性，將各算法結果的平均值和標準差進行對比，其四種算法性能指標對比如表4所示。

由表4可知，以標準差指標為例，與其他三種選址算法相比，HIA算法分別下降71.20%、71.17%、69.34%，說明HIA算法可以更穩定地搜索到最優值。同時HIA算法的平均值數據指標也最小，說明本文算法在收斂方面也具有良好的性能。

4 "結 "論

合理的城市配送中心選址方案可以有效地降低物流成本，提高配送效率。針對智能算法在求解城市配送中心選址問題的局限性和分布性差等缺點，提出一種混合多策略免疫算法：（1）在初始化種群階段，采用Tent混沌映射策略快速構成均勻分布的可行解；（2）在交叉操作階段，引入差分進化策略并采用線性增量規則動態調節不同策略在不同時期的占比，增強全局搜索能力并加快收斂速度；（3）在變異操作階段，采用非均勻變異策略進一步收斂，提高解的質量。實驗結果表明，用改進后的算法求解城市配送中心選址問題所得的選址結果具有合理性，為解決復雜的組合優化問題提供了一種有效的方案。

參考文獻：

[1] 張誠，劉守臣. 多樞紐混合軸輻式鐵路冷鏈物流網絡布局優化研究[J]. 鐵道學報，2021，43（7）：1-9.

[2] 衛振林，李世龍. 城市配送中心布局政府干預機制研究[J]. 交通運輸系統工程與信息，2019，19（5）：7-12.

[3] 楊雨蕾，張錦，孫文杰，等. 動態需求下的基于醫藥前置倉的選址-路徑問題[J]. 控制與決策，2023，38（6）：1670-1678.

[4] "DU J， ZHAN H， DU L. Research on site selection and algorithm of military logistics center[C] // Journal of Physics： Conference Series. IOP Publishing， 2021.

[5] 李浩光，于云華，逄燕，等. 粒子群算法的近紅外光譜定性分析預處理及特征提取參數優化方法研究[J]. 光譜學與光譜分析，2021，41（9）：6.

[6] 王海萍，張鵬飛，徐琢頻，等. LIBS結合VDPSO-CMW算法的高粱Na和Fe定量方法研究[J]. 光譜學與光譜分析，2023，43（3）：823-829.

[7] "VAHIDNIA M H， VAHIDI H， HASSANABAD M G， et al. A spatial decision support system based on a hybrid AHP and TOPSIS Method for fire station site selection[J]. Journal of Geovisualization and Spatial Analysis， 2022，6（2）：30.

[8] "ZHOU Y， QIN X， LI C， et al. An intelligent site selection model for hydrogen refueling stations based on fuzzy comprehensive evaluation and artificial neural network—A case study of Shanghai[J]. Energies， 2022，15（3）：1098.

[9] "CAI C， LUO Y， CUI Y， et al. Solving multiple distribution center location allocation problem using K-means algorithm and center of gravity method take Jinjiang district of Chengdu as an example[C] // IOP Conference Series： Earth and Environmental Science. IOP Publishing， 2020.

[10] "MLADENOVIC N， BRIMBERG J， HANSEN P， et al. The p-median problem： A survey of metaheuristic approaches[J]. European Journal of Operational Research， 2007，179（3）：927-939.

[11] "BRYAN ACOSTA-ANGULO， JENNYFER DIAZ-ANGULO， JOSE LARA-RAMOS， et al. Analysis of the applications of particle swarm optimization and genetic algorithms on reaction kinetics： A prospective study for advanced oxidation processes[J]. Chem Electro Chem， 2022（13）：9.

[12] "ALSATTAR H A， ZAIDAN A A， ZAIDAN B B. Novel meta-heuristic bald eagle search optimisation algorithm[J]. Artificial Intelligence Review： An International Science and Engineering Journal， 2020，53（8）：2237-2264.

[13] 唐俊林，張棟，王孟陽，等. 改進鏈式多種群遺傳算法的防空火力任務分配[J]. 哈爾濱工業大學學報，2022，54（6）：19-27.

[14] "PRAKASH D B， LAKSHMINARAYANA C. Optimal siting of capacitors in radial distribution network using whale optimization algorithm[J]. Alexandria Engineering Journal， 2017，56（4）：99-509.

[15] 張立寧，胡偉晨，王新安，等. 基于免疫算法的鐵電場效應晶體管多態門設計方法[J]. 電子與信息學報，2023，45（10）：1-9.

[16] "DOU S， LIU G， YANG Y. A new hybrid algorithm for cold chain logistics distribution center location problem[J]. IEEE Access， 2020，8：88769-88776.

[17] "XU D， PEI W， ZHANG Q. Optimal planning of electric-vehicle charging stations considering user satisfaction and charging convenience[J]. Energies， 2022，15（14）：5027.

[18] "LI Y， HAN M， GUO Q. Modified whale optimization algorithm based on tent chaotic mapping and its application in structural optimization[J]. KSCE Journal of Civil Engineering， 2020，24（12）：3703-3713.

[19] 劉會宇，韓繼紅，袁霖，等. 基于雙變異策略的自適應骨架差分進化算法[J]. 通信學報，2017，38（8）：201-212.

[20] "LI X T， YIN M H. Modified differential evolution with self-adaptive parameters method[J]. Journal of Combinatorial Optimization， 2016，31（2）：546-576.

[21] 陳忠云，張達敏，辛梓蕓. 多子群的共生非均勻高斯變異樽海鞘群算法[J]. 自動化學報，2022，48（5）：1307-1317.

[22] 李蘇杭，黃晨晨，王勛寶，等. 一種基于輪盤賭策略的防空部署方法[J]. 空天防御，2022，5（2）：42-48.

[23] 周策，白斌，葉楠. 自適應粒子群優化支持向量回歸的工程系統可靠性預測[J]. 機械工程學報，2023，59（14）：328-338.

[24] "SU Y， LUO N， LIN Q， et al. Many-objective optimization by using an immune algorithm[J]. Swarm and Evolutionary Computation， 2022（69）：69.

[25] 徐小平，楊轉，劉龍. 求解物流配送中心選址問題的蜘蛛猴算法[J]. 計算機工程與應用，2020，56（1）：150-157.