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

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

"關(guān)鍵詞：選址應(yīng)用；免疫算法；混沌映射；差分進(jìn)化；非均勻變異

"中圖分類號(hào)：TP301.6; F252.14 " "文獻(xiàn)標(biāo)志碼：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;言

"隨著互聯(lián)網(wǎng)的浪潮，線上消費(fèi)模式的飛速發(fā)展，城市配送中心的物流優(yōu)化問(wèn)題也更加重要。為響應(yīng)習(xí)近平總書記提出的“降低物流成本，推動(dòng)流通體制改革”理念[1]，眾多學(xué)者對(duì)當(dāng)前影響物流的關(guān)鍵因素進(jìn)行研究，通過(guò)選址來(lái)優(yōu)化城市配送中心的物流成本。

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

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

1 "城市配送中心選址問(wèn)題描述

"城市配送中心選址問(wèn)題可以描述為：已知一個(gè)客戶需求點(diǎn)的地址集合，從中選取一定數(shù)量的地址作為配送中心，建立一系列的配送區(qū)域，實(shí)現(xiàn)城市配送中心對(duì)各個(gè)客戶需求點(diǎn)高效率且低成本的配送服務(wù)。

1.1 "選址模型假設(shè)

"城市配送中心選址需要在有限個(gè)地址中滿足各個(gè)客戶位置相應(yīng)的需求，為了避免建立的配送中心選址模型過(guò)于復(fù)雜，需要做出幾點(diǎn)假設(shè)：

"假設(shè)1：配送中心的容量不小于客戶需求點(diǎn)的需求量；

"假設(shè)2：政府允許建設(shè)的最大配送中心數(shù)量和建設(shè)費(fèi)用為固定常數(shù)；

"假設(shè)3：?jiǎn)蝹€(gè)配送中心可以同時(shí)配送其輻射范圍內(nèi)的多個(gè)客戶需求點(diǎn)；

"假設(shè)4：一個(gè)客戶需求點(diǎn)只能被一個(gè)配送中心配送；

"假設(shè)5：配送中心到客戶點(diǎn)的運(yùn)輸過(guò)程使用貨車運(yùn)輸，并且貨車統(tǒng)一規(guī)格型號(hào)；

"假設(shè)6：不考慮城市配送中心和生產(chǎn)商之間的物流成本。

1.2 "選址問(wèn)題模型

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

2 "混合多策略免疫算法

2.1 "混沌分布的種群初始化結(jié)構(gòu)

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

Tent混沌映射機(jī)制：

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

"Tent映射具有更強(qiáng)的遍歷性和均勻分布性。個(gè)體通過(guò)映射關(guān)系生成混沌序列，然后轉(zhuǎn)化為種群搜索空間。Tent混沌映射表達(dá)式為：

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

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

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

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

2.2.1 "差分進(jìn)化策略

2.2.2 "兩種模式的差分進(jìn)化策略

"DE/rand/2/bin模式在算法初期種群分布均勻且廣泛，通過(guò)擴(kuò)大全局搜索的范圍，實(shí)現(xiàn)對(duì)整個(gè)解空間的搜索，隨著算法不斷迭代，個(gè)體大多分布在最優(yōu)個(gè)體周圍，但在迭代過(guò)程中的收斂方向比較發(fā)散，導(dǎo)致收斂速度較慢。

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

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

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

2.2.3 "線性增量規(guī)則

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

式中：G表示當(dāng)前迭代數(shù)；G表示最大迭代數(shù)。若隨機(jī)實(shí)數(shù)小于p，選擇DE/rand/2/bin模式的進(jìn)化策略，當(dāng)隨機(jī)實(shí)數(shù)大于p，此時(shí)的進(jìn)化策略變?yōu)镈E/best/2/bin。因此在算法迭代前期，選中基于隨機(jī)個(gè)體進(jìn)化的概率就會(huì)大于選中基于最優(yōu)個(gè)體進(jìn)化的概率，隨著p的值逐漸從0增至1，算法迭代進(jìn)入后期，選中基于最優(yōu)個(gè)體進(jìn)化的概率就大于選中基于隨機(jī)個(gè)體進(jìn)化的概率，在增強(qiáng)算法搜索能力的同時(shí)加快了收斂速度。

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

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

式中：η的值隨機(jī)取0或1；G表示當(dāng)前迭代次數(shù)；G示最大迭代數(shù)；rand表示0～1范圍內(nèi)的隨機(jī)實(shí)數(shù)；b表示擾動(dòng)對(duì)迭代次數(shù)G的依賴程度，通常隨機(jī)取2～5之間的實(shí)數(shù)。由式（13）可以看出迭代次數(shù)的增加導(dǎo)致結(jié)果逐漸趨近至0。

