鄭宏宇，唐竟超，姚光磊，熊菊霞

（廣西民族大學(xué) 數(shù)學(xué)與物理學(xué)院，廣西 南寧 530006）

0 引言

隨著新經(jīng)濟(jì)和電商平臺的日益發(fā)達(dá)，物流行業(yè)的競爭也越來越激烈?，F(xiàn)代物流配送是指商品從倉庫到需求點(diǎn)的實(shí)體運(yùn)輸過程中，按照現(xiàn)實(shí)需求，將裝卸、運(yùn)輸、流通和加工等功能有機(jī)地結(jié)合以滿足需求點(diǎn)要求的過程。在將商品從制造地運(yùn)輸?shù)叫枨蟮氐倪^程中，需要建立一個中心服務(wù)站點(diǎn)來集中配送商品。建立中心服務(wù)站點(diǎn)的主要目的是將商品有效、快捷地送達(dá)需求地點(diǎn)，這就是物流配送中心。物流配送中心在整條物流系統(tǒng)中具有著承上啟下的重要功能，是供給點(diǎn)和需求點(diǎn)之間相互聯(lián)系的關(guān)鍵紐帶。因此，如何科學(xué)、合理地選定建設(shè)配送中心的地點(diǎn)是整條物流系統(tǒng)分析中的核心內(nèi)容，同時也是物流配送體系合理運(yùn)營的基礎(chǔ)前提。在大規(guī)模連鎖經(jīng)營下，物流配送中心即連鎖公司建立的物資供應(yīng)管理中心，按照公司總店的安排及各分公司的需求，由配送中心向各分公司統(tǒng)一調(diào)配物資，利用物流配送中心大規(guī)模生產(chǎn)和高效率的配送方式減少公司的運(yùn)營成本，以便獲取最高的收益。［1］由于配送中心的選址工作是一項(xiàng)龐大的工程，且往往受到原料配送、運(yùn)輸條件等諸多因素的影響，其合理的選擇既可以節(jié)省建設(shè)和維護(hù)成本，也能保證物流系統(tǒng)高效運(yùn)作。物流配送中心規(guī)模巨大，其建設(shè)與發(fā)展不但關(guān)系到周邊地區(qū)，而且關(guān)系一個城市的經(jīng)濟(jì)發(fā)展建設(shè)以及所在地區(qū)的生態(tài)環(huán)境，［2］因而配送中心的選址設(shè)計(jì)和優(yōu)化方案具有重要的研究意義。

選址問題（Location problem，LP）［3］是運(yùn)籌學(xué)中經(jīng)典的問題之一，一般描述為在一個具有若干供應(yīng)點(diǎn)及若干需求點(diǎn)的區(qū)域內(nèi)，將一定數(shù)量的需求點(diǎn)設(shè)置為配送中心的優(yōu)化過程。［4］1964 年，Hakimi 首先提出了網(wǎng)絡(luò)上的P-中位問題（也稱P-中值問題）與P-中心問題，自此，選址理論的研究開始活躍起來。選址問題包括P-中位問題、P-中心問題和覆蓋問題三個基本問題以及多種擴(kuò)展問題。多配送中心選址問題（Multi-distribution center location problem，MDLP）屬于P-中位選址問題，且涉及的變量及約束條件較多，屬于典型的NPhard 問題［5］，以至于一些傳統(tǒng)的方法難以解決該問題。但隨著智能優(yōu)化算法的興起和多種新型啟發(fā)式仿生算法在近些年被相繼提出，多配送中心選址問題成為學(xué)者們的研究熱點(diǎn)，很多國內(nèi)外專家和學(xué)者都應(yīng)用智能優(yōu)化算法尋找選址問題的最優(yōu)解。Nong［6］采用網(wǎng)絡(luò)分析法（ANP）和優(yōu)劣解距離法相結(jié)合的方法，提出了一種支持配送中心選址的集成多準(zhǔn)則決策分析模型（Multicriteria decision making model，MCDM）。Arsalan 等人［7］基于leader-follower 模型，提出了一個雙層非線性規(guī)劃領(lǐng)域中的枚舉分支切割方法，并通過實(shí)驗(yàn)表明了算法的有效性。Thuy 等人［8］提出了一種基于球形模糊層次分析法和組合妥協(xié)解的混合MCDM 模型，并證明了該模型的有效性。劉培德等人［9］提出了一種基于二維語言相似度的聚類分析算法，并利用該算法構(gòu)建了綜合物流配送中心選址問題的多屬性群體決策求解框架。Li 等人［10］通過Q 學(xué)習(xí)步長和遺傳算子，給出了動態(tài)步長布谷鳥算法用于求解選址問題，并通過實(shí)驗(yàn)證明了該算法的性能優(yōu)勢。

