物流配送中心選址問題研究*

張平東 馬 軍

（沈陽工業(yè)大學管理學院 沈陽 110870）

1 引言

物流配送中心是整個物流系統(tǒng)運作的核心，在物流系統(tǒng)中起著關鍵性的作用。物流配送中心上游是供應商、廠商等，下游就是需求點、用戶，物流配送中心的合理選址直接影響整個物流系統(tǒng)的運作效率［1］。合理的物流配送中心選址可以節(jié)約物流運作成本，有效地提高經(jīng)濟效益，保證物流系統(tǒng)的協(xié)調(diào)運作，對物流行業(yè)的發(fā)展具有重要意義［2～3］。

近些年，有很多學者研究了物流配送中心選址的問題，其中包括單一配送中心選址問題以及多個配送中心選址問題等［4］，朱曉敏等［5］采用重心法以物流運輸成本最小為目標研究了物流園區(qū)選址的問題；曹勇鋒等［6］將重心法和層次分析法結合起來研究了生活垃圾轉(zhuǎn)運站選址的最佳方案；沙磊等［7］采用非線性規(guī)劃法研究了鐵路應急物資存儲倉庫的選址問題；劉善球等［8］運用了遺傳算法以成本最小為目標研究了快遞物流配送中心的最優(yōu)選址方案；徐利民等［9］則采用動態(tài)規(guī)劃法考慮到時間變動對選址問題的影響，研究了倉庫存儲中心的最優(yōu)選址方案。但以上方法都存在一個缺點，那就是精度不高、偏差較大、尋優(yōu)效果不理想等［10］。針對以上問題，本文提出了粒子群算法和模擬退化算法來優(yōu)化物流配送中心的選址問題，這兩種方法具有適用性強、精度較高、收斂速度快等特點，并通過多次仿真實驗得出了兩種算法的適用范圍，為物流配送中心選址問題提供了新的解決方案。

2 物流配送中心選址模型

本研究是以物流配送中心的總配送量最小為研究目標，分別采用粒子群算法和模擬退火算法在給定物流配送中心數(shù)目的條件下，在某一確定范圍內(nèi)確定物流配送中心的最優(yōu)位置。使得配送中心到已知需求點的總配送量（距離×需求量）達到最小，并且滿足各需求點的要求。為了方便建立本文的物流中心選址的數(shù)學模型，做出如下假設：

1）各配送中心容量不限，但必須滿足各需求點需求；

2）每個需求點只能由一個配送中心負責配送；

3）配送中心到需求點距離為直線距離。

根據(jù)以上假設條件，建立物流中心選址的數(shù)學模型可表示為

其中：所有需求點的集合用N表示；所有備選配送中心的集合用M表示；需求點i到離它最近配送中心j的距離用dij表示；需求點i對應的需求量為wi；zij?{0 ，1} ，zij=1 表示需求點i的需求量由配送中心j負責供應，否則zij=0；配送中心到需求點距離的上限用l表示。

式（1）為目標函數(shù)；式（2）表示配送中心的承載容量應該大于或等于需求點的需求量；式（3）表示每個需求點只能由離它最近的配送中心進行配送；式（4）表示每個需求點都會有配送中心進行配送；式（5）表示需求點中被選為配送中心的數(shù)量p；式（6）表示在一定的范圍內(nèi)，配送中心可以對需求點進行配送。

3 求解選址問題的算法介紹

3.1 粒子群算法

粒子群算法實質(zhì)上是模擬鳥類飛行尋找食物的行為，鳥群在飛行中集體協(xié)作，使群體效用達到最優(yōu)化。粒子群算法就是模擬鳥群捕食的行為來解決現(xiàn)實中的優(yōu)化問題，在迭代過程中，粒子本身找到的最優(yōu)解叫做個體極值點，用pbest表示其位置；整個種群找到的最優(yōu)解叫做全局極值點，用gbest表示其位置。粒子就是通過跟蹤這兩個極值來不斷更新尋找方向［11～12］。粒子找到這兩個最優(yōu)解后，根據(jù)式（7）和式（8）來更新自己的速度和位置。粒子i的信息可以用D維向量表示，位置表示為Xi=(xi1，xi2，…，xiD)T，速度表示為Vi=(vi1，vi2，…，viD)T，其他向量類似。則速度和位置更新方程為

式中，c1，c2為學習因子，為粒子i在第k次迭代時，速度的第d維分量。rand1，2是分布在[0 ，1]間的隨機數(shù)。是粒子i在第k次迭代時，位置的第d維分量。

實現(xiàn)過程如下：

第一步：種群初始化；

第二步：迭代設置：設置迭代次數(shù)，并令當前迭代次數(shù)為1；

第三步：更新粒子的速度向量；第四步：更新粒子的位置向量；第五步：更新粒子的局部最優(yōu)解和種群的全局最優(yōu)解；

第六步：終止條件判斷：判斷是否滿足尋優(yōu)結束條件，如果滿足，輸出全局最優(yōu)解，否則繼續(xù)進行迭代［13］。

3.2 模擬退火算法

模擬退火算法起源于固體退火原理，固體物質(zhì)通過加溫使溫度變高，然后緩慢的冷卻，此時原子無規(guī)則移動、排列重組，可以釋放殘余應力，消除材料中差排。整個過程實現(xiàn)了固體內(nèi)部粒子從無序到有序的過程，最終在常溫狀態(tài)下達到基態(tài)，內(nèi)能減至最?。?4～15］。目前該算法普遍適用于優(yōu)化問題的求解。

實現(xiàn)過程如下：