3 "配送中心選址結(jié)果及分析

3.1 "參數(shù)設(shè)置

"為驗(yàn)證算法在選址問(wèn)題中的有效性，選取國(guó)家基礎(chǔ)地理信息數(shù)據(jù)庫(kù)中的31個(gè)地址集合，并從中選取6個(gè)地址作為配送中心，其余作為客戶需求點(diǎn)[22]。本次實(shí)驗(yàn)均在相同環(huán)境的PC機(jī)上進(jìn)行，操作系統(tǒng)為Windows 10，CPU處理器為inter core i7

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

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

3.2 "算法驗(yàn)證

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

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

通過(guò)對(duì)比四種算法的物流成本和迭代次數(shù)來(lái)驗(yàn)證算法在選址問(wèn)題中的可行性，各算法收斂曲線如圖7所示。

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

從表3中的結(jié)果可以看出，HIA算法以最少的迭代次數(shù)達(dá)到最低物流成本，說(shuō)明該算法的尋優(yōu)能力最強(qiáng)。與IA算法、APSO算法和LOBSMO算法相比，成本分別降低3.91%、2.25%和0.69%，說(shuō)明該算法求解選址問(wèn)題時(shí)更具合理性。

為進(jìn)一步驗(yàn)證算法的收斂性能和魯棒性，將各算法結(jié)果的平均值和標(biāo)準(zhǔn)差進(jìn)行對(duì)比，其四種算法性能指標(biāo)對(duì)比如表4所示。

由表4可知，以標(biāo)準(zhǔn)差指標(biāo)為例，與其他三種選址算法相比，HIA算法分別下降71.20%、71.17%、69.34%，說(shuō)明HIA算法可以更穩(wěn)定地搜索到最優(yōu)值。同時(shí)HIA算法的平均值數(shù)據(jù)指標(biāo)也最小，說(shuō)明本文算法在收斂方面也具有良好的性能。

4 "結(jié) "論

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

參考文獻(xiàn)：

[1] 張誠(chéng)，劉守臣. 多樞紐混合軸輻式鐵路冷鏈物流網(wǎng)絡(luò)布局優(yōu)化研究[J]. 鐵道學(xué)報(bào)，2021，43（7）：1-9.

[2] 衛(wèi)振林，李世龍. 城市配送中心布局政府干預(yù)機(jī)制研究[J]. 交通運(yùn)輸系統(tǒng)工程與信息，2019，19（5）：7-12.

[3] 楊雨蕾，張錦，孫文杰，等. 動(dòng)態(tài)需求下的基于醫(yī)藥前置倉(cāng)的選址-路徑問(wèn)題[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] 李浩光，于云華，逄燕，等. 粒子群算法的近紅外光譜定性分析預(yù)處理及特征提取參數(shù)優(yōu)化方法研究[J]. 光譜學(xué)與光譜分析，2021，41（9）：6.

[6] 王海萍，張鵬飛，徐琢頻，等. LIBS結(jié)合VDPSO-CMW算法的高粱Na和Fe定量方法研究[J]. 光譜學(xué)與光譜分析，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] 唐俊林，張棟，王孟陽(yáng)，等. 改進(jìn)鏈?zhǔn)蕉喾N群遺傳算法的防空火力任務(wù)分配[J]. 哈爾濱工業(yè)大學(xué)學(xué)報(bào)，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] 張立寧，胡偉晨，王新安，等. 基于免疫算法的鐵電場(chǎng)效應(yīng)晶體管多態(tài)門設(shè)計(jì)方法[J]. 電子與信息學(xué)報(bào)，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] 劉會(huì)宇，韓繼紅，袁霖，等. 基于雙變異策略的自適應(yīng)骨架差分進(jìn)化算法[J]. 通信學(xué)報(bào)，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] 陳忠云，張達(dá)敏，辛梓蕓. 多子群的共生非均勻高斯變異樽海鞘群算法[J]. 自動(dòng)化學(xué)報(bào)，2022，48（5）：1307-1317.

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

[23] 周策，白斌，葉楠. 自適應(yīng)粒子群優(yōu)化支持向量回歸的工程系統(tǒng)可靠性預(yù)測(cè)[J]. 機(jī)械工程學(xué)報(bào)，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] 徐小平，楊轉(zhuǎn)，劉龍. 求解物流配送中心選址問(wèn)題的蜘蛛猴算法[J]. 計(jì)算機(jī)工程與應(yīng)用，2020，56（1）：150-157.