倉庫選址問題的一種混合算法

楊 立

（運城學(xué)院公共計算機教學(xué)部，山西運城 044000）

倉庫選址問題的一種混合算法

楊 立

（運城學(xué)院公共計算機教學(xué)部，山西運城 044000）

對于一些大型企業(yè)來說，科學(xué)的倉庫布局以及合理的配送方案可以減少物流營運成本，提高企業(yè)效率。針對此問題，本文提出一種基于和諧搜索算法和遺傳算法的混合算法，并通過實驗驗證了該算法的可行性和高效性。

選址；分配；和諧搜索算法；遺傳算法

伴隨著經(jīng)濟的迅速發(fā)展和競爭壓力的不斷增強，企業(yè)逐漸意識到，合理地建立分銷網(wǎng)絡(luò)，加強對分銷環(huán)節(jié)的管理，是在當(dāng)前客戶驅(qū)動的競爭環(huán)境下，提高客戶滿意度，增強企業(yè)競爭力的重要途徑[1]，這類選址—分派問題越來越引起大量研究者的關(guān)注，而隨著計算機技術(shù)的高速發(fā)展，大規(guī)模計算成為可能[2]，很多研究者采用遺傳算法[3]、拉格朗日松弛法[4]、模擬退火算法[5]等算法來求解。本文將傳統(tǒng)遺傳算法與和諧搜索算法相結(jié)合，針對問題設(shè)計有效的編碼方案和遺傳算子對此問題進行求解。

1 模型設(shè)計

倉庫選址及配送方案問題需考慮的現(xiàn)實因素有很多，例如，倉庫與分銷點之間的距離、地價租金、交通狀況、商品運輸成本等。本文為方便對問題進行求解，將倉庫與分銷點之間的距離、交通狀況、運輸成本等因素量化為配送每單位重量所需要的費用，并進行假設(shè)：(1)從已知的若干個備選點中選取其中的某些建設(shè)成倉庫；(2)一個倉庫可以為多個分銷點配送；(3)一個分銷點僅由一個倉庫為其配送；(4)各個分銷點的需求量已知。數(shù)學(xué)模型為：

約束條件：

其中，m為倉庫的個數(shù)；n為分銷點的個數(shù)；xij為從倉庫i到分銷點j配送每單位貨物所需費用；yy為從倉庫i到分銷點j的運輸量；ui為第i個倉庫的啟動費用；Ri為第i個倉庫的容量。

式(1)表示總費用最少；式(2)表示對倉庫需求量應(yīng)小于等于其容量；式(3)表示每個分銷點僅由一個倉庫配送；式(4)表示倉庫應(yīng)覆蓋所有分銷點。

2 和諧搜索算法簡介

和諧搜索算法是2001年提出的、用于求解連續(xù)優(yōu)化問題的一種新穎亞啟發(fā)式算法，可模擬音樂家在音樂表演過程中探尋優(yōu)美樂譜的過程[6]。和諧搜索算法試圖找到一個能夠使目標(biāo)函數(shù)達(dá)到最值的解向量，算法參數(shù)為和諧記憶大小、和諧記憶選擇概率、調(diào)節(jié)概率par、帶寬及調(diào)節(jié)步長等。算法執(zhí)行步驟為：

步驟1初始化設(shè)置，隨機產(chǎn)生和諧記憶矩陣：

其中，N是決策變量的個數(shù)。

步驟2 產(chǎn)生新的解向量，x′i=(x′i1，…，x′id，…，x′iD)，其中 x′id遵循以下規(guī)則產(chǎn)生：

步驟3 更新和諧記憶矩陣。將新產(chǎn)生的和諧向量的目標(biāo)函數(shù)值與和諧記憶中最差的目標(biāo)函數(shù)值進行比較，若新值優(yōu)于最差值，則進行替換。

步驟4 循環(huán)執(zhí)行步驟2和步驟3，直到滿足結(jié)束條件。

3 基于和諧搜索算法和遺傳算法的混合算法

遺傳算法的整體搜索策略和優(yōu)化搜索方法不依賴于梯度信息，因此，它提供了一種求解復(fù)雜系統(tǒng)問題的通用框架[7]，而和諧搜索算法不依賴變量的初始值，是一種隨機搜索算法，且每次迭代中，新的解向量均從所有解向量中產(chǎn)生，算法具有良好的遍歷性[8]，故本文將遺傳算法與和諧搜索算法相結(jié)合?；旌纤惴ㄖ饕鞒倘鐖D1所示。

圖1 算法流程

3.1 編碼方案設(shè)計

筆者對傳統(tǒng)的編碼方案進行改進，傳統(tǒng)編碼經(jīng)常采用的是二進制編碼，針對倉庫選址問題以及相應(yīng)的分配方案問題，本文采用一種具有雙重功能的整數(shù)編碼方案，即從編碼上不僅可以直接得到哪些備選的倉庫被選中，而且還可以直接得到分配方案，即哪個倉庫為哪些分銷點供貨。例如，若要從5個備選的倉庫中選擇其中的若干個為10個分銷點進行配貨服務(wù)，假如得到的解向量為：5-1-4-5-4-4-1-4-5-5，則不僅可以得知1號、4號、5號倉庫被選中，而且可以得知分配方案：1號為2號、7號分銷點供貨，4號為3號、5號、6號、8號供貨，5號為1號、4號、9號、10號供貨。