本文從實(shí)際科學(xué)工程優(yōu)化問題出發(fā)，基于Anita等人提出的人工電場算法（Artificial electric field algorithm，AEFA），針對多配送中心選址模型，提出一種改進(jìn)人工電場算法（Improved artificial electric field algorithm，IAEFA）并進(jìn)行了理論分析。通過仿真實(shí)驗(yàn)，驗(yàn)證了改進(jìn)人工電場算法的良好性能。

1 待解問題和算法描述

1.1 多配送中心選址問題

多配送中心選址問題（MDLP）指的是在某個區(qū)域內(nèi)，已知有n個需求點(diǎn)，要從中選擇m(m＜n) 個作為配送中心向其余的需求點(diǎn)運(yùn)輸貨物，在滿足所有需求點(diǎn)貨物需求的前提下，最小化配送中心與其配送范圍內(nèi)需求點(diǎn)之間的運(yùn)輸費(fèi)用。［11］

為了方便多配送中心選址模型的建立，進(jìn)行如下假設(shè)：

（1） 物流配送中心的供應(yīng)量總能夠滿足需求點(diǎn)的需求量，并由其配送范圍內(nèi)的總需求量決定；

（2） 確保每個需求點(diǎn)有且僅有一個為其運(yùn)輸貨物的配送中心；

（3） 該選址模型只考慮從配送中心到需求點(diǎn)的費(fèi)用；

（4） 配送中心與需求點(diǎn)之間的距離采用二維平面的歐式距離，不考慮地面高度差異和實(shí)際道路系統(tǒng)（如交通堵塞、車輛故障等）。

基于以上假設(shè)，建立如下模型：

約束條件為：

式（1）為目標(biāo)函數(shù)；其中，Z表示總成本，即從選定的物流配送地點(diǎn)到該配送范圍內(nèi)的每個需求點(diǎn)的總運(yùn)費(fèi)；m表示物流配送中心的數(shù)量，n表示需求點(diǎn)的數(shù)量，Dk表示需求點(diǎn)的需求量，djk表示物流配送中心j到需求點(diǎn)k的距離。yjk是0，1 變量，當(dāng)yjk取值為1 時，表示需求點(diǎn)k由配送中心j配送。式（2）確保每個需求點(diǎn)僅由一個配送中心配送。J表示由配送中心組成的集合，K表示由需求點(diǎn)組成的集合。式（3）中，zj為0，1 變量，當(dāng)zj取值為1 時，確定需求點(diǎn)j為配送中心；P表示選定的配送中心的個數(shù)。式（4）確保需求點(diǎn)的需求量只能被選為配送中心的點(diǎn)供應(yīng)。式（5）、式（6）為yjk和zj的定義式。［12］

1.2 人工電場算法

