摘 要: 針對(duì)一類配送中心選址問題,建立了問題的數(shù)學(xué)模型,將和諧搜索算法進(jìn)行改進(jìn)并對(duì)問題進(jìn)行求解,最后將此算法與最優(yōu)保存算法(EGA)和遺傳算法(GA)進(jìn)行比較,驗(yàn)證了算法在計(jì)算結(jié)果方面的精確性和計(jì)算時(shí)間上的高效性。
關(guān)鍵詞: 配送中心;選址;和諧搜索算法;遺傳算法
面對(duì)日益加劇的競(jìng)爭(zhēng)壓力和快速變化的市場(chǎng)需求,企業(yè)的驅(qū)動(dòng)力已由生產(chǎn)轉(zhuǎn)向通過分銷和服務(wù)提供的附加值[1],合理的配送中心布局和貨物配送方案可以在很大程度上降低物流營(yíng)運(yùn)成本,提高企業(yè)競(jìng)爭(zhēng)力。關(guān)于配送中心選址問題,目前主要采用遺傳算法、拉格朗日松弛法、模擬退火算法等對(duì)其進(jìn)行求解,例如參考文獻(xiàn)[2]結(jié)合人工神經(jīng)網(wǎng)絡(luò)與選址影響因素之間的特點(diǎn),研究了基于遺傳算法的神經(jīng)網(wǎng)絡(luò)模型;參考文獻(xiàn)[3]考慮了選址問題中的容量受限問題,設(shè)計(jì)了基于免疫克隆的容量受限工廠選址算法;參考文獻(xiàn)[4]建立了單點(diǎn)物流選址決策模型,設(shè)計(jì)了相應(yīng)的遺傳算法;參考文獻(xiàn)[5]研究了最壞中斷損失下的網(wǎng)絡(luò)設(shè)施選址問題,建立了該問題的雙層規(guī)劃模型,設(shè)計(jì)了基于拉格朗日松弛的混合遺傳算法等。
和諧搜索算法HSA(Harmony Search Algorithm)是由GEEM[6]等人提出的一種全新的啟發(fā)式搜索算法,算法以自然的音樂表演過程為基礎(chǔ),是一種模擬音樂人即席創(chuàng)作過程的智能算法[7],已經(jīng)成功應(yīng)用于多個(gè)領(lǐng)域,如結(jié)構(gòu)設(shè)計(jì)[8]、管道網(wǎng)絡(luò)設(shè)計(jì)[9]、具有連續(xù)函數(shù)的工程優(yōu)化[10-12]、任務(wù)指派[13]等。本文采用和諧搜索算法對(duì)貨物配送中心選址問題進(jìn)行求解,并驗(yàn)證了算法在計(jì)算結(jié)果方面的精確性和計(jì)算時(shí)間上的高效性。
1 問題模型
給定某一地區(qū)備選貨物配送中心及其配送點(diǎn)的地址集合,要求選出一定數(shù)目的地址建立配送中心[14],并確定配送方案,從而建立一個(gè)完備優(yōu)化的配送區(qū)域,實(shí)現(xiàn)配送中心到配送點(diǎn)間的物品配送,使得在選出地點(diǎn)建立的配送中心與各配送點(diǎn)形成的配送系統(tǒng)總配送費(fèi)用最低。
1.1 模型假設(shè)
(1)所有設(shè)定的地址區(qū)域都具備優(yōu)越的運(yùn)輸、交通等條件;
(2)運(yùn)輸費(fèi)用與運(yùn)量和距離成正比;
(3)所有配送點(diǎn)均由配送中心供應(yīng);
(4)所配送的資源情況都一樣;
(5)各配送點(diǎn)的需求量己知;
(6)各配送點(diǎn)需求的貨物一次運(yùn)輸完成;
(7)系統(tǒng)總費(fèi)用只考慮固定設(shè)施建設(shè)費(fèi)用及管理費(fèi)用、運(yùn)輸途中的運(yùn)輸費(fèi)用。
3.3 解向量可行化處理
產(chǎn)生新的解向量時(shí),要根據(jù)數(shù)學(xué)模型中的約束條件對(duì)解向量進(jìn)行可行化處理。處理方法是:從解向量中確定配送中心及配送方案,分別統(tǒng)計(jì)配送中心所對(duì)應(yīng)的配送點(diǎn)的需求量之和,若需求量之和大于該配送中心的容量,則將配送點(diǎn)對(duì)應(yīng)的配送中心根據(jù)配送單位重量貨物時(shí)所需配送費(fèi)用從小到大進(jìn)行排序,根據(jù)排序,將各配送點(diǎn)依次分配給其排在最前的、被選中的、且沒有達(dá)到最大容量的配送中心。
3.4 算法執(zhí)行過程
本文算法的執(zhí)行過程如圖3所示。
4 仿真實(shí)驗(yàn)
某大型公司為了適應(yīng)市場(chǎng)和發(fā)展的需要,計(jì)劃在某地區(qū)建立配送中心,為其分布在市區(qū)各地的30個(gè)配送點(diǎn)配送貨物,通過前期市場(chǎng)調(diào)研,綜合考慮地理位置、交通狀況等因素,確定了10個(gè)備選配送中心。為方便計(jì)算,將配送中心與配送點(diǎn)之間的距離、交通、需用車輛等因素量化為配送每單位重量需要的費(fèi)用,統(tǒng)計(jì)出每個(gè)配送點(diǎn)的需求量以及每個(gè)配送中心的建設(shè)費(fèi)用以及建成后的容量,如表1、表2所示?,F(xiàn)需從10個(gè)備選的配送中心選擇若干個(gè)進(jìn)行建設(shè),并且確定配送方案,使得建設(shè)費(fèi)用及配送貨物所需的費(fèi)用最少。
采用本文和諧搜索算法HSA對(duì)此問題進(jìn)行求解,算法參數(shù)設(shè)置為:和諧記憶大小為30;和諧記憶依戀率為0.6;運(yùn)行代數(shù)為500;和諧記憶選擇概率為0.7;和諧記憶交換概率為0.7。算法獨(dú)立運(yùn)行100次,每次都得到最優(yōu)值2 004,最優(yōu)解向量及相應(yīng)的配送方案如表3所示。
將本文HSA算法與EGA及GA算法從兩方面進(jìn)行比較,一方面將運(yùn)算代數(shù)設(shè)置為500,將三種算法獨(dú)立運(yùn)行10次,分別統(tǒng)計(jì)最優(yōu)解平均值及達(dá)到最優(yōu)解時(shí)平均代數(shù);另一方面將最優(yōu)解設(shè)為2 004,將三種算法獨(dú)立運(yùn)行10次,分別統(tǒng)計(jì)達(dá)到最優(yōu)解時(shí)平均代數(shù)和CPU平均運(yùn)行時(shí)間。結(jié)果如表4所示。
從表4可以看出,HSA算法在計(jì)算效果和計(jì)算效率上都優(yōu)于EGA算法和GA算法。HSA算法的優(yōu)勢(shì)十分明顯,其原因在于HSA是在考慮了所有存在的解向量之后產(chǎn)生一個(gè)新的解向量,具有良好的遍歷性。
本文提出了一種針對(duì)貨物配送中心選址問題的和諧搜索算法。通過算例驗(yàn)證和對(duì)比,表明本文算法可以快速、高效地求解該問題。下一步的研究是嘗試將該算法應(yīng)用于更復(fù)雜的選址問題中,如具有模糊需求的離散選址問題、物流中心動(dòng)態(tài)選址問題等。
參考文獻(xiàn)
[1] 稅文兵,葉懷珍,張?jiān)姴?物流配送中心動(dòng)態(tài)選址模型及算法研究[J].計(jì)算機(jī)應(yīng)用研究,2010,27(12):4476-4479.
[2] 許德剛,肖人彬.改進(jìn)神經(jīng)網(wǎng)絡(luò)在糧油配送中心選址中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(35):216-219.
[3] 漆楊,秦子玄,陳霞,等.基于免疫克隆算法的容量受限工廠選址問題研究[J].計(jì)算機(jī)應(yīng)用,2009,29(1):127-129.
[4] 周興龍,金鵬飛.基于遺傳算法的單點(diǎn)物流選址問題探析[J].物流工程與管理,2010,32(7):39-42.
[5] 楊珺,劉舒佶,王玲.考慮最壞中斷損失下的P-中位設(shè)施選址問題的模型與算法研究[J].中國(guó)管理科學(xué),2011,19(4):120-129.
[6] GEEM Z W,KIM J H,Logannath G V.A new heuristic optimization algorithm:harmony search[J].Simulation,2001,76(2):60-68.
[7] 駱乾坤,王佩,朱國(guó)榮.水文地質(zhì)參數(shù)識(shí)別的快速和諧搜索算法[J].水文地質(zhì)工程地質(zhì),2011,38(4):14-19.
[8] DEGERTEKIN S O.Optimum design of steel frames using harmony search algorithm[J].Structural and Multidisciplinary Optimization,2008,36(4):393-401.
[9] GEEM Z W.Optimal cost design of water distribution networks using harmony search[J].Engineering Optimization,2006,38(3):259-280.
[10] JABERRIPOUR M,KHORRAM E.Two improved harmony search algorithms for solving engineering optimization problems[J].Communications in Nonlinear Science and Numerical Simulation,2010,15(11):3316-3331.
[11] WANG C,HUANG Y.Self adaptive harmony search algorithm for optimization[J].Expert Systems with Applications,2010,37(4):2826-2837.
[12] PAN Q,SUGANTHAN P,TASGETIREN M,et al.A selfadaptive global best harmony search algorithm for continuous optimization problems[J].Applied Mathematics and Computation,2010,216(3):830-848.
[13] ZOU D,GAO L,LI S,et al.A novel global harmony search algorithm for task assignment problem[J].The Journal of Systems and Software,2010,83(10):1678-1688.
[14] 祝延軍,胡純德,高隨祥.單親進(jìn)化遺傳算法在配送中心選址中的應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì),2005,26(3):580-582.
[15] 韓毅,蔡建湖,周根貴,等.廢棄物處理站選址問題的和諧搜索算法[J].計(jì)算機(jī)科學(xué),2011,38(6):255-258.
[16] 李煒,劉全銀,王凱東.基于動(dòng)態(tài)和諧搜索的混合粒子群優(yōu)化算法[J].蘭州理工大學(xué)學(xué)報(bào),2009,35(4):74-77.