3.2 可行性處理方法

對于產(chǎn)生的新的解向量要判斷其是否滿足本問題的約束條件，若不滿足，則要進行可行性處理，具體方法為：首先根據(jù)解向量得到具體的倉庫編號以及相應(yīng)的分配方案，然后判斷所選倉庫的容量是否能夠滿足分銷點的需求量，若不滿足，則對分配方案進行調(diào)整，將所對應(yīng)的分銷點分配給配貨時單位重量花費最少、已被選中且沒有達(dá)到最大容量的倉庫。

3.3 更新解向量

由于和諧搜索算法經(jīng)常用于求解連續(xù)優(yōu)化問題，而倉庫選址問題具有一定的離散性，故在更新解向量時采用遺傳算法中的選擇、交叉、變異操作進行實現(xiàn)。

4 算例驗證

某大型連鎖超市要在某市建立若干貨物倉庫為其分布在市內(nèi)的50個分銷點進行供貨服務(wù)，經(jīng)過前期市場考察，已經(jīng)確定10處備選的倉庫地點，并對倉庫與分銷點之間的距離、地價租金、交通狀況、商品運輸成本等進行綜合考慮，將這些因素量化為從倉庫到分銷點供貨時每單位重量所需費用，并統(tǒng)計出了每個分銷點的需求量，如表1所示。每個倉庫的容量及相應(yīng)的建設(shè)費用如表2所示?，F(xiàn)要確定選擇哪些備選地點進行建設(shè)以及相應(yīng)的分配方案，使得總費用最少。

表1 需求量及單位貨物運輸費用

表2 容量及經(jīng)費

對于該問題，本文采用以上設(shè)計的混合算法，在MATLAB平臺下編程實現(xiàn)，參數(shù)設(shè)置為：最大代數(shù)MAXGEN=500，和諧記憶大小HMS=30，和諧記憶概率HMCR=0.6，選擇概率PS=0.7，交叉概率PCc=0.7，運行后得到的最優(yōu)解向量如表3所示，相應(yīng)的分配方案如表4所示。

表3 最優(yōu)解向量

表4 分配方案

表5 最優(yōu)平均值比較

另外，將本文算法與遺傳算法分別獨立運行10次，并統(tǒng)計得到最優(yōu)解的平均值，結(jié)果如表5所示?？梢钥闯?，本文算法的計算效果明顯優(yōu)于遺傳算法，其原因在于它不僅具有遺傳算法不依賴于問題的具體領(lǐng)域、對問題的種類有很強的魯棒性等特點，而且具有和諧搜索算法良好遍歷性的特點。

5 結(jié)語

本文根據(jù)倉庫選址問題以及分配方案問題，將和諧搜索算法和遺傳算法的主要算子進行有機結(jié)合，形成一種針對此問題的混合算法，通過算例可以證明，該算法可以有效地解決問題。

[參 考 文 獻(xiàn)]

[1]稅文兵,葉懷珍,張詩波.物流配送中心動態(tài)選址模型及算法研究[J].計算機應(yīng)用研究,2010,27(12):4476-4479.

[2]王喆.基于組合遺傳算法的鐵路危險貨物辦理站點整合優(yōu)化[J].計算機應(yīng)用,2010,30(9):2301-2304.

[3]周興龍,金鵬飛.基于遺傳算法的單點物流選址問題探析[J].物流工程與管理,2010,3(27):39-42.

[4]王文峰,劉新亮,郭波.綜合多準(zhǔn)則決策的保障設(shè)施選址—分派方法[J].系統(tǒng)工程理論與實踐,2008,28(5):148-155.

[5]秦進,史峰.物流設(shè)施選址問題的雙層模擬退火算法[J].系統(tǒng)工程,2007,25(2):36-40.

[6]韓毅,蔡建湖,周根貴,等.廢棄物處理站選址問題的和諧搜索算法[J].計算機科學(xué),2011,38(6):255-258.

[7]侯曉峰,薛惠鋒.遺傳算法在城市污水處理廠污泥處理處置項目選址中的應(yīng)用[J].上海交通大學(xué)學(xué)報,2011,45(7):1080-1084.

[8]駱乾坤,王佩,朱國榮.水文地質(zhì)參數(shù)識別的快速和諧搜索算法[J].水文地質(zhì)工程地質(zhì),2011,38(4):14-19.

A Hybrid Algorithm for the Problem of Warehouse Location

YANG Li

(Public Department of Computer Teaching,Yuncheng University，Yuncheng Shanxi 044000，China)

For some large enterprises,scientific warehouse layout and reasonable distribution scheme can reduce logistics operation cost,and improve the efficiency of enterprises.In view of this question,this paper proposes a hybrid algorithm which is based on the harmony search algorithm and genetic algorithm,and show that the algorithm is feasible and efficient by experiments.

location；distribution；harmony search algorithm；genetic algorithm

TP301.6

A

1008-178X(2013)01-0021-04

2012-12-23

2011年運城學(xué)院院級項目（YQ-2011076）。

楊 立（1978-），男，山西運城人，運城學(xué)院公共計算機教學(xué)部講師，碩士，從事計算機應(yīng)用與人工智能研究。