第一步：設定冷卻進度表。主要包括冷卻開始溫度、終止溫度、降溫函數(shù)以及馬爾可夫鏈長度；

第二步：在所建立的數(shù)學模型中找出解空間和目標函數(shù)，并生成初始解；

第三步：新解的產(chǎn)生與接受和最優(yōu)解的存儲；

第四步：在任一溫度下，以第一步設定的馬爾可夫鏈長度重復第三步過程，在按照設定的冷卻進度表設置降低溫度，直至滿足終止溫度的要求［16］。

4 案例分析

案例一：為了研究粒子群算法和模擬退火算法在物流配送選址問題的應用，本文以超市物流中心選址問題為例，進行實驗仿真研究。設在范圍（0，0）到（100，100）的矩形范圍內(nèi)，散布著40 個連鎖超市，每個連鎖超市的坐標及需求量見表1。

表1 40個連鎖超市的坐標及需求量

要求在該矩形區(qū)域內(nèi)選擇5 個位置建立物流配送中心。已知各物流配送中心容量不限，并且每個超市只能由一個物流配送中心負責配送，使得5個物流配送中心到所有超市的總配送量（距離×需求量）最小，其中物流配送中心到超市距離為直線距離。

在仿真中，首先采用粒子群算法求解該問題，其中設置學習因子c1=c2=2，粒子群規(guī)模為1500，最大迭代次數(shù)為50。超市坐標位置圖如圖1所示，每個圓點表示各個超市的位置。圖2 為初始路徑圖，其中每個小正方形表示物流配送中心，圓點與小正方形之間的連線表示某個超市的物資由該物流配送中心進行配送。具體優(yōu)化過程見圖3。經(jīng)過50 次迭代，得到圖4 的最優(yōu)路徑圖，即配送中心為所選配送中心編號（共5 個）：11、15、30、31、32，此時總配送物流量為15896.7738。物流中心選址方案表如表2所示。

圖1 超市坐標位置圖

圖3 粒子群算法優(yōu)化過程圖

圖4 粒子群算法最優(yōu)路徑圖

表2 物流中心選址方案表

接著，本文采用模擬退火算法對該問題進行求解，其中設置初始溫度值為10000，溫度下降速率為0.98，終止溫度為0.01，此時算法停止迭代。具體優(yōu)化過程和最優(yōu)路徑圖如圖5和圖6所示。最后得出配送中心為所選配送中心編號（共5 個）：3 6 10 30 31，此時總配送物流量為16091.7801。物流中心選址方案表如表3 所示，兩種算法的選址性能對比分析表，如表4所示。

圖5 模擬退火算法優(yōu)化過程圖

圖6 模擬退火算法最優(yōu)路徑圖

表3 物流中心選址方案表

表4 兩種算法性能對比分析表

從表3 可以看出，在40 個連鎖超市中確定5 個位置建立配送中心的情況下粒子群算法其整體性能是優(yōu)于模擬退火算法的。

案例二：為了驗證算法性能的普遍性，本文將上述案例中連鎖超市的數(shù)量增加到80 個，配送中心數(shù)量增加到10 個，連鎖超市的坐標及需求量如表5所示。

表5 80個連鎖超市的坐標及需求量

再次進行仿真模擬，采用粒子群算法經(jīng)過50次迭代，具體優(yōu)化過程見圖7，圖8 為最優(yōu)路徑圖，即配送中心為所選配送中心編號（共10 個）：14、18、27、31、48、51、65、70、79、80，此時總配送物流量為22355.5598。

圖7 粒子群算法優(yōu)化過程圖

圖8 粒子群算法最優(yōu)路徑圖

接著采用模擬退火算法求解此問題，具體優(yōu)化過程和最優(yōu)路徑圖如圖9和圖10所示，并將兩種方法性能進行對比，如表6所示。

圖9 模擬退火算法優(yōu)化過程圖

圖10 模擬退火算法最優(yōu)路徑圖

表6 兩種算法性能對比分析表

通過上訴分析，可以看出，在80 個連鎖超市中確定10 個位置建立配送中心的情況下，模擬退火算法在求解物流配送中心選址問題上是優(yōu)于粒子群退火算法的。

案例三：為了更加有效地驗證算法性能的適用性，本案例延續(xù)案例二的連鎖超市坐標和需求量，將連鎖超市擴大到100 個，配送中心擴大到12 個，繼續(xù)進行仿真模擬。增加的20 個連鎖超市坐標及需求量如表7 所示。具體優(yōu)化過程和最優(yōu)路徑圖如圖11 和圖12 所示，兩種方法性能對比分析表見表8。

圖11 粒子群算法最優(yōu)路徑圖

圖12 模擬退火算法最優(yōu)路徑圖

表7 增加20個連鎖超市的坐標及需求量

表8 兩種算法性能對比分析表

通過上訴分析，可以看出，在100 個連鎖超市中確定12 個位置建立配送中心的情況下，模擬退火算法在求解物流配送中心選址問題上也是優(yōu)于粒子群退火算法的。

5 結語

本文將粒子群優(yōu)化算法和模擬退火算法引入到求解物流配送中心選址的問題上，兩種算法在處理物流中心選址問題上都具有操作簡單、收斂速度快、尋優(yōu)精度高等特點。通過多次仿真模擬實驗結果表明，在需求點和配送中心規(guī)模較小時，采用粒子群算法求解該問題是優(yōu)于模擬退火算法的；在需求點和配送中心規(guī)模較大時，采用模擬退火算法求解該問題是優(yōu)于粒子群算法的，并具有一定的普遍性和可靠性，這兩種方法都可以精準地在眾多需求點中確定物流配送中心的最佳位置。