基于變異和動(dòng)態(tài)自適應(yīng) 的物流配送中心選址模型

李 眩，吳曉兵，劉 瓊

（銅陵職業(yè)技術(shù)學(xué)院經(jīng)貿(mào)系，安徽銅陵 244061）

隨著世界經(jīng)濟(jì)的快速發(fā)展及現(xiàn)代科學(xué)技術(shù)的進(jìn)步，物流作為國民經(jīng)濟(jì)的一個(gè)新興服務(wù)行業(yè)形態(tài)，正在全球范圍內(nèi)迅速發(fā)展，給生產(chǎn)、生活及其國際貿(mào)易帶來重大影響。配送中心是物流系統(tǒng)的中心樞紐，在很大程度上決定著物流網(wǎng)絡(luò)結(jié)構(gòu)，連接著貨物供應(yīng)和配送需求兩個(gè)重要的物流節(jié)點(diǎn)，在物流系統(tǒng)中起著承上啟下的重要作用〔1〕。物流配送中心在空間上的分布和選址必須合理和科學(xué)，其選址優(yōu)化問題一直是多數(shù)企業(yè)的重要戰(zhàn)略規(guī)劃問題，也是學(xué)者們關(guān)心和關(guān)注的問題，因其存在非線性、復(fù)雜度高、約束條件多且相互之間難以協(xié)調(diào)，傳統(tǒng)數(shù)學(xué)模型難以求得全局最優(yōu)解〔2〕。粒子群算法（particle swarm optimization，PSO）具有較強(qiáng)的全局尋優(yōu)能力，采用群體并行搜索方式計(jì)算求解，求解效率較高，收斂速度快。本文運(yùn)用帶變異和動(dòng)態(tài)自適應(yīng)雙重機(jī)制對PSO算法進(jìn)行改進(jìn)，將其應(yīng)用于帶約束條件的物流配送中心的選址問題，取得了較好的結(jié)果。

1 物流配送中心選址問題

在物流系統(tǒng)的運(yùn)作中，配送中心的任務(wù)就是根據(jù)客戶的需求及時(shí)、準(zhǔn)確和經(jīng)濟(jì)地配送貨物，決定著物流系統(tǒng)的運(yùn)作效率，物流配送中心在空間上的位置對于物流活動(dòng)具有十分重要的影響，合理科學(xué)的物流中心選址不僅可以大幅降低建設(shè)成本，還可以有效促進(jìn)物流系統(tǒng)的均衡良性發(fā)展，因此該問題的研究具有理論和現(xiàn)實(shí)意義〔3〕。物流配送中心選址問題屬于最小成本問題，模型是復(fù)雜度較高且?guī)в屑s束的非線性優(yōu)化問題，模型存在如下假設(shè)：一個(gè)客戶僅由一個(gè)配送中心供應(yīng)，配送中心的容量能滿足客戶的需求；根據(jù)兩點(diǎn)坐標(biāo)計(jì)算出兩點(diǎn)間的直線距離近似看成兩點(diǎn)間的運(yùn)輸距離；在允許的配送范圍內(nèi)，配送車輛能在一定的時(shí)效范圍內(nèi)將貨物配送給客戶，故配送的時(shí)效性約束可以轉(zhuǎn)化為最大允許配送距離來描述；配送的客戶都在一定范圍之內(nèi)，即客戶的坐標(biāo)有上限下限約束。

在區(qū)域范圍內(nèi)擬為n個(gè)客戶建立一個(gè)物流配送中心，客戶i的坐標(biāo)為（xi，yi），需求量為ωi，最大允許配送距離為D。確定物流配送中心的坐標(biāo)為（X，Y），單位貨物每千米運(yùn)輸成本為p（單位：元/（噸·km）），將配送區(qū)域劃分為m個(gè)子區(qū)域，對應(yīng)子區(qū)域內(nèi)配送中心的建設(shè)成本為Cj，物流配送中心的選址問題就簡化為在滿足最大允許配送距離的前提下，使得總成本f（包括建設(shè)成本和后續(xù)的配送成本）最小。

物流中心選址數(shù)學(xué)模型可以描述如下：

目標(biāo)函數(shù)：

約束條件：