人工電場算法（AEFA）［13］由Anita 等人于2019 年提出，主要模擬了帶電粒子在靜電場中的運(yùn)動，并將其演化成隨機(jī)搜索最優(yōu)解的過程。帶電粒子在搜索空間中受到靜電力的作用進(jìn)行相互吸引或排斥運(yùn)動，使得自身能在搜索空間中移動。為簡化帶電粒子的運(yùn)動原理，在AEFA 算法中，僅考慮帶電粒子之間的吸引力，因此帶電粒子之間可以通過吸引力的作用進(jìn)行相互運(yùn)動，直到所有帶電粒子聚到一起。

在搜索空間中，每一個帶電粒子代表一個可行解，解的適應(yīng)度由帶電粒子的電荷量決定，帶電粒子的電荷量越大，說明該帶電粒子所表示的可行解越接近最優(yōu)解［14］。帶電粒子的運(yùn)動原理如圖1所示。

圖1 帶電粒子受力示意圖

在圖1中，每一個圓圈代表一個帶電粒子，圓圈的大小表示電荷量的大小。帶電粒子Q1受到其他三個帶電粒子的吸引力，最終形成一個合力F和該方向上的加速度。可見Q4的電荷量最大，它對Q1的吸引力最大，所以Q1所受合力的方向更接近Q4對Q1的吸引力方向。因此，AEFA算法在進(jìn)行迭代的過程中，搜索空間中小電荷粒子會向大電荷粒子移動，使算法逐步收斂到最優(yōu)解。［15］

AEFA算法的數(shù)學(xué)模型可以用式（7）、式（8）來描述：

其中，rand為[0，1]之間的任意常數(shù)；Vit+1表示在第t+ 1次迭代時第i個帶電粒子的速度；+1表示在第t+ 1次迭代時第i個帶電粒子的位置；表示在第t次迭代時第i個帶電粒子的加速度。

根據(jù)牛頓第二定律，當(dāng)粒子受到電場力時，加速度的表達(dá)式為：

在第t次迭代時，帶電粒子的電場強(qiáng)度為：

帶電粒子在搜索空間中受到的合力為：

合力根據(jù)帶電粒子所受庫侖力計(jì)算而來，帶電粒子所受庫侖力模型如下：

式（12）中，Kt為庫倫常數(shù)；X表示第t次迭代中的最優(yōu)個體；表示在第t次迭代時，帶電粒子i與帶電粒子j之間的距離；ε為很小的正數(shù)。式（13）為的定義式。式（14）中，K0= 500，α= 30；iter表示當(dāng)前迭代次數(shù)；T表示最大迭代次數(shù)。庫倫常數(shù)的變化使得該算法在迭代前期進(jìn)行全局搜索，找到最優(yōu)解所在范圍；在迭代后期對最優(yōu)解所在范圍進(jìn)行局部搜索。Kt的迭代過程如圖2所示。

圖2 庫倫常數(shù)迭代曲線

算法在迭代過程中規(guī)定第一代種群中所有粒子的電荷量均相同（設(shè)為1），從第二代開始，電荷量的迭代公式如下：

其中，表示第i個帶電粒子在第t次迭代時的電荷量，為的歸一化處理結(jié)果；fi為第t次迭代中第i個粒子的適應(yīng)度值；best (t ) 表示第t 次迭代中的最優(yōu)適應(yīng)度值，worst (t ) 表示第t 次迭代中的最差適應(yīng)度值。

算法在每一次迭代時的位置均由貪婪策略決定：

式（17）表示下一代個體位置的選取方式。若更新后的個體適應(yīng)度劣于上一代，則個體位置不發(fā)生改變；反之采用更新后的個體作為下一代。

由上述分析可知，AEFA 算法的基本實(shí)現(xiàn)步驟如下：

1）在搜索空間中初始化種群數(shù)量、種群位置和最大迭代次數(shù)；

2）初始化帶電粒子的速度(V= 0)、電荷量(Q=1) 和質(zhì)量(m= 1)；

3）計(jì)算庫倫常數(shù)，更新全局最優(yōu)值和最差值；

4）更新個體速度和位置；

5）若算法達(dá)到最大迭代次數(shù)，則輸出當(dāng)前最優(yōu)值；反之，算法跳回步驟3）。

