基于變異和動態自適應 的物流配送中心選址模型

李 眩，吳曉兵，劉 瓊

（銅陵職業技術學院經貿系，安徽銅陵 244061）

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

1 物流配送中心選址問題

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

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

物流中心選址數學模型可以描述如下：

目標函數：

約束條件：

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

2 帶變異和動態自適應雙重優化的PSO算法

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

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

設f（x）為適應度函數，粒子i的個體最佳位置為：

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

第t代的第i個粒子進化到第t+1代時，第j維的速度和位置用如下的進化方程計算：

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

vij>vmax，xij＜xmax時，vij=vmax，xij=xmax或vij＜vmax，xij＜xmax時，vij=-vmax，xij=-xmax。

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

2.2 帶變異和動態自適應雙重機制的PSO算法設計隨著PSO算法研究的不斷深入，人們開始運用自適應變化的參數提升PSO算法性能。已有學者從慣性權重的動態調整入手來優化PSO算法，但僅靠動態調整單一參數提升算法的性能相對有限〔9〕。為此本文不僅對慣性權重和加速因子進行動態時變調整，同時引入動態時變的控制因子來約束粒子的位置更新幅度，因為參數的非線性時變調整能比線性調整獲得更佳的算法性能，這幾項參數的調整皆采取非線性的動態自適應時變調整策略。慣性權重的動態非線性指數遞減的調整公式如下所示：

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

為了防止粒子速度過快俯沖脫離最優解，對粒子位置更新幅度進行控制，對位置更新公式（6）引入動態自適應時變的控制因子ρ（t），對算法后期粒子位置更新幅度進行約束。其變化規律按照如下函數進行調整：

其中，ρmax設為1.8，ρmin設為0.4，α為常數，設為0.009。如此，粒子位置更新公式調整如下：

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

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

圖1 各參數變化曲線

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

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

為了證明算法應用于求解現實中比較復雜、多約束的問題的有效性，在此將其應用于求解物流配送中心的選址，采集了8個客戶的位置坐標，各客戶坐標及其后續物資需求總量見表1。

表1 客戶位置坐標與物資需求量

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

為了與標準PSO算法（c1，c2為常數，慣性權重線性遞減）及其動態自適應PSO算法求解結果進行對比，運行對應程序，適應度函數值變化見圖2，物流配送中心選址結果見圖3。

圖2 適應度函數值變化

圖3 物流配送中心選址結果

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

4 結束語

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