其中，Ia為選址中心m個(gè)可行解坐標(biāo)x，y的下限，Ia=［min（xi），min（yi）］，Ua為選址中心m個(gè)可行解坐標(biāo)x，y的上限，Ua=［max（xi），max（yi）］。模型中，目標(biāo)函數(shù)式（1）表示后期運(yùn)營和前期建設(shè)總成本最低，現(xiàn)實(shí)中僅考慮最低運(yùn)輸周轉(zhuǎn)量或者后期成本最低這個(gè)條件是不夠的，有些緊急情況下一些貨物的配送有時(shí)效性要求，譬如搶險(xiǎn)救災(zāi)物資、生鮮冷鏈產(chǎn)品、緊急醫(yī)護(hù)產(chǎn)品的運(yùn)送；約束條件（2）表示每個(gè)客戶的配送距離必須在允許范圍之內(nèi)，通過這個(gè)約束條件將時(shí)效性要求轉(zhuǎn)變?yōu)榕渌途嚯x要求，利于后期編程簡化處理解決問題；約束條件（3）表示配送的客戶點(diǎn)都分布在一定的地理范圍內(nèi)；約束條件（4）表示各參數(shù)在實(shí)際應(yīng)用中的非負(fù)要求。4個(gè)條件共同構(gòu)成滿足時(shí)效性要求的物流配送中心選址模型，表示滿足時(shí)效性要求下總成本最小的選址目標(biāo)。

2 帶變異和動(dòng)態(tài)自適應(yīng)雙重優(yōu)化的PSO算法

2.1 PSO算法簡介PSO起源于對鳥群覓食行為的研究，由于鳥群覓食和優(yōu)化問題求解在一些方面具有相似性，于是人們模擬鳥群覓食的生物原理去作優(yōu)化決策和尋找問題最優(yōu)解〔4〕。

標(biāo)準(zhǔn)PSO算法實(shí)現(xiàn)過程如下：假設(shè)在M維（即有M個(gè)函數(shù)自變量）搜索域中有n個(gè)粒子組成一個(gè)群體，n代表種群規(guī)模，種群太小則不能保證粒子群體的多樣性，以致算法性能很差，種群太大盡管可以增加尋優(yōu)的效率，阻止早熟收斂的發(fā)生，但無疑會增加計(jì)算量，造成收斂時(shí)間太長，表現(xiàn)為收斂速度緩慢〔5〕。Xi=（xi1，xi2，…，xiM），i=1，2，…，n為粒子i的位置向量，粒子維數(shù)取決于待優(yōu)化函數(shù)的變量數(shù)，其中xik代表粒子在第k個(gè)自變量上的取值，xik?［L，U］，在實(shí)際應(yīng)用中，X每一維保證在一定的范圍內(nèi)，這在函數(shù)優(yōu)化問題中相當(dāng)于是自變量的定義域，L表示第k個(gè)自變量的取值下限，U表示第k個(gè)自變量的取值上限。Vi=（vi1，vi2，…，viM）為粒子i的速度向量，它們都是M維的，vik?［vmin，vmax］，vmin表示粒子在第k維方向上的最小速度，vmax表示粒子在第k維方向上的最大速度，在每一代尋優(yōu)中，粒子將根據(jù)粒子自身找到的歷史最優(yōu)位置和群體找到的歷史最優(yōu)位置來調(diào)整自己的飛行方向和方位〔6〕。記Pi=（pi1，pi2，…，piM）是粒子i自身找到的具有最佳適應(yīng)值的位置；記Pg=（pg1，pg2，…，pgM）是整個(gè)粒子群搜索到的最優(yōu)位置。

設(shè)f（x）為適應(yīng)度函數(shù)，粒子i的個(gè)體最佳位置為：

群體所有粒子找到的全局最佳位置為：

第t代的第i個(gè)粒子進(jìn)化到第t+1代時(shí)，第j維的速度和位置用如下的進(jìn)化方程計(jì)算：

每一維粒子速度和位置都會被約束在一個(gè)范圍內(nèi)，如果超過邊界條件，按如下方法處理，這樣防止了粒子逃遁出解空間的可能性。

vij>vmax，xij＜xmax時(shí)，vij=vmax，xij=xmax或vij＜vmax，xij＜xmax時(shí)，vij=-vmax，xij=-xmax。

算法搜索性能對參數(shù)有較高的依賴性，算法涉及3個(gè)參數(shù)：慣性權(quán)重w、加速因子c1，c2。3個(gè)參數(shù)設(shè)置為定值或者線性變化會對算法尋優(yōu)及效率帶來不利影響〔7〕。另外，在優(yōu)化前期，為了粒子具有較大速度可以提高搜索全局最優(yōu)解的能力，而在后期接近最優(yōu)解時(shí)，為了不使粒子速度過大偏離最優(yōu)位置區(qū)域錯(cuò)失全局最優(yōu)解陷入局部最優(yōu)，因此在后期接近全局最優(yōu)區(qū)域時(shí)，位置更新幅度不宜過大，應(yīng)該對粒子速度進(jìn)行有效掌控和約束，不能忽視后期粒子可能因速度過大俯沖脫離全局最優(yōu)區(qū)域的情況出現(xiàn)，從而造成算法不成熟收斂〔8〕。鑒于上述原因，在PSO算法中引入非線性變化的收縮因子ρ（t），與慣性權(quán)重相比，其更能有效管束粒子的飛行速度，改善算法的收斂能力。