2 人工電場算法解決MDLP 問題原理

人工電場算法的求解是以庫倫定律為依據(jù)的逐代搜索過程。在實(shí)際求解時，采用隨機(jī)數(shù)編碼策略，設(shè)定維度D等于需求點(diǎn)個數(shù)，根據(jù)所需配送中心的數(shù)量對個體進(jìn)行排序并取前m個編號得到所需的配送中心位置。編碼和解碼過程如圖3 所示。

圖3 編碼及解碼策略

假設(shè)種群數(shù)量為N，維度為28，意味著共有28 個需求點(diǎn)。以選取6 個配送中心為例，由圖3 可知，從種群X=(X1，X2，…，XN) 中 任 意 選 取 個 體Xi，i∈{1，2，…，N}，Xi=（0.34，0.41，0.56，0.53，0.82，0.50，0.72，…，0.49）。對Xi進(jìn)行排序，取前6 個的編號（11，13，24，5，19，7），該編號代表一個可行解，即選取編號為11，13，24，5，19，7 的需求點(diǎn)為配送中心。

3 改進(jìn)人工電場算法

3.1 正余弦算法迭代機(jī)制

正余弦算法（Sine cosine algorithm，SCA）［16］利用正余弦函數(shù)的數(shù)學(xué)性質(zhì)，通過添加自適應(yīng)參數(shù)改變正余弦函數(shù)的振幅以實(shí)現(xiàn)算法的全局搜索和局部開發(fā)過程，最終尋得最優(yōu)解。在SCA 算法中個體位置的更新公式如下［17］：

式（18）中，表示在第t+ 1 次迭代時第i個個體的位置；Ptbest表示第t次迭代時種群中的最優(yōu)個體的位置；參數(shù)r1控制個體的搜索方向和步長在迭代時的影響程度；參數(shù)r2控制個體在迭代過程中的搜索距離；r3是一個隨機(jī)權(quán)重系數(shù)，決定最優(yōu)個體位置對當(dāng)前個體下一次迭代的影響程度；r4是控制算法進(jìn)行正弦迭代或余弦迭代的轉(zhuǎn)換概率；式（19）中，a為常數(shù)（一般取2）；iter 表示當(dāng)前迭代次數(shù)；T表示最大迭代次數(shù)；式（20）中，r2為(0，2π) 之間的任意常數(shù)；式（21）中，r3為(0，2) 之間的任意常數(shù)；式（22）中，r4為(0，1) 之間的任意常數(shù)。

為了更好地協(xié)調(diào)正余弦算法的全局搜索和局部開發(fā)過程，現(xiàn)對其進(jìn)行改進(jìn)。參數(shù)r1作為線性函數(shù)，不利于在算法迭代前期進(jìn)行充分的全局搜索，這導(dǎo)致算法在后期的局部尋優(yōu)能力變差。因此對參數(shù)r1進(jìn)行如下調(diào)整：

與之前相比，改進(jìn)后的r1使SCA 算法的全局搜索更加充分，并且利用余弦函數(shù)的數(shù)學(xué)特點(diǎn)，使得r1在固定的范圍內(nèi)上下振蕩，更好地平衡了算法的全局搜索與局部開發(fā)過程。

3.2 反向?qū)W習(xí)策略

Haupt 等人［18］指出，初始種群的優(yōu)劣會直接影響基于種群迭代的群智能優(yōu)化算法整體的搜索速度和解的精度，多樣性好的初始種群有助于提高算法的優(yōu)化性能［19］。然而，原始AEFA 算法在迭代前采用隨機(jī)方式初始化種群個體，這導(dǎo)致初始種群存在偶然性，從而在一定程度上影響了初代種群的引導(dǎo)效果，這會直接影響算法的收斂精度和速度。Tizhoosh 于2005 年提出的反向?qū)W習(xí)策略（Opposition - based learning，OBL）［20］，目前已被成功應(yīng)用在蝗蟲優(yōu)化算法（GOA）、遺傳算法（GA）、蟻群算法（ACO）和蝴蝶優(yōu)化算法（BOA）等算法。反向?qū)W習(xí)策略中關(guān)于反向點(diǎn)的定義如下：［21］

