張平東 馬 軍

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

1 引言

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

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

2 物流配送中心選址模型

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

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

2）每個(gè)需求點(diǎn)只能由一個(gè)配送中心負(fù)責(zé)配送；

3）配送中心到需求點(diǎn)距離為直線距離。

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

其中：所有需求點(diǎn)的集合用N表示；所有備選配送中心的集合用M表示；需求點(diǎn)i到離它最近配送中心j的距離用dij表示；需求點(diǎn)i對(duì)應(yīng)的需求量為wi；zij?{0 ，1} ，zij=1 表示需求點(diǎn)i的需求量由配送中心j負(fù)責(zé)供應(yīng)，否則zij=0；配送中心到需求點(diǎn)距離的上限用l表示。

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

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

3.1 粒子群算法

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

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

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

第一步：種群初始化；

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

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

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

3.2 模擬退火算法

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

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

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

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

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

第四步：在任一溫度下，以第一步設(shè)定的馬爾可夫鏈長(zhǎng)度重復(fù)第三步過程，在按照設(shè)定的冷卻進(jìn)度表設(shè)置降低溫度，直至滿足終止溫度的要求［16］。

4 案例分析

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

表1 40個(gè)連鎖超市的坐標(biāo)及需求量

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

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

圖1 超市坐標(biāo)位置圖

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

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

表2 物流中心選址方案表

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

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

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

表3 物流中心選址方案表

表4 兩種算法性能對(duì)比分析表

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

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

表5 80個(gè)連鎖超市的坐標(biāo)及需求量

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

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

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

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

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

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

表6 兩種算法性能對(duì)比分析表

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

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

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

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

表7 增加20個(gè)連鎖超市的坐標(biāo)及需求量

表8 兩種算法性能對(duì)比分析表

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

5 結(jié)語

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