2.2 帶變異和動(dòng)態(tài)自適應(yīng)雙重機(jī)制的PSO算法設(shè)計(jì)隨著PSO算法研究的不斷深入，人們開始運(yùn)用自適應(yīng)變化的參數(shù)提升PSO算法性能。已有學(xué)者從慣性權(quán)重的動(dòng)態(tài)調(diào)整入手來優(yōu)化PSO算法，但僅靠動(dòng)態(tài)調(diào)整單一參數(shù)提升算法的性能相對有限〔9〕。為此本文不僅對慣性權(quán)重和加速因子進(jìn)行動(dòng)態(tài)時(shí)變調(diào)整，同時(shí)引入動(dòng)態(tài)時(shí)變的控制因子來約束粒子的位置更新幅度，因?yàn)閰?shù)的非線性時(shí)變調(diào)整能比線性調(diào)整獲得更佳的算法性能，這幾項(xiàng)參數(shù)的調(diào)整皆采取非線性的動(dòng)態(tài)自適應(yīng)時(shí)變調(diào)整策略。慣性權(quán)重的動(dòng)態(tài)非線性指數(shù)遞減的調(diào)整公式如下所示：

式中k為控制因子，控制w關(guān)于t函數(shù)曲線的平滑度。隨著自變量的增加，函數(shù)值遞減的速度逐漸下降，指數(shù)函數(shù)改進(jìn)的非線性遞減的慣性權(quán)重復(fù)合PSO算法的要求。在迭代次數(shù)過程中，慣性權(quán)重值的變化應(yīng)該滿足如下要求：前期減少的速度比較慢，慣性權(quán)重值較大且減少幅度較小利于全局探索；后期較小且減少的速度較快，利于粒子展開精細(xì)的局部搜索，這樣在保證收斂速度的同時(shí)又平衡了全局和局部搜索能力，有效避免陷入局部最優(yōu)〔10〕。wstart=0.9，wend=0.4。當(dāng)t=0時(shí)，w（t）=wstart=0.9，當(dāng)達(dá)到最大迭代次數(shù)tmax時(shí)，w（t）=wend=0.4。k取5，后期變化步長較小有較好表現(xiàn)，算法能取得較好的穩(wěn)定性。

為了防止粒子速度過快俯沖脫離最優(yōu)解，對粒子位置更新幅度進(jìn)行控制，對位置更新公式（6）引入動(dòng)態(tài)自適應(yīng)時(shí)變的控制因子ρ（t），對算法后期粒子位置更新幅度進(jìn)行約束。其變化規(guī)律按照如下函數(shù)進(jìn)行調(diào)整：

其中，ρmax設(shè)為1.8，ρmin設(shè)為0.4，α為常數(shù)，設(shè)為0.009。如此，粒子位置更新公式調(diào)整如下：

僅僅減小w會使得算法一旦陷入局部陷阱內(nèi)就很難跳出，極易收斂到局部極值點(diǎn)，加速因子c1（t），c2（t）對算法全局和局部尋優(yōu)能力亦有重要影響，所以同時(shí)對兩個(gè)加速因子進(jìn)行非線性的時(shí)變動(dòng)態(tài)調(diào)整。也采用動(dòng)態(tài)自適應(yīng)時(shí)變調(diào)整策略，按照算法對加速因子的變化要求，c1先大后小，c2先小后大，以指數(shù)函數(shù)為基礎(chǔ)構(gòu)造變化關(guān)系式，使其分別呈現(xiàn)遞減和遞增變化，能讓算法獲得較好的全局尋優(yōu)性能。其調(diào)整函數(shù)如下：

其中，c2max設(shè)為2.0，c2min設(shè)為0.6，α為常數(shù)，設(shè)為0.009。各參數(shù)變化曲線見圖1。

圖1 各參數(shù)變化曲線

