孫 濤

(1.中國石油大學(xué)勝利學(xué)院基礎(chǔ)科學(xué)學(xué)院，山東 東營 257000;2.中國石油大學(xué)儲運與建筑工程學(xué)院，山東 青島 266580)

配送中心選址問題是指在一個固定連續(xù)區(qū)域內(nèi)分布著一些需求點，要求在此區(qū)域建立配送中心，在滿足一定約束的前提下，確定配送中心的位置和需求點的分配方案，使得配送距離最短或配送費用最低。由于問題的復(fù)雜性，傳統(tǒng)優(yōu)化方法很難取得好的效果，而以遺傳算法為代表的智能算法能夠更加有效地求解此類問題。遺傳算法是一種高效的全局優(yōu)化技術(shù)，在優(yōu)化運算、機器學(xué)習、智能控制等許多領(lǐng)域都得到了成功的運用［1-3］，目前已有眾多研究將遺傳算法應(yīng)用于配送中心選址問題［4-6］上，本文在使用遺傳算法時，將配送中心的位置坐標進行編碼，使用貪心算法給出近似最優(yōu)分配方案并計算適應(yīng)度函數(shù)，通過遺傳進化，得出最終的配送中心位置坐標與需求點的分配方案，并通過實例將算法與使用分枝定界法進行比較。

1 配送中心選址問題的數(shù)學(xué)模型

假設(shè)在一連續(xù)的平面區(qū)域D內(nèi)分布著n個需求點，需求點的位置坐標(aj，bj)，j=1，2，…，n，要求在區(qū)域D內(nèi)建立p個配送中心，給出配送距離最短或配送費用最低的配送中心位置及需求點的分配方案，其優(yōu)化問題的數(shù)學(xué)模型

其中，cij為連接的權(quán)重，(xi，yi)為配送中心的位置坐標，i=1，2，…，p，j=1，2，…，n。約束(1)表明一個需求點只能連接到一個配送中心;約束(2)為配送中心連接需求點不能超過k;約束(3)為配送中心位置坐標的幾何約束。

2 遺傳算法的實現(xiàn)

2.1 編碼方案

遺傳算法的編碼是對問題的可行解進行某種編碼，將問題的解空間轉(zhuǎn)化為編碼空間，每一個可行解對應(yīng)一個編碼，稱為個體或染色體，常用的編碼有二進制編碼、實數(shù)編碼等。由于模型中既含有連續(xù)變量，又含有離散變量，為簡化運算，本文采用實數(shù)編碼，將p個配送中心的位置坐標按順序?qū)懗梢粋€2p維的實數(shù)向量，每個實數(shù)向量即為一個個體。

2.2 確定適應(yīng)度函數(shù)

適應(yīng)度是衡量個體優(yōu)劣的指標，它直接決定每個個體的存活概率，而適應(yīng)度函數(shù)的構(gòu)造一般是對目標函數(shù)值進行改造，這時需要計算每個個體對應(yīng)的目標函數(shù)值，對于每個個體，由于配送中心位置坐標已經(jīng)確定，模型就簡化成了一個0－1規(guī)劃模型，通過求解這一簡化模型可得到每個個體對應(yīng)的分配方案和目標函數(shù)值，從而得到每個個體對應(yīng)的可行解與適應(yīng)度函數(shù)。

在此并不求解最優(yōu)的分配方案，而是選用貪心算法給出一個近似最優(yōu)分配方案，具體做法如下:

(1)按需求點到配送中心的距離由小到大排列;

(2)將距離最小的需求點與配送中心選出，將此需求點歸入這一配送中心;

(3)刪除這一需求點對應(yīng)的所有距離值;

(4)檢驗配送中心是否已達到最大連接數(shù)，如果已達最大連接數(shù)，則刪除配送中心對應(yīng)的所有距離值。

(5)返回步驟(1)，直到所有需求點分配完成。

2.3 遺傳算子的確定

(1)選擇算子模擬的是“物競天擇，適者生存”的自然進化原理，是從當前種群中以一定概率選取個體用作父本去繁殖后代，個體被選中的概率與適應(yīng)度值有關(guān)。常用的選擇方法有比例選擇、排序選擇等，本文使用的是比例選擇。