假設(shè)在[lb，ub] 中存在數(shù)x，則x的反向點(diǎn)定義為x′=lb+ub-x。將反向點(diǎn)的定義擴(kuò)展到D維空間，設(shè)p=(x1，x2，…，xD) 為D維空間中的一個點(diǎn)，其中xi∈[lbi，ubi]，i= 1，2，…，D，則其反向點(diǎn)

3.3 精英個體保留策略

在種群進(jìn)行迭代更新時，為確保精英個體即適應(yīng)度好的個體進(jìn)入下一代循環(huán)，采用精英個體保留策略。［22］從第二次種群迭代開始，每次迭代結(jié)束后，均對新一代種群計(jì)算反向點(diǎn)。將新一代種群與其反向點(diǎn)進(jìn)行種群合并操作，并計(jì)算適應(yīng)度值，用適應(yīng)度好的個體替換適應(yīng)度差的個體，使得子代精英個體作為父代繼續(xù)迭代。這可以在一定程度上提高算法的收斂精度。

3.4 柯西擾動策略

柯西擾動策略［23］又稱柯西變異，源自柯西分布。一維柯西分布概率密度如下：

當(dāng)a= 1 時，上式稱為標(biāo)準(zhǔn)柯西分布。圖4 為高斯分布與柯西分布的曲線對比圖。

圖4 兩種分布的概率密度曲線對比

從圖4 可以看出，柯西分布逼近于0 的過程相對平穩(wěn)，比高斯分布更慢，而且在原點(diǎn)附近的峰值也比高斯分布更小。綜上所述，柯西分布可以在計(jì)算中產(chǎn)生更強(qiáng)的擾動能力。將柯西變異引入目標(biāo)位置的更新方式中，利用柯西分布產(chǎn)生的隨機(jī)數(shù)改變當(dāng)前迭代的最優(yōu)值，提高算法的全局搜索能力和脫離局部最優(yōu)能力。［24］

式（25）中，cauchy (0，1) 為標(biāo)準(zhǔn)柯西分布?？挛鞣植茧S機(jī)變量生成函數(shù)為

3.5 算法結(jié)構(gòu)

基于上述分析，本文設(shè)計(jì)的改進(jìn)人工電場算法（IAEFA）流程如圖5 所示。算法步驟如下：

圖5 算法流程圖

1）初始化種群及各項(xiàng)參數(shù)，并計(jì)算種群反向點(diǎn)，擇優(yōu)保存；

2）計(jì)算全局最優(yōu)值（柯西擾動策略）和最差值；

3）在迭代前期使用改進(jìn)的SCA 迭代機(jī)制，在迭代后期使用AEFA 迭代機(jī)制；

4）獲得新種群，計(jì)算反向點(diǎn)，使用精英個體保留策略擇優(yōu)保存；

5）若算法達(dá)到最大迭代次數(shù)，則輸出最優(yōu)解；反之，算法跳回步驟2）。

4 算例仿真和結(jié)果分析

假設(shè)在有28 個需求點(diǎn)的某一區(qū)域內(nèi)，經(jīng)決策需選取6 個需求點(diǎn)作為配送中心向其他需求點(diǎn)運(yùn)輸貨物，表1 為每個需求點(diǎn)的位置及需求信息。進(jìn)行算例仿真時設(shè)置人工電場算法的種群規(guī)模N= 50，最大迭代次數(shù)T= 30。使用軟件：MATLAB R2018a，運(yùn)行環(huán)境為64 位Windows 11 操作系統(tǒng)，計(jì)算機(jī)硬件參數(shù)：處理器類型為AMD Ryzen 5 3500U。機(jī)帶RAM 為12.0 GB，64 位操作系統(tǒng)。