為了增強(qiáng)PSO算法的全局尋優(yōu)能力，陷入局部最優(yōu)時(shí)能盡快跳出局部最優(yōu)的約束，在上述改進(jìn)的基礎(chǔ)上受到生物在免疫遺傳進(jìn)化過程中變異機(jī)制的啟發(fā)，對動(dòng)態(tài)自適應(yīng)PSO算法增加變異操作。由PSO算法的速度和位置的更新公式可知：群體最優(yōu)位置和最優(yōu)適應(yīng)度值影響著粒子的移動(dòng)，所以針對群體當(dāng)前最優(yōu)位置（問題的當(dāng)前最優(yōu)解）以一定概率進(jìn)行隨機(jī)變異操作，對其值進(jìn)行隨機(jī)擾動(dòng)，尤其當(dāng)陷入局部最優(yōu)算法停頓時(shí)，通過引入變異算子使粒子發(fā)生跳躍，迅速逃脫局部極值的束縛，從而增強(qiáng)算法全局尋優(yōu)能力，防止算法過早收斂。變異操作如下：g'=g+rand×d，其中g(shù)為當(dāng)前群體最優(yōu)適應(yīng)度值所對應(yīng)的最優(yōu)位置，rand為在［0，1］之間均勻分布的隨機(jī)數(shù)，d為變異步長（例如d=（Xmax-Xmin）/100，變異步長為搜索區(qū)間長度的百分之一）。在本文中變異概率取0.3。

3 改進(jìn)的PSO算法在物流配送中心選址問題仿真求解

為了證明算法應(yīng)用于求解現(xiàn)實(shí)中比較復(fù)雜、多約束的問題的有效性，在此將其應(yīng)用于求解物流配送中心的選址，采集了8個(gè)客戶的位置坐標(biāo)，各客戶坐標(biāo)及其后續(xù)物資需求總量見表1。

表1 客戶位置坐標(biāo)與物資需求量

擬在位置坐標(biāo)落在20≤x，y≤800的范圍內(nèi)建設(shè)物流配送中心，使得前期建設(shè)成本和后期配送總成本最小。為了滿足物流配送的時(shí)效性要求，約定配送中心到客戶間的配送距離不得大于600 km，配送價(jià)格設(shè)定為10元/（噸·km），并在不同的子區(qū)域內(nèi)建設(shè)成本不一樣：在20≤x，y≤400坐標(biāo)范圍內(nèi)，建設(shè)成本為500萬元；在400＜x，y≤800坐標(biāo)范圍內(nèi)，建設(shè)成本為650萬元；在20≤x≤400，400＜y≤800坐標(biāo)范圍內(nèi)，建設(shè)成本為480萬元；在400＜x≤800，20≤y≤400坐標(biāo)范圍內(nèi)，建設(shè)成本為370萬元。根據(jù)給定的約束條件運(yùn)用提出的改進(jìn)PSO優(yōu)化模型確定物流配送中心的最優(yōu)位置坐標(biāo)，使其運(yùn)作總成本最小。

為了與標(biāo)準(zhǔn)PSO算法（c1，c2為常數(shù)，慣性權(quán)重線性遞減）及其動(dòng)態(tài)自適應(yīng)PSO算法求解結(jié)果進(jìn)行對比，運(yùn)行對應(yīng)程序，適應(yīng)度函數(shù)值變化見圖2，物流配送中心選址結(jié)果見圖3。

圖2 適應(yīng)度函數(shù)值變化

圖3 物流配送中心選址結(jié)果

采用本文提出的基于雙重機(jī)制改進(jìn)的PSO算法求解物流配送中心選址問題，具有較好的收斂性，求得最優(yōu)解的迭代次數(shù)約為40次左右，最佳配送中心坐標(biāo)為（513.77，599.99），建設(shè)成本和后期配送總成本最小為122 800萬元。而標(biāo)準(zhǔn)PSO算法和動(dòng)態(tài)自適應(yīng)PSO算法在求解該問題時(shí)，雖然求解結(jié)果都接近前者的求解結(jié)果，但都沒能收斂到全局最優(yōu)。物流配送中心作為現(xiàn)代物流系統(tǒng)的核心和關(guān)鍵，其選址和布局是一個(gè)復(fù)雜的系統(tǒng)工程。本文構(gòu)建了物流配送中心選址的數(shù)學(xué)模型，并通過改進(jìn)的PSO算法求解最優(yōu)物流配送中心選址方案。求得的方案滿足每個(gè)客戶的時(shí)效性和配送容量要求，而且能顯著地將總成本降低到最少，由此可見，采用基于雙重機(jī)制的PSO算法解決物流配送中心選址問題取得了較好的結(jié)果，在現(xiàn)實(shí)中具有十分積極的意義。

4 結(jié)束語

通過物流配送中心選址模型的應(yīng)用，證明了選址模型的正確性和基于變異和動(dòng)態(tài)自適應(yīng)雙重機(jī)制的PSO算法解決復(fù)雜優(yōu)化問題的有效性，基于雙重機(jī)制的PSO算法改善了易陷入局部最優(yōu)、魯棒性差的缺點(diǎn)，該模型應(yīng)用于物流配送中心選址問題的求解，具有較好的動(dòng)態(tài)觀測性和收斂性。改進(jìn)的PSO算法是一種解決優(yōu)化問題進(jìn)行優(yōu)化決策的好方法，具有較好的應(yīng)用前景。