(2)交叉算子模擬生物進化中的有性繁殖，是從種群中選擇兩個父本個體，通過兩交換組合產(chǎn)生兩個新個體。常用的交叉方案有單點交叉、雙點交叉、均勻交叉等，本文采用單點交叉。

(3)變異算子選擇。對交叉后的染色體進行變異是為了防止算法陷入局部搜索，提高算法達到全局最優(yōu)解的機會，變異操作采用均勻變異，即隨機選取父染色體的一個基因，然后用在可行域內(nèi)區(qū)間中均勻分布的一個隨機數(shù)代替［2］。

2.4 保優(yōu)與終止進化準則

在算法中，記錄每次迭代的最優(yōu)染色體，每次迭代都將記錄的上一代的最優(yōu)染色體取代新種群中適應(yīng)度最差的染色體，以保證優(yōu)良基因的延續(xù)。遺傳算法的終止準則常常是根據(jù)計算代價與計算結(jié)果的權(quán)衡，本文采用預(yù)先設(shè)定進行時限的終止準則。

3 算例分析

在一矩形區(qū)域，隨機分布44個需求點，其坐標見表1，現(xiàn)要求在上述區(qū)域設(shè)置6個地址建立配送中心，使得需求度到配送中心的總路程最短，其中每個需求點只能連接到一個配送中心，而每個配送中心的最大連接數(shù)為8。使用遺傳算法運算，種群規(guī)模為40，進化600代。分別使用貪心算法和分枝定界法計算適應(yīng)度，其中分枝定界法求解使用MATLAB函數(shù)bintprog實現(xiàn)。

表1 區(qū)域站點原始數(shù)據(jù)

遺傳算法的迭代過程比較見圖1，從圖1中可知雖然貪心算法只給出了近似最優(yōu)的分配方案，但經(jīng)過遺傳算法的進化，算法仍然能夠收斂到全局最優(yōu)解。

圖1 算法優(yōu)化過程圖

兩種算法的主要優(yōu)化結(jié)果見表2，雖然所得到的中心位置各異，但最終的目標函數(shù)值相差不大，在計算時間上，由于使用貪心算法在每次迭代中不用求解最優(yōu)，與使用分枝定界法相比，計算效率高出兩個數(shù)量級。

表2 主要優(yōu)化結(jié)果對比

4 結(jié)束語

使用遺傳算法求解配送中心選址問題，將配送中心的位置坐標和需求點的分配方案分開，將位置坐標進行實數(shù)編碼，在計算適應(yīng)度函數(shù)時，采用貪心算法給出分配方案，從而得到適應(yīng)度函數(shù)。與使用分枝定界法比較，雖然貪心算法只給出了近似最優(yōu)的分配方案，但由于遺傳算法的全局尋優(yōu)能力，算法仍然能夠收斂到全局最優(yōu)解，而且由于貪心算法方法簡單、計算量小，在計算時間上，較使用分枝定界法有明顯的優(yōu)勢，實際的算例也驗證了算法的收斂性和有效性。

［1］阮曉青，周義倉.數(shù)學(xué)建模引論［M］.北京:高等教育出版社，2006:116-188.

［2］史峰，王輝，郁磊，等.MATLAB智能算法30個案例分析［M］.北京:北京航空航天大學(xué)出版社，2011:17-26.

［3］王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實現(xiàn)［M］.西安:西安交通大學(xué)出版社，2002:1-50.

［4］吳堅，史忠科.基于遺傳算法的配送中心選址問題［J］.華南理工大學(xué)學(xué)報:自然科學(xué)版，2004.6，32(6):71-74.

［5］劉揚，鞠志忠，鮑云波.一類多級星式網(wǎng)絡(luò)的拓撲優(yōu)化設(shè)計方法［J］.大慶石油學(xué)院學(xué)報，2009，33(2):68-73.

［6］姜大立，楊西龍.易腐物品配送中心連續(xù)選址模型及其遺傳算法［J］.系統(tǒng)工程理論與實踐，2003(2):62-67.