表1 需求點(diǎn)坐標(biāo)及需求量

為保證實(shí)驗(yàn)結(jié)果的有效性，針對該MDLP 問題，將AEFA 算法和IAEFA 算法獨(dú)立運(yùn)行10 次，結(jié)果如表2～表3、圖6～圖7 所示。

圖6 選址方案對比

圖7 尋優(yōu)曲線對比

表2 AEFA 和IAEFA 實(shí)驗(yàn)結(jié)果對比

表3 選址方案及配送方案對比

由表2 可知，在10 次獨(dú)立實(shí)驗(yàn)中，AEFA 算法的最小費(fèi)用為6347.2，IAEFA 算法的最小費(fèi)用為6020.9，與AEFA 相比，IAEFA 的最小費(fèi)用節(jié)省了326.3。圖7的尋優(yōu)曲線也表明，不論是最優(yōu)值還是平均值，IAEFA 算法計(jì)算結(jié)果的都比AEFA 算法的結(jié)果更小，這說明了本文算法的改進(jìn)方式具有一定的性能優(yōu)勢。

將人工魚群算法（AFSA）、文獻(xiàn)［11］、人工電場算法（AEFA）和本文的改進(jìn)算法（IAEFA）應(yīng)用于上述MDLP 問題，四種算法的對比結(jié)果如表4 所示。

表4 性能對比

由表4 可以看出，在最優(yōu)值方面，IAEFA 算法的計(jì)算結(jié)果是6020.9，比其他三種算法節(jié)約了313.1 以上；在平均值方面，IAEFA 算法的計(jì)算結(jié)果是6192.31，比其他三種算法節(jié)約了265.69 以上，說明IAEFA 算法具有更高的求解精度；在標(biāo)準(zhǔn)差方面，IAEFA 算法的結(jié)果是114.61，相比于其他三種算法具有一定的穩(wěn)定性；在平均收斂代數(shù)方面，雖然IAEFA算法不是最快的，但仍然比AESA 算法和文獻(xiàn)［11］快了3 代以上。綜上所述，在解決多配送中心選址問題上，IAEFA 算法具有較高的搜索性能。

5 總結(jié)

本文針對多配送中心選址問題，提出了一種改進(jìn)人工電場算法（IAEFA）。該算法在初始化種群時，利用反向?qū)W習(xí)策略，以提高初始種群規(guī)模的方式增加多樣性，從而使算法的第一代種群具有更好的引導(dǎo)效果；在計(jì)算全局最優(yōu)值時，引入柯西擾動策略，改變每次迭代時最優(yōu)個體的位置，避免了算法出現(xiàn)過早收斂的情況；在迭代過程中，引入正余弦迭代機(jī)制以平衡算法的全局搜索和局部開發(fā)過程；在每一次迭代結(jié)束后，引入反向?qū)W習(xí)策略和精英個體保留策略，不僅提高了種群的多樣性，還確保每次迭代后都是好的結(jié)果替換差的結(jié)果，大幅度提高了算法的收斂精度。通過仿真案例表明，相比于原始人工電場算法、人工魚群算法和文獻(xiàn)［11］中的ALMM-AFSA 算法，本文提出的IAEFA 算法在求解多配送中心選址問題時具有更好的性能。但是，由于多配送中心選址模型的建立基本處在理想情況下，因此，對于更符合真實(shí)環(huán)境，具備更高實(shí)際參考價(jià)值的選址模型是今后進(jìn)一步的研究工作。除此之外，國內(nèi)外對人工電場算法的改進(jìn)研究仍處在初期階段，算法性能尚未被完全發(fā)掘，仍具有較大的提升空間，因此進(jìn)一步開發(fā)人工電場算法的性能優(yōu)勢，分析算法的性能特點(diǎn)是今后深入研究的另一重要方面。