摘 要: 針對一類配送中心選址問題,,建立了問題的數(shù)學(xué)模型,,將和諧搜索算法進(jìn)行改進(jìn)并對問題進(jìn)行求解,最后將此算法與最優(yōu)保存算法(EGA)和遺傳算法(GA)進(jìn)行比較,,驗(yàn)證了算法在計(jì)算結(jié)果方面的精確性和計(jì)算時(shí)間上的高效性,。
關(guān)鍵詞: 配送中心;選址,;和諧搜索算法,;遺傳算法
面對日益加劇的競爭壓力和快速變化的市場需求,企業(yè)的驅(qū)動力已由生產(chǎn)轉(zhuǎn)向通過分銷和服務(wù)提供的附加值[1],,合理的配送中心布局和貨物配送方案可以在很大程度上降低物流營運(yùn)成本,,提高企業(yè)競爭力。關(guān)于配送中心選址問題,,目前主要采用遺傳算法,、拉格朗日松弛法,、模擬退火算法等對其進(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]等。本文采用和諧搜索算法對貨物配送中心選址問題進(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é)模型中的約束條件對解向量進(jìn)行可行化處理,。處理方法是:從解向量中確定配送中心及配送方案,,分別統(tǒng)計(jì)配送中心所對應(yīng)的配送點(diǎn)的需求量之和,,若需求量之和大于該配送中心的容量,則將配送點(diǎn)對應(yīng)的配送中心根據(jù)配送單位重量貨物時(shí)所需配送費(fèi)用從小到大進(jìn)行排序,,根據(jù)排序,,將各配送點(diǎn)依次分配給其排在最前的、被選中的,、且沒有達(dá)到最大容量的配送中心,。
3.4 算法執(zhí)行過程
本文算法的執(zhí)行過程如圖3所示。
4 仿真實(shí)驗(yàn)
某大型公司為了適應(yīng)市場和發(fā)展的需要,,計(jì)劃在某地區(qū)建立配送中心,,為其分布在市區(qū)各地的30個(gè)配送點(diǎn)配送貨物,通過前期市場調(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對此問題進(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)勢十分明顯,其原因在于HSA是在考慮了所有存在的解向量之后產(chǎn)生一個(gè)新的解向量,,具有良好的遍歷性,。
本文提出了一種針對貨物配送中心選址問題的和諧搜索算法。通過算例驗(yàn)證和對比,,表明本文算法可以快速,、高效地求解該問題。下一步的研究是嘗試將該算法應(yīng)用于更復(fù)雜的選址問題中,,如具有模糊需求的離散選址問題,、物流中心動態(tài)選址問題等。
參考文獻(xiàn)
[1] 稅文兵,,葉懷珍,,張?jiān)姴?物流配送中心動態(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].中國管理科學(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] 駱乾坤,,王佩,,朱國榮.水文地質(zhì)參數(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] 李煒,劉全銀,,王凱東.基于動態(tài)和諧搜索的混合粒子群優(yōu)化算法[J].蘭州理工大學(xué)學(xué)報(bào),,2009,35(4):74-77.