孫 濤

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

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

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

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

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

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

2.1 編碼方案

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

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

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

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

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

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

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

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

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

2.3 遺傳算子的確定

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

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

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

2.4 保優(yōu)與終止進(jìn)化準(zhǔn)則

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

3 算例分析

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

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

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

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

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

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

4 結(jié)束語

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

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

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

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

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

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

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